r*****k
发帖数: 1281 | 1 1 find kth element in two sorted arrays.
2 write a function to implement aligned memory allocation.
阿三面的，我第一题只给出o(k)的结果，第二题也写的不利索。挂了。我太弱了，还是
要练熟经典题啊！！
★ 发自iPhone App: ChineseWeb - 中文网站浏览器 |
h*c
发帖数: 1859 | 2 如果是sorted,应该lg(k)
【在 r*****k 的大作中提到】
: 1 find kth element in two sorted arrays.
: 2 write a function to implement aligned memory allocation.
: 阿三面的，我第一题只给出o(k)的结果，第二题也写的不利索。挂了。我太弱了，还是
: 要练熟经典题啊！！
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
r*****k
发帖数: 1281 | 3 O(log n)+O(log m), where n and m are the length of the two arrays.
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 h*c 的大作中提到】
: 如果是sorted,应该lg(k)
|
p*****2
发帖数: 21240 | 4
感觉写起来也不好写，如果没练过的话。有时间应该练练这题。
【在 h*c 的大作中提到】
: 如果是sorted,应该lg(k)
|
p*****2
发帖数: 21240 | 5
第二题什么意思。就是内存起始位置是%4的？
【在 r*****k 的大作中提到】
: 1 find kth element in two sorted arrays.
: 2 write a function to implement aligned memory allocation.
: 阿三面的，我第一题只给出o(k)的结果，第二题也写的不利索。挂了。我太弱了，还是
: 要练熟经典题啊！！
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
V******y
发帖数: 460 | |
h*c
发帖数: 1859 | 7 m,n里面有个大的,小的可以忽略...
【在 r*****k 的大作中提到】
: O(log n)+O(log m), where n and m are the length of the two arrays.
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
h*c
发帖数: 1859 | 8 新的C
支持alignment了
【在 p*****2 的大作中提到】
:
: 第二题什么意思。就是内存起始位置是%4的？
|
r*****k
发帖数: 1281 | 9 就是内存起始地址能被某数整除。
也是经典题，应该可以google到。
mymalloc(int size, int align) 返回一个大小为size 开始地址能被align整除的一块
内存。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 第二题什么意思。就是内存起始位置是%4的？
|
r*****k
发帖数: 1281 | 10 是的。但是忽略后也不是logk
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 h*c 的大作中提到】
: m,n里面有个大的,小的可以忽略...
|
|
|
h*c
发帖数: 1859 | 11 恩.我以外k是总数...
【在 r*****k 的大作中提到】
: 是的。但是忽略后也不是logk
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
g*********8
发帖数: 64 | 12 第一题ihascode1337的确给出了两个数组不一样的长度的情况，如果一样的长度可以参
考Algorithm Design (by Kleinberg) Chapter 5 Exercise 1,其实也很简单，就是
binary search 的variant，但是这两道的题的coding都很tricky，要非常注意，主要
是递归函数调用的参数传入
他们的coding让我想起了由tree的in-order, pre-order， reconstruct the
binary tree的题，也是一样的tricky编程，也是递归函数调用的参数传递
另外amazon好像还有很好玩的新题：
1）Given a tree preorder sequence such as “NNNLLLL” where N denotes non-
leaf node and L denotes leaf node, with the constraint that no nodes has 1
child. Rebuild the binary tree
2） Given post order traverse of a BST, rebuild the BST |
p*****2
发帖数: 21240 | 13
多申请几个字节的内存，比如4个字节alignment，就多申请4个字节，然后返回%4=0的
起始地址，内存可能比size长最多4个字节。这样可以吗？还是必须要exact size的。
sizeof()返回值就是size?
【在 r*****k 的大作中提到】
: 就是内存起始地址能被某数整除。
: 也是经典题，应该可以google到。
: mymalloc(int size, int align) 返回一个大小为size 开始地址能被align整除的一块
: 内存。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
p*****2
发帖数: 21240 | 14
1
第二题recursion吧
【在 g*********8 的大作中提到】
: 第一题ihascode1337的确给出了两个数组不一样的长度的情况，如果一样的长度可以参
: 考Algorithm Design (by Kleinberg) Chapter 5 Exercise 1,其实也很简单，就是
: binary search 的variant，但是这两道的题的coding都很tricky，要非常注意，主要
: 是递归函数调用的参数传入
: 他们的coding让我想起了由tree的in-order, pre-order， reconstruct the
: binary tree的题，也是一样的tricky编程，也是递归函数调用的参数传递
: 另外amazon好像还有很好玩的新题：
: 1）Given a tree preorder sequence such as “NNNLLLL” where N denotes non-
: leaf node and L denotes leaf node, with the constraint that no nodes has 1
: child. Rebuild the binary tree
|
z*****n
发帖数: 447 | 15 Amazon的这2题：
第一题：既然叶子数为0或者2，可以利用 Number of leaf = number of non-leaf + 1
, 区分了left 和right child，用DP就可以了；
第二题，节点值都得不同吧，而且光post-order肯定不行，还必须有一个in-order的；
post-order确定root, 然后inorder找left, right
non-
has 1
【在 g*********8 的大作中提到】
: 第一题ihascode1337的确给出了两个数组不一样的长度的情况，如果一样的长度可以参
: 考Algorithm Design (by Kleinberg) Chapter 5 Exercise 1,其实也很简单，就是
: binary search 的variant，但是这两道的题的coding都很tricky，要非常注意，主要
: 是递归函数调用的参数传入
: 他们的coding让我想起了由tree的in-order, pre-order， reconstruct the
: binary tree的题，也是一样的tricky编程，也是递归函数调用的参数传递
: 另外amazon好像还有很好玩的新题：
: 1）Given a tree preorder sequence such as “NNNLLLL” where N denotes non-
: leaf node and L denotes leaf node, with the constraint that no nodes has 1
: child. Rebuild the binary tree
|
p*****2
发帖数: 21240 | 16
1
post-order找到root, 然后往前找到一个小于root的就是left tree了，不对吗？
【在 z*****n 的大作中提到】
: Amazon的这2题：
: 第一题：既然叶子数为0或者2，可以利用 Number of leaf = number of non-leaf + 1
: , 区分了left 和right child，用DP就可以了；
: 第二题，节点值都得不同吧，而且光post-order肯定不行，还必须有一个in-order的；
: post-order确定root, 然后inorder找left, right
:
: non-
: has 1
|
z*****n
发帖数: 447 | 17 忘了是BST， 那一个post-order也可以，照你说的往前找第一个小于root的，就可以划
分left
【在 p*****2 的大作中提到】
:
: 1
: post-order找到root, 然后往前找到一个小于root的就是left tree了，不对吗？
|
d*******9
发帖数: 22 | 18 为啥我觉得应该就是log(k)啊... k refers to the k-th smallest
【在 h*c 的大作中提到】
: 恩.我以外k是总数...
|
h*c
发帖数: 1859 | 19 if k = 1
【在 d*******9 的大作中提到】
: 为啥我觉得应该就是log(k)啊... k refers to the k-th smallest
|
d*******9
发帖数: 22 | 20 kth element一定在array A的前k个+array B的前k个里
如果 A[k/2] < B[k/2]，那么kth element在A[k/2...k]+B[1...k/2]里
如果 A[k/2] > B[k/2]，那么kth element在A[1...k/2]+B[k/2...k]里
then do it recursively
【在 h*c 的大作中提到】
: if k = 1
|
|
|
h*c
发帖数: 1859 | 21 好像是对的,其实这个程序我写过,很久以前,现在都忘了
【在 d*******9 的大作中提到】
: kth element一定在array A的前k个+array B的前k个里
: 如果 A[k/2] < B[k/2]，那么kth element在A[k/2...k]+B[1...k/2]里
: 如果 A[k/2] > B[k/2]，那么kth element在A[1...k/2]+B[k/2...k]里
: then do it recursively
|
h*c
发帖数: 1859 | 22 看了一下我得笔记
lg(k) = lg(n+m)
so ...
【在 h*c 的大作中提到】
: 好像是对的,其实这个程序我写过,很久以前,现在都忘了
|
d*******9
发帖数: 22 | 23 well, yes...
【在 h*c 的大作中提到】
: 看了一下我得笔记
: lg(k) = lg(n+m)
: so ...
|
a********m
发帖数: 15480 | 24 是lgk吧。 n,m无限大也只考虑前2k个数字。
【在 h*c 的大作中提到】
: 看了一下我得笔记
: lg(k) = lg(n+m)
: so ...
|
p*****2
发帖数: 21240 | 25
恩。同意。
【在 a********m 的大作中提到】
: 是lgk吧。 n,m无限大也只考虑前2k个数字。
|
a********m
发帖数: 15480 | |
H***e
发帖数: 476 | 27 这两题电面也太阴了
【在 r*****k 的大作中提到】
: 1 find kth element in two sorted arrays.
: 2 write a function to implement aligned memory allocation.
: 阿三面的，我第一题只给出o(k)的结果，第二题也写的不利索。挂了。我太弱了，还是
: 要练熟经典题啊！！
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
S*******w
发帖数: 24236 | 28 咋啦 这2题也算简单的吧
【在 H***e 的大作中提到】
: 这两题电面也太阴了
|
l*****a
发帖数: 14598 | 29 1。不能算很简单吧
2。电话中写的很好，再念出来，比较难吧
【在 S*******w 的大作中提到】
: 咋啦 这2题也算简单的吧
|
H***e
发帖数: 476 | 30 你写过么第一题？
try it out 呵呵 lg的复杂度那种
想起来比较简单，真正写，谁能在一小时内写加调对(想算法时间不算)，算大大牛了。
【在 l*****a 的大作中提到】
: 1。不能算很简单吧
: 2。电话中写的很好，再念出来，比较难吧
|
|
|
H****s
发帖数: 247 | 31 这两道题不简单吧，第一题思路不难，但coding算top 5%的难题了。
说实在，问第一题够阴的。
【在 S*******w 的大作中提到】
: 咋啦 这2题也算简单的吧
|
B*******1
发帖数: 2454 | 32 是啊，老印这不是明坑人吗？ 这题onsite还差不多。 |
m*******l
发帖数: 12782 | 33 恩,第一体比较tricky
【在 B*******1 的大作中提到】
: 是啊，老印这不是明坑人吗？ 这题onsite还差不多。
|
l*****a
发帖数: 14598 | 34 咱俩说的不是一个意思？
【在 H***e 的大作中提到】
: 你写过么第一题？
: try it out 呵呵 lg的复杂度那种
: 想起来比较简单，真正写，谁能在一小时内写加调对(想算法时间不算)，算大大牛了。
|
p*****2
发帖数: 21240 | 35
他应该是回的你楼上的。
【在 l*****a 的大作中提到】
: 咱俩说的不是一个意思？
|
l*****a
发帖数: 14598 | 36 then it is better to reply directly while not reply my post
【在 p*****2 的大作中提到】
:
: 他应该是回的你楼上的。
|
H***e
发帖数: 476 | 37 喔
我确实是回你的
你说不能算很简单，其实我的意思是很难勒
【在 l*****a 的大作中提到】
: then it is better to reply directly while not reply my post
|
w***g
发帖数: 5958 | 38 赞犀利！
【在 d*******9 的大作中提到】
: kth element一定在array A的前k个+array B的前k个里
: 如果 A[k/2] < B[k/2]，那么kth element在A[k/2...k]+B[1...k/2]里
: 如果 A[k/2] > B[k/2]，那么kth element在A[1...k/2]+B[k/2...k]里
: then do it recursively
|
z*y
发帖数: 1311 | |
r*****k
发帖数: 1281 | 40 没看啊。。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 z*y 的大作中提到】
: 第一题1337里不就有么
|
|
|
C*********u
发帖数: 116 | 41 迷糊第一题，既然是array，读Kth element不是O（1），直接就找到了吗？为啥我看不
懂题目. :( |
p*****2
发帖数: 21240 | 42
两个array呀。
【在 C*********u 的大作中提到】
: 迷糊第一题，既然是array，读Kth element不是O（1），直接就找到了吗？为啥我看不
: 懂题目. :(
|
C*********u
发帖数: 116 | 43 噢,那就是找从小到大的第k个或者是从大到小的第k个？
【在 p*****2 的大作中提到】
:
: 两个array呀。
|
a*****n
发帖数: 158 | 44 里面有的题都算比较难的了，嘿嘿，否则也不值得大牛写。。。
【在 z*y 的大作中提到】
: 第一题1337里不就有么
|
H*****1
发帖数: 4815 | 45 是log k
第一个array里二分作为pilot在第二个array里二分查找
如果m > k; n > k，只用搜索a[0:k-1] 和 b[0:k-1]
【在 r*****k 的大作中提到】
: 是的。但是忽略后也不是logk
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
g*********e
发帖数: 14401 | 46 第一题是log(k)吧 每次都少一半
难点在于M,n值不同，并且一开始就有一个
要是m=n>=k 还容易的 |
w****x
发帖数: 2483 | 47 第一题我在1337什么里看了, 复杂的一塌糊涂, 不大相信有多少人就算知道思路的情况
下能现场写出来lgk的, 特别是如果没见过的情况下.
我估计出这个题的人就像考考merge sort |
h********w
发帖数: 221 | 48 我弱了，第一题啥意思？能细说么？为啥大家都能理解？ |
r*****k
发帖数: 1281 | 49 1 find kth element in two sorted arrays.
2 write a function to implement aligned memory allocation.
阿三面的，我第一题只给出o(k)的结果，第二题也写的不利索。挂了。我太弱了，还是
要练熟经典题啊！！
★ 发自iPhone App: ChineseWeb - 中文网站浏览器 |
h*c
发帖数: 1859 | 50 如果是sorted,应该lg(k)
【在 r*****k 的大作中提到】
: 1 find kth element in two sorted arrays.
: 2 write a function to implement aligned memory allocation.
: 阿三面的，我第一题只给出o(k)的结果，第二题也写的不利索。挂了。我太弱了，还是
: 要练熟经典题啊！！
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
|
|
r*****k
发帖数: 1281 | 51 O(log n)+O(log m), where n and m are the length of the two arrays.
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 h*c 的大作中提到】
: 如果是sorted,应该lg(k)
|
p*****2
发帖数: 21240 | 52
感觉写起来也不好写，如果没练过的话。有时间应该练练这题。
【在 h*c 的大作中提到】
: 如果是sorted,应该lg(k)
|
p*****2
发帖数: 21240 | 53
第二题什么意思。就是内存起始位置是%4的？
【在 r*****k 的大作中提到】
: 1 find kth element in two sorted arrays.
: 2 write a function to implement aligned memory allocation.
: 阿三面的，我第一题只给出o(k)的结果，第二题也写的不利索。挂了。我太弱了，还是
: 要练熟经典题啊！！
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
V******y
发帖数: 460 | |
h*c
发帖数: 1859 | 55 m,n里面有个大的,小的可以忽略...
【在 r*****k 的大作中提到】
: O(log n)+O(log m), where n and m are the length of the two arrays.
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
h*c
发帖数: 1859 | 56 新的C
支持alignment了
【在 p*****2 的大作中提到】
:
: 第二题什么意思。就是内存起始位置是%4的？
|
r*****k
发帖数: 1281 | 57 就是内存起始地址能被某数整除。
也是经典题，应该可以google到。
mymalloc(int size, int align) 返回一个大小为size 开始地址能被align整除的一块
内存。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 第二题什么意思。就是内存起始位置是%4的？
|
r*****k
发帖数: 1281 | 58 是的。但是忽略后也不是logk
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 h*c 的大作中提到】
: m,n里面有个大的,小的可以忽略...
|
h*c
发帖数: 1859 | 59 恩.我以外k是总数...
【在 r*****k 的大作中提到】
: 是的。但是忽略后也不是logk
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
g*********8
发帖数: 64 | 60 第一题ihascode1337的确给出了两个数组不一样的长度的情况，如果一样的长度可以参
考Algorithm Design (by Kleinberg) Chapter 5 Exercise 1,其实也很简单，就是
binary search 的variant，但是这两道的题的coding都很tricky，要非常注意，主要
是递归函数调用的参数传入
他们的coding让我想起了由tree的in-order, pre-order， reconstruct the
binary tree的题，也是一样的tricky编程，也是递归函数调用的参数传递
另外amazon好像还有很好玩的新题：
1）Given a tree preorder sequence such as “NNNLLLL” where N denotes non-
leaf node and L denotes leaf node, with the constraint that no nodes has 1
child. Rebuild the binary tree
2） Given post order traverse of a BST, rebuild the BST |
|
|
p*****2
发帖数: 21240 | 61
多申请几个字节的内存，比如4个字节alignment，就多申请4个字节，然后返回%4=0的
起始地址，内存可能比size长最多4个字节。这样可以吗？还是必须要exact size的。
sizeof()返回值就是size?
【在 r*****k 的大作中提到】
: 就是内存起始地址能被某数整除。
: 也是经典题，应该可以google到。
: mymalloc(int size, int align) 返回一个大小为size 开始地址能被align整除的一块
: 内存。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
p*****2
发帖数: 21240 | 62
1
第二题recursion吧
【在 g*********8 的大作中提到】
: 第一题ihascode1337的确给出了两个数组不一样的长度的情况，如果一样的长度可以参
: 考Algorithm Design (by Kleinberg) Chapter 5 Exercise 1,其实也很简单，就是
: binary search 的variant，但是这两道的题的coding都很tricky，要非常注意，主要
: 是递归函数调用的参数传入
: 他们的coding让我想起了由tree的in-order, pre-order， reconstruct the
: binary tree的题，也是一样的tricky编程，也是递归函数调用的参数传递
: 另外amazon好像还有很好玩的新题：
: 1）Given a tree preorder sequence such as “NNNLLLL” where N denotes non-
: leaf node and L denotes leaf node, with the constraint that no nodes has 1
: child. Rebuild the binary tree
|
z*****n
发帖数: 447 | 63 Amazon的这2题：
第一题：既然叶子数为0或者2，可以利用 Number of leaf = number of non-leaf + 1
, 区分了left 和right child，用DP就可以了；
第二题，节点值都得不同吧，而且光post-order肯定不行，还必须有一个in-order的；
post-order确定root, 然后inorder找left, right
non-
has 1
【在 g*********8 的大作中提到】
: 第一题ihascode1337的确给出了两个数组不一样的长度的情况，如果一样的长度可以参
: 考Algorithm Design (by Kleinberg) Chapter 5 Exercise 1,其实也很简单，就是
: binary search 的variant，但是这两道的题的coding都很tricky，要非常注意，主要
: 是递归函数调用的参数传入
: 他们的coding让我想起了由tree的in-order, pre-order， reconstruct the
: binary tree的题，也是一样的tricky编程，也是递归函数调用的参数传递
: 另外amazon好像还有很好玩的新题：
: 1）Given a tree preorder sequence such as “NNNLLLL” where N denotes non-
: leaf node and L denotes leaf node, with the constraint that no nodes has 1
: child. Rebuild the binary tree
|
p*****2
发帖数: 21240 | 64
1
post-order找到root, 然后往前找到一个小于root的就是left tree了，不对吗？
【在 z*****n 的大作中提到】
: Amazon的这2题：
: 第一题：既然叶子数为0或者2，可以利用 Number of leaf = number of non-leaf + 1
: , 区分了left 和right child，用DP就可以了；
: 第二题，节点值都得不同吧，而且光post-order肯定不行，还必须有一个in-order的；
: post-order确定root, 然后inorder找left, right
:
: non-
: has 1
|
z*****n
发帖数: 447 | 65 忘了是BST， 那一个post-order也可以，照你说的往前找第一个小于root的，就可以划
分left
【在 p*****2 的大作中提到】
:
: 1
: post-order找到root, 然后往前找到一个小于root的就是left tree了，不对吗？
|
d*******9
发帖数: 22 | 66 为啥我觉得应该就是log(k)啊... k refers to the k-th smallest
【在 h*c 的大作中提到】
: 恩.我以外k是总数...
|
h*c
发帖数: 1859 | 67 if k = 1
【在 d*******9 的大作中提到】
: 为啥我觉得应该就是log(k)啊... k refers to the k-th smallest
|
d*******9
发帖数: 22 | 68 kth element一定在array A的前k个+array B的前k个里
如果 A[k/2] < B[k/2]，那么kth element在A[k/2...k]+B[1...k/2]里
如果 A[k/2] > B[k/2]，那么kth element在A[1...k/2]+B[k/2...k]里
then do it recursively
【在 h*c 的大作中提到】
: if k = 1
|
h*c
发帖数: 1859 | 69 好像是对的,其实这个程序我写过,很久以前,现在都忘了
【在 d*******9 的大作中提到】
: kth element一定在array A的前k个+array B的前k个里
: 如果 A[k/2] < B[k/2]，那么kth element在A[k/2...k]+B[1...k/2]里
: 如果 A[k/2] > B[k/2]，那么kth element在A[1...k/2]+B[k/2...k]里
: then do it recursively
|
h*c
发帖数: 1859 | 70 看了一下我得笔记
lg(k) = lg(n+m)
so ...
【在 h*c 的大作中提到】
: 好像是对的,其实这个程序我写过,很久以前,现在都忘了
|
|
|
d*******9
发帖数: 22 | 71 well, yes...
【在 h*c 的大作中提到】
: 看了一下我得笔记
: lg(k) = lg(n+m)
: so ...
|
a********m
发帖数: 15480 | 72 是lgk吧。 n,m无限大也只考虑前2k个数字。
【在 h*c 的大作中提到】
: 看了一下我得笔记
: lg(k) = lg(n+m)
: so ...
|
p*****2
发帖数: 21240 | 73
恩。同意。
【在 a********m 的大作中提到】
: 是lgk吧。 n,m无限大也只考虑前2k个数字。
|
a********m
发帖数: 15480 | |
H***e
发帖数: 476 | 75 这两题电面也太阴了
【在 r*****k 的大作中提到】
: 1 find kth element in two sorted arrays.
: 2 write a function to implement aligned memory allocation.
: 阿三面的，我第一题只给出o(k)的结果，第二题也写的不利索。挂了。我太弱了，还是
: 要练熟经典题啊！！
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
S*******w
发帖数: 24236 | 76 咋啦 这2题也算简单的吧
【在 H***e 的大作中提到】
: 这两题电面也太阴了
|
l*****a
发帖数: 14598 | 77 1。不能算很简单吧
2。电话中写的很好，再念出来，比较难吧
【在 S*******w 的大作中提到】
: 咋啦 这2题也算简单的吧
|
H***e
发帖数: 476 | 78 你写过么第一题？
try it out 呵呵 lg的复杂度那种
想起来比较简单，真正写，谁能在一小时内写加调对(想算法时间不算)，算大大牛了。
【在 l*****a 的大作中提到】
: 1。不能算很简单吧
: 2。电话中写的很好，再念出来，比较难吧
|
H****s
发帖数: 247 | 79 这两道题不简单吧，第一题思路不难，但coding算top 5%的难题了。
说实在，问第一题够阴的。
【在 S*******w 的大作中提到】
: 咋啦 这2题也算简单的吧
|
B*******1
发帖数: 2454 | 80 是啊，老印这不是明坑人吗？ 这题onsite还差不多。 |
|
|
m*******l
发帖数: 12782 | 81 恩,第一体比较tricky
【在 B*******1 的大作中提到】
: 是啊，老印这不是明坑人吗？ 这题onsite还差不多。
|
l*****a
发帖数: 14598 | 82 咱俩说的不是一个意思？
【在 H***e 的大作中提到】
: 你写过么第一题？
: try it out 呵呵 lg的复杂度那种
: 想起来比较简单，真正写，谁能在一小时内写加调对(想算法时间不算)，算大大牛了。
|
p*****2
发帖数: 21240 | 83
他应该是回的你楼上的。
【在 l*****a 的大作中提到】
: 咱俩说的不是一个意思？
|
l*****a
发帖数: 14598 | 84 then it is better to reply directly while not reply my post
【在 p*****2 的大作中提到】
:
: 他应该是回的你楼上的。
|
H***e
发帖数: 476 | 85 喔
我确实是回你的
你说不能算很简单，其实我的意思是很难勒
【在 l*****a 的大作中提到】
: then it is better to reply directly while not reply my post
|
w***g
发帖数: 5958 | 86 赞犀利！
【在 d*******9 的大作中提到】
: kth element一定在array A的前k个+array B的前k个里
: 如果 A[k/2] < B[k/2]，那么kth element在A[k/2...k]+B[1...k/2]里
: 如果 A[k/2] > B[k/2]，那么kth element在A[1...k/2]+B[k/2...k]里
: then do it recursively
|
z*y
发帖数: 1311 | |
r*****k
发帖数: 1281 | 88 没看啊。。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 z*y 的大作中提到】
: 第一题1337里不就有么
|
C*********u
发帖数: 116 | 89 迷糊第一题，既然是array，读Kth element不是O（1），直接就找到了吗？为啥我看不
懂题目. :( |
p*****2
发帖数: 21240 | 90
两个array呀。
【在 C*********u 的大作中提到】
: 迷糊第一题，既然是array，读Kth element不是O（1），直接就找到了吗？为啥我看不
: 懂题目. :(
|
|
|
C*********u
发帖数: 116 | 91 噢,那就是找从小到大的第k个或者是从大到小的第k个？
【在 p*****2 的大作中提到】
:
: 两个array呀。
|
a*****n
发帖数: 158 | 92 里面有的题都算比较难的了，嘿嘿，否则也不值得大牛写。。。
【在 z*y 的大作中提到】
: 第一题1337里不就有么
|
H*****1
发帖数: 4815 | 93 是log k
第一个array里二分作为pilot在第二个array里二分查找
如果m > k; n > k，只用搜索a[0:k-1] 和 b[0:k-1]
【在 r*****k 的大作中提到】
: 是的。但是忽略后也不是logk
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
g*********e
发帖数: 14401 | 94 第一题是log(k)吧 每次都少一半
难点在于M,n值不同，并且一开始就有一个
要是m=n>=k 还容易的 |
w****x
发帖数: 2483 | 95 第一题我在1337什么里看了, 复杂的一塌糊涂, 不大相信有多少人就算知道思路的情况
下能现场写出来lgk的, 特别是如果没见过的情况下.
我估计出这个题的人就像考考merge sort |
h********w
发帖数: 221 | 96 我弱了，第一题啥意思？能细说么？为啥大家都能理解？ |
r*******m
发帖数: 457 | 97
what is 1337?
【在 z*y 的大作中提到】
: 第一题1337里不就有么
|
j********2
发帖数: 82 | 98 哪位给个正解？
【在 r*****k 的大作中提到】
: 就是内存起始地址能被某数整除。
: 也是经典题，应该可以google到。
: mymalloc(int size, int align) 返回一个大小为size 开始地址能被align整除的一块
: 内存。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
j*****o
发帖数: 394 | 99 cc150不是有答案吗
【在 j********2 的大作中提到】
: 哪位给个正解？
|
w****x
发帖数: 2483 | 100
哪??
【在 j*****o 的大作中提到】
: cc150不是有答案吗
|
|
|
g****y
发帖数: 240 | 101 尝试着写了一下第一题：
def findk(alist, blist, k):
"""Given two sorted array, find kth minimum element"""
m = len(alist)
n = len(blist)
assert (k <= m + n)
if m == 0:
return blist[k - 1]
elif n == 0:
return alist[k - 1]
if k == 1:
return min(alist[0], blist[0])
# divide k into two even parts as much as possible
ai = min(k // 2, m)
bi = k - ai
if bi > n:
bi = n
ai = k - bi
if alist[ai - 1] == blist[bi - 1]:
return alist[ai - 1]
elif alist[ai - 1] > blist[bi - 1]:
return findk(alist[:ai], blist[bi:], k - bi)
else:
return findk(alist[ai:], blist[:bi], k - ai) |
s*********0
发帖数: 89 | 102 我也没找到啊。。。
【在 w****x 的大作中提到】
:
: 哪??
|
w****x
发帖数: 2483 | 103 半年前觉得挺不好写, 现在写也挺快的
int GetMedian(int a[], int n, int b[], int m, int k)
{
assert(a && b);
if (n <= 0) return b[k-1];
if (m <= 0) return a[k-1];
if (k <= 1) return min(a[0], b[0]);
if (b[m/2] >= a[n/2])
{
if ((n/2 + 1 + m/2) >= k)
return GetMedian(a, n, b, m/2, k);
else
return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1)
);
}
else
{
if ((m/2 + 1 + n/2) >= k)
return GetMedian(b, m, a, n/2, k);
else
return GetMedian(b + m/2 + 1, m - (m/2 + 1), a, n, k - (m/2 + 1)
);
}
} |
s***u
发帖数: 101 | 104 第一题为啥要用DP，遇到‘L’做成一个leaf 然后返回给父节点 不就好了么？
1
【在 z*****n 的大作中提到】
: Amazon的这2题：
: 第一题：既然叶子数为0或者2，可以利用 Number of leaf = number of non-leaf + 1
: , 区分了left 和right child，用DP就可以了；
: 第二题，节点值都得不同吧，而且光post-order肯定不行，还必须有一个in-order的；
: post-order确定root, 然后inorder找left, right
:
: non-
: has 1
|
l*****a
发帖数: 559 | 105 I tried. Your code is not working.
#include
#include
#include
#include
#include
#include
using namespace std;
double GetMedian (int* a, int n, int* b, int m, int k)
{
assert(a && b);
if (n <= 0) return b[k-1];
if (m <= 0) return a[k-1];
if (k <= 1) return min(a[0], b[0]);
if (b[m/2] >= a[n/2])
{
if ((n/2 + 1 + m/2) >= k)
return GetMedian(a, n, b, m/2, k);
else
return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1)
);
}
else
{
if ((m/2 + 1 + n/2) >= k)
return GetMedian(b, m, a, n/2, k);
else
return GetMedian(b + m/2 + 1, m - (m/2 + 1), a, n, k - (m/2 + 1)
);
}
}
int main()
{
for(int k = 1000; k < 10000;k++){
int length1 = rand()%k;
int length2 = rand()%k;
double median;
int* A = new int[length1];
int* B = new int[length2] ;
for(int i = 0; i < length1; i++) A[i] = rand() % 10000 ;
sort (A, A+length1 );
for(int i = 0; i < length2; i++) B[i] = rand() % 10000 ;
sort (B, B+length2 );
if ( length1 <= length2 )
median = GetMedian (A, length1, B, length2, (length1 + length2) / 2) ;
else
median = GetMedian (B, length2, A, length1, (length1 + length2) / 2) ;
cout << "median : " << median << endl;
//verfication
vector c (A, A+length1 );
double verifiedMedian;
c.insert (c.end(), B, B+length2 );
sort ( c.begin(), c.end() ) ;
int sz = c.size();
verifiedMedian = c [sz/2] ;
cout << "VERIFIED MEDIAN : " << verifiedMedian << endl;
assert (median == verifiedMedian);
delete[] A;
delete[] B;
}
//verification end
system("pause");
return 0;
}
【在 w****x 的大作中提到】
: 半年前觉得挺不好写, 现在写也挺快的
: int GetMedian(int a[], int n, int b[], int m, int k)
: {
: assert(a && b);
: if (n <= 0) return b[k-1];
: if (m <= 0) return a[k-1];
: if (k <= 1) return min(a[0], b[0]);
: if (b[m/2] >= a[n/2])
: {
: if ((n/2 + 1 + m/2) >= k)
|
C***U
发帖数: 2406 | 106 是logk 你这个是错的
【在 r*****k 的大作中提到】
: O(log n)+O(log m), where n and m are the length of the two arrays.
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
w****x
发帖数: 2483 | 107
恩,这个leetcode都没过
【在 l*****a 的大作中提到】
: I tried. Your code is not working.
: #include
: #include
: #include
: #include
: #include
: #include
: using namespace std;
: double GetMedian (int* a, int n, int* b, int m, int k)
: {
|
w********0
发帖数: 2 | 108 试着写了一下，好像可以，没有仔细测试。
public class FindKthFromTwoArray{
public static void main(String[] args)
{
int[] a = {2,4,6,7,8,10,19,20,24,98};
int[] b = {2,5,15,18,27,34,56,67,100,140};
// int[] a = {2,4,19,29,39,49,59};
// int[] b = {1,5,6,7,12,29,30,33,45,67,78};
// int[] a = {2};
// int[] b = {1};
int k = 16;
int result = FindKthFromTwoArray.findKth(a,b,k);
System.out.println("The kth number is: " + result);
}
public static int findKth(int[] a, int[] b, int k){
return findKth(a,0,b,0,k);
}
private static int findKth(int[] a, int aoffset, int[] b, int boffset,
int k){
assert a.length + b.length >= k+1;
int sa,sb;
if (k == 0) return a[aoffset]< b[boffset]? a[aoffset]:b[boffset];
if (k%2 == 0){
sa= k/2; sb = k/2-1;
}
else {
sa= k/2; sb = k/2;
}
int amid = sa + aoffset;
int bmid = sb + boffset;
if (amid > a.length-2)
return linearSearch(a,aoffset,b,boffset,k);
if (bmid > b.length-2)
return linearSearch(a,aoffset,b,boffset,k);
if (a[amid] < b[bmid])
return findKth(a,amid+1,b,boffset,k-sa-1);
else
return findKth(a,aoffset,b,bmid+1,k-sb-1);
}
public static int linearSearch(int[] a, int aStart, int[] b, int bStart,
int k){
int count = 0;
int i=aStart,j=bStart;
while(count < k){
if (i == a.length-1 && j == b.length-1)
return a[i]> b[j]? a[i]:b[j];
if (i == a.length-1){
j++;
if (b[j] >= a[i])
return b[k-a.length];
}
else if (j == b.length-1){
i++;
if (a[i] >= b[j])
return a[k-b.length];
}
else{
if(a[i] < b[j])
i++;
else
j++;
}
count++;
}
return a[i]< b[j]? a[i]:b[j];
}
} |
g*******n
发帖数: 214 | 109 请问楼主是网申的么？怎么拿到电面的？
谢谢！
【在 r*****k 的大作中提到】
: 1 find kth element in two sorted arrays.
: 2 write a function to implement aligned memory allocation.
: 阿三面的，我第一题只给出o(k)的结果，第二题也写的不利索。挂了。我太弱了，还是
: 要练熟经典题啊！！
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
