TripAdvisor

通过LinkedIn投，面试的是social组的一个Team Leader。
1. 刚刚工作两个月为什么跳槽？（多谢另一篇帖子里一位仁兄的建议，这次回答的不错）
2. 因为我上一个project也是social的，非常专业的问了project里面的三个部分是怎么做的。（这部分感觉他满意度一般，因为我有点不能get到他的点，需要他重复）
3. LinkedList和ArrayList分别是什么（continuous和pointer）
4. 他们的cons和pros（random access和manipulation time complexity两方面回答的）
5. 在sorted arraylist里面search一个element，time complexity多少？
6. 如果在sorted linkedlist里面，时间复杂度又是多？（这个答的最不好，我想了很久有没有lgn的解法，最后没想到。然后说如果用同样的算法的话，为了能够找到mid元素，依次需要n/2, n/4, n/8 ... 的time，但是我跟她说我忘了等差数列求和公式了 ...）然后他继续问，如果不需要让你用原来的算法呢。（我说就先扫一遍，用hashmap<ele position, address of ele>记录。然后再用lgn的算法就可以了。）他

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

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

补充内容 (2015-10-9 06:08):
今天收到onsite:)  因为补充有字数限制，所以homework的题目写在回复里了。PS.今天上班的时候老板把我叫过去说，要么好好干好么就辞职，加上前些天被fb和linkedin简历拒。接到这个onsite的时候简直激动的热泪盈眶

补充内容 (2015-11-6 05:11):
onsite面经见回复

补充内容 (2015-11-12 07:05):
昨天收到offer。跟hr打电话的时候要求extend deadline，对方很不开心。问什么时候有official offer，她说昨天或者今天。结果都下班了还没发来，发邮件也没回，而且Google面的也不是很好，哎。

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

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

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

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

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

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

“3. 给一个数组a，返回一个index这个index之前的element都比a[index]小，之后的都比a[index]大。时间复杂度O(n)。用三个变量，flag，curMax，和res，分别记录，当前是否发现这样的index，当前发现的最大值，和当前符合输出要求的res。第一遍没写好，然后又用了不少时间才解出来。感觉面试官反应一般。”

请问这道题目空间复杂度有什么要求呢？

Stupidog 发表于 2015-11-6 11:44
“3. 给一个数组a，返回一个index这个index之前的element都比a小，之后的都比a大。时间复杂度O(n)。用三个 ...

没说，我给的是O(1)

yangzeyao 发表于 2015-11-7 00:22
没说，我给的是O(1)

能分享一下具体思路么？

我只能想到用2个额外的array，一个存从左到右扫描，当前的Max，另一个存从右到左扫描，当前的Min。

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

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

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

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

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

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

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

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