各位前辈好 我想我跟原PO一样也需要帮助
文长且有点抱怨文 请见谅
我可能运气比较差 上个月因为家里有事回台湾一趟
回来以后公司就叫我不用来上班了
明明放假前经理也批假了 唉 简而言之我就是失业了
其实我自认coding应该是还可以
leetcode一直都有在写 版上很多人强调的不要背题
多问问题我自认都有做到 都能够用推理的去把一个新题解出
再看别人的解去改进 自己手写都有做到
但我不知道是不是真的流年不利 总是在面试最后一关拿不到自己真的想要去的offer
目前面过的大厂:
VMWare / MagicLeap
有过但是当时因为家庭因素decline...
Google
on-site后没过目前冷冻中
Amazon
失业后面的 面SDE后HR打来说原则上?过了但感觉JAVA经验不够
问我能不能转system engineer
我答应后也是无声卡
当然还有很多大小公司族繁不及备载
但昨天也刚面完一间on-site 我想是我主要发这篇的原因
面完HR告诉我一切都很好 但coding这关bar真的还差一点
叫我先练一下两个月后再跟他连络一次
题目确实不难 但我不知道是我跟面试官不对盘还是我自己问题比较大
因为如果不对盘那就算了 我觉得我也没办法改变什么
但如果我自己问题大 我想上来真心寻求版友建议
以下强调我绝对没有背题 但因为发文所以我尽可能简化
第一题:
给定一个array 建造一个complete binary tree
ex: [1, 2, 3, 4, 5, 6]
1
/ \
2 3
/\ /
4 5 6
先清楚地把binary树原理等等解释清楚 有问条件等等
当然我用BFS可以解完了没问题
面试官问那如果有给定一棵树 输出inorder的顺序
我用递回也解出来也没问题
但他这时候的问题变成是 如果给定原本的array怎么直接output inorder
老实说我听了问题楞了一下 我问他不就两个functions在这里了
我们为何不能直接叫这两个function就好?
他觉得有其他办法 想知道我会怎么做
我就说我会有一个大function去包这两个小的function这样
(后来HR跟我说面试官觉得我用暴力解... 不愿意去思考有没有其他方法...)
其实我回来还有检讨一下 但真的有其他更好的办法吗?
第二题:
给定一个array 找出第二大的数字
我知道版友看到一定会笑掉大牙 这么简单也不会过...
但没关系 我知道leetcode有类似的 但我们不能背题 对吧
我开始问主考官问题 确认到底要什么
是否可以保证答案一定存在? 不保证 size可能小于2 要throw error
是否可以保证每个数字都是唯一的? 不保证 可能有重复的数字
数字是否有特定范围? 不知道 这都随机的
ex:
[1, 1, 2, 2, 3, 3] 答案2
一开始我先用hash map去把重复的数字过滤掉
先看数量够不够 够的话用sort找出倒数第二个
结果面试官问复杂度(N log N) 他说他不喜欢这个
因为要用额外的memory 想问有没有N的方法
我说可以记录说最大跟大二大同时是什么
我有先写大概的想法跟code 但我提醒觉得这样会有问题
面试官一直觉得没问题 搞不清楚为什么我说会有问题 叫我先写出来
好的我们写差不多跟这个几乎一样的
https://www.geeksforgeeks.org/find-second-largest-element-array/
他觉得ok 其实我当下闭嘴就好 但我可能自己假会 一直跟他说我觉得这样会有问题
因为如果[3, 3] 跟 [3, INT32_MIN] 这个function会丢出一样的结果
但是事实上第一个阵列没有正确答案 第二个却是有的
照他当初自己说的任何数字可能性都有 那他要求的这种方法不就死了...
我才告诉他这样的方法会有问题 原本的优点在哪等等
但反正他可能不是很喜欢我原本的方法跟答案
但HR跟我说面试官觉得我在这边卡住 而且他给了提示我却没办法完成他的要求
我心里才OS这样明显就有问题了...最后他自己才发现要至少两个不一样的元素才可以用
这样的算法吧...
自我检讨:
我自己很常纠结一些为什么一定要照面试官的答案才是标准答案这样的思维去跟他们讨论
我自认应该很和善的去了解跟题出自己的想法
可能他们就会觉得我在硬凹还是没有理解的透彻
加上我自己心态可能也有点崩了(以下开玩笑请不要太认真)
现在整天躺在床上
心里都OS面试官都是智障吗
例如第一题如果他有好的办法 是不是可以提出来我们两个讨论
分析优缺点 这才是讨论问题的本质不是吗?
第二题我就给test case就打脸了 还一直叫我先写出来
然后又说我卡住
就跟妹子一样要什么不讲清楚 要别人去猜他到底要什么
猜不到就说别人不合格 我是要应征软件工程师还是算命师?
还是我其实就闭嘴乖乖把戏演好就好 也不要自作聪明提出很多想法去质疑面试官?
反正把offer拿到才是最重要的?
之前有类似这样做 这样又会被说我们要可以互相讨论的team player 不是单纯解题机器
真的搞的心很累...
加上其实刚毕业一年又失业 当初能够申请new grad的优势又没了
真的处在一个很尴尬的时间点 才会上来求助
如果版友们有觉得适合的软件工作能够内推的请让我知道
(如果是华盛顿 加州 或是德州 那会更好!)
或是如果能只针对我的问题给予建议我也会很感激
最近觉得废到笑所以如果知道我是谁的请不要认亲
谢谢

