Google 2019 intern 热乎电面面经

献上LG一周前Google电面面经^_^

LG面的是2019 summer intership research scientist岗

之前一直以为是reserach面,没想到上来两面都加了coding面

第一面:
有很多航班list,比如[“Shanghai”, “Beijing”, depart time, arrive time], …
然后给出一个出发城市,到达城市,求所用的最短时间

第二面:
min max问题
两个都非常聪明的人玩猜字游戏,数字在1到100之间。B来猜A的数字。B每猜到数字k,B的cost是k;B猜时,A只有三种回答:对了,大了,小了。
在这个过程中,A的目的是最大化B的cost,B的目的是最小化自己的cost。
问B最小的cost是多少?

最近面试,急需下载地里资料,无奈总是积分不够,~谢谢谢谢

第一题有重复吗?比如上海到北京有3点一班5点一班?
第二题有点像扔鸡蛋?

第二题DP做,dp(i,j) 表示target在该区间内时对应的cost,dp(i,j)=min{max(dp(i,k-1),dp(k+1,j))+k} for k in range(i,j+1) 不过时间复杂度是O(N^3),可以用memo稍微降低时间复杂度.

按照第二题题设的意思,如果A只能回答正确答案,不能说谎,那A如何能影响局势?

补充内容 (2018-10-31 12:27):
唯一的变量是挑选目标值吗

补充内容 (2018-10-31 12:52):
以及目标值是在开始游戏时决定,还是在B回答过程中可以改变

按照面试官的意思,A心中的那个值是变化的

第一题应该是有重复的,同样的出发地,目的,不同的时间
第二题,扔鸡蛋?是个博弈的过程,A心中的那个数是可以变化的,目的是最大化B的cost

感觉比drop egg难,drop egg是算次数,跟大小无关,你这题跟猜的数有关

第二题如果a不能修改自己的答案,是陵寇溜溜溜,不知道蠡口上有没有。a能修改自己答案真不会了。

请问楼主第一面 要考虑候机时间吗? 还有只给了出发和到达城市 没有给出发时间吗? 谢谢

第一题是dfs嘛?