UT Austin CS MS 18Fall入學感受

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷知名AI创业公司
图灵视频
招聘多个工程师职位
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
查看: 1571|回复: 19
收起左侧

Google 店面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
owenqyzhang 发表于 2017-11-2 06:42:35 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩

2017(10-12月) 码农类General 硕士 全职@Google - 网上海投 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
面试官感觉是个美国人,上来让我自己介绍了一个project,大概5分钟,然后直接开始做题
1. 给一个数组A,找出满足条件的(i, j)对。条件1:A[j] = A[i] + 1,条件2:j - i尽量大
写完以后followup条件1改成A[j] > A[i]. followup我一开始想错了,发现的时候已经没时间了,估计是跪了吧。。。. 一亩-三分-地,独家发布

评分

参与人数 1大米 +5 收起 理由
edyyy + 5 给你点个赞!

查看全部评分


上一篇:热呼呼的狗家挂经
下一篇:IBM guru 电面 地里题目总结
我的人缘0
angiehoo 发表于 2017-11-8 07:00:32 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  66% (6)
 
 
33% (3)  踩
我觉得可以把数字和index当做一个pair ,然后对pair按照数字的大小进行排序,(O(nlogn))
然后对pairs从头开始扫描(O(n)),不断更新最小的index,然后对每对pair的index 减去最小的index,记录下最大的差值,应该就可以了.1point3acres网
回复

使用道具 举报

我的人缘0
兜兜笔 发表于 2017-11-2 07:38:54 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
followup是不是可以类似最长上升子序列那样做?

一个线性表作栈,每当当前元素 a 比栈顶小时压入. 比栈顶大时对栈二分查找到小于 a 的最大值 b,比较二者位置ai - bi和已知最大差.
回复

使用道具 举报

我的人缘0
edyyy 发表于 2017-11-2 07:16:18 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  90% (149)
 
 
9% (16)  踩
owenqyzhang 发表于 2017-11-2 07:09
第一题我也是用hash map做的,我先以为不能有负的,写完以后他问我有没有edge case,我想了半天说也许没 ...

原来这样,那你加两行就对了。nlog(n)是sort nums的index让后scan array解。.留学论坛-一亩-三分地
比如 【0,1,0,2,1】 index = {0,1,2,3,4} (需要o(n) memory)
sort index according to nums, 就有 {0,2,1,4,3} 代表 【0,0,1,1,2】
max j - i = 4
回复

使用道具 举报

我的人缘0
rickliang 发表于 2017-11-2 07:10:11 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
楼主能写个例子吗

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
edyyy 发表于 2017-11-2 07:03:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (149)
 
 
9% (16)  踩
像这样?? j - i 尽量大,如果不能为负数的 所以要 j > i
  1. int maxDiff(vector<int>& nums) {
  2.     unordered_map<int, int> m;
  3.     int maxdiff = -1;
  4.     for (int i = 0; i < nums.size(); i++) {. 围观我们@1point 3 acres
  5.         if (m.count(nums[i]) == 0) m[nums[i]] = i;
  6.         if (m.count(nums[i] - 1)) maxdiff = max(maxdiff, i - m[nums[i] - 1]);
  7.     }. 留学申请论坛-一亩三分地
  8.     return maxdiff;.本文原创自1point3acres论坛
  9. }
复制代码

A[j] > A的时候只能for (int i = 0; i < nums.size(); i++ ) while (nums < nums[i + 1]) i++这样找了??
回复

使用道具 举报

我的人缘0
edyyy 发表于 2017-11-2 07:04:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (149)
 
 
9% (16)  踩
美国人就爱自己出题,然后让你分析,不一定像国人面馆那样bug free.楼主等等消息吧。。。。
回复

使用道具 举报

我的人缘0
 楼主| owenqyzhang 发表于 2017-11-2 07:09:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
edyyy 发表于 2017-11-2 07:03
像这样?? j - i 尽量大,如果不能为负数的 所以要 j > i

