一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2529|回复: 19
收起左侧

Google电面

[复制链接] |试试Instant~ |关注本帖
兰台 发表于 2016-10-7 02:40:49 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
好像是个美国小哥,叫Micheal, 上来直接贴题:
第一题: 给出一个dictionary,给出一个list里面包含首字母, output:在dictionary中找到的以list中首字母开头的最长的单词。例如:dict: {"hello", "hi", "lot", "laugh", "me"}, list:{"h, l"}; output: {"hello", "laugh"}dier
第二题:直接贴图片了,反正我是没想到啥好方法。。忽略图片里的那个deny access...实在是截屏截晚了,大家凑活看吧~. From 1point 3acres bbs
楼主肯定是又跪了。。so sad...


补充内容 (2016-10-7 02:41):
第二题output:2
Screen Shot 2016-10-06 at 11.26.26 AM.png

评分

2

查看全部评分

本帖被以下淘专辑推荐:

木易wen 发表于 2016-10-19 03:27:35 | 显示全部楼层
第二题已光荣登上lc大榜 https://leetcode.com/problems/sentence-screen-fitting/
回复 支持 2 反对 0

使用道具 举报

lxxxxxxx 发表于 2016-10-7 02:46:00 | 显示全部楼层
都好难啊.... 请问一下楼主咋做的?
回复 支持 反对

使用道具 举报

XavierWangXY 发表于 2016-10-7 02:58:29 | 显示全部楼层
第一题 类似inverted index 存一个 首字母->单词列表的 hashmap。单词列表可以用以单词长度为weight的heap
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-10-7 03:19:08 | 显示全部楼层
第二题greedy?
回复 支持 反对

使用道具 举报

白丁117 发表于 2016-10-7 03:42:53 | 显示全部楼层
没看懂题啥意思...lz可以解释下吗?多谢~
回复 支持 反对

使用道具 举报

mdzzxswl 发表于 2016-10-7 03:48:18 | 显示全部楼层
为什么电面 会有 截图。。。
回复 支持 反对

使用道具 举报

小雨嘀嗒 发表于 2016-10-7 06:30:42 | 显示全部楼层
第二题感觉就直接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++;
                        }
.1point3acres缃                }
                return res;
        }
回复 支持 反对

使用道具 举报

virpro 发表于 2016-10-7 06:40:13 | 显示全部楼层
第一题定义一个Map<Character, List<String>>,key是首字母,List<String>存最长的String。然后遍历dictionary同时update这个map。这样做可以吗?
回复 支持 反对

使用道具 举报

 楼主| 兰台 发表于 2016-10-8 00:43:18 | 显示全部楼层
第一题我就是一个先扫一遍list用HashSet<Character>存要找的首字母。再扫一遍dict用一个HashMap<Character, String>存最长的string。第二题就说了下思路,面试官也没给啥提示。。.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

virpro 发表于 2016-10-8 01:50:38 | 显示全部楼层
兰台 发表于 2016-10-8 00:43
第一题我就是一个先扫一遍list用HashSet存要找的首字母。再扫一遍dict用一个HashMap存最长的string。第二 ...
. visit 1point3acres.com for more.
如果同一个character有两个最长的String你怎么解决?比如hello, heard。
回复 支持 反对

使用道具 举报

aisingioro 发表于 2016-10-8 02:09:00 | 显示全部楼层
第一题用trie树?
回复 支持 反对

使用道具 举报

 楼主| 兰台 发表于 2016-10-8 03:55:33 | 显示全部楼层
virpro 发表于 2016-10-8 01:50
如果同一个character有两个最长的String你怎么解决?比如hello, heard。

我们没讨论任何corner case,我代码里貌似就默认找第一个了。。
回复 支持 反对

使用道具 举报

 楼主| 兰台 发表于 2016-10-8 03:56:53 | 显示全部楼层

我也提供了这种思路 然后小哥说这和hashmap有啥区别 我说没区别都是O(N)。。所以就还是写的hashmap。。
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-10-8 23:21:28 | 显示全部楼层
请问第二题到底是啥意思,是指把这个list里的单词在屏幕上全部显示出来有多少种排列方法么?
回复 支持 反对

使用道具 举报

hellojay 发表于 2016-10-9 10:47:03 | 显示全部楼层
同问,第二题的输出2是怎么来的
回复 支持 反对

使用道具 举报

printf_ll 发表于 2016-10-9 23:59:47 | 显示全部楼层
感觉就是这题:https://www.careercup.com/question?id=5701279419465728
回复 支持 反对

使用道具 举报

b20160819 发表于 2016-10-28 02:48:47 | 显示全部楼层
兰台 发表于 2016-10-8 03:56
我也提供了这种思路 然后小哥说这和hashmap有啥区别 我说没区别都是O(N)。。所以就还是写的hashmap。。

谢谢楼主分享!输入的list里只是char, 感觉hash map更简单;如果是不定长度的的string作为prefix,还是trie好点
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-10-29 05:52:25 | 显示全部楼层
我的第一题思路:
一扫描dict,找出最长字符串长度
二扫描dict,找出所有最长长度字符串,收入一个hashmap,key为首字母,value为一个arraylist的字符串
然后遍历list(首字母),从hashmap中get值,组成结果。. from: 1point3acres.com/bbs
复杂度应该是O(n) n=dict 长度
回复 支持 反对

使用道具 举报

美女的 发表于 2016-10-30 01:31:14 | 显示全部楼层
好难啊....马上就要面了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 03:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表