跨专业求职SDE

2014-10-21 from 迷彩的瓜皮帽
国内EE本科，有些Java基础。美帝Master IE，期间没有一门编程相关的课。跨专业SDE求职艰辛历程终于有回报，发点面经回馈本版。

Glassdoor

1. Convert string to integer

2. How to implement a Queue

题简单，更要考虑周到，什么string里有没有什么特殊字符，如果用str.charAt()后面减去’a’，如果string太长了会不会overflow。

Programming interview exposed书中有详细解释。对于数据结构，也先clarify一下：比如可不可以用这个数据结构来implement，需要design哪些functions，整体讨论清楚了再说思路，尤其是为什么要用这个方法，凭啥linkedlist来实现queue就是好，如果可以的话先随便说几个别的数据结构，讨论一两句这个为什么不可行或者不efficient(比如用array来存，浪费空间，删除完了还得把elements都shift啊)，让面试官觉得你在想各种不同的方法。

这是我第一个电面，略紧张，感觉语速不慢 但不知道自己在说什么。就当积累经验了。

Medalia (online test)

之前写过这个的面经而且贴了个大家讨论热烈题的我的解法。

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=106494&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311

Reverse linked list in group, given ListNode head and k

Input: 1-2-3-4-5, k = 2. Output: 5-3-4-1-2

给你一棵树(不是BT)，孩子们是个List<TreeNode>，找到两个subtrees并且哥儿俩结构一样(不是TreeNode数值一样)，并且使得树的Node数量最多。

Tango

之前发过就不重述了，有朋友发了个很全的它家题(好像是6道)

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=106076&page=1#pid1459836

Aspera (online test)

有个txt文件，里面有173k行，每行一个单词，要求找到最长和第二长的单词thatcan be concatenated by other words，并且print出来一共有多少词可以由其它词组成，基本原理就是cc150里的原题。要求注重效率和运行时间。

做完了运行大概0.56-0.7s，听说有trie的方法实现起来很简单，在github上找了一个用trie实现的，运行了一下平均时间0.7s，就没仔细研究。

大概两个月了，中间发信从来没有回复，到现在还没给结果。

eBay

这个比之前发的帖子technical question更详细一点

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=106216&page=1#pid1462667

第一轮

问hashtable的实现，和howit works，我说的时候提到了一个mappingrelation between key and value，让我举个例子，就说contact(名字对应号码)，讨论了两句怎么实现，然后他问如果一个名字对应好多相同的号码hashcode有collision怎么办，我说不知道，rehash行不行，他说collision是由于….而产生的所以rehash还是会产生，我说我还是不知道。然后就开始做题：Givena string, find the character that reaches the max number of occurrence firstfrom left to right.  Print that characterand its number of occurrence.

第二轮

国人，感觉很严肃，问了问简历问题，开始做题:给一个matrix，都是1或0，返回连接着的1的最大数量，好像有个题叫biggestisland，用bfs，visit完一个点就把它改成3，写完问如果不修改原matrix的话怎么办，那就再来个boolean二维数组，visit过了变成true然后在recursivefunction里把条件改一下。写了两个testcase检查对不对。还有十几分钟时间，那边传来“可以说中文了”，长舒一口气，满脸泪，说了说上一轮问我的问题过去没学过完全不会啊，然后他给我了一些建议，然后就goodluck了。

国人始终都特别好，最后提醒我写code前一定要把想法说出来，每写一点code就稍微解释一下，coding和表达交流同样重要。

两天后收到下一轮。4-5hours skype loop interview，签了NDA，题中等偏难，都做出来了而且当时自己写了很多testcases检查，面试官没说有bug，但还是挂了。

Snapchat

在eBay两个电面之后一天，snapChatGoogle Hangout，美国小哥，人很好很耐心，感觉就是：一边听着我蹩脚的英文，一边点头假装明白我在说什么…

聊简历，做过的东西，非常细致地问了很多细节和如何实现。然后开始出题：2sum, 3sum, 4 sum，这之间稍微变换了条件(比如:sort和unsort实现起来有什么不同)，后来加了点限制，要求minimizethe index of second number, input: {1 2 3 4 7 8 } target = 10, 返回{1,4}

