I*********g
发帖数: 93 | 1 关键是O(1)的space。
我知道有人做出了timeO(nlgn) space O(1)的算法
期待有人做出O(n)的 |
|
P*******7
发帖数: 55 | 2 已面试facebook, bloomberg, linkedin三家，都拿到offer。在本版收益很多，特来回
馈。
背景：12月-4月找faculty全军覆没，5月份开始准备工业界面试，花了近1个月时
间将本版1万
多帖子过了一遍，发现绝大部分面试题都不出其中，非常有用。这里补充一些自己遇见
的题目：
推荐“A Collection of Dice Problems”,面试facebook时遇到不少概率题，都不超出
这篇文
章的思路和难度。
Lock-free algorithms。推荐
http://www.ibm.com/developerworks/java/library/j-jtp04186/index.html
Bloomberg题目较容易，比如一个数组只有0，1两个数字，如何O(n)time, O(1)space排
序。但
同样思路的题目在facebook就变成一个数组有k个不同数字,假设k是常数，如何O(n)
time,
O(1)space排序，现场写出程序还是很麻烦。
另外小尾羊曾总结O(nlgn)的算法找出最长增长序列，面试中有遇到。
排序和binary sear |
|
I**A
发帖数: 2345 | 3 嗯，我说，有两种办法，一种呢O(nlgn)，一种呢,可以借助hashtable达到O(n)，
interviewer自己就说了，听听O(n)的，不过显然他知道这个算法。。
你这个interviewer自己不把题目搞清楚的确是比较奇怪。。 |
|
c******a
发帖数: 789 | 4 排序以后是要各自再过一遍d...
O(nlgn)+O(n), 后者可以忽略
naive那可是O(n^2)，所以排序了再两个一起从头便利好。 |
|
r******e
发帖数: 80 | 5 first round phone interview with Amazon with an India. Got rejected. share
the questions which hopes other people
Questions 1: ( I am not sure if I misunderstand his question but I share
what I know) Given n Integer numbers, all of the numbers except one occur
twice and only one occur once. Find it.
Solution 1: Sort the array and loop and find it. time O(nlgn), space O(1)
Solution 2: using hashtable, time O(n), space O(n)
And then, he said what about numbers can occur more than twice or |
|
w******g
发帖数: 67 | 6 刚开始看书，理解不够深刻，哪位大侠给科普一下。
1. 这三个算法都平均复杂度都是 (nlgn), 该怎么选择用哪一种算法呢？
2. 看到以前有例子说n非常大的话用merge sort，几台机器分别sort，然后再merge，
这是为什么
呢？merge sort 不是需要而外的空间～n 吗？这时候用quicksort 会不会好一些？
多谢。 |
|
s***r
发帖数: 12 | 7 来自主题: JobHunting版 - 一道算法题 hashmap,O(n)
如果按字母顺序，treemap,O(nlgn) |
|
z***9
发帖数: 696 | 8 我也刚搞玩二面, 应该是老美，谈了谈我的research, he said that is interesting.
接着开始coding, 很简单，关于字符串的，不过没听清楚他在问什么，接着他讲了个
例子才明白。然后，simple solution，O(n^2), 接着binary search 优化O(nlgn),接
着bit map 优化 O(n), 接着时间到了。。。，
问题：
1） 刚开始没听清楚耽误了时间
2） simple solution coding 时出了个小错误，后纠正
不知到最后能不能onsite。。。 |
|
n*****y
发帖数: 361 | 9 因为赶着年底毕业，九月底才开始投简历。这个offer来的太快，小startup就是动作快
，从十月初联系我，到 offer, 就两周。那几个大公司的 on-campus interview还都没
开始。也算是 hot startup,但这里肯定没人知道的，移民版知道这个公司的更多些。
就不透露公司的名字和考题了，见谅。
HR 联系之后，先是组里的头直接电面，问了一个他们实践中的问题，我没想出答案，
但还是扯了扯。后来就在谈公司做什么，我有准备，问了很多问题。刚放下电话,HR问
我什么时候作 coding test, 可以马上把题发给我, 就是fill Java class, 实现某些
功能，一般给 2-3个小时。我想这么大工作量，不能拖，否则牵扯时间和精力，就说马
上作，决定不准备了，冒一定风险。结果一个小时做完发给他们，小impress了一下。
然后另一个 team lead 马上打电话二面，顺便考察一下是不是真是我自己写的程序。
这就是一天三面，两电一编程，然后就给 onsite了。面了组里的4个lead,HR 和
Founder。前两个基本都在问我的 research和 big ... 阅读全帖 |
|
n*****y
发帖数: 361 | 10 因为赶着年底毕业，九月底才开始投简历。这个offer来的太快，小startup就是动作快
，从十月初联系我，到 offer, 就两周。那几个大公司的 on-campus interview还都没
开始。也算是 hot startup,但这里肯定没人知道的，移民版知道这个公司的更多些。
就不透露公司的名字和考题了，见谅。
HR 联系之后，先是组里的头直接电面，问了一个他们实践中的问题，我没想出答案，
但还是扯了扯。后来就在谈公司做什么，我有准备，问了很多问题。刚放下电话,HR问
我什么时候作 coding test, 可以马上把题发给我, 就是fill Java class, 实现某些
功能，一般给 2-3个小时。我想这么大工作量，不能拖，否则牵扯时间和精力，就说马
上作，决定不准备了，冒一定风险。结果一个小时做完发给他们，小impress了一下。
然后另一个 team lead 马上打电话二面，顺便考察一下是不是真是我自己写的程序。
这就是一天三面，两电一编程，然后就给 onsite了。面了组里的4个lead,HR 和
Founder。前两个基本都在问我的 research和 big ... 阅读全帖 |
|
s*******r
发帖数: 47 | 11 那怎解？ 没有限制用球数， 貌似平均时间O(nlgn)是最好的解法了 |
|
d****j
发帖数: 293 | 12 Sort的话不如直接弄个Set来表示目前candidate行的行号
刚开始，1-N个数全放进去
扫描第一列，检查Set的(行号,第一列)是否为1，是就删掉
扫描第二列，检查Set中剩下的行号的第二列是否为1，是就删掉
....
如果每次能删掉1/2的话，复杂度不就是
(N + N/2 + N/4 + N/8 +....)*O(set_operation) = 2N*O(set_operation)
Set如果用hash实现，查找删除就是O(1), 总共就是O(N)
如果用BST实现，总共就是O(NlgN) |
|
t*****j
发帖数: 1105 | 13 做好情况O(nlgn),最差情况还是O（n2）。
is |
|
t*****j
发帖数: 1105 | 14 popular 三连击那个，不需要排序吧，只需要给2n个指针，然后一个map就行了。复杂
度nlgn，别想太复杂了。 |
|
g*********s
发帖数: 1782 | 15 i think the 2-heap solutions is just sigma(O(lgK)) which implies O(NlgN)?
However, linear selection is sigma(O(K)) i.e. O(N^2).
complicat
gave up |
|
J*********n
发帖数: 370 | 16 来自主题: JobHunting版 - 有A[i]
this really doesn't make too much sense since you will have to maintain a
heap to retrieve the max element among the n elements, which turns out
to be O(nlgn). But without knowing A[i] < A[n+i], we can also achieve this
by some sorting algorithms.
Unless there is a quicker method to retrieve the max element, I don't see
the value of having this property. |
|
i****d
发帖数: 35 | 17 TAOCP Vol.4介绍了一种据说很古老的方法，我觉得可行
唯一不便的是最开始需要把原始字符串拍个序
不过鉴于n! >> nlgn，所以我觉得也没啥问题
基本的思想是我们需要从1,2,3,...n 生成到 n,n-1,...1
只需要提供一个根据当前排列，生成下一个排列的方法就可以了
通过个例子也许更好描述一点
123
132
213
...
321
1. 每次从右向左扫描，碰到第一个a[j]停止，此时 a[j-1]....a[0] 是非递增的，但a
[j] < a[j-1]
比如说 132，我们就在1这个地方停止。因为从3往后看都是非递增的，但是从1看就不
是了，1<3。直观上理解，这时候后面的a[j-1]...a[0]已经是最大的了，要想更大，必
须得调整前面的数了。
2. 从a[j-1]...a[0]中找到一个刚好比a[i]大的数，交换a[j], a[i]。其实就是从0~j-
1扫描，碰到第一个a[i]>a[j]就找到了。或者你想二分查找也可以。
还是看132, 找到第一个比1大的是2，交换后变成231。
直观想的话，a[n-1]...a[j+1]我们显然不想动，因为只要活动a... 阅读全帖 |
|
i****d
发帖数: 35 | 18 印象中要用到range search
就是去BST里面找的时候
不然分析不出来O(nlgn)的 复杂度
such
corner |
|
D*********y
发帖数: 876 | 19 先把x方向左右两条边都sort一下，O(nlgn)
然后用以下的判断：
bool overlap(Rect a, Rect b) {
return ( a.ul.x <= b.lr.x &&
a.ul.y >= b.lr.y &&
a.lr.x >= b.ul.x &&
a.lr.y <= b.ul.y );
}
其中ul是upper left，lr是lower right
找满足a.ul.x <= b.lr.x和a.lr.x >= b.ul.x的
然后把满足条件的矩形的y方向两条边，加上要比较的矩形本身，sort一下
找到满足a.ul.y >= b.lr.y和a.lr.y <= b.ul.y |
|
v*******7
发帖数: 187 | 20
solution #1:
using hashtable/hashmap that keeps track of (key, value) pairs where key is
the
element in array while value is the frequency.
scan each element e in the array, if e does not exist as a key in hashtable,
insert
(e, 1) into hashtable. If e exists in hashtable, move to the next one until
the end
of the array.
iterate the key in hashtable and store them in the old array.
Time Complexity: O(N), Space complexity: O(N).
solution #2:
sort the array first (quicksort, O(NlogN) in time on av... 阅读全帖 |
|
|
v*******7
发帖数: 187 | 22
对，如果heap用binary tree来表示，那么需要有parent指针的信息，in place可以做
，我这里刚
才想了一个算法，是O(nlgn)的做法，可以做到。
我在想用array表示的heap转换成array 表示的BST要怎么做。 |
|
v*******7
发帖数: 187 | 23
Sorry，呵呵，刚明白过来，要是用array表示的heap，那做起来更简单，因为不需要用
到parent
指针了，其他都一样，那么time complexity还是O(nlgn),也是inplace的。 |
|
t****0
发帖数: 235 | 24 do you have to call
getMin n times to get the linked list?
that is nlgn
I think it does not matter if pointer or array is used to represent the
heap right? |
|
t**d
发帖数: 352 | 25 what is the bug? I can't see the difference.
also, how's the runtime turn out to be n? isn't the worst time still n^2
because of the while loop? average time nLgn ? |
|
l******l
发帖数: 66 | 26 Here is a thought:
With the sorted index-value array x as above:
1. Left pointer start from x[0], using binary search (or linear search,
won't affect
overall big-O complexity ) find the first j (right pointer) such that
x[j].num-x[0].num>k;
then from j to the end, find the largest index, let it be m.
2. Now move left pointer to x[1], move right pointer from j to the left,
until we find the first j'
such that x[j'].num-x[1].num>k. Compare new indexes with m, update the new
m
. Also update the lar... 阅读全帖 |
|
S****z
发帖数: 666 | 27 谁来解析一下为什么得先求这个最小下标，思路是啥？
然后后面的为每个i找j怎么就是O(nlgn)了？
【4
(2
= |
|
J****a
发帖数: 15 | 28 Based on ibread's method, I think this is easy to understand, welcome any
comments.
Example: [-2, 2, -1, 3, -6] and k=3
For step 2
1) 还是计算sum[i]。O(n) sum_origianl=(-2,0,-1,2,-4)
2)排序，排的时候以sum[i]为key，同时带上下标i。O(nlgn)
sum=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)]
3)给排好序的 arrary, every i , sum[i]-k; O(n)
(in order to在排序好的sum数组中找 sum[j] 正好 <= sum[i]-k, so I create a
sumnew)
Sumnew=[(-7,4),(-5,0),(-4,2),(-3,1),(-1,3)], next step is 在sum中找 最小下
标。
4)找min-index[i]. O(n)
a=0, b=0;
Temp=n+1; (p... 阅读全帖 |
|
b*m
发帖数: 34 | 29 似乎现在的解法都不太完美。
ihasleetcode 的算法有点诡异。
Using binary search, we found the smallest j that satisfies the condition
sorted_cum[i]+k >= sorted_cum[j]
这里 为什么用这个不等式sorted_cum[i]+k >= sorted_cum[j]
使你打错了造成了我们的误解吗？
假设i〉j s[i]-s[j]>=k 才是我们要的， 还是 这里有什么深意呢？求解释？
然后你是要找刚好满足条件的，这个binary search 似乎不能保证找的的是刚好满足条
件的临界位置，只能保证满足条件，所以这里要找到刚好满足条件的那个按你的算法似
乎还是要n*n。
然后
你这里的
min_index[] = {1, 1, 1, 1, 1, 1, 1, 6, 6, 10, 10}
max_index[] = {11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10}
的实际物理意义是当前sorted cum array 当前对应的坐标后的元素中... 阅读全帖 |
|
|
y******5
发帖数: 43 | 31 Thank you for your post.
2 念了一段code, 问我什么问题
int f(int x) {
if(x==1) return 1;
return x*f(x-1);
}
Problems:
(1). x<0
(2). overflow
4 一个int数组, 给你一个sum, 找出和是sum的两个int
solution 1: hash table, time complexity O(n), space complexity O(n)
solution 2: sort in-place, time complexity O(nlgn), space complexity O(1) |
|
f*********i
发帖数: 197 | 32 That is not correct, the DP can be O(nlgn)
however, it need O(n) space, that is a problem.
The idea of DP goes like it:
int num = Integer.MAX_Value;
for(int i=1;i*i
if(num > a[i*i]+a[n-i*i])
num = a[i*i]+a[n-i*i]
}
a[n] = num;
a[1]=1,a[2] =2,a[3] = 3, then use DP from n>=4
For each n, it need to compare logn times, overall time complexity is O(
nlogn) which is less than O(n^(3/2))
DP is O(n ^ (3/2) ) .
减枝不好算。不过，即使是Math.Int, 大于2B的数值，访问的node也不超过10万个（不
记得是4千还
是4万多）。
我程序里面统计了访问次数 |
|
g**e
发帖数: 6127 | 33 wiki后面提供了一个O(nlgn)的，用到binary search |
|
g***s
发帖数: 3811 | 34 lijiang give a function my_swap with O(1) -- assume flip is O(1)
then you can use the my_swap function to implement O(nlgn) algorithm |
|
g**e
发帖数: 6127 | 35 第六题有比O(n)更快的方法吗？除了interval tree?但是建立树就要O(nlgn)了
new
3,
interval, |
|
g*********s
发帖数: 1782 | 36 what is the complexity requirement?
i think O(NlgN) is easy to come up with. |
|
g*********s
发帖数: 1782 | 37 赞。
n就可以吧？如果递减不成立就去更新递增，反之亦然。
相等？应该和先后抛无关吧。就像经典抽签问题，谁先抽都一样。
O(NlgN). what do you mean by "why" here?
what is this? |
|
g*********s
发帖数: 1782 | 38 正整数的数组x[1..n]，分成k段，找分段法，minimize the maximum sum of any
pieces,
minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
dp:
f(n,k) = min { max { f(i,k-1), sum(x[j]) | i = 1..n, j = i+1..n } }
这个复杂度是O(K*N^2)，可以加速到O(K*NlgN)？
如果输入改成非负整数数组呢？
如果改成任意整数呢？
二分法要求必须是正整数吧？ |
|
m**q
发帖数: 189 | 39 这个思路不错。
感觉应该需要一些额外空间来记录start[]和end[]两个数组元素的对应关系，不过额外
空间也是O(n)的。
重复起点的问题可以在O(n)时间解决，最后扫一遍数组，减掉重复计算的值就行了。
ps:另外一种统计个数的方法是对每个区间二分查找，不用额外空间，不过就是O(nlgn)了 |
|
d*******l
发帖数: 338 | 40 嗯，不过需要先排序所以还是O(nlogn)。上面讨论的区间树我有点记不清具体内容了，
但感觉如果建树再对每个区间查找所有overlap的区间，应该也不会好于O(nlogn)了吧
。不知有没有本质上更好的办法
nlgn)了 |
|
|
|
|
w**n
发帖数: 122 | 44 面了四个人(都是Sr. MTS) + HM
前面两个，感觉还可以。不会的，稍加提示，就答出来了。
HM带着吃午饭，没有技术问题，基本都是behavior问题，或者就是介绍他们现在做的东
西。
下午是两个女工程师，感觉就很差
有个女印印，问了很多怎么debug dump file的问题。这个弄得我很头疼。
而且明明我不是很在行， 她还不停地摁着这个方向反复问。
另外一个表情很严肃，老是皱眉头。跟她说话也很费劲。她连什么时候是call copy
constructor和什么时候call operator=都分不清楚。她问了不少database的问题，但
是我简历上完全没有DB经验。哎。。。
算法问得不太多， 也就问问概念层面的东西， 没让写程序
有什么排序算法， 各个的效率怎么样
什么情况下O(n^2)会比O(nlgn)效率更好
coding办（C++）问得很细， 概念问了很多
什么时候应该用initialization list
virtual inheritance
multi inheritance
virtual function
virtual constrctor/destru... 阅读全帖 |
|
h****a
发帖数: 70 | 45 这个怎么答？
什么情况下O(n^2)会比O(nlgn)效率更好？ |
|
c********l
发帖数: 8138 | 46 我觉得问题的本意好像不是这个
而是说什么情况下算法复杂度为O(n^2)的排序算法（如冒泡）
比O(nlgn)的排序（快速）效率更好？ |
|
m**q
发帖数: 189 | 47 程序有点没看懂，看描述复杂度是O(n^2)?
这题应该可以O(nlgn)的
.. |
|
H****s
发帖数: 247 | 48 这题就是 weighted interval scheduling 吧。 每个conference 的 weight就是它的
长度， 然后要求就总weight最大。 DP 就可解一般O(n^2), 使用特殊数据结构可以O(
nlgn) |
|
c*******n
发帖数: 63 | 49 1.sort three array first --> nlgn
2.1 form the first two elements --> n^2
2.2 find the third element of triplet --> lgn (binary search)
or as justcoder said, hash the third array, then the searching will be
O(1)
==> O(n^2 * lgn) or O(n^2) |
|
f****4
发帖数: 1359 | 50 来自主题: JobHunting版 - 问道排序题 应该没有吧
假设存在O(nlgn)，则有
T(n) = 2T(n/2)+f(n)
需要f(n) = O(n)
考虑2n+1个数
n个1， n个3
3 3 3 3...3 1 1 1 1...1 2
用reverse()改成
1 1 1 1...1 2 3 3 3 3...3
需要 f(n) = n + n*( (n+1)+n) = O(n^2)
最后需要的run time 是O(n^2) |
|
