a*********9
发帖数: 523 | 1 ZUAN人品，分享今天的面经：
1点的面试，大概40分钟，中国人，只问了两个问题:
1. Print a tree (not necessary a binary tree) by level
2. Swap two parts in a sorted array (numbers), then given a number, find
out its position in the new array.
第1个问题可以用QUEUE每次进队一个NODE，然后退队时把所有SUB NODES入队
第2个问题我是先找出第一个swap part的尾和第2个swap part的头，然后再各自的PART
里做
BINARY SEARCH，最后的复杂度是 O(n), 被问到直接SEARCH的复杂度和这个比起来怎样
就答不上
来了，估计也是悲剧了 |
g**e
发帖数: 6127 | 2 都是老题
PART
【在 a*********9 的大作中提到】
: ZUAN人品，分享今天的面经：
: 1点的面试，大概40分钟，中国人，只问了两个问题:
: 1. Print a tree (not necessary a binary tree) by level
: 2. Swap two parts in a sorted array (numbers), then given a number, find
: out its position in the new array.
: 第1个问题可以用QUEUE每次进队一个NODE，然后退队时把所有SUB NODES入队
: 第2个问题我是先找出第一个swap part的尾和第2个swap part的头，然后再各自的PART
: 里做
: BINARY SEARCH，最后的复杂度是 O(n), 被问到直接SEARCH的复杂度和这个比起来怎样
: 就答不上
|
a*********9
发帖数: 523 | 3 ...我都是第一次见啊
【在 g**e 的大作中提到】
: 都是老题
:
: PART
|
x**********n
发帖数: 1262 | 4 那请指导一下, thanks!
【在 g**e 的大作中提到】
: 都是老题
:
: PART
|
Z*****Z
发帖数: 723 | 5 第二题我是第1次见。这个swap是不是两个部分一定要大小相同，并且不能有overlap。
如果是这样的话就很容易。
查找的复杂度么，如果能再原数组里用binary search，那么处理之后的index可以在常
数时间内算出来。总复杂度还是lgN
PART
【在 a*********9 的大作中提到】
: ZUAN人品，分享今天的面经：
: 1点的面试，大概40分钟，中国人，只问了两个问题:
: 1. Print a tree (not necessary a binary tree) by level
: 2. Swap two parts in a sorted array (numbers), then given a number, find
: out its position in the new array.
: 第1个问题可以用QUEUE每次进队一个NODE，然后退队时把所有SUB NODES入队
: 第2个问题我是先找出第一个swap part的尾和第2个swap part的头，然后再各自的PART
: 里做
: BINARY SEARCH，最后的复杂度是 O(n), 被问到直接SEARCH的复杂度和这个比起来怎样
: 就答不上
|
g**e
发帖数: 6127 | 6 我觉得他这里说的swap只是把sorted array分成两部分，然后swap。就是那道经典的
shifted array binary search老题
如果是swap数组任意两块的话，最坏情况只能O(n)吧
【在 Z*****Z 的大作中提到】
: 第二题我是第1次见。这个swap是不是两个部分一定要大小相同，并且不能有overlap。
: 如果是这样的话就很容易。
: 查找的复杂度么，如果能再原数组里用binary search，那么处理之后的index可以在常
: 数时间内算出来。总复杂度还是lgN
:
: PART
|
P***o
发帖数: 96 | 7 第二题好像在版内出现过几次了，就是 search a number in a rotated sorted array吧
【在 Z*****Z 的大作中提到】
: 第二题我是第1次见。这个swap是不是两个部分一定要大小相同，并且不能有overlap。
: 如果是这样的话就很容易。
: 查找的复杂度么，如果能再原数组里用binary search，那么处理之后的index可以在常
: 数时间内算出来。总复杂度还是lgN
:
: PART
|
a*********9
发帖数: 523 | 8 PARTS大小不一定一样，直接看到的应该是SHIFT后的数组了。
【在 Z*****Z 的大作中提到】
: 第二题我是第1次见。这个swap是不是两个部分一定要大小相同，并且不能有overlap。
: 如果是这样的话就很容易。
: 查找的复杂度么，如果能再原数组里用binary search，那么处理之后的index可以在常
: 数时间内算出来。总复杂度还是lgN
:
: PART
|
z****n
发帖数: 1379 | 9 第二题是不是用二分法找分界点，然后用两个二分法search数，复杂度仍然是logN
你可能是用一遍遍历找分界点，所以变成o（n）了
PART
【在 a*********9 的大作中提到】
: ZUAN人品，分享今天的面经：
: 1点的面试，大概40分钟，中国人，只问了两个问题:
: 1. Print a tree (not necessary a binary tree) by level
: 2. Swap two parts in a sorted array (numbers), then given a number, find
: out its position in the new array.
: 第1个问题可以用QUEUE每次进队一个NODE，然后退队时把所有SUB NODES入队
: 第2个问题我是先找出第一个swap part的尾和第2个swap part的头，然后再各自的PART
: 里做
: BINARY SEARCH，最后的复杂度是 O(n), 被问到直接SEARCH的复杂度和这个比起来怎样
: 就答不上
|
a*********9
发帖数: 523 | 10 是的，能详细说说怎么用BINARY SEARCH找分界点吗？
【在 z****n 的大作中提到】
: 第二题是不是用二分法找分界点，然后用两个二分法search数，复杂度仍然是logN
: 你可能是用一遍遍历找分界点，所以变成o（n）了
:
: PART
|
|
|
x***n
发帖数: 464 | |
d****e
发帖数: 251 | 12 Search and find i until a[i] > a[i+1]? Not much different from regular
binary search.
【在 a*********9 的大作中提到】
: 是的，能详细说说怎么用BINARY SEARCH找分界点吗？
|
a*********9
发帖数: 523 | 13 That's what I am thinking too
【在 d****e 的大作中提到】
: Search and find i until a[i] > a[i+1]? Not much different from regular
: binary search.
|
a*********9
发帖数: 523 | 14 还在办手续，没上班呢
【在 x***n 的大作中提到】
: lz，你不是去高通上班了吗，咋又开始面试了？
|
c*r
发帖数: 278 | 15 That is completely different than the regular binary search.
In binary search, from the comparison result, we know the sub problem to
solve (which part to continue searching).
To find this 分界点, if a[i] < a[i+1], what is the next step (the sub problem)?
So the solution is not looking for 分界点, but which part to continue searching. That us not much different from regular binary search.
【在 d****e 的大作中提到】
: Search and find i until a[i] > a[i+1]? Not much different from regular
: binary search.
|
z****n
发帖数: 1379 | 16 二分查找分界点是可以的，不过不是跟下一个元素比较，而是跟第一个或最后一个元素
比较
每次跟最后一个元素比较，如果比最后一个元素大，则分界点在后半段，如果比最后一
个元素小，则分界点在前半段
也可以跟第一个元素比较，如果比第一个元素大，则分界点在后半段，如果比第一个元
素小，则分界点在前半段
problem)?
searching. That us not much different from regular binary search.
【在 c*r 的大作中提到】
: That is completely different than the regular binary search.
: In binary search, from the comparison result, we know the sub problem to
: solve (which part to continue searching).
: To find this 分界点, if a[i] < a[i+1], what is the next step (the sub problem)?
: So the solution is not looking for 分界点, but which part to continue searching. That us not much different from regular binary search.
|
d****e
发帖数: 251 | 17 对，所以说还是一样的，就是递归改变搜索range而已。
【在 z****n 的大作中提到】
: 二分查找分界点是可以的，不过不是跟下一个元素比较，而是跟第一个或最后一个元素
: 比较
: 每次跟最后一个元素比较，如果比最后一个元素大，则分界点在后半段，如果比最后一
: 个元素小，则分界点在前半段
: 也可以跟第一个元素比较，如果比第一个元素大，则分界点在后半段，如果比第一个元
: 素小，则分界点在前半段
:
: problem)?
: searching. That us not much different from regular binary search.
|
