c**********y
发帖数: 38 | 1 同样的一个题，比如说wordbreakII，都是n的平方的复杂度，C++是40ms，java是469ms
，好多别的题目也是这样
oj是怎么判定时间复杂度是否超标的？
看时间不科学吧？时间复杂度跟语言没关系，同样的算法不能换个语言就不通过了吧，
还是每个submission都要跑几个数量级递增的testcase然后比较曲线？这样貌似又太慢。
元芳，你怎么看咧？ |
|
u*****n
发帖数: 126 | 2 在他们家遇到了两个傻B阿三。一个不停的纠正我的逗号和分号，另外一个给的hints都
是废话。最后挂了。他们家的阿三是我面过的所有公司中最极品的。所以面试他们家要
小心傻B阿三。当然他们家的华人美女HR相当的nice，是我遇到的所有HR中最nice的。
总共面了四轮：
第一轮：定义buddy system为一棵complete binary tree。一个node可能为0也可能为1
. 它的
value为1，当且仅当它所有的child的value均为1.
1
|
1 2
| |
1 2 3 4
| | | |
1 2 3 4 5 6 7 8
实现下列的method。
1' clearBit(int offset, int len);
2' setBit(int offset, int len);
第二轮：设计一个task dispatching system，里面有一个task queue和两个function。
1’ trigger。这个func... 阅读全帖 |
|
u*****n
发帖数: 126 | 3 在他们家遇到了两个傻B阿三。一个不停的纠正我的逗号和分号，另外一个给的hints都
是废话。最后挂了。他们家的阿三是我面过的所有公司中最极品的。所以面试他们家要
小心傻B阿三。当然他们家的华人美女HR相当的nice，是我遇到的所有HR中最nice的。
总共面了四轮：
第一轮：定义buddy system为一棵complete binary tree。一个node可能为0也可能为1
. 它的
value为1，当且仅当它所有的child的value均为1.
1
|
1 2
| |
1 2 3 4
| | | |
1 2 3 4 5 6 7 8
实现下列的method。
1' clearBit(int offset, int len);
2' setBit(int offset, int len);
第二轮：设计一个task dispatching system，里面有一个task queue和两个function。
1’ trigger。这个func... 阅读全帖 |
|
u*****n
发帖数: 126 | 4 抱歉没仔细看你的解法。很好的思路。
原题的解法类似，只不过题目本身比较特殊，完整的题目如下。因为是整数，你可以假
设有很大的内存，同时不必考虑collision。
设计一个Map，满足下面的时间复杂度。
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
提示：
如果我们用randomly accessed array，复杂度如下：
add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate:
O(size of array)
如果我么用sequential array, 复杂度如下：
add: O(1) deletion: O(number of elements) lookup:O(number of elements)
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起... 阅读全帖 |
|
u*****n
发帖数: 126 | 5 抱歉没仔细看你的解法。很好的思路。
原题的解法类似，只不过题目本身比较特殊，完整的题目如下。因为是整数，你可以假
设有很大的内存，同时不必考虑collision。
设计一个Map，满足下面的时间复杂度。
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
提示：
如果我们用randomly accessed array，复杂度如下：
add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate:
O(size of array)
如果我么用sequential array, 复杂度如下：
add: O(1) deletion: O(number of elements) lookup:O(number of elements)
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起... 阅读全帖 |
|
z****e
发帖数: 54598 | 6 data modelling这种课，教什么er图这些，这个现在都给information system专业去上了
很多女孩子学这个，尤其印度女的喜欢读这个，他们出来直接找ba的工作
但是statistical modelling这种东西，一般至少也是master以上
而且本科最好学过统计线性代数这些，还有算法
不过算法在统计面前，你就可以感觉出来差别
大部分难点都是统计，而不是算法，甚至本科学的那些算法，真心不难，远不如统计顶用
因为面对无结构，或者结构混乱的数据，复杂度计算其实派不上太大用场
因为无结构要变成有意义的数据是从无到有的一个过程，这是最难的
统计工具尤其擅长把没有任何意义的东西变成有意义，make sense，统计用来做这个
算法复杂度是优化，从100000000到<10，这个难度下降很多，这就跟老张那个证明一样
老张的证明牛逼就牛逼在，他证明了从无限到有限，虽然这个有限很大
离最后2的距离还有点远
但是毕竟有限之内，比起无限到有限，一般来说，会容易很多
不过因为是cs课，所以有时候统计modelling也叫算法
反正互相换，哪个单词牛逼就用哪个
说到底，最后都难在数学上... 阅读全帖 |
|
z**a
发帖数: 69 | 7 已跪，回想我的这次onsite经历，那就是一个joke啊，浪费了我的时间，也浪费了面试
官的时间。还浪费了我一天PTO飞过去。
第一轮，关键词，无厘头。开始先各自寒暄了几句，天真的我没有想到后来的尴尬。第
一个问题是：“如果有一个大文件，只有小写的（关键）的a-z（关键），那么怎么压
缩这个文件呢？”我是最近看大数据的东西看得有点太投入了，上来就说把文件分段，
hash每段，有个server专门存内容，bla，bla…，他问，那怎么恢复呢，我说每个文件
最后表现为一串hash key，恢复的时候按hash key找到存放的位置就行了。他没说啥，
我意识到这不是他想要答案，不过我最后才意识到这其实都不是想要问的问题。。。为
了引导我，他举了个例子说比如：abcd…z重复了一百遍。这你怎么存呢？当时我有点
懵了，我说：”这不就是存个abcd…z，然后存个100不就得了？”，他又问还有“怎么
恢复“，我老实点的说：”有多少遍，恢复的时候写多少被“. 他接着说：”abcd…z
100遍不是连续的呢？“我以为他说的是先50遍在这，后50遍在那，虽然我现在感觉有
点地方不对劲了，也只有硬着头皮说，... 阅读全帖 |
|
w**s
发帖数: 8 | 8 贡献电面 (F)
尽点微薄之力，祝大家（包括我自己）找工作顺利！一起加油！
========================================================================
阿三 男
1. 轮流介绍背景
2. 为何F,来了想干啥
3. 输入一字符串，输出一最长重复串 (比如AxyxyxA中xyx就是), 分析一般复杂度及最
坏情况下复杂度
4.（后缀词排序？）输入一字符串s，输出一整数组A。复杂度分析。
输入：s = "zxy"
0: zxy
1: xy
2: y
输出：[1,2,0]
5. 提问环节
方法：两题都直接暴力之，每题到最后都被阿三叫停说可以了，不用编了。
反馈：三小时后通知onsite。
======================================================================== |
|
h*******e
发帖数: 1377 | 9 楼主的面试官要改变关于什么的复杂度啊，5 ^4 才６２５ 不到０．０１秒就算完
了如果字典是o(1) 查询的话 也不大阿，是要改善 关于 每个字符的可能字母数5 的
复杂度 还是要改善关于单词长度４的复杂度啊，楼主问了没有啊？
) |
|
w*****z
发帖数: 1 | 10 我觉得复杂度还是挺高的。搜所有可能单词的话，所有方案数是C(26,5)^4，你说的5*5
*5*5只是一种方案中所有可能的单词个数。这里需要遍历所有方案找出最好的。
如果按词典搜的话，每个词取或不取，最坏情况时间复杂度是O(2^n)，n是词典的单词
个数。当然其中可以减掉很多枝。
所以我觉得时间复杂度还是挺高的。不知道我是不是有什么地方没想到，不吝赐教。谢
谢。
， |
|
o****s
发帖数: 143 | 11 上周onsite的，昨天刚接到电话，悲剧了~~ ，还是有些失落，上来为以后面试求求
bless，顺便说下经过， 签了nda，题目不太好多说，一共5轮：
第一轮：2道coding，问复杂度， 1道design，coding不难
第二轮：1道有关图的题，我给了个解，然后要降低复杂度，又给了一个，然后没时间
，就没写code，面试官说，that should work
第三轮：给了用数组表示的树的题，2问，第一问答得可以，第二问脑袋发晕，程序木
有写完。。。。
第四轮: 一个dp题，中间一个corner case没有考虑，给了个hint，后来做出来
第五轮：聊了点简历，然后做题，我给了个答案，对方让降低复杂度，想到了heap，但
是没完全想通
本来想在google买件纪念品的，结果貌似一定要让employee陪着才能买。。。。
大家加油！ |
|
b******i
发帖数: 914 | 12 来自主题: JobHunting版 - 问G家一题 给一个array of int，以及一个range (low, high)，找出array中所有的continuos
subsequence使得这个subsequence的和在range之中。
这题一个常规做法就是用一个数组f[n]来存array[0..n-1]的和，然后可以在O(1)时间
内算出任意continuous subsequence的和。再枚举所有的subsequence，和range比较。
这样时间复杂度是O(N^2)，空间复杂度是O(N)
请问有没有更简单的方法呢？不过感觉要找出“所有”的subsequence，隐含就应该是
至少是O(N^2)的复杂度 |
|
|
a*********2
发帖数: 187 | 14 原来的面经是:
*****************************************************
设计一个Map，满足下面的复杂度。
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
提示：
如果我们用randomly accessed array，复杂度如下：
add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate:
O(size of array)
如果我么用sequential array, 复杂度如下：
add: O(1) deletion: O(number of elements) lookup:O(number of elements)
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起来。
*******************... 阅读全帖 |
|
r****7
发帖数: 2282 | 15 小小的打击一下啊。。。我觉得你答的不算好
2. onsite
一面：中东人，题目：输入为一个文件，每一行格式：下级名字，上司名字。
输出：
>A
>>A的下级B的名字
>>>B的下级C的名字
>>A的下级D的名字
...
我的方法：
>> 先建树，然后用inorder遍历树，将层序输出。代码写了近100行。
typo? 这个怎么看也是preorder啊
二面：国人大哥（英语很正，可能是ABC），人很nice。题目：输入：word字典，一个
string。输出：string是否可以由字典里面的word拼接而成
我的方法：先说的搜索的方法，然后让我先实现。实现之后，我说可以加入剪枝，加入
到代码里。并且说这样的话复杂度是O(N^2)的。后面和朋友聊，此题用DP也能解，也是
O(N^2)
这个用trie的话，应该就是O(N + 字典size)的复杂度，所以depends on字典有多大
三面：可能是版上有人说的ABC。题目：给一个二维平面上的点集，需要找一个点（不
是点集里面的点），使得其到所有点的曼哈顿距离之和最小。
我的方法：所有的点的X坐标找中间值，所有的点的Y坐标找中间值（如果点数是... 阅读全帖 |
|
r*******e
发帖数: 340 | 16 时间复杂度的问题,
假设 共有N层楼梯， 鸡蛋在T层及以上会碎
你的方法类似binary search
需要lgN个鸡蛋， 平均复杂度是 lg(N)
原来的方法需要lgT个鸡蛋，平均复杂度是 sqrt(T) |
|
b*******i
发帖数: 20 | 17 好像很麻烦啊，匆匆想到下面三种解法，抛砖引玉。
1. 暴力求解，时间复杂度至少是O(S^3)，我不确定
找到下面各种矩形
R0 = 相交至少0次的矩形 （就是原来的矩形）
R1 = 相交至少1次的矩形，(就是上一步R0的交集，复杂度O(S^2), 如果为空，就不要
往下算了)
R2 = 相交至少2次的矩形 (就是上一步R1的交集)
...
R(S-1) = 相交至少S-1次的矩形
结果是R0-R1+...
2. 分割矩形， 时间复杂度至少是O(S^2)，我不确定
从1个矩形开始，加入第2个矩形后，如果有相交，记录他们分割的小矩形。
再加入第3个矩形，跟前面的小矩形如果有相交，记录他们分割的小矩形。
...
结果是所有分割后小矩形的面积之和。
3. 另外坐标是整数，离散化方法。 |
|
g******n
发帖数: 10 | 18 你的第二种方法最坏情况下时间复杂度是 O(n^2)，不是 O(n)，因为不是每次都刚好把
数组分成长度相当的两半，最坏情况下两边长度分别是 0 和 n-1，所以 T(n) = T(n-1
) + O(n)，总的时间复杂度是 O(n^2). 另外这种方法也不叫 selection sort，而是
叫做 randomized-select，因为过程跟 randomized-quicksort 的 partition 非常相
似，期望时间复杂度是 O(n)。详细内容可以看 CLRS pp. 215, §9.2
Selection in expected linear time |
|
c********5
发帖数: 26 | 19 我看paper能力不太行，不过看起来data stream里面是无序的，那样的话是要用堆加
count的，只是时间复杂度做不到O(lgn)
这里是有序数组，如果是n/k的话时间复杂度O(klgn)，空间复杂度本来就是O(k)啊
这里这道题比paper里面的简单吧，如果是那道题我应该写不出完整代码的，heapify什
么都没有写过 |
|
x*****0
发帖数: 452 | 20 下面这道题是在版上看到的一道题。请问大家有什么想法吗？
设计一个Map，满足下面的时间复杂度。
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
提示：
如果我们用randomly accessed array，复杂度如下：
add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate:
O(size of array)
如果我么用sequential array, 复杂度如下：
add: O(1) deletion: O(number of elements) lookup:O(number of elements)
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起来。
对于这题的提示，sequential array指的就是link list? 把每一对阅读全帖 |
|
x*****n
发帖数: 195 | 21 5. 打印一个数的所有unique 的factor组合, 这个出现好多次了，例如12: (1, 12), (
2,2,3), (2, 6), (3, 4)重点是follow up 要cut branch降
低复杂度，然后估计复杂度, 标准答案是O(n3)。－L
求教怎么降低复杂度到N^3到。只想到DFS的法子。。。
(1
etc |
|
J*********a
发帖数: 50 | 22 这题看起来和leetcode的Maximal Rectangle 很像，但似乎不可能找到类似的复杂度的
解法。
能想到的solution
1.preprocess：建立一个matrix［］［］存［0］［0］到［i］［j］的sum，这个可以
用dp解决，复杂度O（n^2）
2.check 以每一点为右下点的最大可能的矩阵，这个每个点都是O（i＊lg（j））的复
杂度了吧。除了可以用个binary search来减少一点复杂度，我也想不到别的办法了。 |
|
c*********n
发帖数: 1057 | 23 楼主能不能说下8的解法？还有时间复杂度？这种要递归的怎么分析复杂度我一直不太
会。还有9的复杂度？ |
|
p******o
发帖数: 4 | 24 面试官： 口头叙述的 Merge two sorted list
Me：接口是LinkedList还是Array?
面试官： 每种接口有什么优缺点
Me: 回答这是需求问题，LinkedList不需要临时存储空间
面试官：分析空间复杂度
Me: O（1） and O(n), 继续问需要用什么写Code
面试官：随便
Me: 写了标准实现with class Node {int val, Node next}, merge(Node head1, Node
head2)
面试官：为什么自定义Node class, 不用java.util.LinkedList?
Me: ... (这个真没仔细想过，胡乱答的)
面试官：纠缠各种java code 细节 of Node class: public, private, constructor等
Me: 回答以为是主要写算法，可以重写Node class to production ready.
面试官: 不用了，如何实现Merge K sorted list
Me: 可以递归调用Merge two sorted list, 或heap
面试官：... 阅读全帖 |
|
w****a
发帖数: 710 | 25 这两天收到打车app，租房app，某all in one hr平台的口头offer，package细节下周
能出来，这周末提前好好考虑下。
另外手里还有个fb的offer保底。
板上大牛们帮分析下，现在去哪家还能有点汤喝？
---
10/28 update
准备卖身去打车公司当司机了，要去的组我非常喜欢，感觉能学到很多东西。
其实租房网也很不错，我其实纠结了很久。他们家去了之后基本可以随便去喜欢的组，
做喜欢的事情，这点很给力。至于车间的装修多么的好，我就不用说了，大家随便搜搜
图片就可以看出来。
但是综合来看，最后还是选择去当司机。主要是以下几点原因：
1. 要去的组业务多，公司貌似很重视。我觉得很能锻炼人，这个对new grads来说比什
么都重要。
2. 要去的组同胞多，甚至基本都是同胞。我觉得在美国，真正最后能帮上忙称之为人
脉的，永远只能是同胞。
3. 未来的manager是标准的德艺双馨，我打听了很多人，都说口碑很好。我觉得找工作
跟找phd有些许相似的地方，公司本身未必那么的重要，去哪个组以及你的老板怎么样
，有时候能直接决定你的career path。
4. Packa... 阅读全帖 |
|
|
发帖数: 1 | 27 来自主题: JobHunting版 - 求3题思路 第一题：类似于求Subset问题(不包含重复元素)。时间复杂度O(2^n)
第二题：Celebrity问题，一头一尾指针分别从头、尾两个方向向中间靠拢，每次都可
以淘汰一个元素，拿到备选元素之后再扫一遍原来的数组来确认找到的元素为最终结果
。时间复杂度O(n), n为数组长度。
第三题：分别从左往右、从右往左扫描两遍字符串即可，时间复杂度O(n), n为字符串
长度。
,3
follow |
|
发帖数: 1 | 28 我就觉得我挺笨的，刷题比高中数学难多了。
好不容易写出一个非暴力解的，上网搜“解题报告”发现人家的时间复杂度比我好太多。
好不容易写出个时间复杂度不错的，一看人家空间复杂度O(1).
然后再努力，人家写的比我恨不得短一半。。。
一道题就这么从开始看到最后看懂最优解（还记不住。。） 得好几个小时。。
都快抑郁了。。 |
|
u*****a
发帖数: 6276 | 29 【 以下文字转载自 PDA 讨论区 】
发信人: baodiao (钓鱼岛), 信区: PDA
标 题: 怎样看待华为前工程师杨学志关于4G核心专利的看法？
发信站: BBS 未名空间站 (Tue Jun 9 14:03:22 2015, 美东)
从网上看到一篇华为前工程师杨学志关于4G核心专利的看法， 不知各位有何高见？
当事人揭秘4G核心专利：高通没那么多，中国没那么少！
http://www.c114.net/news/41/a886875.html
1985年，在美国硅谷成立了一家叫Qualcomm(高通)的公司。这家公司把军用的CDMA技术
用于民用通信，推出了IS-95标准，成为与欧洲的GSM竞争的第二代移动通信系统。
在第二代的商业竞争当中，GSM还是取得了的胜利。但是在高通公司的创始人当中有一
位世界级的科学家，叫做Andrew Viterbi，就是那位Viterbi译码算法的发明人，IEEE
Fellow，并获得了美国最高科技奖。在他的推动下，产业界相信了CDMA代表了无线通信
技术的发展方向，因此第三代移动通信的三个国际标准，WCDMA，CDMA2000和TD-... 阅读全帖 |
|
m***e
发帖数: 89 | 30 【 以下文字转载自 PDA 讨论区 】
发信人: baodiao (钓鱼岛), 信区: PDA
标 题: 怎样看待华为前工程师杨学志关于4G核心专利的看法？
发信站: BBS 未名空间站 (Tue Jun 9 14:03:22 2015, 美东)
从网上看到一篇华为前工程师杨学志关于4G核心专利的看法， 不知各位有何高见？
当事人揭秘4G核心专利：高通没那么多，中国没那么少！
http://www.c114.net/news/41/a886875.html
1985年，在美国硅谷成立了一家叫Qualcomm(高通)的公司。这家公司把军用的CDMA技术
用于民用通信，推出了IS-95标准，成为与欧洲的GSM竞争的第二代移动通信系统。
在第二代的商业竞争当中，GSM还是取得了的胜利。但是在高通公司的创始人当中有一
位世界级的科学家，叫做Andrew Viterbi，就是那位Viterbi译码算法的发明人，IEEE
Fellow，并获得了美国最高科技奖。在他的推动下，产业界相信了CDMA代表了无线通信
技术的发展方向，因此第三代移动通信的三个国际标准，WCDMA，CDMA2000和TD-... 阅读全帖 |
|
f********t
发帖数: 6999 | 31 【 以下文字转载自 JobHunting 讨论区 】
发信人: mudhoof (正在长牙的羊), 信区: JobHunting
标 题: 这么热闹, 我也报Google offer
发信站: BBS 未名空间站 (Tue Feb 23 12:32:47 2010, 美东)
今天刚刚通知的, 特别感谢一起讨论的krone, geniusxsy, hnm, 特别是blaze教了我很
多, 还要特别感谢mitbbs59的总结帖
一起报offer, 好事成三, 大吉大利, 包子分光为止
贴下我的复习材料
题目大全:
http://www.spellscroll.com/viewquestions/?tag=algorithm
http://www.thecareerplus.com/?page=resources&cat=10
http://interviewcyclopedia.blogspot.com/
http://www.doctorinterview.com/A.html
http://toptechnotes.blogspot.com/search/label/algorith... 阅读全帖 |
|
f******e
发帖数: 164 | 32 【 以下文字转载自 JobHunting 讨论区 】
发信人: unichen (greedyrouter), 信区: JobHunting
标 题: Pure Storage面经， 遇到傻X阿三
发信站: BBS 未名空间站 (Sat May 24 11:44:44 2014, 美东)
在他们家遇到了两个傻B阿三。一个不停的纠正我的逗号和分号，另外一个给的hints都
是废话。最后挂了。他们家的阿三是我面过的所有公司中最极品的。所以面试他们家要
小心傻B阿三。当然他们家的华人美女HR相当的nice，是我遇到的所有HR中最nice的。
总共面了四轮：
第一轮：定义buddy system为一棵complete binary tree。一个node可能为0也可能为1
. 它的
value为1，当且仅当它所有的child的value均为1.
1
|
1 2
| |
1 2 3 4
| | | |
1 2 3 4 5 6 7 8
实现下列的metho... 阅读全帖 |
|
r****y
发帖数: 26819 | 33 另外再说一个感想
棋类的游戏，说到底，其实是暂时的
比如五子棋，变化少一点的，找出了先行必胜的套路，就没什么好玩的了
象棋复杂一些，所以还能玩一玩，围棋更复杂一些，还能继续扩大棋盘，复杂性可以
继续下去，但是说到底，在某个规则下，还是有个复杂度的极限的
这样的游戏，是征服客观存在着的不变的复杂度
这基本上就是棋类游戏很孤独的本质原因，万一复杂度被算尽了，也就不好玩了
真正无法玩到尽头的游戏是poker和桥牌这样的概率型游戏
看的是心理战，和人交流，观察别人的技巧，与人斗其乐无穷
其实我一直喜欢下棋，最近多了一些这样的感慨
I |
|
d***a
发帖数: 13752 | 34 写得很好。不过，围棋过于依赖于Moore's Law是不行的。
Moore's Law六十年的发展，处理复杂度的提高相当于从
5x5棋盘复杂度发展到8x8的棋盘复杂度。Moore's Law
已经提出了五十年，再发展十年没有问题，但之后就很
难说了。 |
|
E******w
发帖数: 2616 | 35 关于AlphaGo使用的算法的论文网上可以看到，虽然没有具体的细节，但是可以了解个
大概。这里我尝试解释一下为什么现在AI的棋力比过去有质的飞跃。它的弱点到底有可
能在哪里。
机器最大的优势是暴力搜索，利用高运算量多机联网的方式，在极短的时间内可以搜索
数量巨大的可能变化。这个能力人无法与之抗衡。机器的核心弱点是不明白为什么，不
明白道理，不会推理，形势判断显然也远不如人。对于围棋这样复杂度很高的游戏，机
器搜索能力再强，能搜的变化也只是所有变化的一小部分，如果花大量时间去搜索没有
意义的变化，搜索能力就不会对棋力有多大的影响。
过去AI集中解决的问题，就是对可能的变化的重要性进行排序。假设人在短时间内只能
搜索100种变化，而AI在同样的时间可以搜索几千万种变化，只要AI能够对各种变化排
序，保证人搜的那100种变化都被排在了几千万之内，那样AI就同样可以搜索人搜索过
的变化，逻辑推理能力的弱点就可以得到弥补。只要这个目的达到了，这100种变化是
不是用推理得出来的，这并不重要。（同样的道理，如果AI有能力搜索所有的变化，根
本就不需要任何推理能力也可以战胜人，归根结底是机器和人各有... 阅读全帖 |
|
B*********r
发帖数: 267 | 36 zz
这是我遇到的google面试题目,希望后来者好运.
1.求直方图的最大内接矩形,假设每个细条的宽度为1.这个题很hot,两个人来问.我没想
出什么好的算法.
2.NxN行列有序的矩阵查找一个数.以前有人遇到过.O(N)的时间复杂度
3.给定一篇文章,求包含所有单词的最短摘要.O(N)的时间复杂度
4.将MxN的矩阵转秩,要求O(1)的空间复杂度.参考群论中cyclic group,group
generator
5.开放式问题,怎么避免重复抓取网页
6.开放式问题,有些网站每天只允许有限次访问,怎么抓取网页使得索引尽量全面和新鲜
7.写一个singleton pattern的例子
8.vector vs. arraylist, growth strategy & complexity
9.在C++文件中只declare class A, 但不以任何方式define class A, 是做什么用
10.virtual function
11.讨论html vs. xhtml vs. xml
12.描述在浏览器中敲入一个网址后所发生的事情.dns,cache等 |
|
b***e
发帖数: 15201 | 37 恩 我转发答案吧 不一定对阿
发信人: philofellow (大智若愚), 信区: JobHunting
标 题: Re: 微软intern面经（一些解答）
发信站: BBS 未名空间站 (Wed Jan 19 22:22:13 2011, 美东)
本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
1. atoi
当时写的程序很不细致，没有判断正负，字符串中字符不为数字，字符串过长越界等情
况。写完后想起来了，然后口头补充了一下，面试官说知道我的意思就直接到下一道题
了。
2. 用递归
bool Equal(Node* a, Node* b){
if(a == NULL && b != NULL) || (a != NULL && b == NULL)
return false;
if(a == NULL && b == NULL) return true;
return (Equal(a->left, b->left) && Equal(a->right, b->right)) || (Equal(a-
>left, b->right) && ... 阅读全帖 |
|
x**********s
发帖数: 6296 | 38 我是一名程序员，昨天晚上去相亲，感觉现在的女生... 相亲时，我就随便问了三个问
题，她竟然一个都答不上来，也没有讨论的气氛。。。
先问了一个“虚函数和纯虚函数有什么区别？”，她愣在那里半天，既不回答，也不说
说自己的观点。
看她对C++没什么研究，就问一点算法一点的问题吧“怎么实现二叉树的深度优先遍历
？”，她说话了“二叉树？有多深？”
崩溃了，万般无奈之中，记得女孩子普遍对时间敏感，“哈希表插入操作的时间复杂度
是多少？”她终于活跃了："哈希表是谁?...多复杂？..."
----------------------------------------------------------------------------
--------------------------------------------------------------
我是一名化学家，昨天晚上去相亲，感觉现在的女生...相亲时，我就随便问了三个问
题，他竟然一个都打不上来，也没有讨论的气氛。。。
先问了一个“伪姜泰勒效应和分子轨道理论哪个能更好的解释臭氧的极性？”，她愣在
那里半天，既不会打，也不说说自... 阅读全帖 |
|
d*******g
发帖数: 36 | 39
数
我自认不是大虾。
说说我的想法。
从你的问题描述来看，你的问题和“find top m elements from a sequence of n
elements"没有什么差别。你给出的复杂度（n log n) 就是排序的时间复杂度。
对于不同的alphabet,时间复杂度是不一样的。
你想得到的具体多少次..., 我想，你讲的是不是算法优化问题，更像编码优化问题。
以前我的北京工作，就专门搞编码优化。 我个人觉得，编码优化depends on 数据的
property. |
|
d*****u
发帖数: 17243 | 40 这门课一般有三个等级
一个是本科二年级的那个，算法和数据结构
讲的都是比较实用的，简单的复杂度分析、查找排序，二叉树，hash表，贪心算法等等
一个是本科高年级和研究生通用的
主要覆盖复杂度分析、贪心算法、动态规划、NP理论之类的
还有就是更高级的
主要有更详细的复杂度分析、P NP的各种证明啥的，没啥用 |
|
h*****a
发帖数: 1718 | 41 第一题比你想的要tricky。用loop要看怎么用，如果是一个一个乘上去是O(n)复杂度是
不行的，要O(log(n))的复杂度才可以。还有其它的trick，比如n是负数需要处理。用
递归也要看怎么用，就算用的对能降低复杂度也不是最优solution，因为额外的栈开销
造成可能的stack overflow。
就算上面都考虑到了，也写对了，还有计算过程中overflow的问题要考虑，如何对
overflow给出一个合理的解决方案，也是很考经验和功力的。
第二题很基本，但从我面试别人的经历看，很多人给不出perfect的solution。 |
|
g*****g
发帖数: 34805 | 42 原题没要求要保证顺序，要保证顺序很容易。
出现新单词的时候给个数字标号，打印子图之前
排序一下即可。因为节点数远远小于边的数目。
这个复杂度在最坏情况下就是O(mlogm + n)
通常mlogm < N < m^2，所以计算复杂度不变仍然是O(N)。
存储复杂度是O(m^2)， |
|
c*m
发帖数: 1114 | 43 这不就是一个排序问题么？
对 p_i 排序，O(klogk)复杂度
排完后新vector是,...
然后对w_i*按照i从大到小遍历一遍，如果w_(i+1)*（就是
从右向左测试w_i*是个递减数列，碰到不对的话删除左节点。) 复杂度o(k) (当然你也
可以从左到右遍历，反正记得出了问题就删除左节点就行。)
总复杂度O(klogk+k)=O(klogk)? |
|
i**********e
发帖数: 1145 | 44 写了一个，如果是 k 个数组，每个数组长度最多是 N 的话，那么时间复杂度就是 O(
kN Log (k) )。需要空间复杂度 O(k) 来暂时储存暂时的 indices，来记录每个数组已
经进行到哪里了。
这个也可以用 divide and conquer，每次分半合并，递归解决。虽然时间复杂度是一
样的，但实际上肯定没有用 heap 快，因为递归的关系。
另一个变种就是 merge k sorted linked list，返回一个新的链表。这个就不需要额
外空间，可以每个 list 直接 advanced，指向每个链表进行的位置。但是编写起来很
麻烦，如果你不懂得点技巧的话。这个在 C++ 里用 double dereferencing pointer
代码可以写得相当简洁。
typedef pair Pair;
vector mergeKSortedArrays(vector > A) {
int k = A.size();
priority_queue, greater阅读全帖 |
|
d******i
发帖数: 7160 | 45 背景是想做k个最小值的维护，用了k-size的大顶堆。
本来逻辑上是顺畅的:
新元素比堆顶大，直接pass；
o/w替换堆顶，做个ShiftDown维护。
按说复杂度log2(k)吧，撑死找条path走到底。
代码当然可以写，但还是指望STL堆函数给点捷径，结果很失望。
貌似只能先pop_heap清掉，再入尾后push_heap，非得整理两次不可,代码如下：
//remove the old top one, since no longer qualify
pop_heap(vmo1.begin(),vmo1.end(),classcmp);
vmo1.pop_back();
//insert the new one, since must qualify
vmo1.push_back(*ivmo); //*ivmo是比堆顶小的新元素
push_heap(vmo1.begin(),vmo1.end(),classcmp);
复杂度一下子double了，成了2*log2(k)。
当然可以用复杂度k的make_heap，就不提了。
有没有利用STL现有堆函数实现这个ShiftDown的简单... 阅读全帖 |
|
z*******3
发帖数: 13709 | 46 因为mobile的东西小啊
而且历史短啊
mobile就那点东西，有啥复杂的计算？
就游戏的复杂度会高点，尤其是3d游戏复杂度会高点
其他都不会太高，2d游戏的复杂度也就那么一回事
基本上构建了一个场景，剩下的把图片音乐给换一下就可以了
就根本不需要开发，一般一个team的程序员控制在2－3个人就可以搞了
我一个人也没啥特别麻烦的
问题在于backend不能这么搞
backend所有东西都是堆积上去
随着年代增加而增加，而且越来越多，越来越大
象web server那种用node，go和ruby重写三次，不让写就跑路的
这种情况几乎不允许出现
这才叫工程，这才叫软件工程，这个领域才需要软件工程
因为人多，需要协调和一致性，而不是几个手工作坊的产品就大谈什么软件工程
你这不是笑话吗？
你连例子都没举对，你说的mobile那不叫软件工程，那叫艺术
甚至你说它们是工程，它们都觉得你侮辱了它们 |
|
q*c
发帖数: 9453 | 47 这不对。你每天被按摩桑拿，就算这样 100 年，你也自在舒服。
你每天被人抽，就算被打一辈子，照样苦逼。没法适应。
人有自然特性，有脑容量，有些东西符合人的特点， 复杂度低于人的舒适度， 有些东
西， 就是逆反人的特性， 复杂度大于人的舒适限度。
复杂度自然有其绝对的定义， 你这种抹杀程度区别，把一切都变成个人选择习惯，妥
妥的大左派，我没猜错？ |
|
