h**********d
发帖数: 4313 | 1 都是前两个礼拜面的，下个礼拜2面，来攒个rp
AMAZON
1. Research
2. 实现Java String class的repleaceAll() method，不可以用String本身的replace(
), replaceAll()
3. 合并2个BST, 要求O(n)time
4. 2个stack -> 1个queue
GOOGLE
1. Research 因为我是做NLP的,machine learning涉及了一些，问的比较细，有点烦。
。。
2. 找一个string出现最多的字母，扩展问了很多，内存，多核CPU，多个多核CPU
machine...一开始给的hashmap的解法最后combine会有点问题，反正吭哧吭哧的答了，
最后自己觉得并没有improve多少time complexity..
祝福以下大家和自己 |
p******1
发帖数: 26 | |
d******u
发帖数: 397 | |
t****0
发帖数: 235 | |
c********t
发帖数: 5706 | 5 bless
replace(
【在 h**********d 的大作中提到】
: 都是前两个礼拜面的，下个礼拜2面，来攒个rp
: AMAZON
: 1. Research
: 2. 实现Java String class的repleaceAll() method，不可以用String本身的replace(
: ), replaceAll()
: 3. 合并2个BST, 要求O(n)time
: 4. 2个stack -> 1个queue
: GOOGLE
: 1. Research 因为我是做NLP的,machine learning涉及了一些，问的比较细，有点烦。
: 。。
|
i**9
发帖数: 351 | 6 合并2个BST, 要求O(n)time,
flatten two bst by in order traversal ,and rebuild a bigger bst, 有更直接的
办法吗
replace(
【在 h**********d 的大作中提到】
: 都是前两个礼拜面的，下个礼拜2面，来攒个rp
: AMAZON
: 1. Research
: 2. 实现Java String class的repleaceAll() method，不可以用String本身的replace(
: ), replaceAll()
: 3. 合并2个BST, 要求O(n)time
: 4. 2个stack -> 1个queue
: GOOGLE
: 1. Research 因为我是做NLP的,machine learning涉及了一些，问的比较细，有点烦。
: 。。
|
t****0
发帖数: 235 | 7 this looks like nlgn
的
【在 i**9 的大作中提到】
: 合并2个BST, 要求O(n)time,
: flatten two bst by in order traversal ,and rebuild a bigger bst, 有更直接的
: 办法吗
:
: replace(
|
t****0
发帖数: 235 | 8 if a merge sort is used..
【在 t****0 的大作中提到】
: this looks like nlgn
:
: 的
|
b***u
发帖数: 22891 | |
i**9
发帖数: 351 | 10 merging two sorted array takes O(n)
【在 t****0 的大作中提到】
: this looks like nlgn
:
: 的
|
|
|
g*********s
发帖数: 1782 | 11 这个算法确实是线性的，但代码写起来还挺繁琐：
1) in-order traverse and merge bst T1 and T2 into a sorted array X,
O(N+M).
2) create a balanced bt T with N+M nodes, can be achieved by O(N+M) but
the # of node at each level needs some calculation with patience.
3) in-order traverse T and fill up T with X.
的
【在 i**9 的大作中提到】
: 合并2个BST, 要求O(n)time,
: flatten two bst by in order traversal ,and rebuild a bigger bst, 有更直接的
: 办法吗
:
: replace(
|
t****0
发帖数: 235 | 12 2) it seems not requiring balanced...
http://stackoverflow.com/questions/4235013/create-balanced-bina
search-tree-from-sorted-linked-list
BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
if (start > end) return NULL;
// same as (start+end)/2, avoids overflow
int mid = start + (end - start) / 2;
BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
BinaryTree *parent = new BinaryTree(list->data);
parent->left = leftChild;
list = list->next;
parent->right = sortedListToBST(list, mid+1, end);
return parent;
}
BinaryTree* sortedListToBST(ListNode *head, int n) {
return sortedListToBST(head, 0, n-1);
but
【在 g*********s 的大作中提到】
: 这个算法确实是线性的，但代码写起来还挺繁琐：
: 1) in-order traverse and merge bst T1 and T2 into a sorted array X,
: O(N+M).
: 2) create a balanced bt T with N+M nodes, can be achieved by O(N+M) but
: the # of node at each level needs some calculation with patience.
: 3) in-order traverse T and fill up T with X.
:
: 的
|
g*********s
发帖数: 1782 | 13 then how to maintain the balanced property?
【在 t****0 的大作中提到】
: 2) it seems not requiring balanced...
: http://stackoverflow.com/questions/4235013/create-balanced-bina
: search-tree-from-sorted-linked-list
: BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
: if (start > end) return NULL;
: // same as (start+end)/2, avoids overflow
: int mid = start + (end - start) / 2;
: BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
: BinaryTree *parent = new BinaryTree(list->data);
: parent->left = leftChild;
|
h**********d
发帖数: 4313 | 14 对对，我忘记说了，是两个balanced 大小都为n nodes的bst
【在 t****0 的大作中提到】
: 2) it seems not requiring balanced...
: http://stackoverflow.com/questions/4235013/create-balanced-bina
: search-tree-from-sorted-linked-list
: BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
: if (start > end) return NULL;
: // same as (start+end)/2, avoids overflow
: int mid = start + (end - start) / 2;
: BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
: BinaryTree *parent = new BinaryTree(list->data);
: parent->left = leftChild;
|
h**********d
发帖数: 4313 | 15 我一开始就说了个nlogn的bst insertion，他说要o(n)的，不在乎space
然后我就说了这个笨办法，不知道有没有更好的，不过他seems满意
直接的
【在 i**9 的大作中提到】
: 合并2个BST, 要求O(n)time,
: flatten two bst by in order traversal ,and rebuild a bigger bst, 有更直接的
: 办法吗
:
: replace(
|
g*********s
发帖数: 1782 | 16 how do u guarantee this is a balanced bst? the left and right sub-tree
might have unequal number of nodes.
【在 t****0 的大作中提到】
: 2) it seems not requiring balanced...
: http://stackoverflow.com/questions/4235013/create-balanced-bina
: search-tree-from-sorted-linked-list
: BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
: if (start > end) return NULL;
: // same as (start+end)/2, avoids overflow
: int mid = start + (end - start) / 2;
: BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
: BinaryTree *parent = new BinaryTree(list->data);
: parent->left = leftChild;
|
g*********s
发帖数: 1782 | 17 how about the merged bst? is it required to be balanced?
【在 h**********d 的大作中提到】
: 我一开始就说了个nlogn的bst insertion，他说要o(n)的，不在乎space
: 然后我就说了这个笨办法，不知道有没有更好的，不过他seems满意
:
: 直接的
|
h**********d
发帖数: 4313 | 18 对，最后的bst也应该是balanced
所有操作都应该是O(n)
【在 g*********s 的大作中提到】
: how about the merged bst? is it required to be balanced?
|
g*********s
发帖数: 1782 | 19 then how did u ensure the merged bst is balanced?
【在 h**********d 的大作中提到】
: 对，最后的bst也应该是balanced
: 所有操作都应该是O(n)
|
h**********d
发帖数: 4313 | 20 就是从一个sorted array建立balanced bst
Node sortedArrayToBST(int[] a, int l, int r){
if(l > r){return null;}
int mid = l+(r-l)/2;
Node root = new Node(a[mid]);
root.setLeft(sortedArrayToBST(a, l, mid-1));
root.setRight(sortedArrayToBST(a, mid, r));
return root;
}
【在 g*********s 的大作中提到】
: then how did u ensure the merged bst is balanced?
|
|
|
g*********s
发帖数: 1782 | 21 sorry, but can u prove this is balanced? i believe this algorithm creates
a bst. but i'm not convinced the created bst is balanced.
u can see the left and right sub-tree can have size difference by 1. if u
do recursion, then is it possible at each level the left and right may
have difference by 1? if so the worst case this difference is accumulated
with an O(lgN) bound...
【在 h**********d 的大作中提到】
: 就是从一个sorted array建立balanced bst
: Node sortedArrayToBST(int[] a, int l, int r){
: if(l > r){return null;}
: int mid = l+(r-l)/2;
: Node root = new Node(a[mid]);
: root.setLeft(sortedArrayToBST(a, l, mid-1));
: root.setRight(sortedArrayToBST(a, mid, r));
: return root;
: }
|
m****i
发帖数: 650 | 22 2. 实现Java String class的repleaceAll() method，不可以用String本身的replace(
), replaceAll()
2. 找一个string出现最多的字母，扩展问了很多，内存，多核CPU，多个多核CPU
machine...一开始给的hashmap的解法最后combine会有点问题，反正吭哧吭哧的答了，
最后自己觉得并没有improve多少time complexity..
这两个可以详细说说么 |
m****i
发帖数: 650 | 23
creates
u
accumulated
2 BSTs have n nodes each, therefore, the combined sorted array is even
size. It can guarantee that the left and right subtree are equal size.
【在 g*********s 的大作中提到】
: sorry, but can u prove this is balanced? i believe this algorithm creates
: a bst. but i'm not convinced the created bst is balanced.
: u can see the left and right sub-tree can have size difference by 1. if u
: do recursion, then is it possible at each level the left and right may
: have difference by 1? if so the worst case this difference is accumulated
: with an O(lgN) bound...
|
g*********s
发帖数: 1782 | 24 how? if size(left) == size(right), then total node # is 2k + 1 counting
the root, while the array size is even as u said. a contradiction.
【在 m****i 的大作中提到】
:
: creates
: u
: accumulated
: 2 BSTs have n nodes each, therefore, the combined sorted array is even
: size. It can guarantee that the left and right subtree are equal size.
|
m****i
发帖数: 650 | 25
Actually, you are right the left and right subtree have 1 node different.
however, by definition, the balanced tree does not mean left and right
subtree must have equal size.
From wiki
a self-balancing (or height-balanced) binary search tree is any node
based binary search tree that automatically keeps its height (number of
levels below the root) small in the face of arbitrary item insertions and
deletion
【在 g*********s 的大作中提到】
: how? if size(left) == size(right), then total node # is 2k + 1 counting
: the root, while the array size is even as u said. a contradiction.
|
g*********s
发帖数: 1782 | 26 by definition, balanced bst must have the min leaf node level and max
leaf node level difference O(1). by doing this, the max height is
guaranteed to be O(logN) and this is the foundation for O(logN)
operations insert, delete, etc.
but in ur solution, the left and right sub-tree are not identical. and
the left of left and right of left are possibly not identical too. so
the min/max leaf could possibly non-zero. and this diff can accumulate
and breaks the O(1) bound.
unless there's a solid proof of the balanced property. but i can't
figure it out.
my solution is to build a complete binary tree first, which is
guaranteed to be balanced. but this solution is lengthy. so i would be
happy to see an elegant and correctness proven solution.
different.
of
and
【在 m****i 的大作中提到】
:
: Actually, you are right the left and right subtree have 1 node different.
: however, by definition, the balanced tree does not mean left and right
: subtree must have equal size.
: From wiki
: a self-balancing (or height-balanced) binary search tree is any node
: based binary search tree that automatically keeps its height (number of
: levels below the root) small in the face of arbitrary item insertions and
: deletion
|
i**********e
发帖数: 1145 | 27 Please don't get confuse :)
I don't know what you mean by min leaf node and max leaf node. Is it the
node that has min and max values? If it is, then your definition of balanced
bst is wrong.
The correct definition for a balanced bst is:
A tree whose subtrees differ in height by no more than one and the subtrees
are height-balanced, too.
When you subdivide the array and construct the bst top-down, you are
essentially maintaining the following invariant in each subdivision:
|#nodes in left subtree - #nodes in right subtree| = either 0 or 1.
If you want a unbalanced subtree, according to the definition you have to
generate two subtrees where height is differ by two (or above). This means
that in one of the subtree you need at least two level of subdivisions more
than the other subtree. This is impossible as the absolute difference
between the #nodes of both subtrees are at most 1, and each time you
subdivide in the center.
If you still don't understand, try to draw two arrays, where the #elements
in left array is N, and #elements in right array is N+1. Each time you would
subdivide in the middle of the array to two sub-arrays. Could you end up
with where the # of subdivisions of the left array and the # of subdivisions
of the right array differ by two or above?
This is impossible. Therefore, by proof of contradiction the bst must be
balanced. (I know this proof is not solid enough, but you get the idea.)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g*********s 的大作中提到】
: by definition, balanced bst must have the min leaf node level and max
: leaf node level difference O(1). by doing this, the max height is
: guaranteed to be O(logN) and this is the foundation for O(logN)
: operations insert, delete, etc.
: but in ur solution, the left and right sub-tree are not identical. and
: the left of left and right of left are possibly not identical too. so
: the min/max leaf could possibly non-zero. and this diff can accumulate
: and breaks the O(1) bound.
: unless there's a solid proof of the balanced property. but i can't
: figure it out.
|
h**********d
发帖数: 4313 | 28 你跑一下code试试吧，大家解释都不清楚
这个算法是给出层树最小的树，不会向你说的accumulated
【在 g*********s 的大作中提到】
: sorry, but can u prove this is balanced? i believe this algorithm creates
: a bst. but i'm not convinced the created bst is balanced.
: u can see the left and right sub-tree can have size difference by 1. if u
: do recursion, then is it possible at each level the left and right may
: have difference by 1? if so the worst case this difference is accumulated
: with an O(lgN) bound...
|
h**********d
发帖数: 4313 | 29 这题我以前看过
String replaceString(String string, String oldString, String newString){
if(string == null || oldString == null || newString == null){
throw new IllegalArgumentException("Null arguments");
}
if(oldString.equals("")){
throw new IllegalArgumentException("oldString has no content");
}
StringBuilder result = new StringBuilder();
int i = 0;
int j = 0;
while((j = string.indexOf(oldString, i)) >= 0){
result.append(string.substring(i, j));
result.append(newString);
i = j + oldString.length();
}
result.append(string.substring(i));
return result.toString();
}
GOOGLE那题
我就说用hashmap遍历记录count，或者用sort，但是没有前者快
他说就用hashmap把。然后多机多CPU的就把array分段分别处理，但是那样返回的各个
count是subarray的count，不好加起来吧，然后自己就有点晕了。。。。最后我说返回
hashmap，然后再数。。。。他说ok，但自己觉得答的很差
我不知道他说多core机器和多个机器到底要怎样的答案，我除了para computing也想不
出啥
replace(
【在 m****i 的大作中提到】
: 2. 实现Java String class的repleaceAll() method，不可以用String本身的replace(
: ), replaceAll()
: 2. 找一个string出现最多的字母，扩展问了很多，内存，多核CPU，多个多核CPU
: machine...一开始给的hashmap的解法最后combine会有点问题，反正吭哧吭哧的答了，
: 最后自己觉得并没有improve多少time complexity..
: 这两个可以详细说说么
|
i****d
发帖数: 35 | 30 mapreduce?
【在 h**********d 的大作中提到】
: 这题我以前看过
: String replaceString(String string, String oldString, String newString){
: if(string == null || oldString == null || newString == null){
: throw new IllegalArgumentException("Null arguments");
: }
: if(oldString.equals("")){
: throw new IllegalArgumentException("oldString has no content");
: }
: StringBuilder result = new StringBuilder();
: int i = 0;
|
|
|
b********r
发帖数: 118 | 31 你这两个都是电话面试吧 怎么还要2面 应该是onsite了吧 |
b********r
发帖数: 118 | 32 merge两个bst应该很简单吧
in order traverse之后就是2个sorted array了 然后用merge sort的merge
3个operation都是o(n) 所以total就是o(n) |
h**4
发帖数: 828 | |
d***b
发帖数: 24 | 34 看看这个Web Developer的求职网站：
http://jobguideweb.com/engineer-jobs/web-developer-jobs.html
replace(
【在 h**********d 的大作中提到】
: 都是前两个礼拜面的，下个礼拜2面，来攒个rp
: AMAZON
: 1. Research
: 2. 实现Java String class的repleaceAll() method，不可以用String本身的replace(
: ), replaceAll()
: 3. 合并2个BST, 要求O(n)time
: 4. 2个stack -> 1个queue
: GOOGLE
: 1. Research 因为我是做NLP的,machine learning涉及了一些，问的比较细，有点烦。
: 。。
|
E***n
发帖数: 166 | 35
replace(
这个replaceAll的第一个参数是regex,如果是replaceAll("[a-c][0-9]", "a"),怎么实
现它？还是他们只要你实现字符串替换字符串就行了？
【在 h**********d 的大作中提到】
: 都是前两个礼拜面的，下个礼拜2面，来攒个rp
: AMAZON
: 1. Research
: 2. 实现Java String class的repleaceAll() method，不可以用String本身的replace(
: ), replaceAll()
: 3. 合并2个BST, 要求O(n)time
: 4. 2个stack -> 1个queue
: GOOGLE
: 1. Research 因为我是做NLP的,machine learning涉及了一些，问的比较细，有点烦。
: 。。
|
