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的? |