加油 那你现在是用opt？

原po有身分吧

感觉目前你路也还没走死

第一题，如果我是面试官，我会认为你没有认真追求最佳解他的follow up就是想问你当需求变的时候，可不可以避掉一些不需要的effort。

已寄信

第一题就是 (i+1)*2-1 直到超出size 就是inorder第一个 也许可以研究一下heap

面试不是只是把题解了就好，面试官可能是未来同事他还会看你的应对态度，太硬太难搞会直接打枪的

(3,3) (3,min) 可以用一些 check 简单解决, 无论如何这都比你 n log n 好... 我如果看到你这么坚持也很阿杂

根据index算左右不都跟你说了 只是从root = nullptr改成 i > size 停止的 recursive？ 坦白说 从文章跟现在都感觉你难以沟通

看你文章叙述 你现在还是觉得你的方法比较好 我是面试官可能也会怕怕的尤其你建 map 不只慢还要花 n 空间复杂度

https://bit.ly/2YShpOR 很简单自己看吧

你可以从array建出tree，就代表array index跟tree node有直接关系，所以中间可以把直接建树的cost省下来i大已经讲了

其实有同感 看完你的文我反而觉得工作上你可能不是太好沟通 你的态度看起来就是不相信有更好的方法好的工程师看到问题马上就会反问 那[3,3]应该return什么而不是写完看到有这个case不能处理 去找sub-optimal的

我也觉得看文章 不一定是程式的问题 有时候工作能力好解决个性问题很难解 但我只是针对文章的感觉 如果你平常的个性不是如此 那么就要练习一下面试技巧 了解面试的目的

第一题 123456 -> 1 23 456 => 1 425 63 -> 425163第二题 112233 => 1 => 12 => 231. O(2N) 2. O(N) * O(2log2)** 2. O(N) * O(log2)

我自己的感觉是 你试着讨论优缺点 但你应该miss了一些很明显的点 面试官很容易就发现你的depth不足 大部分时候我在这种地方都能刷掉很多人

有时候退一步，反而是进一步，能力反而不一定是最大原因

讨论解法trade off的前提是多个效能相似的解法，而你的面试官的提示基本上都已经是在提醒说有个效能更好的做法，你没抓到点而只想讨论次佳解的话很难让面试官帮你写好的feedback

第二题 他想说的重点是 n log n 不大好吧，但你好像有点纠结在别人 O(n) 的 "bug" 然后说自己 n log n 比较好好像有没看到问题本质的嫌疑我觉得你下次可以改成说，你原本想说你这个解法会有什么样的问题，如果这个不打紧的话，这样的确不错，然后看有没有办法绕过或解决那个 "bug"最后我觉得不断精进是要的，但也不用纠结特定的一次面试没过的原因千百种，把自己准备好从来只是增加机会再确认结果前没有100%的事

面试是要找未来同事，你明显表现出很难共事的特质

面试官对题目很熟 默认就是最佳解 这种时候要跟着演好

比你优秀的或同程度的一大堆。。。一般人宁愿选程度差一点，但是好共处的

撇除这些互动先不谈 很单纯的来看 你这两题也都没有写出最佳解 建议平常还是要多延伸思考 多质疑自己我这样真的是对的吗? 有没有最佳解? 有没有其他做法?要常常挑战自己的答案 不要画地自限 公司最怕的就是 newgrad 进来然后不听其他人的建议...

小剧场有点多 就算题目有许多可质疑的点 也应该先赶快设定好假设 把解先写出来 写完再来讲自己觉得有疑问的点 然后再改进 而不是马上拿问题去打问题..拼命丢问题回去不是展现能力的好方法 反而会让人觉得不好相处 毛很多