A[j] > A的时候只能for (int i = 0; i < nums ...

第一题我也是用hash map做的,我先以为不能有负的,写完以后他问我有没有edge case,我想了半天说也许没有这种对,或者j-i是负的,然后他就让我加上了这两种情况。第二个他说有个nlogn的解法,先preprocess一下,我也没想出来

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
 楼主| owenqyzhang 发表于 2017-11-2 07:12:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
rickliang 发表于 2017-11-2 07:10
楼主能写个例子吗

比如A=[5, 2, 4, 5, 3, 1], 就返回(1, 4)
回复

使用道具 举报

我的人缘0
shuidiaogetou 发表于 2017-11-2 23:05:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
edyyy 发表于 2017-11-2 07:16
原来这样,那你加两行就对了。nlog(n)是sort nums的index让后scan array解。
比如 【0,1,0,2,1】 index  ...

能具体说说如何scan解吗?
回复

使用道具 举报

我的人缘0
 楼主| owenqyzhang 发表于 2017-11-2 23:10:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
shuidiaogetou 发表于 2017-11-2 23:05
能具体说说如何scan解吗?
.留学论坛-一亩-三分地
sort完以后就在index list里面找最大的差,而且保证大数在后面,参考 http://www.geeksforgeeks.org/max ... tween-two-elements/

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
shuidiaogetou 发表于 2017-11-2 23:52:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
owenqyzhang 发表于 2017-11-2 23:10
sort完以后就在index list里面找最大的差,而且保证大数在后面,参考 http://www.geeksforgeeks.org/maxi ...
. 留学申请论坛-一亩三分地
类似max subarray sum?
回复

使用道具 举报

我的人缘0
rickliang 发表于 2017-11-3 02:11:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
owenqyzhang 发表于 2017-11-2 23:10
sort完以后就在index list里面找最大的差,而且保证大数在后面,参考 http://www.geeksforgeeks.org/maxi ...

但是在index list里找最大的差,还有保证A[j] = A + 1,这部分怎么处理呢
. from: 1point3acres
补充内容 (2017-11-3 02:11):
A[j] = A + 1
回复

使用道具 举报

我的人缘0
691469063 发表于 2017-11-3 10:36:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
从后往前扫, 维护一个单调增的vector, 每次来的值大于最后一个元素就push_back, 搜索的时候就binarysearch, 这样可以吗?
回复

使用道具 举报

我的人缘0
绿林旋风 发表于 2017-11-12 12:42:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (57)
 
 
8% (5)  踩
看到楼主说的follow up可以刀nlogn, 我在想是不是可以用multiset?
scan一遍,每次insert当前的数, 然后用lower_bound找到这个数在multiset中最靠前的位置,然后这个位置和multiset.begin()的差就是当前位置满足条件的最大差了
这个流程应该是nlogn的,但是似乎只能找到i<j的情况
回复

使用道具 举报

我的人缘0
绿林旋风 发表于 2017-11-12 12:51:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (57)
 
 
8% (5)  踩
另外14楼的说法应该是对的,我给想麻烦了
回复

使用道具 举报

我的人缘0
张欣 发表于 2017-11-13 12:32:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (54)
 
 
31% (25)  踩
owenqyzhang 发表于 2017-11-2 07:12. 一亩-三分-地,独家发布
比如A=[5, 2, 4, 5, 3, 1], 就返回(1, 4)

楼主,请问hashmap的做法是handle不了哪两种情况,看到你说j-i可以为负? 那这样你给的这个例子是不是该返回(1,5)不是(1,4)? 谢谢
回复

使用道具 举报

我的人缘0
张欣 发表于 2017-11-13 12:32:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (54)
 
 
31% (25)  踩
owenqyzhang 发表于 2017-11-2 07:12
比如A=[5, 2, 4, 5, 3, 1], 就返回(1, 4)
来源一亩.三分地论坛.
楼主,请问hashmap的做法是handle不了哪两种情况,看到你说j-i可以为负? 那这样你给的这个例子是不是该返回(1,5)不是(1,4)? 谢谢
回复

使用道具 举报

我的人缘0
张欣 发表于 2017-11-13 12:35:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (54)
 
 
31% (25)  踩
owenqyzhang 发表于 2017-11-2 07:12. more info on 1point3acres
比如A=[5, 2, 4, 5, 3, 1], 就返回(1, 4)

楼主,请问hashmap的做法是handle不了哪两种情况,看到你说j-i可以为负? 那这样你给的这个例子是不是该返回(1,5)不是(1,4)? 谢谢
回复

使用道具 举报

我的人缘0
 楼主| owenqyzhang 发表于 2017-11-13 12:37:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
张欣 发表于 2017-11-13 12:32
楼主,请问hashmap的做法是handle不了哪两种情况,看到你说j-i可以为负? 那这样你给的这个例子是不是该 ...

hash map没有问题,做法类似2sum,(i, j)是有顺序的,(1, 5)是不对的,只有可能是(5, 1),这样j-i就是-4
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-19 14:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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