g*********s
发帖数: 1782 | 1 No, I don't see how your code can handle it. |
|
t*****j
发帖数: 1105 | 2 做好情况O(nlgn),最差情况还是O（n2）。
is |
|
b*****e
发帖数: 474 | 3 1) 我采用的是对分法，mid = (start+end)/2。当然是 2 T(n/2) 了
2) 这个。。。 很容易自己验证一下嘛。代码都给出了，有疑问的话，
构造一组输入，比如
int a[] = { 1,1,1,1,1,1,1,4,4,4,1,1,1,1,1,1 }; // 答案是16
看看和心目中所想是不是一样。 |
|
g*********s
发帖数: 1782 | 4 no, i don't get it. ur half-cut method is different with what I posted.
in addition, i don't think one test case can justify the correctness
algorithm.
can u verbally describe ur idea? the key is how to maintain the optimality
when u merge the 1st/2nd half optimal solution and the optimal solution
crossing the pivot. |
|
|
b*****e
发帖数: 474 | 6 OK, 左右两半的最大矩形面积可用递归得到，不多说了。
横跨中间的矩形，最高就是 height = table[mid], 长度可以向两边
搜索得到。
搜索过程中，或者遇到边界，或者在遇到边界前碰到降低的高度。这个时候
就取下一个最高的高度，然后继续向两边搜索在新高度下的最大边长。
这个过程中记录下最大面积的那个就行了。
这个从中间向两边搜索的过程有点像 merge-sort 里的 merge 过程，是
个简单的 O(n) 过程。 |
|
g*********s
发帖数: 1782 | 7 你这样解释一下就对了。这个方法可行，不过和我原帖的思路不一样。 |
|
l******y
发帖数: 472 | 8 有谁能讲讲那个用stack做的O(n)的算法么？上面的链接里说的没看明白
还有请问lz，dp做到O(n) ? thanks |
|
|
l****y
发帖数: 44 | 10 面的是business platform division 的SQL Server team。我简历上一个DB的keyword
都没有，我连DB的课都没上过，不
知道他们怎么选的。尽管这样，题目全是基本的算法和coding，没有考DB的任何问题。
可惜我还是表现很差，感觉脑子进
水了（或者是进seattle的雨了）。面试从12：30开始（本来说是10点，临时改了，说
是他们上午有会），见了4个人。3
个是印度人，还有一个不知道是什么国籍的。
我就把所有technical的题罗列下来吧。很多都是常见题。
给一个array of integers, 需要多少个comparison能找到min? how about min and
max? what's the best worst-
case? (3n/2)
怎么merge两个sorted的array，n 个呢？
给一个tree，把同层的nodes都连起来，assume每个node都有个指针，你要让它指向下
一个同层的node。
count 1's in an integer.
mergeSort, mergeSort without r... 阅读全帖 |
|
d****j
发帖数: 293 | 11 我就把所有technical的题罗列下来吧。很多都是常见题。
1. 给一个array of integers, 需要多少个comparison能找到min? how about min and
max? what's the best worst-case? (3n/2)
====>
n-1 comparison to find min
两两比较之后再在大的一堆中找大的，小的一堆中找小的
n/2 + n/2 - 1 + n/2 -1 = 3n/2.
记得MIT Algorithm (CLRS)上面有提到这个。
2. 怎么merge两个sorted的array，n 个呢？
====>
两个很容易，n个的话，用每个array的第一个元素构建一个heap，再heap sort，每挑
出一个值，再去对应的array中取一个值添到heap中。具体实现可能要修改数据结构。
3. 给一个tree，把同层的nodes都连起来，assume每个node都有个指针，你要让它指向
下一个同层的node。
====>
见 ihas1337code 的blog：
http://www.ihas1337code.... 阅读全帖 |
|
g*******s
发帖数: 490 | 12 就是有2个linkedlist，size都为n, 他们可能merge，就是share at least on common
node，问怎么判断是否merge，找
那个common node.
naive的方法就是2个loop，比较address了。o(n squre)
我想了个方法就是，2个list按address排序，这样是o(nlogn)，然后比较address in
two sorted list, 这样是o(n)。
还有更好的办法么？ |
|
j*****u
发帖数: 1133 | 13 帮作者(我的朋友)说几句，他们基本上都是用工作之余的私人时间写的这本书，当时时
间很仓促，我觉得第一版这个水准已经很不错了。
另外我觉得这个题在下一页解释的还是比较清楚的。
以中线二分的时候，已经知道了左右两区间的最小距离，MDist是其中的小者，那么考虑
过中线的pair时就可以排除所有在中线左右MDist之外的所有点，因为他们之间的距离肯
定大于MDist。所以BD可能比CD距离更小，但是BD不可能小于MDist所以可以不予考虑。
这样，每次二分我们只需要考虑中线左右MDist区间的点，对左边MDist内的每个点，在
右边区间最多只可能有6个点距离
直维护一个按y坐标sort的点的list，在中间区域找最小点对就是O(n)的
所以整个算法是O(nlogn)的
不知道我解释清楚了没有。
短， |
|
C*****n
发帖数: 1872 | 14 sort完，两数组直接从头比较就可以了吧
虽然最后还是O（nlogn)，但是比较的这部分就降为O(n)了 |
|
f*********i
发帖数: 197 | 15 The solution costs O(nlogn) for sorting
However, since this array is already sorted, there is an O(N) approach
public static int array_sortedArray_find_close_to_zero(int[] arr){
int first=0,last = arr.length-1;
int sum = arr[first]+arr[last];
int min_to_0 = Math.abs(sum);
while(first
sum = arr[first]+arr[last];
if(Math.abs(sum)
min_to_0 = Math.abs(sum);
if(sum>0)
last--;
else if(sum<0)
... 阅读全帖 |
|
i**9
发帖数: 351 | 16 1 load all schedule to a arraylist/vector, 所有行程按start time sort（根据要求
选sort algrithm O(n)(radix/counting) or O(nlogn)）, 然后从头走一遍 ending
time 跟后面的 start time 比较，如果有 conflict 就做mark 并且用老的endtime跟
当前
endtime比较 做 更新,
2 harsh
3 dutch national flag
4 这种题看着头晕，需要细心和耐心 |
|
M7
发帖数: 219 | 17 First 电面:
1. 谈一下不同数据结构的优缺点。
2. 一个大文本文件里有电话号码。每行至多有一个号码。How do you process and
return the total number of phone numbers. (in command line, use grep and wc)
3. A generic tree. how to print out nodes by level (one lever a line)
说了pseudo code, 要求电面后email给他。
4. A database application is slow. How do you investigate the problem and
how to improve it.
Second 电面:
1. 写一个函数，输出一个整数里1-bit的数目。比如CountOneBits(7)应返回3。
2. 网页很慢。找出可能原因。（和一面的最后一个问题差不多）
3. 下面statements的区别是什么？接着问了关于constructor的问题(copy), shallow
vs. d... 阅读全帖 |
|
|
p*****n
发帖数: 368 | 19 来自主题: JobHunting版 - 问一算法题 这种题估计就是每次对半分，然后递归，总的complexity变成O(nlogn) |
|
c******t
发帖数: 391 | 20 How about this one? Is this O(NlogN) solution?
#include
#include
using namespace std;
void finddup(int arr[], int length){
hash_map hm;
cout<
for(int i=0; i
hm[arr[i]]++;
}
hash_map::iterator it;
int dup=0;
for(int i=0; i
it=hm.find(arr[i]);
if(it->second>1){
dup=it->first;
cout<
}
}
cout<
}
void main(){... 阅读全帖 |
|
v*******7
发帖数: 187 | 21
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... 阅读全帖 |
|
h**********d
发帖数: 4313 | 22 我一开始就说了个nlogn的bst insertion，他说要o(n)的，不在乎space
然后我就说了这个笨办法，不知道有没有更好的，不过他seems满意
直接的 |
|
b*******s
发帖数: 5216 | 23 heap sorting O(nlogn)
然后就可以说这是BST了
root是n/2的点
左child是 n/4 ,右child是3n/4
一路二分下去
仅仅是各层节点没有按顺序存放而已 |
|
C***y
发帖数: 2546 | 24 why not quick sort on the heap?
这样的话还是O(nlogn),但是不需要额外空间
———————————————————
俺错了，heap sort是O（1）的空间 |
|
v*****d
发帖数: 348 | 25 公司名就不说了，估计版上没几个人听说过。个人觉得挺难的，主要是以前没碰到过
给一个array, 判断是否有subarray的sum是0. 要求O(n)算法
给一个array, 给一个given number k, 给出最长的subarray的length, 这个subarray
的sum大于或等于k.要求O(nlogn)算法
被那个经典的maximal sum subarray的题误导了，一开始就没想到正点上去。都是面试
官给了hint才做出来，悲剧。。move on了 |
|
b*m
发帖数: 34 | 26 似乎现在的解法都不太完美。
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 当前对应的坐标后的元素中... 阅读全帖 |
|
M7
发帖数: 219 | 27 面试里也就粗略地说一下，linear, NlogN, quadratic ....
那些NP, P-space ... Polynomial hierarchy的东西只有做理论的人才研究的。
不过回想当时钻研Garey & Johnson的时候，还是挺好玩的。 |
|
w**********l
发帖数: 8501 | 28 靠，一群似懂非懂的外行在这扯淡。google那两 ceo读书的时候，做什么的知道吗？
As of November, 1997, the top search engines claim to index from 2 million (
WebCrawler) to 100 million web documents (from Search Engine Watch). It is
foreseeable that by the year 2000, a comprehensive index of the Web will
contain over a billion documents
这就是算法复杂度的意义， big O（n）都是不能承受之重，更别说动不动就O(nlogn)
了。 |
|
r********3
发帖数: 2998 | 29 那你知道Google真的优势是在于Map-Reduce的并行计算和存储系统，GFS这些不?
Google那种级别的海量存储，关键在于存储I/O，进程调度这些的优化。至于实际的算
法，用来用去都是O(n)，实际差别太大了。
学校里面研究算法分析，只看什么O(n),O(nlogn),O(n^2)，和工业界比起来。太native
了，太simple了。
更何况，同样一个O(n)的算法，能够在内存，还是外存实现，千差万别。你不会不知道
硬盘的速度比内存慢1000倍吧。还有，你访问数据的顺序，周期，对你的算法影响也很
大。你知道为什么CPU总线速度，CPU的L2 Cache那么重要？那才是决定你的计算速度的
优势，不是说你写几页纸，证明你的算法是一个O(N)，你就牛了。
( |
|
j*****u
发帖数: 1133 | 30 如果把binary tree转成double linked list的话，时间是O(nlogn)肯定可以，时间O(n
)空间constant的还没想到。
假设树是满的，要么用logn的辅助空间暂存node，要么用logn的时间去找到没有或只有
一个child的node。是不是有什么tricky的办法？ |
|
B*M
发帖数: 1340 | 31 http://en.wikipedia.org/wiki/Longest_increasing_subsequence
Efficient algorithms
The algorithm outlined below solves the longest increasing subsequence
problem efficiently, using only arrays and binary searching. It processes
the sequence elements in order, maintaining the longest increasing
subsequence found so far. Denote the sequence values as X[1], X[2], etc.
Then, after processing X[i], the algorithm will have stored values in two
arrays:
M[j] — stores the position k of the smallest val... 阅读全帖 |
|
|
B*M
发帖数: 1340 | 33 我run了程序，去掉P，一样可以返回数组，
不知道是不是我的test case太简单了，
我试了好几个，都没试出来，P什么时候才是必要的，
分析也看不出来，好像M就足够了， |
|
j*****u
发帖数: 1133 | 34 没有仔细看wiki，如果要返回数组是需要2个array的
比如这个例子: 5 6 7 1 2
最终M = {3, 4, 2}，如果没有P，返回的数组就成了1 2 7而不是5 6 7了。 |
|
a***y
发帖数: 547 | 35 try 10 20 30 40 50 1 2
what in M would be 1 2 30 40 50 |
|
|
|
|
|
|
m*****y
发帖数: 120 | 41 yes, sort is nlogn, and here n is actually n*n, so it is n*n*log(n*n) => n*n
*logn. |
|
z****o
发帖数: 78 | 42 这个是标准的Suffix Array的 nLogn 吧 |
|
z****o
发帖数: 78 | 43 先构造后缀：
abcabcdfabcdf
bcabcdfabcdf
cabcdfabcdf
abcdfabcdf
bcdfabcdf
cdfabcdf
dfabcdf
fabcdf
abcdf
bcdf
cdf
df
f
之后排序,并且计算相邻string的longest common prefix长度：
0 abcabcdfabcdf
3 abcdf
5 abcdfabcdf
0 bcabcdfabcdf
2 bcdf
4 bcdfabcdf
0 cabcdfabcdf
1 cdf
3 cdfabcdf
0 df
2 dfabcdf
0 f
1 fabcdf
然后要最长的就是那个 5， 最多的就是连续正数的最大长度+1 = 3
整个计算过程是 nLogn的 |
|
e****a
发帖数: 449 | 44 . 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非
湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针
对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司:
Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公司。 有一
点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经验
,
j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统和网络的基本知识, 还有就是
经常在
mitbbs 学习大牛们的帖子. 整理了版上一年内的 和 careercup 上的一些面经, 比较
乱, 大家
可以参考下, 基本上概括了店面的所有题，onsite的大部分题. 非常感谢版上的常驻大
牛小牛们给
我的帮助，现在牛牛们都忙着发财... 阅读全帖 |
|
l******t
发帖数: 2243 | 45 congrats!
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
. 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非
湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针
对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司:
Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公司。 有一
点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经验
,
j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统和网络的基本知识, 还有就是... 阅读全帖 |
|
f*********i
发帖数: 197 | 46 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万多）。
我程序里面统计了访问次数 |
|
F**********r
发帖数: 237 | 47 一个任意的数组，找出一个严格单调递增的最长子序列。只知道怎么用dynamic
programming.求一个nlogn的算法。谢谢！ |
|
R***i
发帖数: 78 | 48 公司名就不说了
题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。
比如[1,2,0] return 3, [3,4,-1,1] return 2
我给了2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of
integers， time O(n), space O(n)。 但面试的人告诉我都不是最优解，有time O(n)
, constant space的解。。。现在都没想明白，大家集思广益吧 |
|
f***g
发帖数: 214 | 49 0.02
如果不是inplace，就找个数组临时存一下。
要排序，所以O(nlogn)
如果是inplace，就先变成linked list
排序，再变回来。O(n^2)
复杂度都不低，楼主要不咱私下讨论讨论？ |
|
a******7
发帖数: 106 | 50 poster-order walk on binary tree, take each node and insert into new binary
search tree, with only pointer manipulation, time complexity O(nlogn) |
|
