由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Google Phone Interview
相关主题
linkedin电面题谷歌面经
这两个edit distance的codeleetcode的run time error
Microsoft screening programming problem问下Linkedin的一道电面
4sum的那道题最新L家面经
做一下common prefix in sorted string arrays开始刷leetcode,第一道题一直有run time error
上一道我以前喜欢出的题目吧问一道FB面试题
好象是google的高频题目google seti onsite
一道字符串题目新鲜的T电面题
相关话题的讨论汇总
话题: lru话题: cache话题: find话题: log话题: sizea
进入JobHunting版参与讨论
1 (共1页)
a***g
发帖数: 234
1
1. Given 2 sorted arrays A and B, find the kth element in the merged array A
U B
Time complexity requirement: log(k)
2. Least Recently Used (LRU) Cache: discards the least recently used items
first
How do you design and implement such a cache class?
1) find or search the item quickly
2) when there is a cache miss and cache is full, u want to replace the
least recently used item quickly
r****o
发帖数: 1950
2
第一题两个sorted array是不是可以不一样长?
第二题可以用min heap实现吗?

A

【在 a***g 的大作中提到】
: 1. Given 2 sorted arrays A and B, find the kth element in the merged array A
: U B
: Time complexity requirement: log(k)
: 2. Least Recently Used (LRU) Cache: discards the least recently used items
: first
: How do you design and implement such a cache class?
: 1) find or search the item quickly
: 2) when there is a cache miss and cache is full, u want to replace the
: least recently used item quickly

a***g
发帖数: 234
3
可以不一样长
min heap不能find the item quickly

【在 r****o 的大作中提到】
: 第一题两个sorted array是不是可以不一样长?
: 第二题可以用min heap实现吗?
:
: A

r****o
发帖数: 1950
4
min heap直接返回top不就可以了吗?

【在 a***g 的大作中提到】
: 可以不一样长
: min heap不能find the item quickly

a***g
发帖数: 234
5
top is the minimal, you also need to access to any other item quickly

【在 r****o 的大作中提到】
: min heap直接返回top不就可以了吗?
m****u
发帖数: 3915
6
第一题怎么做?
c**a
发帖数: 316
7
log(k)?
log(N) 可以实现吧。 log(k) 不可能吧。
第一题。
第二题, 2个binary tree, 再加一个 stack 不久行了。

A

【在 a***g 的大作中提到】
: 1. Given 2 sorted arrays A and B, find the kth element in the merged array A
: U B
: Time complexity requirement: log(k)
: 2. Least Recently Used (LRU) Cache: discards the least recently used items
: first
: How do you design and implement such a cache class?
: 1) find or search the item quickly
: 2) when there is a cache miss and cache is full, u want to replace the
: least recently used item quickly

h****r
发帖数: 2056
8
log(k)可能,
把问题退化为find k th element from a[0,k-1] and b[0,k-1],一下子就查找长度从N
退化到k级别(2k)。
比较a[k/2]和b[k/2],如果a[k/2]小,那么 the element一定在a[k/2,k]和 b[0, k/2
]中,反之则在a[0, k/2]和b[k/2,k]中,重复这个步骤继续二分法比较下去即可。

【在 c**a 的大作中提到】
: log(k)?
: log(N) 可以实现吧。 log(k) 不可能吧。
: 第一题。
: 第二题, 2个binary tree, 再加一个 stack 不久行了。
:
: A

r****o
发帖数: 1950
9
请问你能不能再推广到更general的case,
1)一个array 长度>k,另一个array长度 2)两个array长度都k

从N
/2

【在 h****r 的大作中提到】
: log(k)可能,
: 把问题退化为find k th element from a[0,k-1] and b[0,k-1],一下子就查找长度从N
: 退化到k级别(2k)。
: 比较a[k/2]和b[k/2],如果a[k/2]小,那么 the element一定在a[k/2,k]和 b[0, k/2
: ]中,反之则在a[0, k/2]和b[k/2,k]中,重复这个步骤继续二分法比较下去即可。

