10.28 Google 电面 及 寻求加拿大小伙伴

昨天电面的Google。一开始他自我介绍了下，之前在做gmail，做了四年的样子，现在转到infrastructure（记不清）了。


然后口头问了几个问题。问如果想在电脑上存一个dictionary怎么搞。然后扯到了hashmap，问我的实现。紧张了，只说了一部分我想说的。感觉答得相当一般。接着问database primary key怎么实现的。我表示database的课忘的差不多了。就说记得是B tree或者变种。。。然后说具体的不太情况。话说回答的时候还能听到我回答的回音，感觉好distracting。。。


我本来以为就是闲聊下，然后做题呢，不知道有这个环节。。。然后是做题。

做题的时候他才说自己的python并不咋的，他主要用C，C++和javascript的。他出的题也都是现场从C、C++那类改过来的。

第一题，给个string比如，“549”要求输出+1之后的string。很简单的。但他没让用那个最直接的 str（int（s）+1）。我就从右往左扫一遍。他一开始以为我错了，后来是他看错了。。。

第二题，给一个string然后以另外一个string内字符的顺序sort。比方说，a = “abddded”， b = “dea”， 然后a按b sort之后就是“ddddeab”。我先是用b内字符第一次出现的index来建立一个dictionary然后直接用sorted搞，当然要考虑 1）b中字符重复，“dead”这种情况还有2）a中有字符不在b的情况。完了之后他告诉我如果不用考虑stable sort的话，可以优化。于是我想了下，直接根据a建立个dict然后顺序遍历b就成，当然前面说的两天都还要适当考虑。

总的来说，题目比较简单。。。但自己还是有点紧张，影响了表现。anyways，希望能帮助到其他人并且攒攒RP。

下面这段和电面已然没关系了。

加拿大找工作

话说地里有多少现在在加拿大找工作的？欢迎加好友相互讨论。

可能和很多人不一样，我希望能留在加拿大，感觉加拿大挺好（工资比美帝低了一个层次倒是真的）。当初Google第一次给面试机会，因为是MTV的，所以没搞，重申了加拿大的office。 地里关于加拿大找工作的信息太少了，都不知道在加拿大该申哪些公司。。。每天在glassdoor上瞄，但绝大多数还不招entry level的。。。其实这也是机遇，等我找好了工作，我要写一个加拿大找工作的帖子。。。


希望在地里能接触到更多也在申请加拿大的公司的童靴，相互交流。还有如果有在加拿大的能内推的伙伴的话，就更感激不尽啦。


plug
最后还是无耻plug下自己的iOS应用吧： GeeksforGeeks Reader: https://itunes.apple.com/us/app/geeksforgeeks-reader/id991254978?mt=8. 近五星好评。今天下载量刚过1K，每天近百人用的样子。一半来自印度，但他们都不给好评/评论。。。免费的应用好么。。。于是我今天在该国撤下了这个应用。希望地里的伙伴们喜欢的话能给个好评



补充内容 (2015-12-7 14:22):
app现在有了个in app purchase。主要是host需要钱，开发需要经历，而且现在没有工作。希望大家体谅~

关注一亩三分地微博：
Warald

跟楼主握个手。加拿大的美国公司靠谱一些，看你想做哪方面的。东部ottawa有cisco, shopify, trip advisor, montreal有ibm, intel, oracle, shopify, expedia, autodesk, nuance, morgan stanley etc etc, 搞不懂为什么大公司会去渥太华那么适合老年人居住的城市

补充内容 (2015-12-8 02:53):
当然montreal和waterloo还有google

补充内容 (2015-12-8 02:53):
montreal和vancouver game industry比较发达，van还有fb, msft, sony studio

感谢分享！App做的漂亮！

ex172000 发表于 2015-10-29 09:27
感谢分享！App做的漂亮！

不客气~喜欢的话给个好评哈~

gnijuohz 发表于 2015-10-30 01:32
不客气~喜欢的话给个好评哈~

已经评了~

同～ 在toronto么

ex172000 发表于 2015-10-29 10:40
已经评了~

太感谢了~

wxr.dal 发表于 2015-10-29 10:52
同～ 在toronto么

不在呢，在calgary。。。不过想去温哥华或者toronto那边工作。我们加好友私聊吧😄

感觉在加拿大找工作还是要投美国的公司，本地公司的工资水平真的低的可怜阿。楼主可以多看看温哥华和多伦多两个大城市的机会吧。

