Google 第一题应该是 Graph 的概念 共有1000个点 (0 ~ 999) 每个点的 neighbor 是相差一个 distance 的其他数字 目标是要找出 Hamilton Circuit def gen_neighbor(n, num): '''得到一个list包含num的邻点。 例如 num=111 时，传回值为 [110, 112, 101, 121, 11, 211] ''' neighbor = [] for digit in range(n): factor = 10 ** digit d = (num // factor) % 10 if d > 0: neighbor.append(num - factor) if d < 9: neighbor.append(num + factor) return neighbor def find_path(start, visited, n): '''从起点start开始，找邻点加入visited，直到全部点都加入为止。 ''' visited_set = set(visited) max_size = 10 ** n while True: for n in adjlist[start]: if n not in visited_set: visited.append(n) visited_set.add(n) start = n break if len(visited) == max_size: break return visited n = 3 adjlist = [gen_neighbor(n, i) for i in range(10 ** n)] path = find_path(0, [0], n) 完整的 Hamilton Circuit 要考虑当 find_path 无法加入全部点时，要如何处理。 但在这个例子中，总是可以加入全部点，所以不需要处理。 ※ 引述《changyuheng (Henry)》之铭言： : 我也是中央在学，贡献 Google 第一题：http://bit.ly/2qn4iHE : 第二题我会说每一个二分点都测 m 次，最後再实际测试比对结果。 : O(mn) : θ(m log n) : ※ 引述《william45682 (QQQQQQ)》之铭言： : : --- : : Google : : 有投一个google 履历不过连面试都没面试就被reject了 = =…(难过QQ : : 不过我强者同学的第一阶段心得 : : 假设现在给你一个n 代表有几位数 : : 然後 说 假设n为3好了 代表有000~999这1000个数字 : : 然後现在要把这1000个数字排序 : : 排序规则是 两个数字之前 的distance差1 : : 两个数字的distance是指 两个数字拿起来比对 不一样的那几位数相差的总和 譬如说 111 跟 222 distance 是3 111 113 distance 是 2 111 011 distance是1 : : 给出一组合法的排序 : : 然後第二题是 用git的时候会有很多commit 假设现在的code是坏的 前面有n个commit你需要找出哪个commit後面坏掉了 你可以选择询问任一个commit 他会回答你是好的还是坏的 这个很简单 二分搜就好 但是现在题目是 如果你问他 他是好的他就会回答你是好的 他是坏的 有50%机率回是好的 50%机率回是坏的 : : 电话面试， 他叫我打code在 google云端上 : : 整个过程大概45分钟 : : 因为是工程师面所以比较多问的是技术问题 像是前面问我有没有遇过甚麽有趣的题目之类的 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 59.127.245.66 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1496258013.A.0E4.html