U*********y 发帖数: 54 | 1 //如果不爱分享, 至少懂得回报
1.一个整数数组a[], 每个元素的值代表能向前跳1到a[i]格,问最少跳几步刚好到达数
组的末端, 超出数组的index或到不了末端算失败
2.排好序的连续数组只缺一个数,二叉搜索找出来
3.Boggle游戏, 返回牌面上所有有效单词
4.按顺时针打印二叉树边缘, 解法见leetcode
5.zigzag打印二叉树, 解法见leetcode
6.电话号码的regular expression
7.二叉搜索树找相等或最相近某值的节点
8.singleton的多线程
9.股票最佳买入和卖出点
10.Kth分割 (快排序的分割步骤)
11.网络用户的网速慢,如何设计浏览器加速网页的浏览速度
12.浏览器输入URL,发生了什么
13.给电话号码, 打印所有可能字符串
14.写API, 允许用户注册一个程序到ID, 注销一个程序, 运行一个ID下所有的程序
15.找质数
16.atoi
17.讲电话本的trie设计,对比哈希表
3家的电/店的题目放在了一起,大部分都算常见题.
经验总结: 面试的不定因素太多,感觉就像抽奖. 所以不要放弃,感觉准备好了的话(以上题见过6-8
成)就尽量多找些面试来面. 面试找不到就改简历,找推荐,骚扰recruiter. |
z*********8 发帖数: 2070 | 2 这两个的区别是?
4.螺旋打印二叉树
5.zigzag打印二叉树 |
U*********y 发帖数: 54 | |
w****x 发帖数: 2483 | |
U*********y 发帖数: 54 | 5 大部分是常见题,哪家都会面到的吧. 没有分类是因为有的签了NDA
【在 w****x 的大作中提到】 : 我靠, 至少分哪家哪家的分个类吧
|
w****x 发帖数: 2483 | 6 嗯谢谢楼主了.
螺旋打印二叉树 --- 这个貌似挺难的
"二叉搜索树找相等或最相近某值的节点" -- 靠,这题居然想了半天, 我可以去死了 |
a********m 发帖数: 15480 | 7 “二叉搜索树找相等或最相近某值的节点" -不是难题但是最优解也不是那么容易的。
【在 w****x 的大作中提到】 : 嗯谢谢楼主了. : 螺旋打印二叉树 --- 这个貌似挺难的 : "二叉搜索树找相等或最相近某值的节点" -- 靠,这题居然想了半天, 我可以去死了
|
b****e 发帖数: 45 | 8 这道题用普通binary search外加一个min_diff变量保存当前查询过
所有节点的最小绝对差值应该就可以了吧
【在 a********m 的大作中提到】 : “二叉搜索树找相等或最相近某值的节点" -不是难题但是最优解也不是那么容易的。
|
z****h 发帖数: 164 | |
w****x 发帖数: 2483 | 10 打印边缘节点也不会, 当初看到这题直接放弃了,看不下去了 |
|
|
d******a 发帖数: 238 | 11 谢谢楼主!
第十道题 Kth分割 是什么题目啊?能说详细点吗,谢谢。 |
z****h 发帖数: 164 | 12 我也是,直接看答案了。
【在 w****x 的大作中提到】 : 打印边缘节点也不会, 当初看到这题直接放弃了,看不下去了
|
k******I 发帖数: 238 | 13 第一题那个整数数组跳到末尾的,哪里能找到完整的题? |
t*****j 发帖数: 1105 | 14 这题就是图论两点间最短路径法,Dijestra. O(n)空间时间复杂度。
【在 k******I 的大作中提到】 : 第一题那个整数数组跳到末尾的,哪里能找到完整的题?
|
t*****j 发帖数: 1105 | 15 感谢分享!
有几个问题,能麻烦楼主或者哪位回答下吗?谢谢啊!
~~~~~ 这题能麻烦讲清楚下吗?数是连续的吗?如果不是连续的,怎么知道缺哪
个?
~~~~~~~~能麻烦
~~~~~~~~~~~~~能麻烦再讲清楚些吗?怎么zigzag打印?
就是把树的形状打印出来?我不太明白,呵呵。
【在 U*********y 的大作中提到】 : //如果不爱分享, 至少懂得回报 : 1.一个整数数组a[], 每个元素的值代表能向前跳1到a[i]格,问最少跳几步刚好到达数 : 组的末端, 超出数组的index或到不了末端算失败 : 2.排好序的连续数组只缺一个数,二叉搜索找出来 : 3.Boggle游戏, 返回牌面上所有有效单词 : 4.按顺时针打印二叉树边缘, 解法见leetcode : 5.zigzag打印二叉树, 解法见leetcode : 6.电话号码的regular expression : 7.二叉搜索树找相等或最相近某值的节点 : 8.singleton的多线程
|
U*********y 发帖数: 54 | 16 正解
【在 b****e 的大作中提到】 : 这道题用普通binary search外加一个min_diff变量保存当前查询过 : 所有节点的最小绝对差值应该就可以了吧
|
U*********y 发帖数: 54 | 17 对不起,应该是只打印边缘, 已修正
【在 z****h 的大作中提到】 : http://www.leetcode.com/2010/10/print-edge-nodes-boundary-of- : binary.html : 只是打印边缘接点。 : 螺旋打印二叉树要求中间结点也打印吧? : 求答案。 : 谢谢
|
U*********y 发帖数: 54 | 18 我之前也没见过, 凭感觉写了一个greedy的解法, 就是每一步都取i+a[i]的最大值. 可
以具体讲讲用Dijestra的解法吗?
【在 t*****j 的大作中提到】 : 这题就是图论两点间最短路径法,Dijestra. O(n)空间时间复杂度。
|
p*****2 发帖数: 21240 | 19
traverse一下就可以了吧?
【在 w****x 的大作中提到】 : 打印边缘节点也不会, 当初看到这题直接放弃了,看不下去了
|
p*****2 发帖数: 21240 | 20
要求返回那个节点呀。有这个就够了吧?
【在 b****e 的大作中提到】 : 这道题用普通binary search外加一个min_diff变量保存当前查询过 : 所有节点的最小绝对差值应该就可以了吧
|
|
|
p*****2 发帖数: 21240 | 21
不用这么复杂吧?
【在 t*****j 的大作中提到】 : 这题就是图论两点间最短路径法,Dijestra. O(n)空间时间复杂度。
|
t*****j 发帖数: 1105 | 22 哦哦哦,简单递归就行,DP存剪枝。
【在 p*****2 的大作中提到】 : : 不用这么复杂吧?
|
g*******n 发帖数: 214 | 23 感谢分享!
★ Sent from iPhone App: iReader Mitbbs Lite 7.52 |
p*****2 发帖数: 21240 | 24
DP复杂度n^2吧?这题的正解是O(n)吧?
【在 t*****j 的大作中提到】 : 哦哦哦,简单递归就行,DP存剪枝。
|
G******e 发帖数: 229 | |
t*****j 发帖数: 1105 | 26 O(n).
【在 p*****2 的大作中提到】 : : DP复杂度n^2吧?这题的正解是O(n)吧?
|
t*****j 发帖数: 1105 | 27 DP也可以O(n)啊。
【在 p*****2 的大作中提到】 : : DP复杂度n^2吧?这题的正解是O(n)吧?
|
G**********s 发帖数: 70 | 28 其它題找到了•可是這個?
14.写API, 允许用户注册一个程序到ID, 注销一个程序, 运行一个ID下所有的程序
-这题啥意思 |
w****x 发帖数: 2483 | 29 打印树边界那题, 真要很仔细观察才能看出来啊!! |
G**********s 发帖数: 70 | 30 恩,第一次看到这题也很晕。。不过蛮有意思的
【在 w****x 的大作中提到】 : 打印树边界那题, 真要很仔细观察才能看出来啊!!
|
|
|
a********m 发帖数: 15480 | 31 好像不太一样。先说你用几次binary search?
【在 b****e 的大作中提到】 : 这道题用普通binary search外加一个min_diff变量保存当前查询过 : 所有节点的最小绝对差值应该就可以了吧
|
p*****2 发帖数: 21240 | 32
我还没看答案呢。有时间再看。我感觉两个边很容易找,然后就是按顺序找叶子了。
【在 w****x 的大作中提到】 : 打印树边界那题, 真要很仔细观察才能看出来啊!!
|
p*****2 发帖数: 21240 | 33
说一下思路好吗?
【在 t*****j 的大作中提到】 : DP也可以O(n)啊。
|
w****x 发帖数: 2483 | 34
啊, 服了, 原来就是left-most bottom 和 right most 啊, 我还以为是那种edge, 想
了半天
_______________28_______________
/ \
4____ ____69
\ /
__8__ __56__
/ \ / \
__7 12__ __34 __27__
/ \ / / \
5_ _13 _2 _3 39
\ / / /
6 11 10 9
原来7, 5都不打印, 那也没什么难的
【在 p*****2 的大作中提到】 : : 说一下思路好吗?
|
w****x 发帖数: 2483 | 35
这题他说的没错, 就是按search的路径找diff最小的, 你可以证明
如果当前节点比目标数字小, 你只需要search右子树, 因为左子树所有节点的diff肯定
更大,
如果当前节点比目标数字大, 你只需要search左子树, 因为右子树所有节点的diff肯定
更大,
相等的话那就是最小喽.
把上面3条想通了就可以了, 我想了7,8分钟, NND
【在 a********m 的大作中提到】 : 好像不太一样。先说你用几次binary search?
|
a********m 发帖数: 15480 | 36 是的,想通了狠容易,但是有些细节地方一开始没想到也狠正常。比如下面这个树目标
数字是4.
2
/ \
1 50
/ \
45 60
【在 w****x 的大作中提到】 : : 这题他说的没错, 就是按search的路径找diff最小的, 你可以证明 : 如果当前节点比目标数字小, 你只需要search右子树, 因为左子树所有节点的diff肯定 : 更大, : 如果当前节点比目标数字大, 你只需要search左子树, 因为右子树所有节点的diff肯定 : 更大, : 相等的话那就是最小喽. : 把上面3条想通了就可以了, 我想了7,8分钟, NND
|
z****h 发帖数: 164 | 37 dijkestra的空间时间复杂度是O(n)??
求实现。。。
【在 t*****j 的大作中提到】 : 这题就是图论两点间最短路径法,Dijestra. O(n)空间时间复杂度。
|
z****h 发帖数: 164 | 38 求正解。。
【在 p*****2 的大作中提到】 : : 说一下思路好吗?
|
h**6 发帖数: 4160 | 39 两个指针,一个指向开始跳的位置,一个指向到达的位置。扫描到数组末尾结束。
【在 U*********y 的大作中提到】 : //如果不爱分享, 至少懂得回报 : 1.一个整数数组a[], 每个元素的值代表能向前跳1到a[i]格,问最少跳几步刚好到达数 : 组的末端, 超出数组的index或到不了末端算失败 : 2.排好序的连续数组只缺一个数,二叉搜索找出来 : 3.Boggle游戏, 返回牌面上所有有效单词 : 4.按顺时针打印二叉树边缘, 解法见leetcode : 5.zigzag打印二叉树, 解法见leetcode : 6.电话号码的regular expression : 7.二叉搜索树找相等或最相近某值的节点 : 8.singleton的多线程
|
a********m 发帖数: 15480 | 40 假设a->b这个区间可以最少用n步。用n+1步能达到的是:
c = max{array[i] + i, i = a->b}
现在是b->c这个区间可以用n+1步达到。
循环到c>目标就可以了。
【在 z****h 的大作中提到】 : 求正解。。
|
|
|
t*****j 发帖数: 1105 | 41 我错了,貌似还是O(n^2),哪怕递归。
O(n)的解法怎么弄啊?能私我么?
谢了!
【在 p*****2 的大作中提到】 : : 说一下思路好吗?
|
p*****2 发帖数: 21240 | 42
想想用greedy。
【在 t*****j 的大作中提到】 : 我错了,貌似还是O(n^2),哪怕递归。 : O(n)的解法怎么弄啊?能私我么? : 谢了!
|
t*****j 发帖数: 1105 | 43 OK,就是算最远能到达的范围,因为所有在最远能到达范围
内的所有地方都是可以到达的,因为这些范围是连续的。
【在 a********m 的大作中提到】 : 假设a->b这个区间可以最少用n步。用n+1步能达到的是: : c = max{array[i] + i, i = a->b} : 现在是b->c这个区间可以用n+1步达到。 : 循环到c>目标就可以了。
|
t*****j 发帖数: 1105 | 44 哇,你回帖这么快....神仙....
谢啦!
【在 p*****2 的大作中提到】 : : 想想用greedy。
|
a********m 发帖数: 15480 | 45 恩。每一步算一批。其实还是dp思路,区别在具体应用方法。
【在 t*****j 的大作中提到】 : OK,就是算最远能到达的范围,因为所有在最远能到达范围 : 内的所有地方都是可以到达的,因为这些范围是连续的。
|
z****h 发帖数: 164 | 46 谢谢虫子。
不过好像这还是O(n2)的复杂度吧。
如有错误请更正。
【在 a********m 的大作中提到】 : 假设a->b这个区间可以最少用n步。用n+1步能达到的是: : c = max{array[i] + i, i = a->b} : 现在是b->c这个区间可以用n+1步达到。 : 循环到c>目标就可以了。
|
p*****2 发帖数: 21240 | 47
greedy算法就是O(n)
【在 z****h 的大作中提到】 : 谢谢虫子。 : 不过好像这还是O(n2)的复杂度吧。 : 如有错误请更正。
|
a********m 发帖数: 15480 | 48 不会呀。每个点算一次,然后和当前的max比较一次。没别的计算了。
【在 z****h 的大作中提到】 : 谢谢虫子。 : 不过好像这还是O(n2)的复杂度吧。 : 如有错误请更正。
|
a********m 发帖数: 15480 | 49 纯greedy不对,比如下面这个:
2,100,1,1,1,1,1,1
【在 p*****2 的大作中提到】 : : greedy算法就是O(n)
|
Z*****Z 发帖数: 723 | 50 建议大家直接上LeetCode,Jump Game II,过了之后直接贴代码,呵呵。
【在 a********m 的大作中提到】 : 不会呀。每个点算一次,然后和当前的max比较一次。没别的计算了。
|
|
|
a********m 发帖数: 15480 | 51 差不多这个意思吧。没运行过不保证没小错误。
int Steps(int* array, int n) {
int start = 0;
int end = 0;
int steps = 0;
while (end < n) {
steps++;
int next = end;
for (int i = start; i <= end; ++i) {
int reach = array[i] + i;
next = max(next, reach);
}
start = end + 1;
end = next;
assert(start <= end);
}
return steps;
}
【在 Z*****Z 的大作中提到】 : 建议大家直接上LeetCode,Jump Game II,过了之后直接贴代码,呵呵。
|
w****x 发帖数: 2483 | 52
不就DP O(n^2)吗??
【在 p*****2 的大作中提到】 : : greedy算法就是O(n)
|
t*****j 发帖数: 1105 | 53 张包子看着好眼熟啊....
【在 Z*****Z 的大作中提到】 : 建议大家直接上LeetCode,Jump Game II,过了之后直接贴代码,呵呵。
|
p*****2 发帖数: 21240 | 54
greedy是O(n)的解。
【在 w****x 的大作中提到】 : : 不就DP O(n^2)吗??
|
p*****2 发帖数: 21240 | 55
啥叫纯greedy呢?
【在 a********m 的大作中提到】 : 纯greedy不对,比如下面这个: : 2,100,1,1,1,1,1,1
|
a********m 发帖数: 15480 | 56 纯greedy就是一直尽量往远跳。
【在 p*****2 的大作中提到】 : : 啥叫纯greedy呢?
|
p*****2 发帖数: 21240 | 57 public int jump(int[] A)
{
int ans = 0;
int n = A.length;
int start = 0;
int end = 0;
while (end < n - 1)
{
int max = 0;
for (int i = start; i <= end; i++)
max = Math.max(max, i + A[i]);
ans++;
start = end + 1;
end = max;
}
return ans;
} |
w****x 发帖数: 2483 | 58
greedy 又不能保证最优, 这题就考个DP, 别折腾啦, 还没见过哪家面试考greedy的
【在 p*****2 的大作中提到】 : public int jump(int[] A) : { : int ans = 0; : int n = A.length; : int start = 0; : int end = 0; : while (end < n - 1) : { : int max = 0; : for (int i = start; i <= end; i++)
|
t*****j 发帖数: 1105 | 59 保证最优的,同学。
【在 w****x 的大作中提到】 : : greedy 又不能保证最优, 这题就考个DP, 别折腾啦, 还没见过哪家面试考greedy的
|
p*****2 发帖数: 21240 | 60
本来就是尽量往远跳呀。这样才能有最小的步数呢。
【在 a********m 的大作中提到】 : 纯greedy就是一直尽量往远跳。
|
|
|
p*****2 发帖数: 21240 | 61
看我程序。
【在 w****x 的大作中提到】 : : greedy 又不能保证最优, 这题就考个DP, 别折腾啦, 还没见过哪家面试考greedy的
|
t*****j 发帖数: 1105 | 62 greedy对啊,2 然后100,然后末尾。
【在 p*****2 的大作中提到】 : : 看我程序。
|
p*****2 发帖数: 21240 | 63
是呀。就是greedy解呀。
【在 t*****j 的大作中提到】 : greedy对啊,2 然后100,然后末尾。
|
a********m 发帖数: 15480 | 64 你的程序检查每个点,不算尽量往远跳的greedy。greedy是:
start = 0;
end = 0;
while (end < n) {
end = array[start];
}
【在 p*****2 的大作中提到】 : : 是呀。就是greedy解呀。
|
p*****2 发帖数: 21240 | 65
看怎么解释尽量吧?
【在 a********m 的大作中提到】 : 你的程序检查每个点,不算尽量往远跳的greedy。greedy是: : start = 0; : end = 0; : while (end < n) { : end = array[start]; : }
|
w****x 发帖数: 2483 | 66
太牛X了, 这都能想到, 能不能描述一下你是怎么一步步想到这个的??
【在 p*****2 的大作中提到】 : : 看怎么解释尽量吧?
|
p*****2 发帖数: 21240 | 67
这题以前讨论过呀。
【在 w****x 的大作中提到】 : : 太牛X了, 这都能想到, 能不能描述一下你是怎么一步步想到这个的??
|
a********m 发帖数: 15480 | 68 俺的例子里面:
2, 100, 1,1,1
第一步你没有前进2而是前进1就已经不是greedy了。解法里面有greedy的影子但不是真
正的greedy。
【在 p*****2 的大作中提到】 : : 这题以前讨论过呀。
|
w****x 发帖数: 2483 | 69
算了, 遇到这种题直接投降, greedy出现概率太低了, 记得以前有个什么安排活动不让
时间冲突的题也是greedy, 还有一个数学方法证明greedy最优解的公式啥的, 直接放弃
了...
【在 p*****2 的大作中提到】 : : 这题以前讨论过呀。
|
p*****2 发帖数: 21240 | 70
我还真没学过算法。看来我对greedy的理解有误呀。
【在 a********m 的大作中提到】 : 俺的例子里面: : 2, 100, 1,1,1 : 第一步你没有前进2而是前进1就已经不是greedy了。解法里面有greedy的影子但不是真 : 正的greedy。
|
|
|
a********m 发帖数: 15480 | 71 这个题的解是有greedy的感觉。
【在 p*****2 的大作中提到】 : : 我还真没学过算法。看来我对greedy的理解有误呀。
|
Z*****Z 发帖数: 723 | 72 赞美一下二爷的这个解。
但是我要+1这不是greedy.
【在 p*****2 的大作中提到】 : : 我还真没学过算法。看来我对greedy的理解有误呀。
|
U*********y 发帖数: 54 | 73 我当时写的解法和你差不错, 只不过是用递归写的, 面试官又问怎么证明算法的正确性
, 没有证出来. 有没有想法如何证明?
【在 p*****2 的大作中提到】 : : 我还真没学过算法。看来我对greedy的理解有误呀。
|