r****o
发帖数: 1950
10
能不能说说第二题为什么用binary tree和stack?

【在 c**a 的大作中提到】
: log(k)?
: log(N) 可以实现吧。 log(k) 不可能吧。
: 第一题。
: 第二题, 2个binary tree, 再加一个 stack 不久行了。
:
: A

相关主题
上一道我以前喜欢出的题目吧谷歌面经
好象是google的高频题目leetcode的run time error
一道字符串题目问下Linkedin的一道电面
进入JobHunting版参与讨论
h****r
发帖数: 2056
11
这两个都还不到search 2k data的程度。

【在 r****o 的大作中提到】
: 请问你能不能再推广到更general的case,
: 1)一个array 长度>k,另一个array长度: 2)两个array长度都k
:
: 从N
: /2

r****o
发帖数: 1950
12
题目是要log(k)的复杂度啊。

【在 h****r 的大作中提到】
: 这两个都还不到search 2k data的程度。
b******v
发帖数: 1493
13
第1题:假设A,B的size分别为A, B,不失一般性,假设A <= B
(1)先假设k <= A
则merge后的第k个元素只可能在A和B的前k个元素里面,并且是这2k个元素的median
在两个size为k的sorted array中找median是网上的老题,复杂性log(k)
(2)如果k > A
如果A+B-k+1 <= A (i.e. k >=B+1 ),则可以考虑A和B的后A+B-k+1个元素找median
O(log(A+B-k+1)) <= O(log(k+k-k)) = O(log(k))
(3) 如果 A < k <= B
这个等我吃完饭继续想

A

【在 a***g 的大作中提到】
: 1. Given 2 sorted arrays A and B, find the kth element in the merged array A
: U B
: Time complexity requirement: log(k)
: 2. Least Recently Used (LRU) Cache: discards the least recently used items
: first
: How do you design and implement such a cache class?
: 1) find or search the item quickly
: 2) when there is a cache miss and cache is full, u want to replace the
: least recently used item quickly

s*********t
发帖数: 1663
14
find(a[0,k],b[0,k]):
if a(k/2)==b(k/2): OK!
elif a(k/2)>b(k/2): find( a[0,k/2], b[k/2, k] )
else find(a[k/2,k],b[0,k/2])

A

【在 a***g 的大作中提到】
: 1. Given 2 sorted arrays A and B, find the kth element in the merged array A
: U B
: Time complexity requirement: log(k)
: 2. Least Recently Used (LRU) Cache: discards the least recently used items
: first
: How do you design and implement such a cache class?
: 1) find or search the item quickly
: 2) when there is a cache miss and cache is full, u want to replace the
: least recently used item quickly

b******v
发帖数: 1493
15
如果A < k <= B
则取array B的median,用binary search找出它在A中的位置,
由此可以找出它在整个(A+B)个数中的位置k0,
(a)如果k = k0,则程序结束
(b)如果k < k0,则可以扔掉B的后一半和A的后半段
(c)如果k > k0, 则可以扔掉B的前一半和A的前半段
这样问题转化为两个size为A'和B/2的sorted array的情形
使用递归可以解决

【在 b******v 的大作中提到】
: 第1题:假设A,B的size分别为A, B,不失一般性,假设A <= B
: (1)先假设k <= A
: 则merge后的第k个元素只可能在A和B的前k个元素里面,并且是这2k个元素的median
: 在两个size为k的sorted array中找median是网上的老题,复杂性log(k)
: (2)如果k > A
: 如果A+B-k+1 <= A (i.e. k >=B+1 ),则可以考虑A和B的后A+B-k+1个元素找median
: O(log(A+B-k+1)) <= O(log(k+k-k)) = O(log(k))
: (3) 如果 A < k <= B
: 这个等我吃完饭继续想
:

r****o
发帖数: 1950
16
你说的第2)和第3)种情况有什么区别?

