Google 电面

写了一下。。感觉要20分钟，如果再算上思考和测试，再加上面试的压力，感觉要写很久的。。lz电面是只有这一个题么？

happysshao 发表于 2014-10-27 11:56
你给出的例子类似：

{bearcat: bearc, bear: ""}

如果是 abbb:abbb; abb:""; ab:"" （ 这个好像不对啊，abb和ab一样？，应该是abbb: abbb, abb: abb, ab: ""?）
为什么
["zebra", "dog", "duck",”dot”]
不是 dog: dog, dot: do, duck: d, zebra: ""
？我好想理解错了？

补充内容 (2014-11-1 10:23):
我理解错了？如果某个字符串是另外一个的前缀，那是没法表示的，所以就返回空？

happysshao 发表于 2014-10-27 11:55
如何向上查找，难道你要建立双向的trie?
我当时也是提高这样的思路，但是感觉写不出来。。。

最简单的办法：
在查找的时候，从root开始，把每个节点的值和节点个数都另存到一个list里
等找到该节点，然后查看一遍已经存好的路径，就很容易得到结果了。

比如用stack<pair<string,int>>
找到 dot 的时候 :
current_str: "dot"
stack：   <"do",2>
             <“d”, 2>
             <“”， 1>
然后查一遍就行了：
while !stack.empty() {
  top = stack.top()
  stack.pop()
  if top.second>1
      return current_str;
  else
      current_str = top.first
}



如果是duck的例子：
current_str:  "duck"
stack<>:  <"du",1>
              <"d", 2>
              <"",0>
所以找到du是结果

其实45min 是可以写完的，只实现insert 和 min prefix就行了

1. #include<iostream>
   
2. #include<vector>
   
3. #include<string>
   
4. using namespace std;
   
5. 
   
6. class Node {
   
7. public:
   
8.     bool is_word;
   
9.     int count;
   
10.     vector<Node*> children;
    
11. 
    
12.     Node() {
    
13.         is_word = false;
    
14.         count = 0;
    
15.         for(int i = 0; i < 26; i ++) {
    
16.             children.push_back(NULL);
    
17.         }   
    
18.     }   
    
19. 
    
20.     void insert(string word) {
    
21.         count ++;
    
22.         if(word.size() == 0) {
    
23.             is_word = true;
    
24.             return;
    
25.         }   
    
26.         int tmp = word[0]-'a';
    
27.         if(children[tmp] == NULL) {
    
28.             children[tmp] = new Node();
    
29.         }   
    
30.         children[tmp]->insert(word.substr(1));
    
31.     }   
    
32. 
    
33.     string minPrefix(string word) {
    
34.         if(word.size() == 0 || count == 1) {
    
35.             return "";
    
36.         }   
    
37.         string rst;
    
38.         rst.push_back(word[0]);
    
39.         rst += children[word[0]-'a']->minPrefix(word.substr(1));
    
40.         return rst;
    
41.     }   
    
42. };
    
43. 
    
44. int main() {
    
45.     Node* root = new Node();
    
46.     root->insert("zebra");
    
47.     root->insert("dog");
    
48.     root->insert("duck");
    
49.     root->insert("dot");
    
50. 
    
51.     cout << root->minPrefix("zebra") << endl;
    
52.     cout << root->minPrefix("dog") << endl;
    
53.     cout << root->minPrefix("duck") << endl;
    
54.     cout << root->minPrefix("dot") << endl;
    
55. }
    

复制代码

这题有人完整写出来吗？

麻烦问下这轮电面除了coding问题还会问什么别的技术问题（例如和个人方向有关的）吗？另外coding的时候是必须完全标准语言写么，还是可以混入一些pseudocode？谢了

这个不是common prefix么？ 遇到common指针move，否则输出，brute force还是好写一点。要是trie的话，建数要花点时间，除非面试官说可以用相应的函数，要不我感觉45分钟有点悬

happysshao 发表于 2014-10-27 11:56
你给出的例子类似：

{bearcat: bearc, bear: ""}

你不是说 Use the shortest unique prefix to represent each word in the array
那abb与ab的 “shortest unique prefix” 怎么是一样的了？

用trie做的话
遍历一直找第一个count为1的点然后返回记录的path；如果没找到count为1的点就没有，返回空“”
不知道理解对不对？

class PrefixTreeNode {
        public int count;
        public PrefixTreeNode[] next;
        public PrefixTreeNode(int c) {
                count = c;
                next = new PrefixTreeNode[26];
                for (int i = 0; i < next.length; ++i)
                        next[i] = null;
        }
};

class ShortestUniquePrefixTree {
        public PrefixTreeNode root = new PrefixTreeNode(0);

        public void add(String word) {
                PrefixTreeNode tmp = root;
                for (char c : word.toLowerCase().toCharArray()) {
                        if (tmp.next[c - 'a'] != null) ++tmp.next[c - 'a'].count;
                        else tmp.next[c - 'a'] = new PrefixTreeNode(1);
                        tmp = tmp.next[c - 'a'];
                }
        }

        public String getShortestUniquePrefix(String word) {
                if (word == null || word.length() == 0) return null;
                PrefixTreeNode tmp = root;
                char[] array = word.toLowerCase().toCharArray();
                for (int i = 0; i < array.length; ++i) {
                        if (tmp.next[array[i] - 'a'] == null)  return null;
                        else if (tmp.next[array[i] - 'a'].count == 1) return word.substring(0, i + 1);
                        else tmp = tmp.next[array[i] - 'a'];
                }
                return word;
        }
};



public static void main(String[] args) {
        String[] input = {"zebra", "dog", "duck", "dot"};
        ShortestUniquePrefixTree supt = new ShortestUniquePrefixTree();
        for (String str : input)
                supt.add(str);
        for (String str : input)
                System.out.println(str + ": " + supt.getShortestUniquePrefix(str));
}



zebra: z
dog: dog
duck: du
dot: dot