第二题O(N)的解法是有办法分辨你举的例子的 你再想想吧

难搞 不想当你同事 就这么简单讲个笑话搞不好就上了

def inorder(arr, i):if i >= len(arr): return []return (inorder(arr,i*2) + [arr[i]] +inorder(arr, i*2+1))print(inorder([0,1,2,3,4,5,6], 1))我也在找，一起加油吧

LeetCode在招人 有工作经验的话履历可以发给我

很多人似乎搞错了什么，以为面试只要回答对全部问题就会过，忘记面试是在选同事而不是只考能力。 我自己也好几次面试问题保证答对，但软实力表现太差别人不要我的

话不投机半句多，磁场不合~

先不说个性问题，你这篇文提的所有被考的技术题都是“你想错了、面试官的想法是对的”（等有心人把正确方法解释给你听），你竟然还觉得“面试官都智障”，真扯，是面试官们都觉得你是智障吧...上面竟然多数推文都只说你个性上有问题而已，可能大家没有仔细看你的题目，你的技术上完全很不行......（然后说实在的，现在资源这么多了，你怎么不自己先去google解答、弄懂以后再来PO文？）其实我本来不会这么凶的，不过看到你妹子那段真的觉得你面不上好爽，最讨厌你这种性别歧视的男工程师。本来想要写篇文回应你这篇被面试官问到的问题的正确解答，看到妹子那段就觉得你这种人还是一直找不到工作算了，爽。上面sssh5566大大说“很多人以为面试只要回答对全部问题就会过”，可是事实上这一篇原PO是错的一蹋糊涂的程度，离“所以问题都回答对”还很远。

楼上别气 他第一轮是答对的呀 是没理解什么叫做follow up吧

是啦，真的不要觉得面试官白痴，题目我们自己都讨论过了followup是刺探你对程式设计的理解程度，不是智障乱问如果你先入为主觉得面试官在乱问，那也无从followup

看到妹子那段同样感到不爽

完全同意 jennya然后你举的那几题都不难 你没接到面试官的提示只能说是你的问题

同意J大，自己跟面试官沟通不好固执己见，关女生什么事

我觉得这个技术问题的根源其实是个性或思想问题，有时候技术问题并不是完全是一个人真的知识不足或逻辑非常差，而是没去认真思考自己有错或不够好的可能性

第一题告诉你他是complete b-tree其实就等于你可以靠index来做traversel 了, l-child = i * 2 + 1,r-child = i * 2 + 2, parent = (i - 1) / 2写个递回就解决

路过嘘性别歧视

自己面试有问题牵拖女生是怎样

面试考coding是基本，主要想看的还是个姓吧…

推J大，这两题followup原po都错得离谱，光从你叙述我都会给no-hire了，更不用说这还是你主观的描述

1.阵列建二元树：(X) 不必使用BFS，使用for循环将阵列跑一遍就可以做到，省下bfs queue的空间2.二元树inorder：(O) 使用递回没问题3.阵列inorder：(X) 一样可写成递回，只是递回里面每当要呼叫子树时，用index的方式。这是合理的需求，假设原本的资料格式就是阵列，现在唯一需求就是输出inorder，难道你要每次都新建一个中继用的二元树、输出完inorder以后就不用？因此你的想法“已经有两个function为何不用”其实是不太好的反对理由，你并没有理解到面试官题目的需求（不要新建中继二元树）、你想不到方法达成、你听不进去面试官的引导提示4.给定阵列找第二大数字：(X) 先用简单些的题目、假设数字不会重复好了，那你还是用nlogn的sort然后拿第二大吗？你要是有在认真写题目，应该会知道最佳解是O(n) one pass循环、使用变量和if else。而今换成数字会重复的版本也是一样。面试官一直提示，她的方向是对的，O(n)没有任何副作用且就是最佳解。然后你贴的网页就已经说one pass是最佳解了为何你会没有看进去，还会有自己的想法认为O(N)有问题= =有自己的想法不要紧，每个人也都有自己想做的时候，可是你看到那个网页，应该要能够“察觉”自己的想法不太对劲吧。关于你说的bad case，[3, 3]你应该要回传错误值，你就算用sort也是得回传错误值阿。

楼上第一题怎么用for 建complete b-tree?我还真想不到而且还是在不用额外内存的情况下利用pre or inorder traversal建还是需要暂存parent不然要怎么返回parent node?

