聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4680|回复: 19
收起左侧

Google电面

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

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

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

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

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

补充内容 (2016-10-7 02:41):. Waral 博客有更多文章,
第二题output:2
Screen Shot 2016-10-06 at 11.26.26 AM.png

评分

2

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 459, 订阅: 123
木易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;. Waral 博客有更多文章,

                        // add to next line. 1point 3acres 论坛
                        if (c - indexCol < word.length()) {
                                count++;
                                indexCol = word.length() - 1;
                        }
. From 1point 3acres bbs
                        // add to current line
                        else {
                                indexCol += word.length() - 1;
                                if (indexCol + 1 == c - 1) {. 留学申请论坛-一亩三分地
                                        indexCol = 0;
                                        count++;. 一亩-三分-地,独家发布
                                }. From 1point 3acres bbs
                                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-google 1point3acres
                        if (++index == text.length) {. more info on 1point3acres
                                index = 0;
                                if (count < l) res++;
                        }
                }
                return res;
        }
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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。第二题就说了下思路,面试官也没给啥提示。。
. from: 1point3acres
回复 支持 反对

使用道具 举报

virpro 发表于 2016-10-8 01:50:38 | 显示全部楼层
兰台 发表于 2016-10-8 00:43
第一题我就是一个先扫一遍list用HashSet存要找的首字母。再扫一遍dict用一个HashMap存最长的string。第二 ...

如果同一个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 | 显示全部楼层
. 围观我们@1point 3 acres
我也提供了这种思路 然后小哥说这和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.本文原创自1point3acres论坛
我也提供了这种思路 然后小哥说这和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值,组成结果。. 留学申请论坛-一亩三分地
复杂度应该是O(n) n=dict 长度
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 11:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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