Google电面

好像是个美国小哥，叫Micheal, 上来直接贴题：
第一题： 给出一个dictionary，给出一个list里面包含首字母， output：在dictionary中

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

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

sad...


补充内容 (2016-10-7 02:41):
第二题output：2

第二题已光荣登上lc大榜 https://leetcode.com/problems/sentence-screen-fitting/

第二题感觉就直接scan array吧，用几个pointer记录位置，注意考虑corner case就行，简单写了下，能run 图里的test case.

public static int solution(String[] text, int c, int l) {

                int count = 0, index = 0, indexCol = 0, res = 0;
                while (count < l) {
                        String word = text[index];
                        // one line cannot hold the whole word.
                        if (word.length() > c)
                                return 0;

                        // add to next line
                        if (c - indexCol < word.length()) {
                                count++;
                                indexCol = word.length() - 1;
                        }

                        // add to current line
                        else {
                                indexCol += word.length() - 1;
                                if (indexCol + 1 == c - 1) {
                                        indexCol = 0;
                                        count++;
                                }
                                if (indexCol + 1 == c) {
                                        indexCol = c > 1 ? 1 : 0;
                                        count = c > 1 ? count + 1 : count + 2;
                                }
                        }

                        // move to next word or return to first word
                        if (++index == text.length) {
                                index = 0;
                                if (count < l) res++;
                        }
                }
                return res;
        }

兰台 发表于 2016-10-8 03:56
我也提供了这种思路 然后小哥说这和hashmap有啥区别 我说没区别都是O（N）。。所以就还是写的hashmap。。

谢谢楼主分享！输入的list里只是char, 感觉hash map更简单；如果是不定长度的的string作为prefix，还是trie好点

都好难啊.... 请问一下楼主咋做的？

第一题 类似inverted index 存一个 首字母->单词列表的 hashmap。单词列表可以用以单词长度为weight的heap

第二题greedy？

没看懂题啥意思...lz可以解释下吗？多谢~

为什么电面 会有 截图。。。

第一题定义一个Map<Character, List<String>>，key是首字母，List<String>存最长的String。然后遍历dictionary同时update这个map。这样做可以吗？

第一题我就是一个先扫一遍list用HashSet<Character>存要找的首字母。再扫一遍dict用一个HashMap<Character, String>存最长的string。第二题就说了下思路，面试官也没给啥提示。。

兰台 发表于 2016-10-8 00:43
第一题我就是一个先扫一遍list用HashSet存要找的首字母。再扫一遍dict用一个HashMap存最长的string。第二 ...

如果同一个character有两个最长的String你怎么解决？比如hello, heard。