然后是条件不变，还是要更小的index，实现3 sum，4 sum，后来outof time了就写了pseudocode，说了说思路，因为中间有一点卡住了很久在提示下才解决，面完当时就觉得很后悔思路一断就不会思考 肯定挂了。最后5分钟让我提问，聊了聊，我说对于非cs的newgrad有没有什么建议，他突然消失在屏幕中过了一会儿举了本CRACKINGTHE CODING INTERVIEW回来，在镜头面前晃了晃，说这是个好东西，多看看。

不出意外后来收到拒信，感觉没有进到下一轮纯粹是自己的问题。但是对于这种很成功的startup，感觉纯刷题远远不够。

Taboola

Israel的公司，看了它家网站觉得做的东西非常有意思。更有意思的是非常随性的面试官，东部时间12:30面试，提前2分钟邮件说能不能推后半小时，上班有点迟到~

先是问了很多概念的东西，能够记住的是：

Talk about Collections; different JOINS (DB); inheritanceand give an example; compare ArrayList, LinkedList and Array; static; singleton…然后问了道coding问题，lc简单级别，然后最后大部分时间用来讨论如何设计一个电梯。

Guidewire

所有电面中感受最好的，没有之一。Recruiter始终非常礼貌，感觉非常友好 尊重，问了很多概念性东西包括DBDS Algorithm Concurrency iterator，口头说了说Recursion(tail recursion)及如何搜索tree，比较recursive和iterative。然后出了道brainteaser：10feet的井 蜗牛每天上爬3ft下掉2ft，几天后可以爬出来，我脱口而出的答案让他有点惊讶。然后说了说如何设计这个小蜗牛。

上周五和seniorengineer电面:

1. 如何实现chessgame，在我design的时候让我着重说了几点：WhatKey Objects you will design; how to check whether it’s a valid movement; how tocheck whether this movement is threatening the King (将军)

2. How to design a hash table, how to deal with collision(rehash or use linkedlist)

都是口头表述，本来说半小时面试最后聊了45分钟，非常友好最后还推荐了我本书说对newgrad非常有帮助。上周五刚面完，这周等等看吧。

Expedia

两轮电面，第一轮：

1. Fibonacci, print all the first n numbers. N=5, print 0 11 2 3

2. Given sorted array and a target number, find the numberof occurrences of the target number.

还是那句话，题越是简单越是要考虑清楚，而且无论如何都要一步到位，用最优解。尽量别费劲写个bruteforce然后再口头上优化最后没时间写最优解了。

Solution 1: brute force, O(n)

Solution 2: binary search, 找到target然后往两边linear搜索直到不是target为止.

Solution 3: 基于方法2，继续binary search，O(n)for worst case.

然后问我2和3什么区别，方法2：O(logn)just for best case and O(n) for worst case, 方法3：需要左右边界分开搜O(2*logn)，3更好。最后想起来如果target找不到怎么办，return-1.

当天收到下一轮通知。

第二轮：

Merge two sorted array. 很快写完，看了眼没bug，让写几个test，我用的Junit语句assertEqual，expected exception之类的，要求判断所有情况，结果最后还是落了个what if the given arrays are not sorted? 赶快在前面加了个判断的方法。

过了个周末，一睁眼收到onsite通知。

5轮(4technical + 1 manager)，签了NDA就不说了，没有lc原题，题不很难但很灵活，所有人（包括三姐）都很友好。

onsite全程感受棒棒的。

在那边一共住了两个晚上，回家睡了一觉，第二天一睁眼看到早晨5点多发的邮件：extendan offer。

第一个onsite就拿下了offer，相当开心。

其它

关于烙印。除了三姐和一个三哥以外，其他的都比较cold，有的甚至没法正常交流。不过无论如何别受影响，如果你题做的bugfree而且最优解，他没有任何理由拒你，否则可以直接找recruiter。如果让人抓住你code里比较严重的问题，那就别抱怨面试官的问题。

关于英文。曾经几次phoneinterview都过不了，录音，听听自己语速语调就明白了。不光面试中积累经验，自己也要纠正发音和语速。Technicalinterview时候没必要读完题就张口说，开始觉得尽量不让电话里有空白的时间，否则很尴尬。到后来才知道比起语无伦次或者一句话两三遍才说清楚，想个十几秒然后简单几句话说明白你的思路要好太多，说话时也明显更自信。

关于跨专业求职，还有很多话要说，有时间再总结一下。