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的理解有误呀。
|
