Google最新电面，现在的电面都这么难吗！

遇到一个magic square 只写了暴力解 HR说面试官的反馈是不能熟悉使用树和字典 这个题用树和字典能解吗？

步惊云 发表于 2019-1-24 19:37
hamilton graph 了解一下， 具体是tsp。 https://en.wikipedia.org/wiki/Travelling_salesman_problem

...

请问这题是要找euler circuit吗？有k^(n-1)个vertices，每个v还有一个out degree k，这样time complexity是O(k^(n-1) )？请问有啥可以降低complexity的方法吗？感觉好难，找哈密顿path感觉更难了，完全不懂

补充内容 (2019-1-25 05:45):
打错了， time complexity O(k^n)？还可以降吗？

louise 发表于 2019-1-25 03:15
遇到一个magic square 只写了暴力解 HR说面试官的反馈是不能熟悉使用树和字典 这个题用树和字典能解吗？

是那个 Implement Magic Dictionary？那感觉brutal force也不是暴力解啊，完全正经解。

谷歌简历挂的路过..............

三周后店面，看LZ的经历，很怕啊

步惊云 发表于 2019-1-25 03:32
感觉你就是会被点草的那种. 不会做题还叭叭叫.

看sample size, 这题不知道怎么给的限制. 题 ...

https://leetcode.com/problems/cracking-the-safe/solution/

Hierholzer算法也是找欧拉回路的经典算法了，无论你拿dfs还是bfs还是干脆就写一个二重循环都比你用TSM的O(N^2*2^N) DP算法要在时间和空间上要优秀。

而且，算法面试考察的是面试者coding和应用基本算法和数据结构的能力，是应当避免考察这种知道一个“冷门”算法就巨简单，不知道就一行code都写不出来的题目的。至于TSM的DP解法，我不认为这种难度的题目应该出现在店面，尤其是第二问里，面试造火箭也不是这么造的。

如果我是面试官，在面试者提到dfs不能做的时候我就会提醒ta每次要把一个点的edge全部扫完才能离开这个点。面试者即使不能证明但只要自己手动跑一下就知道这样能做结果，那么就可以写code，如果面试者能bug-free的写完并正确的分析复杂度我觉得就可以给hire了

sanmi0814 发表于 2019-1-25 07:33
是那个 Implement Magic Dictionary？那感觉brutal force也不是暴力解啊，完全正经解。

是个N*N的二维数组 然后每个格子里可以放1到N*N的数字 每个数字只能用一次
填好的格子里每一行每一列顶点间的对角线的数字加起来和要一样

zsj2725 发表于 2019-1-25 09:15
https://leetcode.com/problems/cracking-the-safe/solution/

Hierholzer算法也是找欧拉回路的经典算 ...

求问一个问题。任意给一个indegree = outdegree的directed graph，Hierholzer找欧拉的时候是会有backtrack的？我看了lc cracking safe的答案（Hierholzer算法的解法），为啥能保证不back-track呢？这个是因为所有的node都有一样的in/out degree吗？求解答。


补充内容 (2019-1-25 10:07):
但是general的有欧拉的directed graph，每个node虽然自己的in/out degrees是一样的，但是并不是universal一样的？

twilightgod 发表于 2019-1-24 16:23
753用BFS就可以保证最少步数

BFS我一开始也想到了，但是实现起来非常麻，因为BFS的话要用非常多的空间来记录对每一个状态那些字符串已经访问过了。