X*********n
发帖数: 570 | 1 背景: cs fresh phd 菜鸟 无任何industry 经验
从10月14号第一次校园面试到今天正式签了offer letter寄回给公司, 整整三个月的找
工总算是告一段落了.
也不记得是9月底还是10月初的时候, 学校career fair, 那时候还没有正式准备找工作
, 或者说刚有找工的想法, 还没有开始复习, 就打印了几分简历, 折成纸飞机, 对准了
几个大公司投射了过去. 这次career fair, 促成了我头两个面试. 一个是M, 另一个是
A.
说起来M的面试真是搞, 面试前几天HR给我发信让我给想要的职位排个队. 那form上白
纸黑字写的清清楚楚, 只是给各个职位列个先后顺序, 还说无论怎么选, 都会考虑
Software Engineer 也就是传说中的码工. 这次我土了, 我想PH.D好歹选个Project
Manager吧, 然后把码工列在了第二位. 交了表约了10月14号面. 结果面试当天去到现
场, 面试官是个老印, 说你面Project Manager啊, 我说是啊. 那说说怎么给Kids
design一个vehicle吧. 我大脑先短路了大概... 阅读全帖 |
|
w****a
发帖数: 710 | 2 10分钟面经系列，这次是T家。
上次FB二面终于如期收到拒信，move on了。T家的一面希望大家bless啊。
刚开始给我一分钟时间问了我两个behavior问题，一个是我现在在做什么，一个是why
T家。
然后就开collabedit了，就写了一道题。题很简单，板上的XDJM们相信都能秒杀。
给一个多叉树和一个节点，求出这个节点所有path下来的数字的和。比如给出树和节点
4
4
/ \
2 1
\
3
答案就是413+42 = 455。
这个题倒没什么，拿到就问了他需不需要考虑big int的问题，他说不需要，int肯定够
用。那就放心写了。写完之后我怕有bug在纸上反复写各种test验证。他问我干啥，我
就说我在做“单元测试”。他就让我别在纸上画了直接在collabedit上写。我就把他给
的sample用函数流程走了一遍。。
随后就是一系列的follow up。我一开始给的解不是最优解（犯2了，啥也没想上来先用
了vector存所有路径下的数字，最后我逐个相加）。他也没说什么，因为代码本身没问
题，就是跟我说让我说出时间复杂... 阅读全帖 |
|
l****i
发帖数: 2772 | 3 CS fresh PhD. 西雅图，已经接到HR电话，悲剧，攒RP，发面经。
第一轮，2个人。每个人先介绍了几分钟。给题，boggle，先让我分析怎么解决。代码
写到8个方向递归的时候，被打断，说知道我后面会怎么写了，让我先分析这个程度的
复杂度，他们有其他问题要问。最后15分钟，问了一大堆behavior，关于team work的
一类的问题，有矛盾怎么解决，team里有人不干活，team里有人和你不同意见等等，要
求给出一些以前经历的例子。
第二轮，老美白人。开始问了很多object oriented的问题。abstract class，
interface，什么情况下如何选择，inheritance VS composition等等。然后一个
coding，按行统计词频，不难，hashtable解决。 写code的中间，问了很多次复杂度，
基本上我写一行code，他会问一下这一行的复杂度。然后给了一个OOD，一个tree的结
构，计算表达式。然后又出了一题OOD，题目还没解释完，外面的第3轮人就敲门了。
第三轮，南美或者欧洲女。这一轮我很崩溃。第一轮，按层遍历二叉树。直接问我，你... 阅读全帖 |
|
C******x
发帖数: 91 | 4 恩, 接口清晰很多了,正在临摹中。。。 多谢指教！
具体到算法，
对于没有parent指针的tree，
对于++运算符 , 两个方案，
1 迭代器中维护一个栈，好处是遍历一次的复杂度是O(n)， 坏处是空间， 如果是后
缀加加， 每次都要复制一遍栈~ 如果不小心用后缀++遍历, 实际复杂度是O(n^2)，用
前缀++没有
这个问题, 复杂度还是O(n)
2 每次++，都调用next函数，要么找右子节点的最小值，要么从root找起，找到下一
个节点~ 最坏复杂度还是O(n^2)
另外，如果还是--， 还得额外维护一个栈~
对于有parent指针的tree
方便的找next就好了，遍历一遍的平均复杂度应该是O(n)~ 最坏的情况下貌似也是O(
n)[不是非常确定]
问题:
知道板上有人面试面到这个题，貌似还是高频
请问到底到写到什么程度，要求所有的接口，然后写出上面的那种case啊？
网上找到一些代码，正在修改~
感觉如果真要写清楚，还要定义Node，BSTree, 然后才能定义Iterator， 不仅仅是单
纯的非递归中序遍历二叉树~
了。 |
|
p********n
发帖数: 165 | 5 抛个砖：
A*算法的核心是点到点求最短距离，不是点到面。而且需要好的heuristic function，
即使是在矩阵中找点对点最短距离也不一定是最好算法。
这个题，假设gym为n^2 matrix，k个器械。 用Dijkstra计算每个器械到非障碍物的距
离，复杂度为k*n^2*log(n),其中log(n)为maintain 一个priority queue的复杂度，
queue里最多的元素不可能是n^2而是n。
然后iterate 一遍matrix，找出离k个器械距离和最小的一个element，复杂度为n^2.
所以最后复杂度为 O(k*n^2*log(n))
当然这个题两个相邻点的距离都是uniform的话，可以不用Dijkstra,而用Breath-First
Search，复杂度可以进一步降低到O(k*n^2). |
|
e********3
发帖数: 18578 | 6 这个我感觉挺简单的呀：
1.Peek多次，直到找到两个不同的元素，因为是排序好的，这样你知道整个collection
里面所有元素的上限和下限。
2.然后开始peek,只要不是最大的元素，一律pop出来按照顺序放到array里面，用一个
array index保持当前在array中的位置。
3.重复元素一样按照在原来Quack中的顺序放到array里面，这样你的算法就是stable的
排序。
上面是原始的解法。这个时间的复杂度是O(n*m),m是平均需要多少次找到最小的元素，
空间复杂度是O(n).
更加高效的是新建一个stack和一个queue，如果是最小的元素，push到queue里面，如
果是最大的元素，push到stack里面，所有Quack里面的元素取出来以后，合并queue和
stack，queue是已经从小到大排好序的，直接放进array，stack最上面的是最小的，所
以也是pop出来直接放到array。
queue里面最大的元素小于stack里面最小的元素，所以需要先把queue里面的元素放到
array里面，然后再把stack里面的元素放到array里面，这个程序的... 阅读全帖 |
|
e********3
发帖数: 18578 | 7 这个我感觉挺简单的呀：
1.Peek多次，直到找到两个不同的元素，因为是排序好的，这样你知道整个collection
里面所有元素的上限和下限。
2.然后开始peek,只要不是最大的元素，一律pop出来按照顺序放到array里面，用一个
array index保持当前在array中的位置。
3.重复元素一样按照在原来Quack中的顺序放到array里面，这样你的算法就是stable的
排序。
上面是原始的解法。这个时间的复杂度是O(n*m),m是平均需要多少次找到最小的元素，
空间复杂度是O(n).
更加高效的是新建一个stack和一个queue，如果是最小的元素，push到queue里面，如
果是最大的元素，push到stack里面，所有Quack里面的元素取出来以后，合并queue和
stack，queue是已经从小到大排好序的，直接放进array，stack最上面的是最小的，所
以也是pop出来直接放到array。
queue里面最大的元素小于stack里面最小的元素，所以需要先把queue里面的元素放到
array里面，然后再把stack里面的元素放到array里面，这个程序的... 阅读全帖 |
|
k******e
发帖数: 19 | 8
情况
你这明显是先入为主了，面试最忌讳的就是先入为主，不跟着面试官的思路来想。
这问题是个很基本的东西，MINHEAP和MAXHEAP都可以。基本就是有N个ITEM，找其中的
TOP K的问题。
- 用MINHEAP的话，空间复杂度是O（K）， 时间复杂度是O（NlogK）。
这个方法适用于当数据不能PRELOAD进MEMORY，比如说数据是从一个STREAM来的。你
就是先建立一个大小是K的MINHEAP， 在ROOT的就是最小的，其他K-1个都比ROOT大，然
后从省下的N-K个里一个一个取，和你的ROOT比较，如果比ROOT小的就丢掉，比ROOT大
的就REPLACE ROOT，然后将其 SIFT DOWN。
－ 用MAXHEAP的话，空间复杂度是O（N）， 时间复杂度是 O（KlogN）。
这个办法只能用在N不是太大的时候，可以先HEAPIFY，用时O（N）。现在你的ROOT
是最大的，把ROOT拿掉放进你的RESULT里，你的HEAP的ROOT空了，把最后一个元素放进
ROOT，SIFT DOWN， 又得到一个MAXHEAP，重复刚才的操作K次，得到你的RESU... 阅读全帖 |
|
k******e
发帖数: 19 | 9
情况
你这明显是先入为主了，面试最忌讳的就是先入为主，不跟着面试官的思路来想。
这问题是个很基本的东西，MINHEAP和MAXHEAP都可以。基本就是有N个ITEM，找其中的
TOP K的问题。
- 用MINHEAP的话，空间复杂度是O（K）， 时间复杂度是O（NlogK）。
这个方法适用于当数据不能PRELOAD进MEMORY，比如说数据是从一个STREAM来的。你
就是先建立一个大小是K的MINHEAP， 在ROOT的就是最小的，其他K-1个都比ROOT大，然
后从省下的N-K个里一个一个取，和你的ROOT比较，如果比ROOT小的就丢掉，比ROOT大
的就REPLACE ROOT，然后将其 SIFT DOWN。
－ 用MAXHEAP的话，空间复杂度是O（N）， 时间复杂度是 O（KlogN）。
这个办法只能用在N不是太大的时候，可以先HEAPIFY，用时O（N）。现在你的ROOT
是最大的，把ROOT拿掉放进你的RESULT里，你的HEAP的ROOT空了，把最后一个元素放进
ROOT，SIFT DOWN， 又得到一个MAXHEAP，重复刚才的操作K次，得到你的RESU... 阅读全帖 |
|
d********w
发帖数: 363 | 10 我们面对的系统越来越复杂，我们的软件也越来越庞大，包括我们一些技术的细分也越
分越细，在这种情况下，其实一个人很难做一个事情，往往要靠团队的这种力量去把一
个事情做好，但怎么能够把团队带起来，怎么能够比较好的建设团队，然后让团队运转
的比较高效，这其实是跟写代码还是不一样的，所需的技巧也不太一样。今日头条副总
裁谢欣，实时连线在硅谷的数据工程师董飞，分享他们在过去总结的一些管理的经验。
硅谷企业文化
我们来看一下硅谷，经常说一些巨头facebook、linkedin、谷歌，这几个大公司他们的
首字母简称FLG，当然他们都是一些技术型很强的公司。他们的福利跟待遇肯定是一流
的，除了这些之外还有文化方面的吸引，我举几个，比如说Facebook，它有一个新兵训
练营，新的工程师通过几周之内全方位的了解公司，之后就选择他感兴趣的组。创始人
Mark说过，最大的风险就是不愿意承担风险，还有一句是move fast and break things
. 如果在前进过程中没有遇到磕磕碰碰，说明不够快，这是一个快鱼吃慢鱼的时代，也
是创新的源泉。之前也在LinkedIn工作过，它比较强调的是用户第一，... 阅读全帖 |
|
m**a
发帖数: 1840 | 11 【 以下文字转载自 EE 讨论区 】
发信人: mola (Super Baby), 信区: EE
标 题: 为极解密：如何看待华为拿下5G“短码”方案？
发信站: BBS 未名空间站 (Thu Dec 8 12:21:31 2016, 美东)
朋友大作，发在知乎。欢迎点赞和转发。
https://www.zhihu.com/question/52732376
美国当地时间11月17日凌晨0点45分，在刚刚结束的3GPP RAN1 87次会议的5G信道编码
方案讨论中，经过艰苦卓绝的努力和万分残酷的竞争，以中国华为公司主推的Polar
Code（极化码）方案，成为5G控制信道eMBB场景编码方案。
编者按
“华为极化码事件”内幕：
极化码获得的并非之前大肆炒作的“短码”。
极化码打败的对手并不是LDPC，而是在控制信道上取代4G现有技术TBCC。
若非极化码最终靠非技术手腕挤进控制信道，华为投资几十亿的5G“三神器”在5G NR
第一阶段业已全部打水漂。
整个5G信道编码又经历一番怎样波澜壮阔的争斗，这背后又隐藏着多少暗流汹涌的阴谋
诡计。“为极解密” 为您最全方位的解析。
为极解... 阅读全帖 |
|
Q*K
发帖数: 3464 | 12 【 以下文字转载自 JobHunting 讨论区 】
发信人: zysxqn (十项全能), 信区: JobHunting
标 题: 报google offer，并分享找工作经验
发信站: BBS 未名空间站 (Mon Oct 25 14:50:37 2010, 美东)
刚刚从了google的offer，base 116k，bonus 15%, stock unit 160, relocation
7500。由于签了保密协议，具体的面试题就不详细透漏了，都是很基本的算法题，
先说算法，再coding，没有长老级别的难题，也没问什么其他东西，就是算法。听
说最近google招人很多，大家好好准备算法，现在进google真的没有以前想象的那
么难了。
开始找工作以来就在这个版上取经，收益良多，所以也想分享一下自己找工作的经
验，回馈版面。
我是fresh cs phd，学校排名50左右，找工作开始就将目标定在硅谷，因为喜欢那
里的天气和中餐，初期也会投些其他地方的大公司，积累积累面试经验。一共拿到
了A，O，BB，G，M五家大公司的onsite，也许是被人看出来了只想去硅谷，A和BB的
... 阅读全帖 |
|
I******c
发帖数: 163 | 13 有些概念理解不了，请教一下。
我理解amortized analysis就是针对一系列操作，分析他们的平均时间复杂度。即使其
中某一个操作可能很费时，但是平均下来可能时间复杂度并不大。
但是我不理解的地方是，比如在fibonacci heap中，我们是不是也应该针对一系列操作
，计算平均时间复杂度。但是我看到书中往往拿某一个操作，比如DECREASE-KEY操作的
amortized cost和binary heap中相应操作的worst case下的时间复杂度比较。这样比
较有意义吗？如果是单纯比较某一个操作，为什么不都拿worse case下的时间复杂度进
行比较呢？
谢谢 |
|
h**o
发帖数: 548 | 14 复杂度 of access: O(1)
复杂度 of insert: O(1)
复杂度 of delete: O(1)
复杂度 of traverse: = O(n)
不是 hash. 因为 hash 的复杂度 of traverse: >= O(n) |
|
I******c
发帖数: 163 | 15 假设有N个数列，每个数列的元素个数是M. 那么两个数列合并的时间复杂度是O(M)，这
种合并需要进行（N/2+N/4+N/8...+1)=N次。所以总的时间复杂度是O(MN)
对于堆合并，如果使用binary heap的话，建堆需要N*O(M). 合并需要O(M)*N。所以总
的时间复杂度是O(MN)
如果使用Binomial heap的话，我不太确认建堆的时间复杂度，合并需要O(lgM)*N
还可以使用fibonacci heap, 不过时间复杂度用的是amortised, 不好比较。
使用Binomial heap和fibonacci heap实现的话可能需要额外空间。 |
|
z****e
发帖数: 54598 | 16 哪里要那么复杂
针对经度和纬度分别建两个index，查找效率是2*lg(n)复杂度，还可以并行
然后这种互相之间没有任何关联的数据
直接就可以分派出n个任务，然后汇总，reduce后交给客户
所以就解决了scale out的问题，随便分库，每个库自己做好index就可以
所以最后时间复杂度是lg(n)/m，m是分派出来的worker#
这是查找，然后update和insert，这个因为分库了
保证每一个库所伺候的nodes不会太多便可
update/insert的话我没看出有啥问题，做到线性scale没啥问题
index用tree结构比较好，保证update，insert和查找都是o(lg(n))的复杂度
一般mobile app上获取location/coordinates都有很多现成的api
拿到的一般是经度和纬度
最后就是一般社交数据，精度要求都不会太高，跟money transaction不能比
所以不做任何replica都没啥问题
说到底就是，经度和纬度之间没有任何必然联系，这种不做hash比较好
不做的话，直接并行两个threads，一个找经度，一个找纬度，最后汇总
然后找... 阅读全帖 |
|
t********e
发帖数: 1169 | 17 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitbbs59 (bEQi), 信区: JobHunting
标 题: 本版1年以内的所有 面经题目，含帖子link [为大家方便]
发信站: BBS 未名空间站 (Fri Jan 29 14:20:44 2010, 美东)
不敢保证全部涵盖，大部分的都在。
我自己找了一遍，大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了，只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celeb... 阅读全帖 |
|
t********e
发帖数: 1169 | 18 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitbbs59 (bEQi), 信区: JobHunting
标 题: 本版1年以内的所有 面经题目，含帖子link [为大家方便]
发信站: BBS 未名空间站 (Fri Jan 29 14:20:44 2010, 美东)
不敢保证全部涵盖，大部分的都在。
我自己找了一遍，大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了，只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celeb... 阅读全帖 |
|
m**a
发帖数: 1840 | 19 朋友大作，发在知乎。欢迎点赞和转发。
https://www.zhihu.com/question/52732376
美国当地时间11月17日凌晨0点45分，在刚刚结束的3GPP RAN1 87次会议的5G信道编码
方案讨论中，经过艰苦卓绝的努力和万分残酷的竞争，以中国华为公司主推的Polar
Code（极化码）方案，成为5G控制信道eMBB场景编码方案。
编者按
“华为极化码事件”内幕：
极化码获得的并非之前大肆炒作的“短码”。
极化码打败的对手并不是LDPC，而是在控制信道上取代4G现有技术TBCC。
若非极化码最终靠非技术手腕挤进控制信道，华为投资几十亿的5G“三神器”在5G NR
第一阶段业已全部打水漂。
整个5G信道编码又经历一番怎样波澜壮阔的争斗，这背后又隐藏着多少暗流汹涌的阴谋
诡计。“为极解密” 为您最全方位的解析。
为极解密
作者：见南山
第一章 极之澄清
第一章 第一节 5G到底哪一部分码会考虑使用极化码？
第一章 第二节 极化码在长码上真的是几票惜败于LDPC么？
第一章 第三节 5G NR 极化码到底打败了谁？
第二章 极化之源
第二章 第一节 前5G -- 毫... 阅读全帖 |
|
N******G
发帖数: 33 | 20 首先，需要一个缓存存最近10分钟的访问，即（user id， timestamp）pair，这是一
个滑动窗口，时间复杂度和读入一样，空间复杂度取决于最繁忙10分钟有多少访问
然后，建一个map，key是user id，value是这个user id最近10分钟的访问次数。读入
新访问，则对应value +1， 然后处理已经过期的访问（>10分钟），将对应value -1。
每次读入均摊时间复杂度O(1)。空间复杂度=不同user个数。当然如果删除value=0的
map，空间复杂度=max(所有连续10分钟里出现不同user id的个数) |
|
w*********g
发帖数: 30882 | 21 丰田一绝 - 28万行代码竟有1万多全局变量，庞大的bug培养基地
来源: 日理万机 于 2013-11-07 05:22:57 [档案] [博客] [旧帖] [给我悄悄话] 本文
已被阅读：249次 字体：调大/调小/重置 | 加入书签 | 打印 | 所有跟帖 | 加跟贴 |
查看当前最热讨论主题
More Sharing Services
转贴自：http://club.tgfcer.com/thread-6817371-1-1.html 网友Kuzuryuusen的文章
抗日的理论基础 -事后诸葛-
----------------------------
【第一部分】背景简介
前几年闹得沸沸扬扬的丰田刹不住事件最近又有新进展。十月底俄克拉荷马的一次庭审
，2007年一辆2005年凯美瑞暴冲（Unintended Acceleration，UA）致一死一伤事件中
丰田被判有责。引起广泛关注的是庭审中主要证人Michael Barr的证词让陪审团同意丰
田的动力系统软件存在巨大漏洞可能导致此类事件。这是丰田在同类事件中第一次被判
有责。庭审过后丰田马上同意支付300万美元进入调解程... 阅读全帖 |
|
s*****e
发帖数: 16824 | 22 复杂度上去了以后就是质变，因为你电脑的提升是有极限的。举个例子来说，当年下赢
卡斯帕洛夫，用的是深蓝服务器，当时最快的服务器之一。现在随便弄个强一点的家用
电脑就足够对付人类最强棋手了。这就是因为电脑速度提升加上国象软件优化了。中国
象棋复杂度跟国象差不多，所以目前也是一台普通电脑就够了。将棋的复杂度比国象，
中象高20个数量级，现在要对付还不是最厉害的职业棋手，需要600台机器联网计算才
行。而围棋的复杂度比将棋高100个数量级，就算把全地球的每一个原子都换成一台计
算机，然后把这些计算机全联网，仍然不够下赢职业棋手的。这就是量变产生质变，国
象乃至将棋是现有计算能力可解的问题，围棋不是，而且如果没有什么新的算法出来的
话，未来也看不到可解的希望。 |
|
n********d
发帖数: 7676 | 23 量子通信之不负责任科普
首先，量子通信分广义和狭义。广义是用纠缠态光子来做信息载体，就好像无线通信通
过无线波传信息，光通信通过光（一般是激光）传信息。广义量子通信有很玄的部分，
比如teleportation，就是说纠缠光子在无限远距离可以传送状态，近似于心灵感应。
这个理论上靠不靠谱咱不说，咱不搞物理，但是这个离实际应用似乎还有若干光年的距
离，所以这里咱不拿这个说事。好吧，如果你是物理专家，觉得这个很靠谱，很快就能
用来传hello world。那就不用往下看了。
那么不谈这个teleportation，就说说单光子的的传送吧。这个和心灵感应不同，是需
要发送光子到接收端的。这个大家都能接受，对吧？现在的量子通信是怎么做的呢？光
子是波啊，有波就有振动方向啊。这个方向在传输过程中如果不受干扰是不变的。物理
名词叫偏振态。接收端用一个偏振镜，你就想象成一个细缝吧。那么这个细缝的方向和
这个波的偏振方向是一致的话，这个光子就可以被接收到了。接收端的偏振片是要转动
的，转一个角度收一个光子。很简单吧。别被纠缠态啥的名词忽悠了，激光通信里偏振
态是一个研究很多的问题，不同偏振态的光子在介... 阅读全帖 |
|
发帖数: 1 | 24 【 以下文字转载自 JobHunting 讨论区 】
发信人: apprentice00 (数学学徒), 信区: JobHunting
标 题: Didi labs糟糕的面试经历
发信站: BBS 未名空间站 (Wed May 16 15:11:49 2018, 美东)
interviewer的名字叫 Xusheng Sun
非常糟糕 不仅粗鲁无礼 喜欢抢话插话 而且技术很差 脑子不够用
按照约定的时间晚了很多 面试时间本来就不长 晚了既不解释也不道歉
问题问不到点子上 说个什么半天反应不过来
宝贵的面试时间竟然当场用来看我的简历 还看了很长时间 我还得保持安静让他把我的
简历看完 作为面试人 你早干什么去了
不停打断我说话 不停用很傻的 自以为有道理的问题challenge我 解释了他为什么是错
的 还是不停的put words into my mouth
（问题是serialize 的serialize 二叉树） 我说用level order traverse 他说指数复
杂度 必须用别的顺序的方式遍历
我解释复杂度是节点数目的线性函数 硬说是指数复杂度 也是树的高度的指数 但是... 阅读全帖 |
|
发帖数: 1 | 25 【 以下文字转载自 JobHunting 讨论区 】
发信人: apprentice00 (数学学徒), 信区: JobHunting
标 题: Didi labs糟糕的面试经历
发信站: BBS 未名空间站 (Wed May 16 15:11:49 2018, 美东)
interviewer的名字叫 Xusheng Sun
非常糟糕 不仅粗鲁无礼 喜欢抢话插话 而且技术很差 脑子不够用
按照约定的时间晚了很多 面试时间本来就不长 晚了既不解释也不道歉
问题问不到点子上 说个什么半天反应不过来
宝贵的面试时间竟然当场用来看我的简历 还看了很长时间 我还得保持安静让他把我的
简历看完 作为面试人 你早干什么去了
不停打断我说话 不停用很傻的 自以为有道理的问题challenge我 解释了他为什么是错
的 还是不停的put words into my mouth
（问题是serialize 的serialize 二叉树） 我说用level order traverse 他说指数复
杂度 必须用别的顺序的方式遍历
我解释复杂度是节点数目的线性函数 硬说是指数复杂度 也是树的高度的指数 但是... 阅读全帖 |
|
c****3
发帖数: 10787 | 26 SHA家族的五个算法，分别是SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512，由美国
国家安全局（NSA）所设计，并由美国国家标准与技术研究院（NIST）发布
SHA-0破解
2004年8月17日，在CRYPTO 2004的Rump会议上，王小云，冯登国、来学嘉，和于红波宣
布了攻击MD5、SHA-0 和其他杂凑函数的初步结果。他们攻击SHA-0的计算复杂度是2的
40次方，这意味着他们的攻击成果比Joux还有其他人所做的更好。请参见MD5 安全性。
2005年二月，王小云和殷益群、于红波再度发表了对SHA-0破密的算法，可在2的39次方
的计算复杂度内就找到碰撞。
SHA-1破解
鉴于SHA-0的破密成果，专家们建议那些计划利用SHA-1实作密码系统的人们也应重新考
虑。在2004年CRYPTO会议结果公布之后，NIST即宣布他们将逐渐减少使用SHA-1，改以
SHA-2取而代之。
2005年，Rijmen和Oswald发表了对SHA-1较弱版本（53次的加密循环而非80次）的攻击
：在2的80次方的计算复杂度之内找到碰撞。
2005年二月，王小云、殷益群... 阅读全帖 |
|
c****3
发帖数: 10787 | 27 SHA家族的五个算法，分别是SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512，由美国
国家安全局（NSA）所设计，并由美国国家标准与技术研究院（NIST）发布
SHA-0破解
2004年8月17日，在CRYPTO 2004的Rump会议上，王小云，冯登国、来学嘉，和于红波宣
布了攻击MD5、SHA-0 和其他杂凑函数的初步结果。他们攻击SHA-0的计算复杂度是2的
40次方，这意味着他们的攻击成果比Joux还有其他人所做的更好。请参见MD5 安全性。
2005年二月，王小云和殷益群、于红波再度发表了对SHA-0破密的算法，可在2的39次方
的计算复杂度内就找到碰撞。
SHA-1破解
鉴于SHA-0的破密成果，专家们建议那些计划利用SHA-1实作密码系统的人们也应重新考
虑。在2004年CRYPTO会议结果公布之后，NIST即宣布他们将逐渐减少使用SHA-1，改以
SHA-2取而代之。
2005年，Rijmen和Oswald发表了对SHA-1较弱版本（53次的加密循环而非80次）的攻击
：在2的80次方的计算复杂度之内找到碰撞。
2005年二月，王小云、殷益群... 阅读全帖 |
|
j*********n
发帖数: 6034 | 28 【 以下文字转载自 Auto_Fans 俱乐部 】
发信人: andrews (旱鸭子), 信区: Auto_Fans
标 题: 丰田工程师真的该枪毙啊
发信站: BBS 未名空间站 (Sun Nov 3 00:14:23 2013, 美东)
看下面的这文章，我是无语了……
以前不知道什么是＂在看不到的地方偷工减料＂， 这回见识了。 以后不敢买丰田车了
转贴自：http://club.tgfcer.com/thread-6817371-1-1.html 网友Kuzuryuusen的文章
----------------------------
【第一部分】背景简介
前几年闹得沸沸扬扬的丰田刹不住事件最近又有新进展。十月底俄克拉荷马的一次庭审
，2007年一辆2005年凯美瑞暴冲（Unintended Acceleration，UA）致一死一伤事件中
丰田被判有责。引起广泛关注的是庭审中主要证人Michael Barr的证词让陪审团同意丰
田的动力系统软件存在巨大漏洞可能导致此类事件。这是丰田在同类事件中第一次被判
有责。庭审过后丰田马上同意支付300万美元进入调解程序。
出于好奇，... 阅读全帖 |
|
r****o
发帖数: 1950 | 29 大家看看我的想法对不?
可以模仿merge sort,先考虑N为偶数的情况
设这N列为c1,c2,...,cN
将c1和c2, c3和c4, ..., c_{N-1}和cN 两两 merge成一个长2N的列，设为d1,d2,...d_{N/2}
然后再将d1和d2,d3和d4,...,d{N/2-1}和d{N/2}两两merge成一个长4N的列，
如此反复merge,直到最后剩下两个长N*N/2的列，用binary search可找到median。
时间复杂度，O(N)+O(2N)+...+O(N*N/2)+O(2lgN)=O(N^2 lgN).
空间复杂度O(N^2).
当N为奇数时，可将最中间那列先空着，当左右两边都merge成了长(N-1)N/2的列后，再merge成一个长(N-1)N的大列，然后问题可归结为一个长(N-1)N的列和一个长N的列，都排好序，找median的问题。
时间复杂度和空间复杂度应该和偶数时一样。 |
|
p*u
发帖数: 136 | 30 这个问题是有解的。不过面试考这样的题，太不厚道了，完全是超出能力范围的题目。
这是TAOCP上的一个练习题，有一篇196x年的论文专门给了解法的。
基本思想是把数组分成 sqrt(n + m) 这样的块，然后重复利用空间。
1，前n个数有序，后m个数有序。把前n个数和后m个数，分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
2，把前n个数的块和后m个数的块，做merge，用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
3，对于作为swap空间的最后一个块，直接做冒泡排序。时间复杂度O(n + m)，空间复杂度是O(1)的。
大致思想是上面这样的，具体细节我也记不清楚了。可以看看TAOCP，上面有习题解答。 |
|
h**6
发帖数: 4160 | 31 沿着对角线遍历一次，复杂度仍然是O(N^2)。因为每条对角线都只需要寻找比以前更大
的边长，也就是更大的B1、B2值。虽然遍历单条对角线复杂度是O(N^2)，但对角线的值
都是相关的，因此遍历全部对角线的复杂度也是O(N^2)。
通过运行时间也能看出来，同样是10000*10000的矩阵：
剪枝之前，O(n^2logn)算法耗时96.406秒，O(n^3)算法耗时1263.265秒。
剪枝之后，两个算法运行时间分别为10.156秒和9.375秒。此时复杂度相同，前一个算法因较复杂开销更大故更慢。 |
|
h**6
发帖数: 4160 | 32 楼上的代码好像仍然不是很对，这是两个版本的代码，假设a已排序。
由于a排序需要额外的复杂度，因此两个版本的复杂度差别不是很大。
逐个查找，O(M)，总复杂度O(MlogM+MlogN)
bool findelements(int* a, int M, int K, int x)
{
int prev = a[0];
int count = 1;
for(int i=1; i
{
if(a[i] >= prev+x)
{
count++;
prev = a[i];
}
}
return count>=K;
}
二分查找，O(KlogM)，总复杂度O(MlogM+KlogMlogN)
bool findelements(int* a, int M, int K, int x)
{
int* prev = a;
for(int i=1; i
{
int* curr = lower |
|
h**6
发帖数: 4160 | 33 本题有三种方法可以解答：
1.直接筛选法：
for(int m=0; m<(1<
{
for(int x=0; x<=m; x++)
{
if((x^(m-x)) == m)
cout<
}
}
对于每一个固定的m，循环次数为 m+1 次，总循环次数为 2^(2n-1)+2^(n-1)，复杂度
为 O(2^(2n)) 或 O(4^n)。
2.按位枚举法：
int* one = new int[n];
for(int m=0; m<(1<
{
int mask = 1, k = 0;
for(int i=0; i
{
if(m & mask)
one[k++] = mask;
mask <<= 1;
}
for(int i=0; i<(1<
{
int mask2 = 1, x = 0;
for(int ... 阅读全帖 |
|
t**********n
发帖数: 145 | 34 找工作这段时间以来常匿名浏览，在版上获益良多。不久前刚拿到A公司的Offer，特地
注册了账号，呈上面经，以感谢各位xdjm。
先说一下我的背景，国内CS硕士，毕业后在国内做了三年startup。去年10月搬家到西
雅图，11月初开始撒简历，没有什么reference，直接网投。就在投简历到A公司网站上
之后一个礼拜不到就有recruiter发来email说邀请电面。BTW，至今其他投递的简历没
有一个有音讯的，回想起来感觉很lucky，另外说明A公司直接网投是有用的。
因为自己的背景，所以apply主要是SDE/AJAX/front-end的position。其实这类
position的面经在上网还挺少的，所以希望我的面试经过可以给大家提供这方面的参考。
面的过程一共是3轮phone interview和2轮on-site，其中一次是8个session，另一次是
3个session，面的比较多，可能是因为有2个team都感兴趣的关系。
整理了一下印象比较深的问题有以下这些：
========比较Personal的一些问题========
1）简单介绍自己。每个interviewer必... 阅读全帖 |
|
g**u
发帖数: 583 | 35
假设该元素不在BST中，首先找到最后一个比该元素小的节点，然后找到第一个比该元素大的节点，返回2个节点中离目标最近的节点。
下面是实现，等待拍砖。
node * findClose(node *root, int value)
{
if(!root)
return NULL;
node * smaller=findLastSmaller(root, value);
node * greater=findFirstGrearer(root, value);
//we will also need to check both of smaller and greater are not NULL
return value-smaller->value< greater->value - value?smaller:greater;
}
node * findLastSmaller(node * root, int value)
{
if(!root)
return NULL;
node * result=NULL;
while... 阅读全帖 |
|
J*********n
发帖数: 370 | 36 来自主题: JobHunting版 - 请教一道题 之前的遇到过的一道面试题，还是用skype面试的，感觉很别扭。当时因为前面被问了
很多data mining的问题，答得不好，到时后面有点乱套了，代码还没写完时间就到了，
结果就挂了。。。。
从log文件里找出访问次数最多的10个url,经典的做法是用hashtable算出每个url访问
的次数，然后遍历hashtable中的每个url，用minHeap找出最大的十个。时间复杂度为O
(n+mlog10), n为log里url的数目，m为distinct url的数目，空间复杂度为O(m), 如果
扩展到最多的k个url，时间复杂度就是O(n+mlogk), 空间不变(因为k超过了m的话只能
返回m个url)。
如果有更好的解法可以把时间或者空间复杂度降下来，还望不吝赐教，多谢！ |
|
i**********e
发帖数: 1145 | 37 Credits to adjlist for the following proof. This is a proof that printing
all possible combinations has the worst case complexity of O(N^3). However,
for printing any one of the combination, O(N^2) is possible by using extra
space (hash all possible pair-sums to a table).
这是详细证明--4sum(找全所有可能解)最坏情况下算法复杂度至少是O(N^3) ---
考虑下面的测试用例：
[1，2，3，4，5，...,n,
-1,-2,-3,...,-n-(n-1)-(n-2) ],target=0
从1,2,3,..,n里任意取三数，和都小于或等于n+(n-1)+(n-2). 也就是说这里面任意三
个正数都能匹配一个负数，使得和为0。i.e.这儿至少有n(n-1)(n-2)种不同的元素组合
其和为target.
结论： 对... 阅读全帖 |
|
i**********e
发帖数: 1145 | 38 Credits to adjlist for the following proof. This is a proof that printing
all possible combinations has the worst case complexity of O(N^3). However,
for printing any one of the combination, O(N^2) is possible by using extra
space (hash all possible pair-sums to a table).
这是详细证明--4sum(找全所有可能解)最坏情况下算法复杂度至少是O(N^3) ---
考虑下面的测试用例：
[1，2，3，4，5，...,n,
-1,-2,-3,...,-n-(n-1)-(n-2) ],target=0
从1,2,3,..,n里任意取三数，和都小于或等于n+(n-1)+(n-2). 也就是说这里面任意三
个正数都能匹配一个负数，使得和为0。i.e.这儿至少有n(n-1)(n-2)种不同的元素组合
其和为target.
结论： 对... 阅读全帖 |
|
i*********7
发帖数: 348 | 39 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
母，但是变出来的都是valid word。
例子：head->heal->teal->tell->tall->tail
给你一个input和target，判断input能不能到达target。
说算法复杂度。
第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
第三个面试官：求平方根。不能用牛顿迭代法。
第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
栈）
第五个面试官：估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
栈的具体运作是怎样的？
忘了说了，这题还有一个follow up：
如果让你设计编译器的栈，你怎么设计？
第二，先写一个mergesort。
然后问你算法复杂度，但是有条件：假如你每访问一个整型数的算法复杂度为o(a)，总
的算法复杂度... 阅读全帖 |
|
i*********7
发帖数: 348 | 40 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
母，但是变出来的都是valid word。
例子：head->heal->teal->tell->tall->tail
给你一个input和target，判断input能不能到达target。
说算法复杂度。
第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
第三个面试官：求平方根。不能用牛顿迭代法。
第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
栈）
第五个面试官：估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
栈的具体运作是怎样的？
忘了说了，这题还有一个follow up：
如果让你设计编译器的栈，你怎么设计？
第二，先写一个mergesort。
然后问你算法复杂度，但是有条件：假如你每访问一个整型数的算法复杂度为o(a)，总
的算法复杂度... 阅读全帖 |
|
d**s
发帖数: 98 | 41 非常规的解法：
http://blog.csdn.net/anchor89/article/details/6055412
经典面试题:设计包含min函数的栈,O(1)空间实现方法
分类： 数据结构和算法 2010-12-04 22:20 2102人阅读 评论(10) 收藏 举报
题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数
min、push以及pop的时间复杂度都是O(1)。
注:这是06年一道Google的面试题.
先来说个常规解和他的一个优化,常规解的时间复杂度符合要求,但需要线性的额外空间.
常规解(参考 http://zhedahht.blog.163.com/blog/static/25411174200712895228171/):
除了题目要求的栈之外新开一个栈,用来记录最小值,每当在原栈中push数据后,与最小
值栈中的栈顶元素比较,如果新值较小,则在最小值栈中push新值;否则再次push栈顶元
素.
pop的时候,只要将最小值栈也pop一下就行了.
这样,min函数只需要返回最小值栈的栈顶元素即可.
常规解空间上的一个优化:
一般... 阅读全帖 |
|
d*********g
发帖数: 154 | 42
首先，当k=4的时候，正确答案不应该是第[2][0]个元素么？还是说你的k是从0开始取
的？如果k从0开始取的，那k=4的时候正确答案是第[1][1]个元素。那么这个时候需要
做5次堆操作，也就是O((k+1)*log(row length))。为了方便，认为k是从1开始取的吧
，也就是说k=1时需要找最小的元素。这个时候取第k个元素的复杂度是O(k*log(row
length)).
你给的O(column length * \log(row length)) 没有一般性吧？取第k个元素与是否遍
历某一列没有必然联系。
当k是median的时候，自然复杂度就是O(mn/2 * log(row length))了，但是这不妨碍
O(k*log(row length)) 的正确性啊，因为这时k就等于 mn/2。所以说取得第k个元素
的复杂度是O(k*log(row length))没有问题吧？这个复杂度的逻辑其实很好想啊，要取
第k个元素，就要进行k次堆操作；每进行一次对操作就要log(row length)的时间。 |
|
f*********d
发帖数: 140 | 43 补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
包子！
===============================================
Oct.19th ，东部时间1:30， 一面，印度a3
1，为什么基于比较的排序问题复杂度下界是O(nlogn)
回答出来了，他表示赞同
2，分析下面递归算法的复杂度
Alg(array, size)
split -> A1, A2, A3.... O(n)
Alg(A1, size/3)
Alg(A2, size/3)
这个题目是硬伤，他push我快快快，我一紧张，递归函数没有写好， 写出来之后
说用主定理，再一紧张把 a 和 b搞反了。。。
F(n) = a * F(1/b n) + O(n)
总的来说这题做错了
3， 大数据的平方 X^2 X很长 不能用int long 之内的表示
一开始就反应时Divide and Conque， 他表示赞同， 但是我始终没有到NlogN, 只
到了N... 阅读全帖 |
|
j*****y
发帖数: 1071 | 44 一面的第三题一般是可以做到 n^(log3) 吧？
比如 算 A * A where A is n digits number
A = B * 10^(n / 2) + C
A * A = B * B * 10^n + 2 * B*C * 10(n / 2) + C * C
need to compute B * B, B * C and C * C
So we compute three items below:
(B+C) * (B+ C) = B*B + 2*B*C + C*C
B*B
C*C
from which we can get 2*B*C = (B+C) * (B + C) - B*B - C*C
let the time for A^2 is T(n)
so we have T(n) = 3 T(n/2) + O(n)
and T(n) = O(n^(log3)
这里假设两个 n digits number的求和需要 O(n)的时间
补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
包子！
=======================... 阅读全帖 |
|
S**I
发帖数: 15689 | 45 ☆─────────────────────────────────────☆
bailngw (bailing) 于 (Tue Apr 10 12:32:15 2012, 美东) 提到:
昨天居然又被问到了：
屋子里有n个人，如果i 认识 j, 那么他们之间有条directed edge. 如果有这么一个人
：大家都认识他，但他不认识其他任何人，我们叫他celebrity.
如果在O(n)时间找出celebrity?
谢谢
☆─────────────────────────────────────☆
longway2008 (longway2008) 于 (Tue Apr 10 12:39:51 2012, 美东) 提到:
DFS ?
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Apr 10 12:39:58 2012, 美东) 提到:
建个图之有入没有出就是了
昨天居然又被问到了：屋子里有n个人，如果i 认识 j, 那么他们之间有条directed
edge... 阅读全帖 |
|
a********3
发帖数: 228 | 46 T家的第一面，我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次
得来的。。。
题目是关于9位SSN号的随机分配和回收，实现下面两个函数。
SSN assignRandom()
//分配新的随机号。should randomly return an unassigned SSN and should make
this number unavailable for future assignRandom() calls
void release(SSN)
//回收一个随机号。should make the given SSN available for future
assignRandom() calls.
SSNs are in the range : [100000000 - 999999999]
实现assignRandom函数时，如果连续调用rand()函数直到找到一个unassigned，时间复
杂度最坏就可能是O(n)。我实现的是分别维护assigned和unassigned两个集合，
unassigned的集合用BST index，assignRa... 阅读全帖 |
|
a********3
发帖数: 228 | 47 T家的第一面，我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次
得来的。。。
题目是关于9位SSN号的随机分配和回收，实现下面两个函数。
SSN assignRandom()
//分配新的随机号。should randomly return an unassigned SSN and should make
this number unavailable for future assignRandom() calls
void release(SSN)
//回收一个随机号。should make the given SSN available for future
assignRandom() calls.
SSNs are in the range : [100000000 - 999999999]
实现assignRandom函数时，如果连续调用rand()函数直到找到一个unassigned，时间复
杂度最坏就可能是O(n)。我实现的是分别维护assigned和unassigned两个集合，
unassigned的集合用BST index，assignRa... 阅读全帖 |
|
w****a
发帖数: 710 | 48 背景：新鲜小硕，申的是2013北美new grads，SDE
地点：都柏林office
没签nda，直接放送了。坐等拒信，明年再来。
第一轮：
写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
需要描述详细时空复杂度，最好情况最坏情况和平均情况。
第二轮：
第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
开始他都没看懂。中间出了一点点小问题，但是改对了。因为我没考虑到1这个情况，4
的0次方是1。太粗心了。然后他让我别用hash_set，用普通方法做一个。我就写了个循
环的方法。循环的方法倒是一次性bug free了。pow4伺候完就开始第二题了。
最短路径那个时间不够了没做完。 不过没做完他倒是没说啥因为开始做这题的时候已
经就剩下10分钟了，他说没做完没事，讲下思路就行。我就没怎么花心思在code上，重
点讲了BFS，画了图给他描述了... 阅读全帖 |
|
w****a
发帖数: 710 | 49 背景：新鲜小硕，申的是2013北美new grads，SDE
地点：都柏林office
没签nda，直接放送了。坐等拒信，明年再来。
第一轮：
写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
需要描述详细时空复杂度，最好情况最坏情况和平均情况。
第二轮：
第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
开始他都没看懂。中间出了一点点小问题，但是改对了。因为我没考虑到1这个情况，4
的0次方是1。太粗心了。然后他让我别用hash_set，用普通方法做一个。我就写了个循
环的方法。循环的方法倒是一次性bug free了。pow4伺候完就开始第二题了。
最短路径那个时间不够了没做完。 不过没做完他倒是没说啥因为开始做这题的时候已
经就剩下10分钟了，他说没做完没事，讲下思路就行。我就没怎么花心思在code上，重
点讲了BFS，画了图给他描述了... 阅读全帖 |
|
n*******w
发帖数: 687 | 50 最大的case是range（25000, 0，-1），就是25000 ~ 1
其实应该包含另一种极端情况，就是25000个元素全是1
比较了两个方向的DP，发现了一点有意思的地方。
DP的方向是可能影响复杂度的。
方法1
如果递归式从后往前写，在 i 位置前面顺序判断任意一个位置能不能到i
那么如果数组里边的数字都很大，甚至达到O(n)的话，复杂度是O(n)
如果数组里边数字都很小，比如全是1，那么复杂度变成O(n^2)
方法2
递归式从前往后写，在i位置判断i往后能达到的任意一个位置。
复杂度刚好相反。
做了一些testing，假设数组大小n=10000
数组里边元素全是k，哪个更快，时间单位是ms，那个true表示两行种方法结果相同
方法2 方法1
k= 1 True 34.02304649353027 6190.130949020386
k= 8 True 43.0300235748291 ... 阅读全帖 |
|
