pinterest 电面跪经

跪的略奇妙，可能还是简历不好看。面试官花了半个小时的时间聊天，然后明确说了只面一道。
给一个很大的字典（有问面试官需不需要

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

有再问别的followup。

回头也在自己电脑上跑了，没什么问题。然而还是跪了

LeeYYY 发表于 2017-11-15 15:37
这题就是 LC原题：

https://leetcode.com/problems/longest-word-in-dictionary/description/

感觉就是从我这个帖子过去的。。。

1. public class BuildDict {
   
2. 
   
3.     public static TrieNode root;
   
4. 
   
5.     public static void main(String[]args){
   
6.         String[] dict = {"w", "wo", "wor", "wt", "world", "worl", "wto"};
   
7.         System.out.println(maxWord(dict));
   
8.     }
   
9. 
   
10.     public static String maxWord(String[] dict){
    
11.         int max = 0;
    
12.         String res = "";
    
13.         root = new TrieNode(0, "");
    
14.         for(String word : dict){
    
15.             TrieNode node = root;
    
16.             char[] arr = word.toCharArray();
    
17.             for(char c : arr){
    
18.                 if(node.children[c - 'a'] == null){
    
19.                     node.children[c - 'a'] = new TrieNode(node.depth + 1, node.word + c);
    
20.                 }
    
21.                 node = node.children[c - 'a'];
    
22.             }
    
23.             if(node.depth > max){
    
24.                 max = node.depth;
    
25.                 res = node.word;
    
26.             }
    
27.         }
    
28.         return res;
    
29.     }
    
30. 
    
31. }
    
32. 
    
33. class TrieNode{
    
34.     TrieNode[] children;
    
35.     int depth;
    
36.     String word;
    
37. 
    
38.     public TrieNode(int d, String w){
    
39.         depth = d;
    
40.         children = new TrieNode[26];
    
41.         word = w;
    
42.     }
    
43. }

复制代码

按照楼主的意思，写了一版代码，能不能麻烦看下是不是这个意思，谢谢

1. public class BuildDict {
   
2. 
   
3.     public static TrieNode root;
   
4. 
   
5.     public static void main(String[]args){
   
6.         String[] dict = {"world", "wo", "wt", "wor", "w", "worl", "wto"};
   
7.         System.out.println(maxWord(dict));
   
8.     }
   
9. 
   
10. 
    
11.     public static String maxWord(String[] dict){
    
12.         if(dict == null || dict.length == 0) return "";
    
13.         Map<String, Integer> map = new HashMap<>();
    
14.         Queue<String> queue = new LinkedList<>();
    
15.         for(String word : dict){
    
16.             if(word.length() == 1) {
    
17.                 queue.add(word);
    
18.             }
    
19.             map.put(word, 0);
    
20.         }
    
21.         String res = "";
    
22.         while(!queue.isEmpty()){
    
23.             int size = queue.size();
    
24.             for(int i = 0; i < size; i++){
    
25.                 String word = queue.poll();
    
26.                 for(char c = 'a'; c <= 'z'; c++){
    
27.                     String tmpWord = word + c;
    
28.                     if(map.containsKey(tmpWord)){
    
29.                         queue.add(tmpWord);
    
30.                         res = tmpWord;
    
31.                     }
    
32.                 }
    
33.             }
    
34.         }
    
35.         return res;
    
36.     }
    
37. }

复制代码

重新写了一版，感觉不用trie也好，用bfs，从1个字符的word开始，有点点像word ladder，楼主提到如果有多个同样长度的话，返回随便一个就好的话，不断更新的话，最后queue空的时候，最后更新的值就是最大长度的word了。还请各位大神指教

输出是list of strings ?

输出就是那个最长的词，有问面试官，如果有同样长度的很多词，要全输出吗，面试官说不用，只用输出一个。

这个build的过程总是从最后添加charactor吗？可不可以这样a->ba ？

lz去反应一下,
顺便问问反馈,哪里要改进.

randrand1 发表于 2017-10-17 07:57
这个build的过程总是从最后添加charactor吗？可不可以这样a->ba ？

不可以， 原话是build the string one character at a time

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

好吧，这为什么没过？是现在都要求这么高还是缘分没到

有点不太懂题意，楼主可以解释一下吗？每个字母只能用一次吗？

烩丸子 发表于 2017-10-20 10:43
有点不太懂题意，楼主可以解释一下吗？每个字母只能用一次吗？

不知道要怎么样才可以讲的更清楚，就是如果字典里有a, ab, abc，那么你就可以输出abc这个词