※ 引述《RockLee (Now of all times)》之铭言： : 上周跟美国那边进行了第一轮电话面试, : (第一次跟国外面试就是魔王等级 Orz...) 说老实话 Google 的面试早就不是魔王等级... 井字游戏输赢有很魔王吗? 我觉得最近大多都是出木桩王, 就是考验基本功而已. 个人经验是 Square 跟 Palantir 的面试问题都有趣得多. : 今天 HR 打电话来说 interviewer 的 feedback 没有很好, : 会再通知我第二轮电话面试的时间. : 根据 HR 的说法, : interviewer 认为我的 code 虽然正确, : 但是一些 follow up 的问题, : 例如复杂度的分析没有做的很好. : 其实我感到有点讶异, 回想一下上次面试过程, : 一开始是问一些过去的学经历(我的背景是本土硕士 六年台厂工作经验), : 然後只出了一道coding的问题(我写完离预定的interview结束时间还有20分钟, 时间上应 : 该够再出一题), : 题目是给一个 array 代表 3 X 3 的井字游戏状态(1:O, -1:X, 0:空格), : 输出一个数字代表结果(1:O win, -1:X win, 0:还没人赢). : 我只想不到一分钟就开始 coding, : coding 完 interviewr 也说 code 看起来应该正确, : 然後问如果输入不是 3 X 3 而是 N x N 我的 code 是否依然正确, : 我回答只要把 3 改成相对的 N 即可. : (一开始我相关code中都直接用3, 此时我有说若一开始设定N=3并在相关code中用N会更容 : 易扩充) : 然後他问我复杂度的部分, : 我也有回答出 time complexity: O(N^2), space complexity: O(1), : 对这个问题应该也已是最佳解. : 然後他问我若 N 大到无法在一台机器运算怎麽办, : 我也有大概讲一下用 row index 当 key, 每一行 row 当 value, : 如何用 map-reduce 架构运算. : 不好意思写得很乱, 我想板上应该不乏在 Google 及其它好公司工作的强者, 想请教一下 : (1) Coding 问题会在 constant factor 上计较吗? : 因为我觉得我遇到的问题input size就是N^2了, : 我的coding顶多只能就 constant factor 作改进. Short answer: Yes constant factor matters. Long answer: 个人觉得敝公司的电话面试越来越松了, 这种 fizz buzz 等级的问题只要 code 会动, 复杂度不要太夸张, 基本都会给过. 我最近还看到一个 tail recursion 转 loop 写坏掉的也让他滥竽充数混进来. 所以个人倾向相信是你推论的时候犯了一些错误而不自觉. 你也没有电话录音, 很难从片面之词推断出你到底哪里答得不好. 另一种可能是这个 interviewer 很严格, 他用 onsite 的标准在检视你的答案. 话说回来 constant factor 重不重要, 你如果 constant factor 比较低当然有加分啊. 你会这样问, 然後答案的 space complexity 又是 O(1), 我大概已经猜出你怎麽做的, 多半就是为了省暂存空间, 所以直的扫一次, 横的再扫一次. 嗯, 勤俭是不错的美德啦, 不过这样做多半 code 跑比较慢. 理由是因为: 1. Memory bandwidth 很贵. 整个 N^2 的矩阵能只扫一次你就不会想扫第二次. 相反的, memory space 很便宜, 你都可以存一个 N^2 的矩阵了, 再多拿 O(N) 存一个 column sum 是有多贵? 2. Cache locality 的问题. 横着扫矩阵很快, 因为 CPU 读记忆体不是一次只读一个 byte, 而是一次读一条 L1 cache line, 在近代 CPU 上面一般而言是 64 bytes 或更多. 这代表的是, 你读矩阵第一格的时候可能因为 cache miss 而 stall 数百个 cycle, 可是你读接下来 63 格的时候, 资料都还会在 L1 cache 里面. 相反的, 当你直着扫的时候, 这多读的 63 bytes 根本完全没有用到, 因为下一个 row 的资料已经在不同 memory block 上, 而当你扫完一整个 column 回来要扫下一个 column 的时候, L1 早已经被刷新, 全部的资料都得重读. 这个原则不只对於 L1 cache 适用, 对於整个 memory hierarchy 都适用. 资料放在云端, 硬碟存不下? 那就要注意存取的 locality, 尽量少 network request. 资料放在硬碟, 记忆体存不下? 那就要注意存取的 locality, 尽量少 swap. 资料放在记忆体, L2 存不下? 那就要注意存取的 locality, 尽量少 cache fault. 结论是, 省暂存空间这个勤俭的行为就像是为了捡路上的铜板而被十八轮大卡压过去. : (2) 会希望先跟 interviewr 描述想法再开始 coding 吗? : 我在 interview 的时侯是先 coding 完才描述我的方法, : 我在想会因为这样被扣分吗? 会不会扣分因 interviewer 而异, 不过你是应该先描述想法再 coding. 理由: 1. 这是 interview 很重要的一部分, 我们想听的不只是问题的答案, 更重要的是了解你的思路, 了解你是如何解决这个问题. 我们要用的不是知道所有问题答案的人, 而是知道如何解决新问题的人. 2. 先确认对於题目的理解没有错误, 以免你都写完了才发现是听错题目. 3. 先说明你的 approach, 之後 interviewer 也比较容易理解你的 code. 其实综合 2. 3. 点, 就是我们想知道你的沟通能力如何, 实际在工作的时候也不会是一个人死干蛮干, 更多时间其实是花在 code review 上说服你的同侪. 因此事前沟通很重要, 你才不会 code 写完了才发现 code review 不会过, 事後沟通也很重要, 让别人懂你的 code 才有人能继续修改你的 code. : (3) 通常 coding 正确还有哪些原因会得到 negative feedback 呢? 最常见的是沟通能力问题, 或是人看起来阴阴沈沈很难相处, 或是看起来对写程式没有热情. -- 「ふ…ふざけるな！そんあ短い咒文で、魔法を起动できるわけないだろうが！ お前わマウゼルの神に逆らう气なのか？！傲慢な～」 「失礼致しました、诚实に全力でお相手致します。 第一战术级‧军用攻性魔法‧出よ、武雷神〈トール〉！」 〈スクラップド‧プリンセス〉 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 173.228.125.35