m**q
发帖数: 189 | 1 如果是求最近的k个的话，先把每个点和其他点的距离按远近排序，
空间O(n^2)，查找最近的k个复杂度O(k)，如果只查第k个的话O(lgn)
以后很快能得到解答的方法??? |
|
l*********c
发帖数: 29 | 2 感恩节前去了趟amazon onsite，被面的是traffic组里的一个新成立的小team。以下是
我遇到的面试题，另外还附加了一些其他公司的面经。接下来几天就要出结果了，求祝
福。
1.写一段程序比较两棵树是否一样。
2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
的节点。问如何实现clone函数。
3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
6.如何求一个树的mirror（将所有节点的children节点反序排列）.
7.下面这道题目是吃饭的时候问的，题目比较长，大概的意思是,现在亚马逊希望通过
facebook寻找拥有共同爱好的用户，并推荐那些用户所购买的商品给这个用户。如果这
个新用户刚刚通过facebook连接到am... 阅读全帖 |
|
n*******w
发帖数: 687 | 3 bless！
1.写一段程序比较两棵树是否一样。
常见题。
2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
的节点。问如何实现clone函数。
最近版上刚讨论过。先creat big linkedlist然后split。
3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
经典算法。两个stack，一个操作数，一个操作符。写代码其实不简单，要定义操作符
的优先级。
4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
经典题。允许O(n)空间，hashtable。否则先sort，一前一后两个指针往中间找。
5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
版上最近刚讨论过。递归或者iterative都有。
6.如何求一个树的mirror（将所有节点的children节点反序排列）.
跟遍历similar。
7.下面这道题目是吃饭的时候问的... 阅读全帖 |
|
O******i
发帖数: 269 | 4 看去比二分法求方程的根要难些，应该怎么做？为什么最坏情况是O(n)呢？
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
现在给定一个函数，f(x),x在某值之前是非递减的，在某值之后是非递增的。设计一个
算法快速查找这个值。我给出的算法最坏情况是O(n)，平均是O(lgn)，但是很可惜没来
得及写完。
跟离散的情况类似。比如一个数组n个元素，先递增然后递减。找到最大元素的index。
类似binary search。版上最近也讨论过。连续的情况，给定x0，要比较f(x0)与f(x0+
delta)的大小然后binary search。delta是答案的精度。 |
|
c********1
发帖数: 52 | 5 size N 的min-heap
复杂度 lgN * 数组长 |
|
O******i
发帖数: 269 | 6 最近面了一家IT大公司被拒，一共经历了N轮技术面试。自己感觉还不算太坏，但也有
三轮发挥不太完美，所以心里很没底。
结果还是被拒了。
下面是这三轮的详细经历，请大家探讨一下大公司招人的标准。
第i轮是找二叉树从根开始的所有路径，使得该路径上所有节点的值之和等于一个给定
的数。我犯了一个战略错误，因为我在准备过程中看过CarrerCup的更通用的解法，不
要求从根开始，也不要求到叶子结束，于是我直接用了那个思路，在白板上写下了类似
下面的代码
void FindPath(Node* root, int sum, int path[], int level)
{
if (root == NULL)
return;
int s = 0;
for (int i = 0; i < level; i++)
s += path[i];
int value = root->data;
if (s + value == sum)
PrintPath(path, level, value);
path[leve... 阅读全帖 |
|
O******i
发帖数: 269 | 7 嗯，只有在当前节点发现匹配的时候才打印path, 不是每个节点都要打印。
杀鸡用牛刀真是弄巧成拙啊
从根开始的解法用鸡刀就可以了，O(N)
不一定从根开始的解法要用牛刀，O(N*lgN)
题目要求从根开始，用牛刀做，复杂度大了，而且面官会怀疑你是背题啊。 |
|
a********m
发帖数: 15480 | 8 后一半好像是有问题。固定增长的均摊是o(1)。指数增长应该是o(lgn/n)吧。 |
|
H***e
发帖数: 476 | 9 蒽
是的， 最坏是O(lgn)
但是总和是O(n)锕，就是泥打印出来整个inorder traversal,每条边被经过两次
就是inorder traversal的路径
balanced |
|
i******r
发帖数: 793 | 10 Fibonacci直接递推就是O(n)了
其实可以做到O(lgn)，如果你知道公式甚至是O(1)
1) |
|
i***h
发帖数: 12655 | 11 你在排序里面二分法找一个数不得 O(lgN)? |
|
i***h
发帖数: 12655 | 12 对这个问题, 时间是 O(lgN + N), 也是O(N) |
|
h******i
发帖数: 30 | 13 除2个整数不能用乘除.那位给个O(lgn)的解法阿？我只知道O(n)的 |
|
o*******y
发帖数: 115 | 14 度娘的答案。。。
利用快速排序的原理，我们可以在不使用额外数组的情况下达到O(n)的效率，原理为：
取1到n的中间值m = (1 + n)/2，用m将数组分成A1, A2两个部分，A1中的元素全部小于
等于m，A2中的元素全部大于m（注意此处用的是下标，而不是A[m]），如果A1的大小为
m，则空闲元素在A2中，这在前面证明过，然后就在A2中应用同样的方法。
MIN-AVAILABLE-NUM(A, low, up)
if(low == up) return low
m = (low + up) / 2
split = partition(A, low, up, m)
if a[split] == m
then return MIN-AVAILABLE-NUM(A, low, split)
else return MIN-AVAILABLE-NUM(A, split+1, up)
这里递归式为：T(n) = T(n/2) + O(n)，根据主定理的第三种情况，复杂度为O(n)，其
实也就是一个等比数列：n + n/2 + n/4...
但是，此处因为用到递归，所以空间... 阅读全帖 |
|
c*****n
发帖数: 96 | 15 Sort all N intervals by begin and end time respectively, saying B[] and E[]
, for each Interval I(begin, end), find number of intervals with begin time
later than I.end, A, and number of intervals with end time early than I.
begin, B. Then the the number of intervals intersecting with I is N - A - B
- 1. As B[] and E[] are sorted array, A and B can be calculated in lgN, so
total time is nlogn. |
|
c*****n
发帖数: 96 | 16 Sort all N intervals by begin and end time respectively, saying B[] and E[]
, for each Interval I(begin, end), find number of intervals with begin time
later than I.end, A, and number of intervals with end time early than I.
begin, B. Then the the number of intervals intersecting with I is N - A - B
- 1. As B[] and E[] are sorted array, A and B can be calculated in lgN, so
total time is nlogn. |
|
c***g
发帖数: 472 | 17 Given a matrix in which each row and each column is sorted, write a method
to find an element in it.
上面给的算法是，从最右上角开始找起，然后每次去掉一行或者一列。
我有如下疑问
1） 如果从左下角开始，也是对的吧，每次去掉一行或者一列；
2） 这个算法的时间复杂度应该是N*M吧？
3） 可以更加优化么？ 每次找的时候，用二分发找到那个数所在的区间，就是恰好找
到一个大于它的，一个小于它的，这样时间复杂度不就是(lgM * lgN)？
|
|
c***g
发帖数: 472 | 18 Given a matrix in which each row and each column is sorted, write a method
to find an element in it.
上面给的算法是，从最右上角开始找起，然后每次去掉一行或者一列。
我有如下疑问
1） 如果从左下角开始，也是对的吧，每次去掉一行或者一列；
2） 这个算法的时间复杂度应该是N*M吧？
3） 可以更加优化么？ 每次找的时候，用二分发找到那个数所在的区间，就是恰好找
到一个大于它的，一个小于它的，这样时间复杂度不就是(lgM * lgN)？
|
|
e***l
发帖数: 710 | 19 从答案[3,5,3,3,0,2,1,0]推不出来排序的结果，所以先sort的话做了多余的操作。从
后往前建堆，虽然是n次lgn的binary search，但是这个级数能收敛到O(n)。你看书上
建堆的分析。这样应该是对的。 |
|
q******8
发帖数: 848 | 20 int[] smaller_on_right(int[] array){
int length = array.length;
int[] result = new int[length];
ArrayList arraylist = new ArrayList();
for(int i=0; i
arraylist.add(array[i]);
}
Collections.sort(arraylist);//nlgn
for(int j=0; j
result[j] = Collections.binarySearch(arraylist, array[j]);//lgn
arraylist.remove(result[j]);//这步如果是array的话，算法就不是
nlogn了，不过如果是linkedl... 阅读全帖 |
|
e***l
发帖数: 710 | 21 从答案[3,5,3,3,0,2,1,0]推不出来排序的结果，所以先sort的话做了多余的操作。从
后往前建堆，虽然是n次lgn的binary search，但是这个级数能收敛到O(n)。你看书上
建堆的分析。这样应该是对的。 |
|
q******8
发帖数: 848 | 22 int[] smaller_on_right(int[] array){
int length = array.length;
int[] result = new int[length];
ArrayList arraylist = new ArrayList();
for(int i=0; i
arraylist.add(array[i]);
}
Collections.sort(arraylist);//nlgn
for(int j=0; j
result[j] = Collections.binarySearch(arraylist, array[j]);//lgn
arraylist.remove(result[j]);//这步如果是array的话，算法就不是
nlogn了，不过如果是linkedl... 阅读全帖 |
|
D********g
发帖数: 650 | 23 面经回馈本版，只列出technical question.
P1:
A. Add next pointer to each node on a BTree to its next sibling on the same
level.
B. Boggle题，find all possible words from a 2D character array.
P2:
A. Given
interface Iterator {
T next();
boolean hasNext();
}
interface Predicate {
boolean accept(T t);
}
Implement a method that creates an "accept" iterator that returns items
accepted by the passedin pred variable.
Iterator conditionIterator(Iterator input, Predicate pred) {
}
B. Concurren... 阅读全帖 |
|
d******a
发帖数: 238 | 24 写个简单的啊，O(lgn)时间，O(1)空间。
const int ROW = 100;
const int COLUMN = 50;
int get_value(int a[][COLUMN], int m, int n, int pos)
{
int row_pos = pos / n;
int col_pos = pos % n;
return a[row_pos][col_pos];
}
bool binary_search(int a[][COLUMN], int m, int n, int target)
{
int middle;
int start = 0;
int end = m * n - 1;
int middle_value;
while(start <= end)
{
middle = start + (end - start) / 2;
middle_value = get_value(a, m, n... 阅读全帖 |
|
l*****a
发帖数: 14598 | 25 估计笔误，O(lg(M*N)) or O(lgM+lgN) |
|
t**********h
发帖数: 2273 | 26 你的这个题目是150上的原题，O（M+N）可以做。
另外之前版上有讨论一道和这个相似的题，但是matrix本身有一个附加条件，即下一行
的对应的element比这一行的这个element也要大。所以最终就转化为一个一维排好序的
数组了，然后二分O（lgn） |
|
d****o
发帖数: 1055 | 27 Time average O(lgn) worst O(n)
int findSubInt(string in,int mid,int& subBegin,int& subEnd){
subBegin=mid;
subEnd=mid;
while(in[subBegin]!=' '){
subBegin--;
}
if(in[subBegin]==' ') subBegin++;
while(in[subEnd]!=' '){
subEnd++;
}
if(in[subEnd]==' ') subEnd--;
string subStr = in.substr(subBegin,subEnd-subBegin+1);
return atoi(subStr.c_str());
}
bool findInt(string in, int target){
int begin =0;
int end... 阅读全帖 |
|
t*********7
发帖数: 255 | 28 Update:
上周五面的,刚接到HR电话,GG了...原因不清楚...
面试官一,白哥,N连击
面完之后,说了一大堆夸人的话
面试官二,白爷,HM,陪吃饭,聊天
面试官三,烙印, BAR RAISER,问了四个问题
一,用队列实现栈 (我用两个队列,一个只有出栈的时候用来做临时存储空间)
二,他说能不能进栈,出栈都是时间常数开销,我说可以实现双头队列,两边都能进出的,
他说好的.
三,21点游戏,要求就是很多人可以一起玩,然后,玩的时候玩家可以跟发牌器换牌等等,
设计完,还写了一个主方法,他说没问题.
四,实现栈有返回最大值最小值方法,这个老题,大家都懂的.
从头到尾没有表情.
面试官四,白爷,PM, 设计哈希表,包括动态申请存储空间,解决冲突,设计哈希方法等等.
搞完,
说了一大堆夸人的话.
面试官五,白哥,其他组的编程师, 谈简历,还有常规问题,比如你跟老板意见不合之类的.
面试官六,白哥,其他组的PM, 序列化和反序列化二叉树.
前序遍历,空节点用特殊符号代替,序列化,LEETCODE上有
反序列的时候他说输入是个字符串,所以在递归的时候用了一个整数变量模拟输入流的
得到下一个... 阅读全帖 |
|
t*********7
发帖数: 255 | 29 Update:
上周五面的,刚接到HR电话,GG了...原因不清楚...
面试官一,白哥,N连击
面完之后,说了一大堆夸人的话
面试官二,白爷,HM,陪吃饭,聊天
面试官三,烙印, BAR RAISER,问了四个问题
一,用队列实现栈 (我用两个队列,一个只有出栈的时候用来做临时存储空间)
二,他说能不能进栈,出栈都是时间常数开销,我说可以实现双头队列,两边都能进出的,
他说好的.
三,21点游戏,要求就是很多人可以一起玩,然后,玩的时候玩家可以跟发牌器换牌等等,
设计完,还写了一个主方法,他说没问题.
四,实现栈有返回最大值最小值方法,这个老题,大家都懂的.
从头到尾没有表情.
面试官四,白爷,PM, 设计哈希表,包括动态申请存储空间,解决冲突,设计哈希方法等等.
搞完,
说了一大堆夸人的话.
面试官五,白哥,其他组的编程师, 谈简历,还有常规问题,比如你跟老板意见不合之类的.
面试官六,白哥,其他组的PM, 序列化和反序列化二叉树.
前序遍历,空节点用特殊符号代替,序列化,LEETCODE上有
反序列的时候他说输入是个字符串,所以在递归的时候用了一个整数变量模拟输入流的
得到下一个... 阅读全帖 |
|
Z*****Z
发帖数: 723 | 30 我觉得直接上K way merge可能不是最优的。
假设N个数组，每个数组里有N个数，一共有N^2个数，（最大）堆的size也是N。Kway m
erge的复杂度是O(N^2 * lgN)
如果不用堆，而用一个size 为N的数组存储N个指针，每个指针指向自己的数组，可以做
到O（N2） |
|
c***p
发帖数: 221 | 31 cool! 用heap的确浪费时间了, 每排除1个数要花费logN个比较。
学习了！
如果时间复杂度允许是O(N^2 * lgN)，那么空间复杂度可以降到O(1)。
m
以做 |
|
|
A**u
发帖数: 2458 | 33 都是O(1)操作，好像比较拿实现。
先不说getProcessID,
就 说free过程，至多是O(lgN)吧 |
|
Z*****Z
发帖数: 723 | 34 Note k is between 1 and n-1. As k approaching n-1, your algorithm should con
verge to O(n lgn) naturally :) |
|
l*****a
发帖数: 14598 | 35 数组sort就是nlgn
你字符串sort算是n^2*lgn吧 |
|
b****o
发帖数: 59 | 36 又Fail了，已经是连续两年了
1 An array with n elements which is K most sorted. 就是每个element的初始位置
和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster
than O(n*lgn)
2 Paint 一块画板上的区域。从一个点出发，直到所有相邻的和出发点一样颜色的点都
paint 上需要的颜色
3 又一个排序好的不知道长度的数组，在其中search 一个给定值
4 1..n 这些数有两个missing,find out which two are missing. |
|
p**********e
发帖数: 316 | 37 试着答一下：
1） nlgK: sort first k elements first, then determine elements one after
another
2) ???
3) lgn, pretty easy
4) O(n), use bit array, space can be O(n)/32 |
|
c****g
发帖数: 85 | 38 Question: Find the k-th Smallest Element in the Union of Two Sorted Arrays
Given two sorted arrays A, B of size m and n respectively. Find the k-th
smallest element in the union of A and B. You can assume that there are no
duplicate elements.
http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-u
如果A组划k/2，B组划k/2来比较。为方便解释，这里先假设k为偶数,并且m,n>k/2.
如果不满足这些条件，在计算index的时候，会考虑这些情况。
if A[k/2 - 1] == B[k/2 -1] done.
if A[k/2 - 1] > B[k/2 -1]
那么在A[k/2 + 1 - k] 和 B[0 k/2 - 1] 里取k/2 smallest number。
... 阅读全帖 |
|
|
|
n******n
发帖数: 567 | 41 LZ, 我觉得这么修改一些就对了。
void fun(Node roota, Node rootb){
Node x = findRootaInTreeB(roota, rootb);// O(lgn) time
rotateTreeB(rootB,x);//rotate x as the new root of tree B // O(1) time
//continue your algorithm.....
}
时间还是O(n) |
|
K********m
发帖数: 31 | 42 目前我能想到最好的建最小堆 (lgm+lgn)
当然了，建堆也需要时间的 |
|
K********m
发帖数: 31 | 43 目前我能想到最好的建最小堆 (lgm+lgn)
当然了，建堆也需要时间的 |
|
f*********i
发帖数: 197 | 44 Iterative inorder, when meet a leaf node, such node together with the nodes
in the stack form a path.
Time O(n)
space O(lgn) |
|
l****p
发帖数: 397 | 45 第一通电话：
听口音应该是老印的，有点口音，面试过程中好几次我都没听清反复问。
上来没寒暄几句就写代码：
找出一个树中最深的结点。
明显留了好多细节让我问，于是我开始clarify:
1. 是不是binary tree。答：good question, yes, assume it's a binary tree
2. 是不是balanced binary tree。答：does that matter? 我边想边说，好像没关系
然后我再也想不出其它问题了。开始想算法。想一半，他才提醒我说还有一个细节我没
问：如果有多个最深结点怎么办。回答是返回最右的。这是一个失分的点
然后解释算法，可以用深度优先遍历也可以用广度优先遍历，记录所有叶节点的深度，
然后找出最深的。他问复杂度，我说时间是O(N), 空间是O(N). 他说空间能优化吗？我
说能， 在遍历过程中只记录最深的就行。他问这下的空间复杂度，我说是O(1) 。然后
让我开始写代码，我说深度优先呢还是广度优先，他说有什么区别，我说差不多，然后
想想不对，广度优先需要一个queue，这是O(N)的空间，深度的只要O(lgN)的空间，这
... 阅读全帖 |
|
h****n
发帖数: 1093 | 46 第一题，随手写了DFS和BFS，请指教
TreeNode* GetDeepestNode(TreeNode* root)
{
TreeNode* res=NULL;
int curLevel=1,preLevel=0;
DFSHelper(root, res, curLevel, preLevel);
//BFSHelper(root, res);
return res;
}
//Time O(n) space 不算递归栈则O（1） 算的话 O(lgn)
void DFSHelper(TreeNode* root, TreeNode* &res, int & curLevel, int &
preLevel)
{
if(root)
{
if(curLevel>preLevel)
{
res = root;
preLevel++;
}
curLevel++;
DFSHelper(root->right, ... 阅读全帖 |
|
s**********z
发帖数: 61 | 47 如果树是unbalanced，一条线，为什么DFS 空间是lgn? |
|
h****n
发帖数: 1093 | 48 恩 疏忽了
如果树是unbalanced，一条线，为什么DFS 空间是lgn?
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
b*****u
发帖数: 648 | 49
如果没有重复数字的话可以这么弄：
先用0作pivot， 快排，把k个正数选出来 O(n) 时间
选k/2 作pivot，快排，结果少的那一侧缺数，对其继续选中值，快排，直到区间为0，
O(lgn) |
|
h****n
发帖数: 1093 | 50 你的M是指什么呀，我的M是指字符串的长度 avg M是指字符串的平均长度
具体M是多少和你字符串的排列是有关系的
考虑两种极端的情况，假设所有字符串的字符都是同一个字符，
第一种所有字符按照长度从长排到短，那么比较下来的长度就是AVG M
第二种就是所有字符按照长度从短到长排，那么比较下来的长度就是MIN M
divide conquer的复杂度可以用主定理来分析的，主要看最终的复杂度看分支数量，子
问题规模和合并操作的开销
T（n）=a(T/b) + O(n^d)
T（n）= n^d if d > logb a
= n^(logb a) if d < logb a
= n^d * lgn if d == logb a |
|
