G****A
发帖数: 4160 | 1 谢谢。 目前看到的解法都默认不会有duplicate key. |
|
m*****k
发帖数: 731 | 2 hash with collision resolution is still for diff keys, just that they have
same hashcode |
|
G****A
发帖数: 4160 | 3 之前讨论过，不过找不到原帖了。请大家给点思路
考虑过用map寻址, vector存数据. 但是这样没法handle duplicated key的情况。难道
还要自己implement hash with collision resolution? |
|
|
G****A
发帖数: 4160 | 5 谢谢。 目前看到的解法都默认不会有duplicate key. |
|
m*****k
发帖数: 731 | 6 hash with collision resolution is still for diff keys, just that they have
same hashcode |
|
|
l*****a
发帖数: 14598 | 8 getRandom need to use index of Array |
|
l*****a
发帖数: 14598 | 9 getRandom need to use index of Array |
|
a********9
发帖数: 129 | 10 请问hashmap的getRandom()怎么实现，我感觉array里面有的是空的，而且也不是从0
依次摆放，没法简单的返回array[random(size)]啊。。求教 |
|
f*******t
发帖数: 7549 | 11 Interval那题可以用insert,delete和getRandom都是O(1)的数据结构来做 |
|
m****i
发帖数: 15 | 12 找工作期间在本版潜水两个月，收益良多，发一下最近面经和经验作为回馈。
本人背景：美国不错学校电子PHD即将毕业，专业是EDA做电路设计算法优化。因为EDA
已经是一个很稳定的工业，没什么太大的前景，随想转到前沿的tech公司。本专业只投
了一家现在最大的公司，拿到offer。别的投了Google, Facebook, Rocket fuel,
Twitter, Linkedin, Yahoo, Amazon, Box, Oracle. 除了box别的都找人refer了， 在
此感谢板上大哥们的热情帮忙. 除了GFR别的都没理我，可能背景差太大了。
因为之前是学算法的，mit算法书以前就看过两遍，基础还可以，前期8月份刷了遍
leetcode。然后9月初投出简历。两个星期刷Career cup 150， 最后面试期间一直查缺
补漏。到现在尘埃落定大概两个月。 最后GFR全挂，总结下惨痛经历：
1. Facebook电面
面试官做distributed cache infrastructure的，先问我最难的project，没怎么好好
准备过behavior，胡乱说了一通。但是因为做的是电... 阅读全帖 |
|
m****i
发帖数: 15 | 13 找工作期间在本版潜水两个月，收益良多，发一下最近面经和经验作为回馈。
本人背景：美国不错学校电子PHD即将毕业，专业是EDA做电路设计算法优化。因为EDA
已经是一个很稳定的工业，没什么太大的前景，随想转到前沿的tech公司。本专业只投
了一家现在最大的公司，拿到offer。别的投了Google, Facebook, Rocket fuel,
Twitter, Linkedin, Yahoo, Amazon, Box, Oracle. 除了box别的都找人refer了， 在
此感谢板上大哥们的热情帮忙. 除了GFR别的都没理我，可能背景差太大了。
因为之前是学算法的，mit算法书以前就看过两遍，基础还可以，前期8月份刷了遍
leetcode。然后9月初投出简历。两个星期刷Career cup 150， 最后面试期间一直查缺
补漏。到现在尘埃落定大概两个月。 最后GFR全挂，总结下惨痛经历：
1. Facebook电面
面试官做distributed cache infrastructure的，先问我最难的project，没怎么好好
准备过behavior，胡乱说了一通。但是因为做的是电... 阅读全帖 |
|
a********9
发帖数: 129 | 14 L:
问答题
Write-through cache vs write-back cache
what's memory mapped file
算法题，都是老题
1) 给一个nested的int array， 返回sum of int weight by its depth
2) 写一个支持removeRandom的hashtable
3) 一串字符串，返回有多少个substring符合某些pattern，这些pattern都是10char的
长度，所以逐个比较就可以了
4) tree lowest ancestor( tree node have parent pointer)
RF:
基本全是老印，一个比一个吊炸天
1) 给一个数字，可以删除k个digit，返回最小的结果
example num=42139,k=1 == > 2139
answers: 首先从左到右，如果左边的digit比右边的大，就删除左边的digit，如果删
除不够k个digit则把最后的几位删掉，不大好实现，最好把输入变成array再做，或者
java的string
2) 写一个数据结构支持,put,get... 阅读全帖 |
|
f******h
发帖数: 45 | 15 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
s***f
发帖数: 226 | 16 原题是:
Implement below function.
int getRandom(int N, int K[])
Constraints:
->K is sorted and contains elements in range [0,N)
->Output should be a random number between [0,N) excuding elements from K
->probability of generated number should be 1/(N-K.length) and not 1/N
-->int uniform(int N) is given which returns random number [0,N) with 1/N
probability for each number.
->No more than O(1) memory
->No more than O(N) time
提供的解法是：
public int randomNumber(int N, int[] K) { // K is sorted
int x ... 阅读全帖 |
|
Z**********4
发帖数: 528 | 17 session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
或者16bytes。都是2的次方就是。
问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
费。
比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
时候就会浪费一些空间。
所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
object。
其实这个就是用排序，然后从大的变量依次放进block。
有个followup的问题就是：因为我不想过多移动这些变量，所以怎么才能设计一个算法
所需要移动的object最少。
比如如果变量的size一次是4, 4, 1, 1, 8, 8, 1, 1最好的排法是4, 4, 8, 8, 1, 1,
1, 1.而不是8 8 4 4 1 1 1 1因为前一种所需要移动的cost最小。这个没想出来了。。
应该用divide... 阅读全帖 |
|
l*****f
发帖数: 259 | 18 Array + Hash
Hash的key是array里面的值，value是index
getrandom就直接生成index random access array
insert就insert在array最后，同时update hash
delete就先用hash找到对应的index，假设为i。然后swap第i个和array最后一个，然后
删掉array最后一个，同时更新hash
lookup直接hash搞定 |
|
h*******e
发帖数: 1377 | 19 ～～～ 这是两道题， 楼主说的题目leetcode上有，我说的还有这位仁兄解答的是另
一道高频数据结构面试题O(1)时间插入删除修改查找，getrandom()的数据结构设计。 |
|
l*****f
发帖数: 259 | 20 Array + Hash
Hash的key是array里面的值，value是index
getrandom就直接生成index random access array
insert就insert在array最后，同时update hash
delete就先用hash找到对应的index，假设为i。然后swap第i个和array最后一个，然后
删掉array最后一个，同时更新hash
lookup直接hash搞定 |
|
h*******e
发帖数: 1377 | 21 ～～～ 这是两道题， 楼主说的题目leetcode上有，我说的还有这位仁兄解答的是另
一道高频数据结构面试题O(1)时间插入删除修改查找，getrandom()的数据结构设计。 |
|
i******s
发帖数: 301 | 22 说说面经吧，既然有人站内信问。ps: 我觉得就是随机挑了几个。。。四白一印
1.a 一个数组，大小(1M+1)，包含了所有1到1M（M表示一百万）的整数，因此，必有一
个数重复，请找出这个数。尽量说所有可能的解法。
1.b 一个很大的List(假设你用java，不过没关系)，请写一个getRandom，即随机返回
其中一个。
2. 写Fibo，分析时空复杂度，同时讨论何时使用异常，何时用error code。ps: 好像
他还问了一道题，忘了
3a. 4个B(B表示10亿)的整数数组，求median。
3b. boggle
4. 给一个字符串，给出最少插入多少次可以使字符串变为palindrome, 比如abcda就返
回1, 因为可以插入d使得字符串变为abdcda
5a. 考虑一个n叉树，将所有node存在一个数组tree中，node编号从0到n(n为数组大小)
。 arr[i]表示第i个node的parent，请找出该树的深度(即最长的根到叶的路径长度)。
5b. word break 2, 给定字符串和一个字典，找出所有合法的分割使得分割后得到的字
串都在字典中 |
|
f********a
发帖数: 165 | 23 写一个random函数，产生0 ~ n-1的数，但是有一个black list，产生的数不能在black
list里。 bl是sorted的。
int myRandom(int n, vector bl)
{
//.....
}.
时间复杂度log(n)
这里是解
http://www.geeksforgeeks.org/forums/topic/generate-a-random-num
但问题是建立mapping的时候怎么样才能log(n)二分查找 找到下个不在bl里面的数？
follow up是设计一个分布式系统，可以往这个系统里面call一个function叫
getRandom()，每次call返回一个随机数，不能有重复。follow up不用考虑bl. |
|
f********a
发帖数: 165 | 24 写一个random函数，产生0 ~ n-1的数，但是有一个black list，产生的数不能在black
list里。 bl是sorted的。
int myRandom(int n, vector bl)
{
//.....
}.
时间复杂度log(n)
这里是解
http://www.geeksforgeeks.org/forums/topic/generate-a-random-num
但问题是建立mapping的时候怎么样才能log(n)二分查找 找到下个不在bl里面的数？
follow up是设计一个分布式系统，可以往这个系统里面call一个function叫
getRandom()，每次call返回一个随机数，不能有重复。follow up不用考虑bl. |
|
b**********5
发帖数: 7881 | 25 我上一个吧， 不难
1） 就是我的map reduce average 和median
2） 有两个function， multithreaded，
f（x）， g(int x), 让你implement f， 如果是同样地 X 去call g， 一定要等其中
一个finish
3） stock buy sell 一次和二次
4） 我发过的一个matrix 里， 有的cell住着人， 找一个离所以cell的manhattan
distance最小的cell （就是找median）
5） 二个linkedlist， linkedlist是buffer， 每个buffer size不一样， 让你copy
list A的buffer到list B
6) 还有一个是random word， 给你一系列word，具体问题我忘了。 其实就是count
letter A 下面， followed几个A， followed 几个B， followed 几个C， 然后算
letter A follow A 的probability是多少， B follow A 的probability是多少。。。
... 阅读全帖 |
|
b**********5
发帖数: 7881 | 26 在说说最后一道题吧
给一个dictionary， 里面a list of words， 比如 “abcd“， ”abe", "bbc", "
bdcea"
从这个dictionary里， 给一个random word
怎么random么？
从这个字典里， 你可以看到：
第一个letter， 是“a”， 有多少probability， 是“b“， 有多少probability
then if u pick "a", "b" follow "a" with certain probabilty. if u pick "b",
"b" follow "b" with certain probability...
所以implement getRandomWord时， 先generate a random number between 0 and 1，
然后看第一个letter，“a“ 为first letter的probability是30%， 如果generate
为 0-0.3的时候， 就pick ”a”。 如果“b”的probability为60%， 那么generate
为0.3... 阅读全帖 |
|
发帖数: 1 | 27 新鲜面筋，自我感觉非常好以为稳稳的，but。。
HR踩着我其他offer的死亡线发的拒信，难不成也是纠结了好久才决定拒的？
此轮onsite唯二的fail，第一家fail也是个P - Palantir， 大家都懂的
没有怨恨，只有些许不解，而且不给feedback我以后怎么学习一个，怎么查漏补缺
板上规则我懂，发个面筋再说话。让各位老司机帮着掂量，更欢迎Pin内部人士留言or
发信 if lucky
没签NDA
电面： general tree序列化/反序列化，如何thread safe。面试官是Pin的大牛lead
onsite：
1. 有一个function A，会被callback访问到，让实现一个funciton，可以统计过去N秒
这个A被call了几次。 经典题，circular array统计每秒call的次数
顺利写出来，不过提醒了一个bug
2. 经历丰富的国人大哥，一看就是大牛。给一个蹦了的jobID，让找出所有depend on
这个ID 的其他job。 实质就是图的遍历， BFS
3. data structure, add(), delete(), getRan... 阅读全帖 |
|
发帖数: 1 | 28 请教半海 能否打听下Feb 1号面的几个feedback
因为面的自我感觉不错但跪了 想问问哪些方面不足以后好弥补
面的team是data platform
第一位面试官 韩裔 get qps sum of last 5min
第二位老中 fb跳过来 把fail的job找出来 本质是图搜索
第三位烙印+白女 data structure O（1）add remove getRandom
第四位 白男 culture fit
第五位 烙印+老中 system design Pin follow feature
十分感谢 除了P其他都offer 实在耿耿于怀
[在 swjtuer (灌水和coding都要敲键盘) 的大作中提到：]
：最后一句无法苟同
：
：........... |
|
o*q
发帖数: 630 | 29 Google
Show problem tags Hide locked problems
#
Title
Acceptance
Difficulty
Frequency
66 Plus One 35.4% Easy
146 LRU Cache 15.8% Hard
200 Number of Islands 29.7% Medium
288 Unique Word Abbreviation 15.7% Easy
163 Missing Ranges 30.3% Medium
56 Merge Intervals 26.7% Hard
228 Summary Ranges 26.0% Medium
308 Range Sum Query 2D - Mutable 20.8% Hard
279 Perfect Squares 34.1% Medium
388 L... 阅读全帖 |
|
发帖数: 1 | 30 534 Design TinyURL 0.0% Medium
283 Move Zeroes 50.7% Easy
301 Remove Invalid Parentheses 35.5% Hard
273 Integer to English Words 22.4% Hard
621 Task Scheduler 42.4% Medium
67 Add Binary 33.2% Easy
325 Maximum Size Subarray Sum Equals k 43.1% Medium
689 Maximum Sum of 3 Non-Overlapping Subarrays 41.2% Hard
253 Meeting Rooms II 39.3% Medium
17 Letter Combinations of a Phone Number 35... 阅读全帖 |
|
发帖数: 1 | 31 我的名字叫雷锋。My name is Feng Lei.
# Title Solution Acceptance Difficulty Frequency
2
Add Two Numbers 28.2% Medium
3
Longest Substring Without Repeating Characters 24.5% Medium
535
Encode and Decode TinyURL 74.0% Medium
5
Longest Palindromic Substring 25.2% Medium
15
3Sum 21.8% Medium
238
Product of Array Except Self 50.0% Medium
17
Letter Combinations of a Phone Number ... 阅读全帖 |
|
