i*******w
发帖数: 15 | 1 45分钟三个题目，鬼扯完了之后第一个设计一个数据结构，判断一个电话号码是否被占
用。简单地说就是两个集合: available和used。这个数据结构要能支持 1) use 操作
，就是一个号码从available 变成used；2) 判断一个号码是否已被占用；3)
getUnusedNumber(）。反正不难，讨论一下为什么。讨论一下怎么优化。注意一下加锁
。其他看不出来还能考什么了。
第二个题目，已知f: unsigned-> int是一个单调（升）函数。试写出f的逆函数。讨论
了内存有没有限制，没有限制直接把表造出来查。然后他说有限制，那么就二分法查找
。问能不能优化。说弄个static cache记住前面几次f的结果，可以省几次比较。不知
道还能怎么优化。写了code.
第三个题目，两个排序集合，求第k大的元素。说合并排序那样，用O(k)，幸亏我谦虚
地留了个活路：你等会我看看能不能改进。果然是可以改进的，要是话说满了就被动了
。类似二分法改进出来，没有时间写code了。
不知道结果。 |
P**********c
发帖数: 3417 | 2 最后一个，两个排序集合是什么意思？是排好序了吗？那样不是一个埃一个判断就是O(
k)了吗？
【在 i*******w 的大作中提到】
: 45分钟三个题目，鬼扯完了之后第一个设计一个数据结构，判断一个电话号码是否被占
: 用。简单地说就是两个集合: available和used。这个数据结构要能支持 1) use 操作
: ，就是一个号码从available 变成used；2) 判断一个号码是否已被占用；3)
: getUnusedNumber(）。反正不难，讨论一下为什么。讨论一下怎么优化。注意一下加锁
: 。其他看不出来还能考什么了。
: 第二个题目，已知f: unsigned-> int是一个单调（升）函数。试写出f的逆函数。讨论
: 了内存有没有限制，没有限制直接把表造出来查。然后他说有限制，那么就二分法查找
: 。问能不能优化。说弄个static cache记住前面几次f的结果，可以省几次比较。不知
: 道还能怎么优化。写了code.
: 第三个题目，两个排序集合，求第k大的元素。说合并排序那样，用O(k)，幸亏我谦虚
|
g*****i
发帖数: 2162 | 3 用2分法可以达到O(lgN+lnM),很多情况下比o(k)快
O(
【在 P**********c 的大作中提到】
: 最后一个，两个排序集合是什么意思？是排好序了吗？那样不是一个埃一个判断就是O(
: k)了吗？
|
P**********c
发帖数: 3417 | 4 题目要求是O(k)啊。O(lgn+lgm)是跟那个找median的算法类似吗？
【在 g*****i 的大作中提到】
: 用2分法可以达到O(lgN+lnM),很多情况下比o(k)快
:
: O(
|
g*****i
发帖数: 2162 | 5 第一题是2个hashset吗?
【在 i*******w 的大作中提到】
: 45分钟三个题目，鬼扯完了之后第一个设计一个数据结构，判断一个电话号码是否被占
: 用。简单地说就是两个集合: available和used。这个数据结构要能支持 1) use 操作
: ，就是一个号码从available 变成used；2) 判断一个号码是否已被占用；3)
: getUnusedNumber(）。反正不难，讨论一下为什么。讨论一下怎么优化。注意一下加锁
: 。其他看不出来还能考什么了。
: 第二个题目，已知f: unsigned-> int是一个单调（升）函数。试写出f的逆函数。讨论
: 了内存有没有限制，没有限制直接把表造出来查。然后他说有限制，那么就二分法查找
: 。问能不能优化。说弄个static cache记住前面几次f的结果，可以省几次比较。不知
: 道还能怎么优化。写了code.
: 第三个题目，两个排序集合，求第k大的元素。说合并排序那样，用O(k)，幸亏我谦虚
|
g*****i
发帖数: 2162 | 6 题目没要求O(K).对,就是那个median思路.
【在 P**********c 的大作中提到】
: 题目要求是O(k)啊。O(lgn+lgm)是跟那个找median的算法类似吗？
|
f****4
发帖数: 1359 | 7 median思路的话应该是 O(lgK) 吧？
【在 g*****i 的大作中提到】
: 题目没要求O(K).对,就是那个median思路.
|
g*****i
发帖数: 2162 | 8 你未必能在长度是k的序列里找到,可能要找另外一个序列
【在 f****4 的大作中提到】
: median思路的话应该是 O(lgK) 吧？
|
a********m
发帖数: 15480 | 9 是大约lgk吧。比lgn+lgm好多了。
【在 g*****i 的大作中提到】
: 用2分法可以达到O(lgN+lnM),很多情况下比o(k)快
:
: O(
|
f****4
发帖数: 1359 | 10 第k大的只能在第一序列的最后k个&第二序列最后k个数里面
用求median的方法，先找第一序列k个数，不在的话就在第二序列k个书，用2分法找
O(2lgk) = O(lgk)
【在 g*****i 的大作中提到】
: 你未必能在长度是k的序列里找到,可能要找另外一个序列
|
|
|
P**********c
发帖数: 3417 | 11 没看懂，什么叫做先找第一序列k个数，用2分法找，找的目标是什么。
【在 f****4 的大作中提到】
: 第k大的只能在第一序列的最后k个&第二序列最后k个数里面
: 用求median的方法，先找第一序列k个数，不在的话就在第二序列k个书，用2分法找
: O(2lgk) = O(lgk)
|
h*****n
发帖数: 61 | 12 这个和查找一个key弄混了吧
【在 f****4 的大作中提到】
: 第k大的只能在第一序列的最后k个&第二序列最后k个数里面
: 用求median的方法，先找第一序列k个数，不在的话就在第二序列k个书，用2分法找
: O(2lgk) = O(lgk)
|
g*****i
发帖数: 2162 | 13 原来如此
【在 f****4 的大作中提到】
: 第k大的只能在第一序列的最后k个&第二序列最后k个数里面
: 用求median的方法，先找第一序列k个数，不在的话就在第二序列k个书，用2分法找
: O(2lgk) = O(lgk)
|
P**********c
发帖数: 3417 | 14 他那个不对吧。我觉得他没有搞清楚要找什么。
【在 g*****i 的大作中提到】
: 原来如此
|
a********m
发帖数: 15480 | 15 记得careerup书上有。
n是在第一个叔祖的下标，m是第二个，所以m=n-1.这样就只有一个未知数n。然后n在[1
,k]折半，关键是终止条件和折半的方法。
【在 P**********c 的大作中提到】
: 他那个不对吧。我觉得他没有搞清楚要找什么。
|
b*******8
发帖数: 37364 | |
e*******r
发帖数: 47 | 17 google jobs and interviews:
http://www.jobguiding.com/it-jobs/it-companies/google.html
【在 i*******w 的大作中提到】
: 45分钟三个题目，鬼扯完了之后第一个设计一个数据结构，判断一个电话号码是否被占
: 用。简单地说就是两个集合: available和used。这个数据结构要能支持 1) use 操作
: ，就是一个号码从available 变成used；2) 判断一个号码是否已被占用；3)
: getUnusedNumber(）。反正不难，讨论一下为什么。讨论一下怎么优化。注意一下加锁
: 。其他看不出来还能考什么了。
: 第二个题目，已知f: unsigned-> int是一个单调（升）函数。试写出f的逆函数。讨论
: 了内存有没有限制，没有限制直接把表造出来查。然后他说有限制，那么就二分法查找
: 。问能不能优化。说弄个static cache记住前面几次f的结果，可以省几次比较。不知
: 道还能怎么优化。写了code.
: 第三个题目，两个排序集合，求第k大的元素。说合并排序那样，用O(k)，幸亏我谦虚
|
g*****i
发帖数: 2162 | 18 我觉得他说的对啊,只可能在每个分序列最开始k个数里.先一个做2分,和另一个对应位
置比较
【在 P**********c 的大作中提到】
: 他那个不对吧。我觉得他没有搞清楚要找什么。
|
P**********c
发帖数: 3417 | 19 为什么m=n-1？
举个例子
1 3 5 7 9 11 13
2 4 6 8
找第四大的数 （8）, 怎么折半的？
[1
【在 a********m 的大作中提到】
: 记得careerup书上有。
: n是在第一个叔祖的下标，m是第二个，所以m=n-1.这样就只有一个未知数n。然后n在[1
: ,k]折半，关键是终止条件和折半的方法。
|
a********m
发帖数: 15480 | 20 a. 写错了。m=k-n.
第四大应该是4吧。
a1比a2个数多，第一次折半是n=3,m=1,
然后5>2而且中间有数字所以n变小，m变大。 n=2,m=2,
现在可以结束因为a1[n-1]
大概思路是这样，中间不一定完全正确。书上有具体代码。
【在 P**********c 的大作中提到】
: 为什么m=n-1？
: 举个例子
: 1 3 5 7 9 11 13
: 2 4 6 8
: 找第四大的数 （8）, 怎么折半的？
:
: [1
|
|
|
f**********o
发帖数: 793 | 21 第一体是不是用trie 更好?
1) use 操作，就是一个号码从available 变成used；
remove node
O(k) k is length of the phone number
2) 判断一个号码是否已被占用；
look up
O(k) k is length of the phone number
如果很大量的电话号码，space 上也节省。 |
s**********e
发帖数: 326 | 22 第三题：
int findKth(int *arr1, int *arr2, int k, int arr1Index, int arr2Index){
if(k == 0){
if(arr1[arr1Index] <= arr2[arr2Index])
return arr1[arr1Index];
else
return arr2[arr2Index];
}
int mid = (k + 1)/2;
if(arr1[arr1Index + mid - 1] <= arr2[arr2Index + mid - 1])
findKth(arr1, arr2, k - mid, arr1Index + mid, arr2Index);
else
findKth(arr1, arr2, k - mid, arr1Index, arr2Index + mid);
}
main调用时arr1Index，arr2Index传入值都是0，assume m>=k, n>=k |
l*****e
发帖数: 1374 | 23 获取unsed phone number 怎么做好呢？
这个问题是不是用bit operation 更方便些。
【在 f**********o 的大作中提到】
: 第一体是不是用trie 更好?
: 1) use 操作，就是一个号码从available 变成used；
: remove node
: O(k) k is length of the phone number
: 2) 判断一个号码是否已被占用；
: look up
: O(k) k is length of the phone number
: 如果很大量的电话号码，space 上也节省。
|
p*******l
发帖数: 67 | 24 For 3), I will call the two arrays as A1[1..n] and A2[1..m] and they are
sorted in descending order. Since the two arrays are sorted, isn't it the
same as find the median number of A1[1..k] and A2[1..k]? |
f**********o
发帖数: 793 | 25 unused numbers 就是遍历这个 trie, 复杂度和有多少node 数相关。
【在 l*****e 的大作中提到】
: 获取unsed phone number 怎么做好呢？
: 这个问题是不是用bit operation 更方便些。
|
N*******7
发帖数: 14 | 26 第二题题意不太理解，是说已知一种一一映射，求逆关系么？
【在 i*******w 的大作中提到】
: 45分钟三个题目，鬼扯完了之后第一个设计一个数据结构，判断一个电话号码是否被占
: 用。简单地说就是两个集合: available和used。这个数据结构要能支持 1) use 操作
: ，就是一个号码从available 变成used；2) 判断一个号码是否已被占用；3)
: getUnusedNumber(）。反正不难，讨论一下为什么。讨论一下怎么优化。注意一下加锁
: 。其他看不出来还能考什么了。
: 第二个题目，已知f: unsigned-> int是一个单调（升）函数。试写出f的逆函数。讨论
: 了内存有没有限制，没有限制直接把表造出来查。然后他说有限制，那么就二分法查找
: 。问能不能优化。说弄个static cache记住前面几次f的结果，可以省几次比较。不知
: 道还能怎么优化。写了code.
: 第三个题目，两个排序集合，求第k大的元素。说合并排序那样，用O(k)，幸亏我谦虚
|
f****4
发帖数: 1359 | 27 0 1 2 3 4 5 6 <- index
1 3 5 7 9 11 13
2 4 6 8
找第四大的数k，k只可能在7 9 11 13和 2 4 6 8中间
先处理a[3~6]7 9 11 13
low a[3] 如果 7是k，那么必有 a[3] > b[3]，不然说明当前数7小于k
high a[6] 如果13是k，那么必有 a[6] > b[0]，不然说明当前数13大于k
当low < k && high > k的时候，我们用2分查找，看mid(9)
mid a[4] 如果 9是k，那么必有 a[4] < b[3] && a[4] > b[2]，
如果a[4] > b[3] a[4]大于k
如果a[4] < b[2] a[4]小于k
这里，我们用mid 替换 high, k只能在[3~4]中间，第一个数组查找结束，k不在第一个
数组里面
那么k必然在b[0~4]里面
low b[0] 如果2是k，必有b[0] > a[6],不然说明当前数2小于k
high b[3] 如果8是k，必有b[3] > a[3],找到
这里需要根据当前a[] index，自动算出对应b[]index(即有1个数组，或2个数组长度都
k)
时间复杂度：最多2个k长的数组的2分查找，2lgn=O(lgn)
【在 P**********c 的大作中提到】
: 为什么m=n-1？
: 举个例子
: 1 3 5 7 9 11 13
: 2 4 6 8
: 找第四大的数 （8）, 怎么折半的？
:
: [1
|
