drawbridge的OA (09.06.2017)

前天在linkedin上海投，昨天拿到OA，发现地里并没有这家公司的资料，只能徒手裸上了
75min的OA，一道题，难度感觉比较大：
Tom和jerry在一个迷宫里，迷宫有些地方有cheese （标记为2），有些地方是空地（标记为0），

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

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

p，求大米

有一个问题，LZ，那就是这道题有没有给cheese数目的上限？
如果上限不大的话，可以使用Wiki上的算法，
因为那个算法需要记录“子集”，上限不大的话可以用bit来记录，过大的话就只能用string之类的来记录了
那样就算时间不超空间也快要超了……

先用bfs找到并存储所有的cheese点对距离
然后调用wiki里的那种dp算法来求TSP问题答案
不过这代码要在75min内写完且BUG FREE就过分了
不允许查资料的话这题绝对有ACM竞赛级别的水准

这个题也太难了，我最后就算知道思路也没写完，GG了。。。

有个小typo: cheese的地方标记为1

嗯？drawbridge有new grad职位么

楼主666～～

这怎么他家OA还有2道题。

今天收到了拒信，哭哭

醉了，考tsp