一亩三分地论坛

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

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

Google MTV 20160921 onsite.

[复制链接] |试试Instant~ |关注本帖
domofeng 发表于 2016-9-22 11:01:55 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Other其他

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

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

x
1. 韩国小伙
binary tree的inorder recursive and iterative 两种写法, 如何测试。

2. 中国年轻美眉
实现一个iterator, input 是一个array{3, 8, 0, 12, 2, 9}, 希望输出是 {8, 8, 8, 9, 9},   也就是eventh number代表 词频, oddth number 代表词, {3, 8, 12, 0, 2, 9}, 就是3个8, 0个12, 2个9.
和美眉商量了输入不用array, 用个List<Integer> 简单好多。
如何测试。

3. 白人小伙
Number of island II
如何测试。

4. 印度老汉。
给一个string, 找出lexical order 最小的, size==k的, subsequence, (note, not substring)
String findMin(String s, k){}
e.g.
input
s=pineapple, k==3,

output: ale
ale is the lexical order smallest subsequnce of length 3.
我是暴力求解的:
1. find the first occur position of distinct char.
2. then start from that position.
. from: 1point3acres.com/bbs 3. dfs to find lenght==3, subsequence(dfs, combination way);
4. find the one with smallest lexical order. . from: 1point3acres.com/bbs


5. 印度小伙, 同时参看上的图
最大假期问题, 之前面经看到过这个, 但是没有具体的描述, 就放过了。 结果就命背的被考到的。。。。。。。。。。我来详细描述下
input:
a. 有n个城市, 每个城市之间有飞行时间,
b. 给个飞行时间,
c. 给个vacation array, 代表每个城市每周的假期。
d. 从第一个城市开始
.1point3acres缃
意思就是每个周你可以呆在一个城市, 然后享受那个城市的假期。
还有个限制, 就是城市与城市之间的飞行时间不能超过给定的飞行时间
output:
求x weeks 你能享受到的最大假期总和
你自己设计输入的数据结构

描述起来真他母亲的繁琐, 怪不得没看到详细的说明。

我的大概想法:
1. 去掉那些飞行时间超过给定飞行时间的边。
2. 用adjancey list做的,
3. 然后bfs, 暴力求解。
4. 没写完。。。。。。. visit 1point3acres.com for more.
.1point3acres缃

. 鍥磋鎴戜滑@1point 3 acres
如图所示, 最大的应该
week1, A, sum=2;
week2, B/C, sum=sum+1;
week3, 回到A, sum+=3
total sum =6

最后两轮都没回答好, 可以说写出来80%。 估计是挂了。 发现碰到没做过的题, 容易慌, 容易去套已经做过的题。。。, 然后思维混乱, 就会开始朝令夕改。 还是应该不去套已经做过的题, 就从个BF 的方法开始。 我都是想搞个优化, 结果最后又回到最初的暴力。。。。, 郁闷。。。。。。。。。

为以后的面试攒人品吧。

IMG_0406.JPG

评分

2

查看全部评分

本帖被以下淘专辑推荐:

hxtang 发表于 2016-9-22 20:21:17 | 显示全部楼层
jacky841102 发表于 2016-9-22 20:10
第四题的解法感觉有点问题
例如 fedcba, k = 3
如果把stack中比较大的都pop出来

我就是说了个大概
pop的时候需要看后面还剩几个元素了
元素不够的时候就含泪不pop了,直接push进去
比如你说的例子,其实是
. from: 1point3acres.com/bbs f->e->d->c->cb->cba
回复 支持 2 反对 0

使用道具 举报

 楼主| domofeng 发表于 2016-9-22 11:50:30 | 显示全部楼层
hxtang 发表于 2016-9-22 11:13
最后两轮确实没答好
4贪心就可以了
5可以dp的

最近看了不少, 从你的回复收益不小, 先感谢下。

关键可能刷题刷习惯, 老想是之前什么题的马甲, 一旦套路选错了, 就进坑了。 哎。。。。。
4. 怎么贪心呀,
5. 怎么dp呀,
能不能给点大概思路呢?
回复 支持 1 反对 0

使用道具 举报

hxtang 发表于 2016-9-22 20:07:59 | 显示全部楼层
NdrZmansN 发表于 2016-9-22 14:07
能不能麻烦你再详细一点讲一下5?
不甚感激.

就是
for 第k周
  for 城市c. 鍥磋鎴戜滑@1point 3 acres
      计算第k周在城市c的话,前k周最大享受的假期数

for loop里面那个计算可以递归根据第k-1周,城市c'的结果来算
回复 支持 1 反对 0

使用道具 举报

hxtang 发表于 2016-9-22 12:22:26 | 显示全部楼层
domofeng 发表于 2016-9-22 11:50
最近看了不少, 从你的回复收益不小, 先感谢下。

关键可能刷题刷习惯, 老想是之前什么题的马甲,  ...

不用谢。我就是看面经的时候顺手灌水...明天要面了略紧张...
. 1point3acres.com/bbs
4就是把输出string当个栈,如果当前进来的字母比栈顶的小,就把栈顶的扔掉,小的放进去
比如pineapple
p->i->in->ie->a->ap->app->al->ale. visit 1point3acres.com for more.

5就是算前x周,假设你最后一周在城市c的话,最多的假期数。

刷lc是容易套路,因为看别人答案忍不住会记。这个等刷面经的时候会好些的,因为通常也没答案。
回复 支持 0 反对 1

