b******p
发帖数: 49 | 1 1. 将一个数字的二进制形式以字符串的形式返回
2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
3. 找一个字符串中最长的只含有N种不同的字符的子字符串
4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
出的数字如果出现在其中就要剔除。（是CareerCup原题）
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。
现在看来自信得从别的地方找了。看起来得再多投几家，至少把LeetCode刷完。
请问这样的心态是否正确，谢谢各位 |
g*********e
发帖数: 14401 | |
h*********o
发帖数: 230 | 3 move on~
第一题就是要转换二进制码？
【在 b******p 的大作中提到】
: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。
|
b******p
发帖数: 49 | 4
对。就是类似python里面的
str(bin(N))
这样子的
【在 h*********o 的大作中提到】
: move on~
: 第一题就是要转换二进制码？
|
g**4
发帖数: 863 | 5 请问LZ这是电面还是onsite？
【在 b******p 的大作中提到】
: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。
|
m********l
发帖数: 791 | 6 第二题如果要求binary search - O(log (m+n))的话就太BT了。。 |
x*******8
发帖数: 145 | 7 第二题就是变种binary search啊，我google onsite的时候被问到了，每次去掉小的头
，大的尾，排除（m+n)/2 |
b******p
发帖数: 49 | 8
这是电面，是一共两场，每场45分钟，开始时间相差一小时的
【在 g**4 的大作中提到】
: 请问LZ这是电面还是onsite？
|
b******p
发帖数: 49 | 9
这题我在leetcode里面做过
我现在觉得我应该是挂在了最后一题
最后一题我之前没做到过，面试官也没让我写程序。
我只解释了我怎么想的，解释到后来他一直说我的做法没有满足他的要求。
估计是因此被拒掉了
再加上第三题写的可能还有bug…
【在 m********l 的大作中提到】
: 第二题如果要求binary search - O(log (m+n))的话就太BT了。。
|
w*****t
发帖数: 485 | 10 第四题：可以用rand()函数吗？如果在blacklist里面就继续生成下一个数？
有复杂度要求吗？
【在 b******p 的大作中提到】
:
: 这题我在leetcode里面做过
: 我现在觉得我应该是挂在了最后一题
: 最后一题我之前没做到过，面试官也没让我写程序。
: 我只解释了我怎么想的，解释到后来他一直说我的做法没有满足他的要求。
: 估计是因此被拒掉了
: 再加上第三题写的可能还有bug…
|
|
|
b******p
发帖数: 49 | 11
这题我完全没做出来
面试官没让我写code，我就和他说了，建一个hash table，或是建一个bloom filter之类
他说这些不行，又补充说：
blacklist是一个链表，所以二分查找的代价和数组的二分查找不一样
他说要“incremental”的解法
也就是将整个blacklist读入，再建hash table的方法通通不行
他说，譬如blacklist里面有几百万个数怎么办？几百万个数就是~400MB，超过了CPU的
缓存的大小。如果建hash table，性能会损失非常大。所以，我说的方法全都错误，不
是他想要的。估计是因此被拒了。
后来才知道这个是CareerCup 12.3这道题目。
没做过，真该面壁思过去…
【在 w*****t 的大作中提到】
: 第四题：可以用rand()函数吗？如果在blacklist里面就继续生成下一个数？
: 有复杂度要求吗？
|
M*********U
发帖数: 28 | 12 第一题的数字仅仅是整数吗？是否包括浮点数？
第三题里这个随机数产生器产生的随机数有范围吗？这个blacklist是保存在数组里还
是链表里？还是要你自己设计数据结构？
【在 b******p 的大作中提到】
: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。
|
A*********c
发帖数: 430 | 13 刚做完leetcode上的那道，感觉电面考median of two sorted arrays，够狠的。
要我比lz跪的还快：）
【在 b******p 的大作中提到】
: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。
|
b******p
发帖数: 49 | 14
第一题是整数
第三题是在链表里，排好序的
【在 M*********U 的大作中提到】
: 第一题的数字仅仅是整数吗？是否包括浮点数？
: 第三题里这个随机数产生器产生的随机数有范围吗？这个blacklist是保存在数组里还
: 是链表里？还是要你自己设计数据结构？
|
A*********c
发帖数: 430 | 15 看了你的面经以后我赶快做了CC的12.3, 做完以后觉得和你这个不是一道题啊。
解法应该是不一样的啊。
【在 b******p 的大作中提到】
: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。
|
f**********3
发帖数: 295 | 16 狗家的设计题就是用来黑的，不管你提出什么方案，就说不行，容易的很
【在 b******p 的大作中提到】
: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。
|
A*********c
发帖数: 430 | 17 没忍住想了一下第四题，上网搜了一下相关信息，学了一个算法。
造福一下大家，写这儿吧。
问题定义应该是这样的，要求生成[1, n], 给个blacklist是禁止的数字, list是排序
好的。
生成算法如下:
1 生成随机数 r in range [1, n-len(blacklist)]
2: 带着这个数字linear scan blacklist，如果生成的的数字大于等于list的当前元素
，则把生成的结果加1。
算法很简单，但是没找到信息证明正确性。我琢磨了一下是正确的，并且是uniform。
举例如下：假设要求生成[1, 10]
例子1. list 是1->2。所生成随机数1－8，然后显然要增加两次，所以最后随机数生成
器的range本质上就是3～10. uniform。
例子2. list 是9->10. 生成的随机数1～8. 显然不跳。最后的的range就是1～8，
uniform
例子3 list是1->3 生成1～8. 如果生成的是1 (这个概率本身是1/8)，碰到1跳一下，
到2，没问题，如果生成的是 >=2的数字，则需要跳两下，本质上是取的(4~10) （这个
概率是7/8) 所以你算一下最终概率还是uniform 在 2还有4~10之间分布。
希望对大伙有点用。
这个算法真神童。
【在 b******p 的大作中提到】
: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。
|
P*******r
发帖数: 210 | 18 这道题目好像以前板上讨论过。
blacklist 是 linkedList 可以一个一个 traverse 还算简单点。
如果是Array, 要求binary search 就变态了。
【在 A*********c 的大作中提到】
: 没忍住想了一下第四题，上网搜了一下相关信息，学了一个算法。
: 造福一下大家，写这儿吧。
: 问题定义应该是这样的，要求生成[1, n], 给个blacklist是禁止的数字, list是排序
: 好的。
: 生成算法如下:
: 1 生成随机数 r in range [1, n-len(blacklist)]
: 2: 带着这个数字linear scan blacklist，如果生成的的数字大于等于list的当前元素
: ，则把生成的结果加1。
: 算法很简单，但是没找到信息证明正确性。我琢磨了一下是正确的，并且是uniform。
: 举例如下：假设要求生成[1, 10]
|
A*********c
发帖数: 430 | 19 有意思，想想。胡说一下啊。
先做一次binary search，找到lower bound。看前面有几个元素，然后把生成数加几。
然后没完，更新binary search的lower bound继续search，重复，直到binary search
返回的结果是－1为止。如何？
binary search外面套一层。
【在 P*******r 的大作中提到】
: 这道题目好像以前板上讨论过。
: blacklist 是 linkedList 可以一个一个 traverse 还算简单点。
: 如果是Array, 要求binary search 就变态了。
|
t******d
发帖数: 1383 | 20 楼主，你不是面试谷歌失败，你是鄙视谷歌失败。Phd都是这样的心态，觉得自己无比
牛逼，所以一旦面试悲剧，就觉得接受不了。 |
|
|
w*****h
发帖数: 423 | 21 问一下楼主，是需要在google doc上把代码写下来还是直接报思路就OK了？ |
r******j
发帖数: 92 | 22 第四题可不可以把blacklist先divide了，比如分成5000个groups，第一个group包含1-
10000范围内的blacklist里面的值，第二个group包含10001-20000范围内的blacklist
里面的值，第三个。。。
然后你每次生成一个random值，先算它是在哪个group里面，然后再去那个group里面看
有没有match。 |
A*********c
发帖数: 430 | 23 给的list，怎么随机访问这些group呢？
1-
blacklist
【在 r******j 的大作中提到】
: 第四题可不可以把blacklist先divide了，比如分成5000个groups，第一个group包含1-
: 10000范围内的blacklist里面的值，第二个group包含10001-20000范围内的blacklist
: 里面的值，第三个。。。
: 然后你每次生成一个random值，先算它是在哪个group里面，然后再去那个group里面看
: 有没有match。
|
b******p
发帖数: 49 | 24
good point .......
反正我现在做好失败的准备了…
如果能有幸再多尝试几家，多收点拒信，锻炼心态也好…
就怕想尝试都没门啊。
【在 t******d 的大作中提到】
: 楼主，你不是面试谷歌失败，你是鄙视谷歌失败。Phd都是这样的心态，觉得自己无比
: 牛逼，所以一旦面试悲剧，就觉得接受不了。
|
g**4
发帖数: 863 | 25 intern电面都这水平了啊，狗狗真心难进啊
【在 b******p 的大作中提到】
:
: good point .......
: 反正我现在做好失败的准备了…
: 如果能有幸再多尝试几家，多收点拒信，锻炼心态也好…
: 就怕想尝试都没门啊。
|
b******p
发帖数: 49 | 26
要在Google Doc上写代码
【在 w*****h 的大作中提到】
: 问一下楼主，是需要在google doc上把代码写下来还是直接报思路就OK了？
|
c********p
发帖数: 1969 | |
r******j
发帖数: 92 | 28 把divide之后的每个sublist一个index，每个index对应一个sublist的起点。应该可以
吧。
【在 A*********c 的大作中提到】
: 给的list，怎么随机访问这些group呢？
:
: 1-
: blacklist
|
b*****c
发帖数: 1103 | 29 就是第k大数，容易被median误导，其实没用
【在 A*********c 的大作中提到】
: 刚做完leetcode上的那道，感觉电面考median of two sorted arrays，够狠的。
: 要我比lz跪的还快：）
|
x*****0
发帖数: 452 | |
|
|
s******r
发帖数: 21 | 31
想向大家请教一下，第三道题目的意思是什么，什么解法比较好。
对于题意，我的理解是，给一个参数N，找出字符串里面只包含N个不同字符的个数。譬
如N=1，那么在字符串"AAAAAA"里面，包含一个不同字符的最长串是6。不知道我理解的
是不是正确？
如果理解正确的话，有什么比较好的解法？我现在能够想到的是O(N^2)。就是用张二维
表，记录所有区间(i,j)之间不同字符串的个数，(i,j+1)的值可以从（i+1，j), (i, j
) 和(i+1, j+1)推导出来。不知道有没有更简便的做法？
【在 b******p 的大作中提到】
: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。
|
A*********c
发帖数: 430 | 32 用slide window应该可以得到一个O(n)的算法。
记录当前的window 开始。当前指针位置是窗口的结束点。
每当碰到一个新的字符把N变成了N+1以后，更新当前最大长度，然后把窗口前移，一个
一个去掉字符，直到N这个constraint被满足为止，然后继续滑动窗口的结束位置。
循环上述过程直到字符串末尾。
j
【在 s******r 的大作中提到】
:
: 想向大家请教一下，第三道题目的意思是什么，什么解法比较好。
: 对于题意，我的理解是，给一个参数N，找出字符串里面只包含N个不同字符的个数。譬
: 如N=1，那么在字符串"AAAAAA"里面，包含一个不同字符的最长串是6。不知道我理解的
: 是不是正确？
: 如果理解正确的话，有什么比较好的解法？我现在能够想到的是O(N^2)。就是用张二维
: 表，记录所有区间(i,j)之间不同字符串的个数，(i,j+1)的值可以从（i+1，j), (i, j
: ) 和(i+1, j+1)推导出来。不知道有没有更简便的做法？
|
s******r
发帖数: 21 | 33
对的，我自己想复杂了。谢谢。
【在 A*********c 的大作中提到】
: 用slide window应该可以得到一个O(n)的算法。
: 记录当前的window 开始。当前指针位置是窗口的结束点。
: 每当碰到一个新的字符把N变成了N+1以后，更新当前最大长度，然后把窗口前移，一个
: 一个去掉字符，直到N这个constraint被满足为止，然后继续滑动窗口的结束位置。
: 循环上述过程直到字符串末尾。
:
: j
|
A*********c
发帖数: 430 | 34 木事儿。
【在 s******r 的大作中提到】
:
: 对的，我自己想复杂了。谢谢。
|
t******5
发帖数: 30 | 35 好解法！
【在 A*********c 的大作中提到】
: 没忍住想了一下第四题，上网搜了一下相关信息，学了一个算法。
: 造福一下大家，写这儿吧。
: 问题定义应该是这样的，要求生成[1, n], 给个blacklist是禁止的数字, list是排序
: 好的。
: 生成算法如下:
: 1 生成随机数 r in range [1, n-len(blacklist)]
: 2: 带着这个数字linear scan blacklist，如果生成的的数字大于等于list的当前元素
: ，则把生成的结果加1。
: 算法很简单，但是没找到信息证明正确性。我琢磨了一下是正确的，并且是uniform。
: 举例如下：假设要求生成[1, 10]
|
w****a
发帖数: 710 | 36 感谢分享面经，move on吧。
2. 找两个已经排好序了的数组中的中位数
凭良心说，这题如果之前没准备过还是有难度的。
此外，从头像来看，楼主是做graphics的？ |
