PocketGem 第一輪電面

一開始問我知不知道任何Shortest Path的演算法，我想到了Dijkstra，但實在沒有認真讀過，所以跟他說沒有印象。


接著給我一張地圖，像是以下這樣
['02111',
'01001',
'01001',
'01003',]


0: can't pass
1: can pass
2: start

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

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

試官沒有什麼口音，通話品質也還不錯，題目也不算太難，過程中也會提示哪裡寫錯了
但這是找工作以來第一次電面，該注意到的很多細節都沒注意到，估計大概是沒希望了。
希望上面的題目能夠幫到地裡的朋友們。

arksha 发表于 2016-8-25 06:20
lz 是收到oa之后做完给的电面么？

對的。7/25 申請，8/3收到OA邀請，8/11做完OA，8/16收到電面邀請，剛剛電面完

小核桃桃 发表于 2016-9-2 00:57
谢谢楼主!我想问下 这道题能走回头路么？

可以的，倒不如說在某些情況下，必須走回走過的路，否則無法到達終點。

例如說，當最短路徑上有一個分岔路口通往兩條除了這個分岔路口以外不相通的路，
其中一條可以拿到Key A，另一條則是會走到門A，
如果這條最短路徑一定要先經過門A才能到達終點，我們必須先走能拿到Key A的那條路，
然後再回頭走到分岔路口，接著再走到門A，最後是終點。

cicean 发表于 2016-9-14 04:40
这还叫不难，我感觉已经非常难了。还有钥匙， 都崩溃了，游戏公司果然不一样

如果直接解這題的話(有門跟Key)是蠻難的，但是因為過程中他一步步確認我理解當下的問題，也等我提出對的解法or方向之後，再提出其他限制，所以至少到了全部條件都提出來之後，知道要怎麼解。

但他們家是有名的Bar很高的公司，所以如果面他們家時，遇到很難的題目，也別太過在意，當做練習就好了。

lz 是收到oa之后做完给的电面么？

楼主第二问是怎么做的呢？

caiqi8877 发表于 2016-8-25 07:00
楼主第二问是怎么做的呢？

我用BFS再加上一個set來存目前手上有的key，
但這裡要注意的是，把新的點放進queue的時候，要copy一個新的set進去，
因為走到不同的path時，手上有的key會不一樣

谢谢楼主!我想问下 这道题能走回头路么？

dancontra 发表于 2016-9-2 02:05
可以的，倒不如說在某些情況下，必須走回走過的路，否則無法到達終點。

例如說，當最短路徑上有一個分 ...

这样。。。我觉得还挺难得 不知道怎么做😢

这还叫不难，我感觉已经非常难了。还有钥匙， 都崩溃了，游戏公司果然不一样

楼主是要输出路径么？ 还是问最短路径长度？

补充内容 (2016-9-14 05:13):
楼主这个给的是String[] 么？