这都是颇基本的题目，然后你四题却只有一题有答对（还不论你写出来的时间和变量命名等等），这是很惨烈的情况，应该要认知到自己的技术要增强；然后比起技术力，更为惨烈的是你毫无自觉...而且还想相反了...“整天躺在床上，觉得面试官都是智障吗”......有懂那几题在干嘛的看到你这句话应该都感到震惊。

震惊，在智障眼中我是智障吗？

同意楼上

@Ninja5566 你说的对。我原本的想法像是这样：https://www.paste.org/97946但是仔细一想这的确和BFS差不多。这部分我的确是呛原PO呛错了。谢谢~~

推 j大解说XD

都要建 tree 了 应该不可能不用额外内存吧..虽然说 tree 已经 implicit 的储存在 array 中了..

找第二大数字 其实可以one pass 用一个heap去记录 最后回传heap的最大值就好了吧 小弟 遇过不只一次跟in 开头国籍的面试官 还不是小小startup 跟我说我写的 O(n) + O(n) 是O(n ^ 2) 他要更好的 我也是 笑笑 其实找工作有时软实力比硬实力重要多了 一起共勉之

推文好热烈XD

用heap那直接sort不就好了……

直接两个变量存最大和第二大if else过去就好了吧

heap......

资遣有资遣费吗？

谢谢分享 留言也都超有用 我猜原po应该也是转行的 所以有点心态上还是解出来就好 再多磨练吧 加油

找第二大可以用min heap吧 一定要用heap的话啦...

回 jatj，用 heap 比较好唷 O(n) 时间可以建出 heap再拿出前2个 也是 + O(log n) 整体还是 O(n)

用个Size = 2的max heap更省空间吧 不过这样就跟两个变量if else过去差不多的意思

用heap的有考虑constant time吗…都是O(n)不代表执行时间差不多啊…

请问用heap不是O(nlogn)吗？全部放进去要O(n)，每次放跟拿都是O(logn)，这样算O(n)建出heap吗？

建只要 O(n) 最大在 root 且 次大一定在 root 的 child

jennya 很佛心，不但告诉你怎么解，还示范了遇到质疑该如何处理。已经很多版友提出你该改进的地方了，原 PO 加油吧…

min heap constant factor 是2,time=O(2n)=O(n),space=O(n)for扫一遍O(1n)=O(n),space=O(1),建heap到底好在哪里?印度面试官觉得heap非最佳解是对的,时间慢2倍空间多N倍然后到底哪几间大公司印度面试官问这题?我想去面,需要工作我错了,build heap证明https://tinyurl.com/yyoq8xmw中间不断利用big O特性省略常数项,所以常数并非2

用大小为2的heap不是 time:O(n log2) space:O(2) 吗?

面试完就是move on 工作就是缘分而已

size2 heap跟for一遍加2个int时间一模一样,空间是常数倍,因为你把原本两int换成两个带int的node,仍然非最佳解阿再来,建heap为O(n)的关键是Heapify,以java来说,你必须直接把collection传进PriorityQueue建构子以保证linear time如果你是建一个空的然后一个个插入那还是O(nlogn)

回 OckhamsRazor：我只是想强调建 heap 真的可以 O(n)，复杂度上比 sort 好，我没有觉得花 O(n) 的时间空间 建 heap 在这题是好方法… 只是“理论”上比 sort 好，实务上我猜还因为 constant 太大比 sort 还烂 (library 的 sort 还往往 worst case n^2 勒…但用起来真的很接近 O(n)了)

第二题你说的那个 case 只要额外用个变量纪录阵列里有没有出现 INT_MIN 就行啦。这样就还是 O(n) 而且你提出的 case 还是会给出正确答案至于阵列里只有一种数字，同样可以检查 top1 top2 是否一样来侦测出来。总之加入各种错误侦测后就得到O(n)且任何case都正确的解比如说 a= [INT_MIN,INT_MIN] 就会导致top1=top2=INT_MINa=[INT_MIN,3]就会top1=3 != top2=INT_MIN 然后就看另外那个变量来检查 INT_MIN 有没有出现在 a 里

高手在民间～

你连第二题这种一看就送分题都做不好 再努力学习吧 别抱怨

x,y=-inf;for i in array {if (i>x) {y=x; x=i}}if len(array)<2 raise error;if y==-inf raise errorreturn y 之类的吧

技术不行沟通不行还搞性别歧视还怪东怪西，再多学习吧你

楼上da大 您的code在原po给的例子(3,-inf) 会给错误结果 应回-inf 实回error

都是别人的错~

第二题用nlogn....我是面试官我也不接受啊