Expedia OA

今天夜间做了一个Expedia的OA，其中3道题分为section1 和 Section2.
Section 1 有两道题目，非常简单，都是basic的DFS或者Hashmap操作
Section 2 有一道题目，题目也是非常简单，但是test case

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

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

了。
转头使用了DP的解法，但是提示是memory又不满足要求。WTF， 一个OA搞成这样你是玩人么？

听天由命吧，求大米。

鸽子 发表于 2019-10-11 00:59
恭喜恭喜！我也收到onsite邀请了，还以为自己凉凉了，楼主machine learning大神厉害了

No. I am a new graduate from school with 2 years of working experience. This account is from one of my friend. So you may talk about the previous account user.

msds 发表于 2019-9-19 10:34
第二题是否可以先sort，然后用2 ponters来做？这样复杂度应该是O(NlogN)，用DFS或者DP应该至少是O(N^2)复杂 ...

给我加米啊，twopointer做不了，又不是问的是两个元素的和，是各种组合的最大值。

gigiwaiwai 发表于 2019-9-14 06:15
Yes. But I use the same idea of Knapsack. We need space for O(n*shreshold). The threshold is prett ...

What if using a rolling array to optimize space complexity for O(threshold)? Does it work?

谢谢分享, 第二题是背包问题吧

爱健身也爱刷题 发表于 2019-9-14 05:22
谢谢分享, 第二题是背包问题吧

Yes. But I use the same idea of Knapsack. We need space for O(n*shreshold). The threshold is pretty big and does not work when I used DP.

Good point. I do not have enough time for changing. I just listed both solution there. Hopefully, I can get a pass here.

楼主投的是什么岗位啊

第二题是否可以先sort，然后用2 ponters来做？这样复杂度应该是O(NlogN)，用DFS或者DP应该至少是O(N^2)复杂度了吧？

问下楼主有接到后续消息吗

今天和楼主遇到一样的第二题，按照Knapsack用dp做我只过了3/13个case...所有楼主后续有消息了吗？