h**o
发帖数: 548 | 1 书上用对半排除法为什么就是time = O（n), 是否有问题那？
fetch(a, i, col) 需 O(1), 所以 把一个a[i]排除掉就需lg(n), 把所有奇/偶a[i]排
除掉就需n * lg(n),这本身就需 time = O（n lgn). 所以这道题time complexity 应
该是 nlgn, 还不如直接用bitmap（求a[i]，然后把a[i]bitmap) 来做呢。
请问我的理解是否对， partition然后排除法好在那儿那 |
|
g****o
发帖数: 547 | 2 不差加法这点时间
你要快 fibonacci number还有 o(lgn)的算法，你可以试试 |
|
g****o
发帖数: 547 | 3 需要计算什么根号5的n次方啊
问题在于这个运算的复杂度是o(lgn)还是o(1)
定。 |
|
a********m
发帖数: 15480 | 4 不对。用heap实现的话还是lgn，这样应该就可以了。
这样回答lz的问题就是heap需要随机访问元素。其它简单类型比如queue,stack都不符
合这个要求。 |
|
|
|
s***5
发帖数: 2136 | 7 考智商行不？还有，用这种方法才能实现O(lgn)算法。 |
|
s******7
发帖数: 1758 | 8 倒，都用近似公式了，要个妹的lgn, 老兄你说的跟我问的是一个问题吗，要不你去看
看二楼的wiki连接，那个公式要当场能推出来，我看高中生估计是奥赛出来的 |
|
d******a
发帖数: 238 | 9 面试官水平不一定比你高，尤其是烙印啥的。我上次去linkedin面试，一烙印说1+1/2+
1/4+....=lgn
啥玩意啊。就你说的这面试官平时估计从来没接触过pthread，不明白很正常。面试很
大程度看眼缘和运气的。
你要想找个题难倒面试官那不是很容易的事嘛。。 |
|
d******a
发帖数: 238 | 10 还有那个lgn的不只是linkedin的烙印，还有个微软的烙印也这么说，当时说的是建一
个堆的时间开销。。
这两人都是senior..碰上这种面试官就是倒霉，不过想想这种人都能混得挺好，咋们也
别把心思就放在做题上了，能忽悠才是正道 |
|
l****1
发帖数: 33 | 11 容易想出一个lgN * N^2的笨算法，更好的想不出来了 |
|
l****1
发帖数: 33 | 12
那是，不过lgn * n^2也能解决负值的case。 |
|
a********9
发帖数: 129 | 13 已挂
电面 1
国人大哥，应该有点放水
1) fabanacia，期待o(lgn)解法,但O(n)也行
2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
只知道worse case 是O(n^2)
onsite1
behavior: 1)有什么跟同事意见冲突的案例，怎么解决
2) 以前做过的项目如果现在再做会有什么不同/改进
3）divide and mod，但不能用/或者%，基本也是leetcode原题了
onsite2
system desgin: 因为我是kernel背景，让我用mutex,cv实现一个semephor，说先考虑
单核，然后拓展到多核，但我只写了单核的就没时间了，不知道多核的会有什么不同，
要求code compilable，MD三哥从一进来就没好脸色，此轮negative
onsite3:
1) 给你10g文件，1g内存，数总共有多少个不同的数，答案是用bit来记录数字，总共
4b个interger,最多用0.5gb来记录，follow up是如果只有400m怎么办，答案是把数字
hash... 阅读全帖 |
|
a********9
发帖数: 129 | 14 已挂
电面 1
国人大哥，应该有点放水
1) fabanacia，期待o(lgn)解法,但O(n)也行
2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
只知道worse case 是O(n^2)
onsite1
behavior: 1)有什么跟同事意见冲突的案例，怎么解决
2) 以前做过的项目如果现在再做会有什么不同/改进
3）divide and mod，但不能用/或者%，基本也是leetcode原题了
onsite2
system desgin: 因为我是kernel背景，让我用mutex,cv实现一个semephor，说先考虑
单核，然后拓展到多核，但我只写了单核的就没时间了，不知道多核的会有什么不同，
要求code compilable，MD三哥从一进来就没好脸色，此轮negative
onsite3:
1) 给你10g文件，1g内存，数总共有多少个不同的数，答案是用bit来记录数字，总共
4b个interger,最多用0.5gb来记录，follow up是如果只有400m怎么办，答案是把数字
hash... 阅读全帖 |
|
D**********d
发帖数: 849 | 15 如果 size 相同的好办一点。不相同得加不少判断，例如是否有空 array etc. 不过原
理一样，深化为找 kth element 的问题就好办了。O(lgN), 不过每次大约能去 k/2。 |
|
s********u
发帖数: 1109 | 16 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
样吧。不过他说会给足时间。
题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
所在的interval返回。
分享题目和答案：https://docs.google.com/document/d/
1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit
这个我记得就是用BST做的。
有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。
中间讨论了一下维护min和max变量是否必要，我说主要是在val超出范围的时候直接判
断，他说那其实interval中间也有空当。我就说那就只有两端的时候，会比较有用... 阅读全帖 |
|
s********u
发帖数: 1109 | 17 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
样吧。不过他说会给足时间。
题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
所在的interval返回。
分享题目和答案：https://docs.google.com/document/d/
1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit?usp=sharing
这个我记得就是用BST做的。
有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。
中间讨论了一下维护min和max变量是否必要，我说主要是在val超出范围的时候直接判
断，他说那其实interval中间也有空当。我就说那就只... 阅读全帖 |
|
J****3
发帖数: 427 | 18 恩 你是对的。找start 和 end 分别都是O(lgn) |
|
M********u
发帖数: 42 | 19 用一个BST来keep所有的message，让所有的message order by time，任何操作的时候
都去检查最老的message是不是需要purge了。insert的时候不仅insert到bst，而且
insert到一个hashtable里。
这样addMsg是O(lgN)，getMsg是O(1), getAvg()是O(1) 假设你keep一个sum和cnt的话
。主要问题是有lock contention |
|
d****n
发帖数: 397 | 20 那constant space complexity呢? recursion的堆栈深度就是lgn了。 |
|
d*****o
发帖数: 310 | 21 update 下，紧接着第二个面试是 median of two sorted array, 直接给了lgn的解法
，他要linear time的解法，短路的两分钟用merge的办法写。 |
|
a*********0
发帖数: 2727 | 22 你被三哥黑了吧，给了lgn，还要linear？ |
|
z***e
发帖数: 58 | 23 已经挂了 发面经。
其他的都很简单，说一个印度人问我的问题比较难：
在一个2D空间里面有很多矩形，矩形都是不overlapping的。 给一个query，也是一个
矩形，问是否空间里面存在一个矩形与其overlapping。
我当时想到了用quad tree， 然后面试官简单的问了思路，然后让我分析复杂度，然后
我又提出使用kdtree，面试官说，分析复杂度啊，然后这就是悲剧的开始了，我分析错
了，说是lgn，其实应该是根号n。
然后他说你把你刚刚说的kdtree数据结构定义是什么，查询一个矩形的代码写出来。本
来挺有信心，但是因为剩下的时间不多了，所有优点慌，写的代码有一个bug被他揪出
来了。我看他撇着嘴就知道要跪了。
还有国人大哥，本来想放水，无奈我不给力，不过人很nice 赞一个。 |
|
|
e*****i
发帖数: 182 | 25 简单来说，你的算法是错的，怎么lgn法啊，看一半如何知道哪一半丢了啊？ |
|
k*****m
发帖数: 14 | 26 1. top-k, lowest-k
可以用selection ranking，O(n)
2. stock
感觉可以用segment tree，查询，插入都是O(lgn) |
|
l*****a
发帖数: 14598 | 27 计算机的课程学过牛顿?
还有那个fibonacci数列的lgn solution.也是同样问题。 |
|
b****n
发帖数: 99 | 28 Citibank Java 面试第二轮， 没有写代码，完全问问题，说说concurrenthashmap 和
multithreading 问题。
三个人，分别面。
第一个，烙印，搞C++，大概问问 OOP的感念和多线程。没有详细的很深入的问题。说
说concurrenthashmap 和 multithreading 问题。
第二个，VP，白人，搞Java的，trading 但是什么领域没听懂，不是framework。问了
几个问题，一个1million的数组，怎么找某一个数。结论：用二叉树。 加问： 最差情
况是 20 次的话，最好是1次，平均多少次。结论：用概率算一下。是lgN-1 次，他给
的结果。
第三个人，白人，女性，像HR。问问工作处理的关系，出了一个怎么找质数的问题，写
个算法就行了，也不用编程。 |
|
n**********2
发帖数: 214 | 29 是他自己推倒的结果，我只大概给了方程，要用点概率，算每个点搜索的次数，最后西
格玛求和他说约等于lgN-1 |
|
s******y
发帖数: 936 | 30 还好吧，我面试的时候写了最优解O（n），然后要我写次优解O(lgn)，写完再写个N^2.
这个看面试官，还有你的速度吧，你写太快了 他没有更多的题目，只能让你优化或
者 写别的解。SDEII的面试题类型和这个差挺大的吧，会更多的design 什么的。 |
|
b*****c
发帖数: 1103 | 31 2nd q: 排序後動態規劃 o(n*n*lgn) |
|
z*******3
发帖数: 13709 | 32 对比一下queue和heap的效率哈
queue的删除很简单，尤其是删除头尾，对内部结构完全没有影响
heap的删除root之后，要heapify，这个开销很大
插入
两个都是lgn，所以queue可以省掉heapify这一个步骤
看hadoop什么都是用priorityqueue，而不是treemap
所以这题貌似heap并不是最优解，只是一个相对简单的解法
看来swjtuer是对的 |
|
z*******3
发帖数: 13709 | 33 对比一下queue和heap的效率哈
queue的删除很简单，尤其是删除头尾，对内部结构完全没有影响
heap的删除root之后，要heapify，这个开销很大
插入
两个都是lgn，所以queue可以省掉heapify这一个步骤
看hadoop什么都是用priorityqueue，而不是treemap
所以这题貌似heap并不是最优解，只是一个相对简单的解法
看来swjtuer是对的 |
|
c***0
发帖数: 449 | 34 是啊，题目说已经建立好了啊，如果你按照kd tree建立的话，查找的复杂度不是lgn吗
？建立的复杂度是排序 |
|
|
z****e
发帖数: 54598 | 36 那就是先通过分clustering来归类大数据？
用这种方式来优化n
把n变成lgn
最后是lgk * lg n |
|
|
l******a
发帖数: 14 | 38 Divid the matrix to 2 by 2. Each are n/2 X n/2
If k<=n*n/4, restrain search to only the top left square
Else if k =>n*n*3/4 restrain search to only the right bottom square
Else restrain search to top right and bottom left square
This way you cut it at least to half size each time
T(n) = 2T(n/2) O(1)
So T(n) = O(nlogn)
O(n) is doable. But I need O(n lgn) and the code.O(n) algorithmhttp://www.cse.yorku.ca/~........ |
|
|
l******a
发帖数: 14 | 40 Divid the matrix to 2 by 2. Each are n/2 X n/2
If k<=n*n/4, restrain search to only the top left square
Else if k =>n*n*3/4 restrain search to only the right bottom square
Else restrain search to top right and bottom left square
This way you cut it at least to half size each time
T(n) = 2T(n/2) O(1)
So T(n) = O(nlogn)
O(n) is doable. But I need O(n lgn) and the code.O(n) algorithmhttp://www.cse.yorku.ca/~........ |
|
b*****c
发帖数: 1103 | 41 不是说了k=o(n^2)吗，晕死
o(n*lgn)基本没戏了，看能不能数学证明下这是不可能的 |
|
|
a****r
发帖数: 87 | 43 空间复杂度O(n). 最好是O(lgn)。constant space 应该不太可能解这道题吧？牛人可
以指点一下。 |
|
e******x
发帖数: 184 | 44 因为之前发过贴，背景就不赘述了，具体说说怎么准备还有面经吧。
骑驴找马，一月底开始刷leetcode，到三月中第一个面试，刷了一遍半吧，明显觉得写
第二遍的时候思路清晰多了，code也比第一遍的简洁。其他的就是每家面试前争对性的
看面经，能看多少是多少，四家只有L面经重复率很高，g家最不能预料题型。后面准备
design的时候都是乱看，一些fb tech talk的视频还有之前有人贴过的fb design的总
结，
但我基础不好，临时抱佛脚感觉也没什么用。面经我就只贴面完有及时记下来的，反正
也给过很多朋友了，就贴上来吧。
已经签了fb，准备八月初start，有同一期的pm我，哈。
脸书:
1. Print all paths of a binary tree
I gave a recursive solution.
Then he wanted to give an iterative way.
2a. Fibonacci (iterative)
2b. Buckets of anagrams
[“cart”,”tarc”, “cat”, “act”, “ract”] -> [[“... 阅读全帖 |
|
w*******8
发帖数: 10 | 45 来自主题: JobHunting版 - M 家电面 是小弱不是大牛
正刷题呢，看到是leetcode上原题就顺手把代码搬过来了
Divide Two Integers：
思路是：既然是int的除法，不用考虑小数部分（余数），就是整数（商），那就数
dividend 里有多少个divisor. 这样，如果商是n 需要O（n）计算，可以用下二分法，
divide&conquer 递归调用一下，就是lgN了
剩下的就是边界条件： 1）正负 2）极值
int 的范围是 -2,147,483,648 to 2,147,483,647
这里有个细节，当时看别人的代码觉得比较巧妙：
正负数的范围是不对称的
-2147483648 abs 一下还是自己本身，那就先count一次，再计算
之前看到很多方法是转成double 再强转回int，其实是没必要的
其他基本的int 计算也大多是这个思路 比如 int sqrt(int) int pow(int) |
|
P**********k
发帖数: 1629 | 46 问一下CLRS里面一道题
Water Jugs Problem大概是在sorting那一章
There are n red & n blue jugs of different sizes and shapes. All red jugs
hold different amounts of water as the blue ones. For every red jug, there
is a blue jug that holds the same amount of water, and vice versa. The task
is to find a grouping of the jugs into pairs of red and blue jugs that hold
the same amount of water.
Operation allowed: Pick a pair of jugs in which one is red and one is blue,
fill the red jug with water and then pour the water... 阅读全帖 |
|
z****e
发帖数: 54598 | 47 tree和hash应该是最常见的两种结构
总体而言，现在用hash比较多，因为hash可以提供amortized o(1)复杂度的search
while tree只能保证o(lgn)复杂度的search
但是如果需要频繁排序，比如经常性插入，删除，弹出一个最小最大值
这个时候才用tree，比如priorityqueue，其实就是堆排序
否则就用hash，包括分布式现在常见的consistent hashing |
|
r*******k
发帖数: 1423 | 48 我觉得他就是引导我要去按小的那个数的列去查找。
数字可能倒不是很重要。
我现在有点晕
一般young矩阵的查找是(m+n)
那么我这么搞，是o(lgm+lgn)?
感觉不大可能啊。。。
and |
|
c*******y
发帖数: 98 | 49 bucket神马的感觉靠谱，不同bucket存到不同机器上去，估计最好用平衡二叉树做一个
可以O lgn 插入，Olgn 查找第k个元素的结构。节点结构至少要包括node左边几个元素
，右边几个元素。每次插入还有平衡都得把这个也考虑一下。 |
|
r*******k
发帖数: 1423 | 50 猜是nlgn排序
然后从大到小开始验证，验证的代价是lgn |
|
