Expedia OA 面经

75分钟 3题,第二题 graph, 比较time consuming.

最后再请问一下,你们做OA 会很认真的读题吗? 前面的description我我得读好几篇才懂,浪费了我好多时间 还没完全弄懂,但是我看他给的example 才感觉更加清楚。

第一题给两个list {1,2,3} {3,2,1} 和一个 counter, counter是0时候,1 -3=-2, counter是1时候跳过 list中当前元素, counter变为0,3 -1 =2.
最后 list1 得分 -2 + 2=0, list2得分 2 - 2 =0, 返回 string “Tie”。
第一题大概是 warmup,直接秒掉。
第二题,读题目就差不多用了10分钟。
你来到一个city,city有 n 个 景点, 景点之间有m条路线,路线是bidirection,并且景点之间只有一条路线(node之间只有一条edge),每个景点有对应的beauty score {10,8,9}, 你只有49分钟,问如何从node 0 开始走,49分钟之内maximize 你走过景点的总 beauty score 并且最后再返回到node 0. 每条edge是有weight的,weight就是 commuting time, {10,13,25} 这样子。
我是用dfs的 但是奈何没写完。

第三题是给你一个list {2,5} 就代表有两个商店,商店1 有 2份杂志,商店2有5份杂志。 杂志的定价是当前商店所剩杂志的数量。例如商店1 杂志卖2¥, 商店2卖5¥。 告诉你 现在已经有 5份杂志被卖了,求问可能的最大的利润,所以是 5 + 4 + 3 + 2 + 2 = 16 ¥。

1 Like