【在 b******v 的大作中提到】
: 第1题:假设A,B的size分别为A, B,不失一般性,假设A <= B
: (1)先假设k <= A
: 则merge后的第k个元素只可能在A和B的前k个元素里面,并且是这2k个元素的median
: 在两个size为k的sorted array中找median是网上的老题,复杂性log(k)
: (2)如果k > A
: 如果A+B-k+1 <= A (i.e. k >=B+1 ),则可以考虑A和B的后A+B-k+1个元素找median
: O(log(A+B-k+1)) <= O(log(k+k-k)) = O(log(k))
: (3) 如果 A < k <= B
: 这个等我吃完饭继续想
:

b******v
发帖数: 1493
17
例如A=100, B=300, k=350
这属于第(2)种情况(k>=B),只需考虑A的后50和B的后50取median
但是如果k=200(A
【在 r****o 的大作中提到】
: 你说的第2)和第3)种情况有什么区别?
r****o
发帖数: 1950
18
how about A=70, B=80, k=100?

【在 b******v 的大作中提到】
: 例如A=100, B=300, k=350
: 这属于第(2)种情况(k>=B),只需考虑A的后50和B的后50取median
: 但是如果k=200(A
b******v
发帖数: 1493
19
情况(2)
三种情形分别为
(1) k <=A
(2) k >=B
(3) A
【在 r****o 的大作中提到】
: how about A=70, B=80, k=100?
y**i
发帖数: 1112
20
如果所有的A都比B小,那么kth元素将是B的250th元素,那你这个情况不是漏选了?(B
的后50是从251th-300th)

【在 b******v 的大作中提到】
: 例如A=100, B=300, k=350
: 这属于第(2)种情况(k>=B),只需考虑A的后50和B的后50取median
: 但是如果k=200(A
相关主题
最新L家面经google seti onsite
开始刷leetcode,第一道题一直有run time error新鲜的T电面题
问一道FB面试题fb电面面经
进入JobHunting版参与讨论
b******v
发帖数: 1493
21
good point我再想想

(B

【在 y**i 的大作中提到】
: 如果所有的A都比B小,那么kth元素将是B的250th元素,那你这个情况不是漏选了?(B
: 的后50是从251th-300th)

b******v
发帖数: 1493
22
我把前文修改了,三种情况的边界应该是
(1) k<=A
(2) k>B
(3) A 对于我前面举的那个例子,应该考虑A+B-k+1=51个元素,而不是50个元素

(B

【在 y**i 的大作中提到】
: 如果所有的A都比B小,那么kth元素将是B的250th元素,那你这个情况不是漏选了?(B
: 的后50是从251th-300th)

h**6
发帖数: 4160
23
总结一下:
1若k<=min(A,B),则A B各取k
2若k>min(A,B),A+B>2k-1,则A全取,B取2k-A
3若k>min(A,B),A+B<2k-1,则令m=A+B-k+1,此时A+B>2m-1,转化为2
4若k>min(A,B),A+B=2k-1, 则A、B都全取
注意:
第1、2、3三种情况共取2k个数,需要求出左中位数,而不是中间两数的平均值
第4种情况共取(2k-1)个数,则需要求出中位数
有没有人介绍一下第二题的解法啊?
x******3
发帖数: 245
24
第二题可以用balanced search tree, 比如RBT
在每个节点中保存以下信息
1) cache tag -> 查找O(lgn)
2) 以本节点为根的子树中最小recent used值 ->查找LRU O(lgn)
f****e
发帖数: 30
25
when u visit a cache, LRU value should be modified. Then how can you change
the min LRU value in subtree within lg(n) complexity

【在 x******3 的大作中提到】
: 第二题可以用balanced search tree, 比如RBT
: 在每个节点中保存以下信息
: 1) cache tag -> 查找O(lgn)
: 2) 以本节点为根的子树中最小recent used值 ->查找LRU O(lgn)