使用道具 举报

hxtang 发表于 2016-9-22 11:13:54 | 显示全部楼层
最后两轮确实没答好
4贪心就可以了
.1point3acres缃5可以dp的
回复 支持 反对

使用道具 举报

774913744 发表于 2016-9-22 11:47:53 | 显示全部楼层
楼主怎么被follow up那么多测试?我表示完全不会。
有哪位大大能给下标准答案么?.鐣欏璁哄潧-涓浜-涓夊垎鍦
请问楼主怎么答的?
回复 支持 反对

使用道具 举报

 楼主| domofeng 发表于 2016-9-22 11:52:26 | 显示全部楼层
774913744 发表于 2016-9-22 11:47
楼主怎么被follow up那么多测试?我表示完全不会。
有哪位大大能给下标准答案么?. 鍥磋鎴戜滑@1point 3 acres
请问楼主怎么答的?

估计什么SDET或者SETI的工程师吧, 之前我有做过automation testing framework的经验。 加之我和HR讲我不在意什么SW, SDET的title, 只要是与coding为主的职位我都OK。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-9-22 12:27:43 | 显示全部楼层
hxtang 发表于 2016-9-22 11:13. 1point 3acres 璁哄潧
最后两轮确实没答好
4贪心就可以了
5可以dp的

就你大实话
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-9-22 12:51:45 | 显示全部楼层
hxtang 发表于 2016-9-22 12:22
不用谢。我就是看面经的时候顺手灌水...明天要面了略紧张.... 1point 3acres 璁哄潧

4就是把输出string当个栈,如果当前进来 ...

大牛呀。。 祝你明天好好面试。拿到offer 我很快也要面g家了
回复 支持 反对

使用道具 举报

 楼主| domofeng 发表于 2016-9-22 13:20:18 | 显示全部楼层
hxtang 发表于 2016-9-22 12:22. 鍥磋鎴戜滑@1point 3 acres
不用谢。我就是看面经的时候顺手灌水...明天要面了略紧张...

4就是把输出string当个栈,如果当前进来 ...

擦, 这个不就是那个https://leetcode.com/problems/create-maximum-number/
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我一直想用https://leetcode.com/problems/remove-duplicate-letters/的思路, 结果当时这个k没有搞明白, 还是水平太弱了。。。。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-9-22 13:25:44 | 显示全部楼层
domofeng 发表于 2016-9-22 13:20
擦, 这个不就是那个https://leetcode.com/problems/create-maximum-number/,

我一直想用https://le ...

其实是新出的remove k digits
回复 支持 反对

使用道具 举报

 楼主| domofeng 发表于 2016-9-22 13:32:09 | 显示全部楼层
zyoppy008 发表于 2016-9-22 13:25
其实是新出的remove k digits

真么多方法都可以做, 结果选了个暴力的, 真的汗颜呀。。。。。。。。。。, 郁闷了, 碎觉去
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-9-22 13:46:17 | 显示全部楼层
domofeng 发表于 2016-9-22 13:32
真么多方法都可以做, 结果选了个暴力的, 真的汗颜呀。。。。。。。。。。, 郁闷了, 碎觉去

楼主为啥。。这么多test。。。表示不太懂怎么test
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-22 13:57:03 | 显示全部楼层
hxtang 发表于 2016-9-22 12:22 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
不用谢。我就是看面经的时候顺手灌水...明天要面了略紧张...

4就是把输出string当个栈,如果当前进来 ...

大神,你要去谷歌啦,坐等你的好消息!
回复 支持 反对

使用道具 举报

NdrZmansN 发表于 2016-9-22 14:07:33 | 显示全部楼层
hxtang 发表于 2016-9-22 12:22
不用谢。我就是看面经的时候顺手灌水...明天要面了略紧张.... 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

4就是把输出string当个栈,如果当前进来 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
能不能麻烦你再详细一点讲一下5?
不甚感激.
回复 支持 反对

使用道具 举报

狂暴CNM地 发表于 2016-9-22 14:42:41 | 显示全部楼层
还是有希望的 今年G面试通过率特别高
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-22 20:02:37 | 显示全部楼层
domofeng 发表于 2016-9-22 13:32
真么多方法都可以做, 结果选了个暴力的, 真的汗颜呀。。。。。。。。。。, 郁闷了, 碎觉去

这两个题是一个问题...就是套了不同马甲出现了两次而已...
那个题非暴力的确实不算好想,尤其是正确性证明。
回复 支持 反对

使用道具 举报

jacky841102 发表于 2016-9-22 20:07:12 | 显示全部楼层
mark 學習一下
回复 支持 反对

使用道具 举报

jacky841102 发表于 2016-9-22 20:10:29 | 显示全部楼层
hxtang 发表于 2016-9-22 12:22
不用谢。我就是看面经的时候顺手灌水...明天要面了略紧张...

4就是把输出string当个栈,如果当前进来 ...
. 1point3acres.com/bbs
第四题的解法感觉有点问题
例如 fedcba, k = 3
如果把stack中比较大的都pop出来
f -> e -> d -> c -> b -> a
没办法找到cba
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-22 20:17:34 | 显示全部楼层
WhatsFLAG 发表于 2016-9-22 13:57
大神,你要去谷歌啦,坐等你的好消息!

非大神...真是大神就不用找工作了...
就是面一下G,但是因为各种主观和客观原因,多半去不了G了...
不过感谢你的祝福...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 14:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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