allenlyn 发表于 2015-10-29 11:02
感觉在加拿大找工作还是要投美国的公司，本地公司的工资水平真的低的可怜阿。楼主可以多看看温哥华和多伦多 ...

关键是我比较喜欢加拿大，感觉在加拿大待几年有身份了再去美帝也不迟。
. 1point3acres.com/bbs
美国现在Donald Trump都能front runner，感觉这个国家和我很不match。

我现在就在看温哥华和多伦多的机会的~

gnijuohz 发表于 2015-10-30 02:05
关键是我比较喜欢加拿大，感觉在加拿大待几年有身份了再去美帝也不迟。

美国现在Donald Trump都能fron ...

Donald Trump都能front run。。。莫名戳中笑点

楼主，请问这种情况你如何处理的 “当然要考虑 1）b中字符重复，“dead”这种情况”

gnijuohz 发表于 2015-10-30 01:58
不在呢，在calgary。。。不过想去温哥华或者toronto那边工作。我们加好友私聊吧😄

咦～这个还能私聊咩～已经加了

pengzewen37 发表于 2015-10-29 11:29
楼主，请问这种情况你如何处理的 “当然要考虑 1）b中字符重复，“dead”这种情况”

未优化的解法是只记录第一次字符出现的位置。dead，d第一次出现下标为0记在hash table中再出现就不管。

优化之后我是用一个set记录的，先把dead的字符加入一个set {‘d'， ’e‘， ’a‘}，然后遍历的时候去掉字符即可，也可以搞个visited set一样的思路。
```python
# 估计坛内编辑器不支持markdown，but 。。。
charSet = set(b)
for c in b:
    if c in charSet:
         ...
        charset.remove(c)
```

大致就是这样子。

flyaway25 发表于 2015-10-29 11:13
Donald Trump都能front run。。。莫名戳中笑点

Donald Trump也是每次都戳中我笑点。。。可是。。。没想到他front runner这么久，我已然笑不出来了哎

gnijuohz 发表于 2015-10-30 03:00
Donald Trump也是每次都戳中我笑点。。。可是。。。没想到他front runner这么久，我已然笑不出来了哎

原本最大的竞争对手希拉里先在丑闻缠身，一想到以后很有可能就是Trump当家，就只能呵呵了。。每次在gym里面都是循环播放他的演讲

gnijuohz 发表于 2015-10-29 13:48
未优化的解法是只记录第一次字符出现的位置。dead，d第一次出现下标为0记在hash table中再出现就不管。
...

所以优化之后的意思是 只用考虑第一次出现的值按照b的顺序排，后面再出现就还是按照a～z的顺序？

flyaway25 发表于 2015-10-29 12:01
原本最大的竞争对手希拉里先在丑闻缠身，一想到以后很有可能就是Trump当家，就只能呵呵了。。每次在gym里 ...

你的gym播放？还是你自己放着听？

不管哪种都是好痛苦的感觉。。。

pengzewen37 发表于 2015-10-29 13:36
所以优化之后的意思是 只用考虑第一次出现的值按照b的顺序排，后面再出现就还是按照a～z的顺序？

恩。。。好像不是的。举个全点的例子吧。
a = “abeeedbbbad” b = “dead”， 以b sort a。

这样的话结果a就变成了ddeeeaabbbb。
他说如果不在的话放在后面就可以不用以a~z来搞。

优化的O（n）算法：

1. <div>a_counter = collections.Counter(a)</div><div>b_set = set(b)</div><div>
   
2. </div><div>result = ""</div><div>for c in b:</div><div>    if c in b_set:</div><div>        result += a_counter[c]*c</div><div>        b_set.remove(c)</div><div>        del <span style="line-height: 1.5;">a_counter[c]</span></div><div><span style="line-height: 1.5;">
   
3. </span></div><div><span style="line-height: 1.5;">for key in a_counter:</span></div><div><span style="line-height: 1.5;">    result += a_counter[key]*key</span></div>

复制代码

大致就是这个样子的~






补充内容 (2015-10-29 15:15):
乱码了不好意思。。。

gnijuohz 发表于 2015-10-29 17:14
恩。。。好像不是的。举个全点的例子吧。
a = “abeeedbbbad” b = “dead”， 以b sort a。

谢啦，谢啦，明白了～～～～

Lz面的Waterloo office嘛？