s******a
发帖数: 103
26
Can I use a hashtable and a min heap for the second problem?

A

【在 a***g 的大作中提到】
: 1. Given 2 sorted arrays A and B, find the kth element in the merged array A
: U B
: Time complexity requirement: log(k)
: 2. Least Recently Used (LRU) Cache: discards the least recently used items
: first
: How do you design and implement such a cache class?
: 1) find or search the item quickly
: 2) when there is a cache miss and cache is full, u want to replace the
: least recently used item quickly

H*****L
发帖数: 5705
27
这个方法和2K里找MEDIAN思路相同但实现比较简洁

从N
/2

【在 h****r 的大作中提到】
: log(k)可能,
: 把问题退化为find k th element from a[0,k-1] and b[0,k-1],一下子就查找长度从N
: 退化到k级别(2k)。
: 比较a[k/2]和b[k/2],如果a[k/2]小,那么 the element一定在a[k/2,k]和 b[0, k/2
: ]中,反之则在a[0, k/2]和b[k/2,k]中,重复这个步骤继续二分法比较下去即可。

x******3
发帖数: 245
28
first find the search cache line, update its LRU value
then just walk up the tree to update each LRU value along its way towards to
root
since updating LRU value only needs to check itself and the new LRU value,
its complexity is just lgn

change

【在 f****e 的大作中提到】
: when u visit a cache, LRU value should be modified. Then how can you change
: the min LRU value in subtree within lg(n) complexity

i********s
发帖数: 133
29
the code for the 1st problem. assume A[0] <= B[0].
int findK(int *A, int *B,
unsigned int sizeA, unsigned int sizeB,
unsigned k)
{
if (sizeA == 0)
{
if (k < sizeB)
return B[k-1];
else
throw std::exception();
}
if (sizeB == 0)
{
if (k return A[k-1];
else
throw std::exception();
}

unsigned int index1, index2;
index1 = std::min(k-1, sizeA-1);
index2 = 0;
i********s
发帖数: 133
30
for question 2, I still it should use a min-priority queue.
相关主题
问一道面试题这两个edit distance的code
leetcode hard 的题要刷吗?Microsoft screening programming problem
linkedin电面题4sum的那道题
进入JobHunting版参与讨论
h*******x
发帖数: 12808
31
可以
是找到第k个元素,不是找到等于k的元素,你想难了。

【在 c**a 的大作中提到】
: log(k)?
: log(N) 可以实现吧。 log(k) 不可能吧。
: 第一题。
: 第二题, 2个binary tree, 再加一个 stack 不久行了。
:
: A

S******a
发帖数: 862
32
其实,k>min(A,B)时,把A,B后面补正无穷,补足到A,B都是k长度。
不用真改变数组的size,override []即可。

【在 h**6 的大作中提到】
: 总结一下:
: 1若k<=min(A,B),则A B各取k
: 2若k>min(A,B),A+B>2k-1,则A全取,B取2k-A
: 3若k>min(A,B),A+B<2k-1,则令m=A+B-k+1,此时A+B>2m-1,转化为2
: 4若k>min(A,B),A+B=2k-1, 则A、B都全取
: 注意:
: 第1、2、3三种情况共取2k个数,需要求出左中位数,而不是中间两数的平均值
: 第4种情况共取(2k-1)个数,则需要求出中位数
: 有没有人介绍一下第二题的解法啊?

1 (共1页)
进入JobHunting版参与讨论
相关主题
新鲜的T电面题做一下common prefix in sorted string arrays
fb电面面经上一道我以前喜欢出的题目吧
问一道面试题好象是google的高频题目
leetcode hard 的题要刷吗?一道字符串题目
linkedin电面题谷歌面经
这两个edit distance的codeleetcode的run time error
Microsoft screening programming problem问下Linkedin的一道电面
4sum的那道题最新L家面经
相关话题的讨论汇总
话题: lru话题: cache话题: find话题: log话题: sizea