|
h*******q
发帖数: 5 | 2 从准备面试开始潜水，在本版上收获不少。所以想尽一点绵薄之力，贡献一点电面面经。
L家 - 挂了：
电面1： 白人，HM.
Chat 5 min.
Basic Question: 10 min: TCP vs UDP, Virtual Memory, Page fault, etc...
Question 1: Mirror a Tree
Solution: recursive
Question 2: Implement a data structure class support: insert, delete and
random get
Solution: two hash map and move last to fill the hole when deleting
电面2： 国人
Question: Java Blocking Queue,
Solution: 参见本版讨论
G家 - 挂了：
电面1: 三哥，很不友好，解题的时候一个劲打岔，想挑个错，结果发现是他错了。然
后让我refine code 15分钟。
Question: Double Circular Sorted... 阅读全帖 |
|
l**********2
发帖数: 5 | 3 今年在板上潜水良久，受益匪浅，特来报offer报题求指导.
先post一下现在还记得的面试题
word ladder
Minimum Window Sub-string
quadtree merge
coins permutation/combination
multiply two big number
swap bits in an integer
read4k
regular expression match
median in two sorted array
egg drop problem
remove all duplicates in place for a give array
cycle detection in linked-list
max contiguous sub-array
3sum
c++ virtual function, virtual inheritance, template partial
specialization. (I said I am 'proficient' in C++ so he said a lot in
depth)
c... 阅读全帖 |
|
a*******a
发帖数: 66 | 4 对每一个位置做recursion，过程中保存已找到的结果；recursion的end case是警察周
围的房间（距离=1） |
|
a*******a
发帖数: 66 | 5 对每一个位置做recursion，过程中保存已找到的结果；recursion的end case是警察周
围的房间（距离=1） |
|
|
t********n
发帖数: 611 | 7
Software Engineer Interview
Anonymous Interview Candidate in New York, NY
Application Details
I applied online. The process took 4 weeks - interviewed at Google in August
2014.
Interview Details
My interview and hiring process was extremely tiring but satisfactory. I
dropped out of college and cancelled my plans to study in an university
because I wasn't learning anything there. I studied and mastered computer
science alone at home within 2 months. Although I am just 19, I d... 阅读全帖 |
|
e*******s
发帖数: 1979 | 8 stack invariant 如何理解
http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_comp
"
When the depth-first search recursively explores a node v and its
descendants, those nodes are not all necessarily popped from the stack
before this recursive call returns. The crucial invariant property is that a
node remains on the stack after exploration if and only if it has a path to
some node earlier on the stack.
" |
|
h*********2
发帖数: 444 | 9 先是写pow(x, n)
recursive和iterative哗哗哗写完了
面试官来了个，
What is the minimum number of multiplications for calculating pow(x, n)?
然后给我举了个例子，要算x^45
iterative的方法是
x --> x^2 --> x^4 --> x^8 --> x^16 --> x^32
然后把x, x^4, x^8, x^32 乘起来
总共需要5 + 3 = 8次乘法
recursive的方法是
x^45 = x^22 * x^22 * x
x^22 = x^11 * x^11
x^11 = x^5 * x^5 * x
x^5 = x^2 * x^2 * x
x^2 = x * x
这样也是需要8次乘法
但是有更好的办法是
x --> x^2 --> x^4 --> x^8
x * x^8 = x^9
x^9 --> x^18 --> x^36
x^9 * x^36 = x^45
这样只需要3 + 1 + 2 + 1 = 7次乘法
然后我就傻了。
查了下，这个问题还蛮出名：
https... 阅读全帖 |
|
g***a
发帖数: 58 | 10 八月的时候面的fb，电面和onsite都是local的，发个面经给版上备战的xdjm参考，求
攒rp
电面：
先聊了聊自己的经历，为什么要来fb之类的问题，因为我有图像处理的背景，就问了一
题相关的。
给一个2D board，上面由 0 和 1 组成，0 背景，1是图像，求里面有多少个连通域，
follow up 是每个连通域的面积是多大。我先写了recursive的做法。后来面试官又要
求了iterative的做法
面完一小时之内，recruiter发邮件说电面过了，可以安排onsite
onsite：
第一轮：主要谈自己以前做的东西，面试官问得比较细，总之就扯了扯。问了一题
coding，给一个数组，问里面有没有两个数相加等于0，给了 O(n) time O(n) space的
做法，和 O(nlog n ) time和 O(1)space的做法
第二轮：给一个bst，和其中一个节点的value，求在bst中比这个节点大的下一个value
，面试官要求 O(1) space和 O(log N) time的解法。
第三轮: regular expression match, leet... 阅读全帖 |
|
d*******5
发帖数: 22 | 11 要求constact space可以用recursive吗？ recursive的stack空间这里到底算不算？ |
|
h*******8
发帖数: 29 | 12 跪了，上面经，估计是有一轮算法不smooth。本人fresh phd。anyway，反正要从别家
鸟。
都不难，欢迎大家讨论
第一轮：聊research，最后问了一题，
write a function f(x), so that f(x) returns true with x% probability。
第二轮：Given k sorted linked list, n elements in total, merge them into one
sorted linked list。
经典题吧，但是居然在复杂度上卡了一下，给出的 log(k)*n的recursion解法。follow
up是如果不允许用recursion如何达到log(k)*n。follow up也没答好，提示是可以用
heap。
中午吃饭
第三轮：convert a binary search tree into sorted double-linked list。
implement memcpy.
第四轮：System design。
Given a location (a coordinate), ret... 阅读全帖 |
|
c******n
发帖数: 100 | 13 也可以说就是这两个
第一个是cc150的办法，用min max Integer recursion
第二个是inorder traversal using recursion
最后一个是第二个的iteration 写法，用Stack
|
|
y***k
发帖数: 162 | 14 ［Update］没想到借了个朋友的ID发个面经也会引发性别问题的争议。面试的主人翁是
个30好几的老大爷。运气真的很好，所有题目都不难。
概略：从本科到PhD一直念的EE。PhD毕业后没怎么找工作就直接到一个小型research
lab做networking research待了2年多。2014年初第一次Google试水，挂在onsite上了
。到了下半年这几家的recruiter开始陆续contact我，想想也差不多是时候换一下环境
了，就安排了感恩节前一周三个电面。电面除了G都非常顺利。G的电面我自己作死，面
完觉得必须挂的。谁知道过完感恩节那周竟然三家都收到onsite通知了。当时的想法是
避免战线拖太长，所以把三个onsite都安排在元旦后第一周。计划利用圣诞／新年长假
养精蓄锐好好复习，然后一鼓作气搞定。现在回头看，这个策略这次发挥的非常出色。
三家onsite都发挥的非常好，据说feedback都不错，最后都拿到了offer，包裹也都挺
不错的（G > L > F）。
准备：我一直不认为临急抱佛脚似的突击能有多大用处。所以准备时间比较长，可以算
从2013下半年就开始了。因... 阅读全帖 |
|
t*****a
发帖数: 106 | 15 题目非常长，我把大概意思和你说一下。就是一般的BST一个node只有一个value, 现在
一个node有两个value，v1,v2.按v1建BST v2就不是BST了，问你咋弄。我给了两个解，
一个是先定义cost funciton, 按一个value建BST，第二个算cost, recursive遍历，然
后找cost最小的。因为recursive是exp的复杂度，所以中间加memory. 第二个我就说了
一下，说可能可以改splay tree, 把一个value当frequency, 然后修改splay tree 算
法，建BST. |
|
i********y
发帖数: 34 | 16 1. check if x is possible (as someone mentioned, x is only possible if it's
a multiple of greatest common divisor K of all buckets)
2. get max steps for each x (1 if x = bucket_i. For others, use max(bucket_i
) and bucket_j where their GCD is K. Repeatedly pour one to the other until
all x are found)
3. get min steps for each x. Use recursive method and try all possibilities,
dynamically update max steps for other x along the way. Number of recursive
depth can't exceed the max step for x. |
|
c******n
发帖数: 4965 | 17 那小哥说recursive 的hint 有点晚了。 一说 recursive 大多数人5分钟怎么都能看出来 |
|
h***k
发帖数: 161 | 18 recursion is never space O1, except tail recursion |
|
l*y
发帖数: 70 | 19 忘了但是我dp and recursive都写了才发现dp对两种都没recursive/dfs好 |
|
t*********r
发帖数: 387 | 20 base case: no moves are possible. going first automatically loses.
recursive case: recursively determine the result of all possible valid moves
. If all next step result in losses, then return win. Otherwise, return loss
. |
|
j******8
发帖数: 746 | 21 FB phone interview, one simple coding question to judge if a string is a
Palindrome.
Gave the Java code of recursive method, then being asked space complexity,
which is O(n). Then gave non-recursive method, which uses constant space. He
seemed satisfied and the interview was over.
But I was told the failure after 2 days. Can anyone suggest what happened on
the earth? |
|
d*****5
发帖数: 1920 | 22 recursive space 我觉得是O(n^2), 堆栈里是 n ＋ (n - 2) + (n - 4)...
不一定对，大牛指点下。
再说用recursive感觉没必要。 String长了容易出问题。 |
|
b**********5
发帖数: 7881 | 23 你自己去看吧。 后面那个recursive， 不是真的recursive solution。 我如果给你
个限制， 就是你一开始不知道string 的length怎么办？ |
|
b*****n
发帖数: 618 | 24 recursion + memorization就行了吧，最简单直观的方法。
排序有什么太大的必要么，空间复杂度也没降。
对每个格子，看它四个方向的邻居组成的最长递增序列是多长，如果之前已经算过了就
不用再算了，如果没算过就recursion算一下 |
|
c******n
发帖数: 4965 | 25 哦，那还是很好的题， 不算难 也有点意义。
recursive(int low[], int []high, int pos) {
if (pos == low.length) {
// print out answer or add answer to list
}
for(int candidate=low[pos];candidate<=high[pos];candidate++) {
answer[pos] = candidate;
recursive(low,high, pos+1);
}
} |
|
y*****e
发帖数: 712 | 26 lz, trie + dfs那题你能再解释一下吗？ *是不是不用放到字典里， 比如说abc*de，
在trie里记录abc，然后skip一个character,再在后面找de? 不是太清楚具体怎么实现
的。。。
另外就是regex那题，DP的complexity是 n^2 + n^2; recursion + backtracking的复
杂度怎么考虑？最坏是2^n吧，怎么说服recursion是更优的办法呢？
另外感觉lz答得不错，phd应该有很高的级别吧，羡慕。。。
sliding |
|
c*****n
发帖数: 95 | 27 ＊可以和任意非空字符匹配 e.g. a - z
DP 复杂度应该是 m * n
recursion + backtracking 是 2^n. recursion好处是，如果没有很多＊时，可能结束
的更早。
， |
|
r********g
发帖数: 219 | 28 这里给出了两种解法。
http://www.tangjikai.com/algorithms/lintcode-390-find-peak-elem
对 divide&conque，虽然听起来很straightforward，但是严格的数学证明其实不简单。
我想了一下，还是用数学反证发。
命题：
先沿着中间一row找到那一row的 peak，如果纵向也是peak，则返回；否则，沿着和
peak同一column，neighbor升高的方向recursively搜索 。反复这样操作，必然会找到
peak。
反证：
假设按照这种搜索方法一直找不到peak。那么每次identify搜索方向的peak时，必然该
点高度比前一个搜索方向peak值高。而假设时始终找不到真正的peak（二维上的），所
以，recursion会无限循环下去，高度值会被不断无限制的提高。这显然是和题目条件
conflict的，即每个点高度都是有限的。
不知道这样说的通否。 |
|
|
t****m
发帖数: 140 | 30 1.白人小哥，扯背景发现是校友
小哥直接说let's start from a simple coding problem
判断string‘（（【】））’里的各种类型的括号是不是match
小哥各种指导暗示，写完了之后跑了几个testcase， 都过了，小哥比我还高兴
把我的code夸了一番，说很concise，然后就提前结束了interview。。。
2.印度小哥
fibonacci number, iterative and recursive
结果在回答recursive 的time complexity 和 space complexity的时候脑子短路了没
答上来
印度小哥很高兴的结束了面试把电话挂了。。。
new grad 面试找工作五个月了没offer，天天上来爆面经攒人品，该刷的题都刷差不多
了，是不是找工作的方法不对，有没有前辈指点一下？ |
|
b*****n
发帖数: 618 | 31 时间复杂度exponential就够了，你如果真要确切答案也行，这个可以算出来的，比如
说你讲的这个近似1.6^n，但是你给了这个答案也还要解释怎么推的，大部分面试官对
这个不一定感兴趣。
这种情况下确切答案是什么不是非常重要，重要的是对整个recursion的过程是不是真
的了解。
答space complexity的时候是只看auxiliary，是stack space都算上，还是input都算上
recursion tree是怎么执行的，这些才是关键。
面试是为了从各个方面考察你的能力，不是一般的考试做卷子，你觉得这样讲你能满意吗 |
|
c******n
发帖数: 4965 | 32 recursive:
minsol(n)= math.min( minsol(k))+1. for all. k
and I is a square number
dp just mechanically transforms the above recuraion to a 1 dimensional array
(how many args there are to the recursive function, how many dimensions
there will be) |
|
i*****h
发帖数: 1534 | 33 这个简单题的考点就是进位，楼主的写法没有错，新建一个array，后面取默认值。关
键是面试官无法沟通，否则最后3行代码一解释就能理解。面试题和product code不同
，就像实际工作中很多都不建议甚至不允许用recursive call，但是面试中有的就要求
用recursion。
这题作为面试题尽量追求in place不是什么大问题，不用这么上纲上线的。 |
|
w*****1
发帖数: 6807 | 34 看名字好像是来自东欧的哥儿们面的，本来HR说好的国人大哥不知道去哪儿了。。。
题目当时说的我就不是特别明白，大概是下面这个意思。
给一个任意大小的matrix A，大小mxn可以非常大，里面元素是0或者1。给个起始坐标[
i][j]。
实现如下过程，如果A[i][j]的邻居（九宫格包括自己）有元素是0，则都改为1。
然后基于已经填好1的区域，向外扩张（每步只能扩张到已填好(都是1)区域的邻居），
如果扩张遇到有0元素都改为1。停止条件是全都到了矩阵边界，或者填好区域的邻居全
是1。
形象一点说，有点像扫雷游戏。0改1可以想象成插小旗，只是雷你都事先都知道了。
当时面试也就剩半个小时了，好像不是leetcode里的题（也可能是，我刷的不是很仔细
），最近又回头搞论文去了，HR说这次面试问的是CS基础题。。。
做了半天想写个recursion算法，也写不出来。快没时间了，面试哥们说这题recursion
没法做，我只能又胡扯了些别的想法。。。又问了问复杂度就算完事了，应该是稳稳的
挂了。
回来贡献一下，看看大牛们的想法，如果能提供代码就更好了，我回头想想这题还是挺
复杂的。 |
|
h****e
发帖数: 2125 | 35 这题一看让你把1变0，自然就是考backtracking。三个方向：dirs = {{0,-1},{0,1},{
1,0}}，当前coordinate要loop through这三个方向。如果新坐标的值是1的话，就要先
变成0同时total变化数量加一，然后call recursive method。在recursive call之后
你还得把新坐标变回1，再try下一个方向。
懂了？ |
|
r******y
发帖数: 21 | 36 SDET职位，python backend
phone: fibonacci数列，各种花样写, iterative, recursive, 然后问了recursive的
时间复杂度和空间复杂度
onsite：
1. Hadoop, pig如何测试，如何分不同的版本测试
2. python regular expression matching的基本匹配和替换，例如把电话号码替换成(
xxx)-xxx-xxxx
3. 简单的python基本问题，半个小时问完了
lunch interview，聊天，culture fit，manager一直在不停地说说，最后我也说了一
些。
4. 三哥面coding, 第一题是select kth largest from array，秒解。第二题是
implement thread-safe non-blocking queue，不会，所以跪在这题。（楼主是new
grad，这方面没什么经验）
5. 三姐聊天，culture fit
6. 跟recruiter聊一聊，然后离开了
大家准备他家面试一定要准备multi-threading, non-blo... 阅读全帖 |
|
g******e
发帖数: 1258 | 37 recursion不就是build stack吗？
[在 jobhunter123 (jobhunting) 的大作中提到：]
：但是不能用recursion。
：
：........... |
|
g*****y
发帖数: 94 | 38 C语言的题，对C语言不是很熟，如果下面的有语法错误的话，还请谅解。对树进行中序
遍历，initial代码如下：
void inorder(TreeNode* root) {
LABEL:
if (root == NULL) {
return;
}
// Left subtree
inorder(root->left);
// Print value
printf("%dn", root->val);
// Right subtree
root = root->right;
goto LABEL;
}
其实上面的代码对于右子树来说就是变相的recursive调用，面试官要求如何用些代码
来取代"goto LABEL;"这句，然后写些iterative的代码来实现这个中序遍历。其实要求
就是怎么做到左子树recursive，右子树iterative。怎么破这个？ |
|
s******k
发帖数: 6659 | 39 忘了cong一下了～沾沾喜气儿
想请教一下2d array A点到B点 带block那题
觉得是个DP问题，recursion里面需要call 8个subcase，优先级根据当前点和终点的相
对位置来决定。然后到达终点的话，就存一下最短的距离，后面如果超过这个距离就不
在继续recursion了。
不知道想法对不对 |
|
t*****l
发帖数: 38 | 40 找板上的兄弟refer了airbnb
recruiter很快联系了我，而且不得不说airbnb的recruiter态度特别好，堪比google
recruiter
电面二话不说上来就做题
一个餐馆，菜单上各种食物价格如下
A， $ X.XX
B， $ Y.YY
C， $ Z.ZZ
D, $ ...
问现在一个人有 一定数额的钱，比如 $MM.MM，如何点菜才能把钱全部花完？
面试官要求列出所有可能的组合
我用了recursive的方法，写出来了
但是在 比较 float number的时候，细节没有处理好
直接比较 X.XX == Y.YY 会出现错误，所以必须要做差来比较
经面试官提醒改了过来
然后周一被通知挂了
这题除了用recursive方法，有更好的解法吗？DP?
**************湾区码农求refer***********
两年左右经验，会python和一些web开发， java啥的之前也做过，但是不熟
刷题应该没问题，正在系统的学习系统设计
求各种refer！请站内联系 |
|
c*****m
发帖数: 271 | 41 楼主题目没有描述清楚，看完你的解答才明白完整的题意是什么。我感觉更好的答案是
并查集和树的结合。peer用并查集表示（一个集合里面的都是peer），manager关系用
树的结构表示。构建过程中先用(manager,A,B)先构建树结构;然后再用(peer,A,C)构建
并查集结构（在树中有父结点的是并查集的root）。is_peer(a,b)要么a,b在一个并查
集中，要么两个所属的并查集有相同的manager。is_manager(a,b)就递归地找了。自己
写的测试用例过了，如有不对请指正
class People:
def __init__(self, name):
self.name = name
#parent in tree to represent employee-manager info,
#tree_parent is manager of this person
self.tree_parent = None
#parent in union-find group
... 阅读全帖 |
|
发帖数: 1 | 42 大弓科技今天的算法加强班试听课，之前吹的多么高大上，结果上课的“老师”居然是
个在家蹲了两年刷题都拿不到offer的人。
更离谱的是，这个所谓的“老师”之前参加过别人的培训班，然后就拿别人的培训班的
内容照着讲，被同学当场揭穿。而且还讲的极烂，思路极不清晰，毫无条理章法可言。
更更离谱的是，该“老师”公然宣称，bfs比dfs好，原因是dfs就是recursion，而bfs
就是iteration！（现场的同学和网上听课的同学应该都有印象）。甚至于同学指出任
何recursion都能转为iteration，dfs与bfs的区别不在于此，该“老师”只知道傻坐着
，甚至于需要他们的大老板冲进教室，出来说不要回答同学问题（现场听的同学应该都
有印象）。
今年上半年大弓科技的算法加强班在LA开，很多同学都反应说老师讲的极烂，思路含糊
，而且根本回答不了同学的正常问题。现在看样子是这个“老师”在LA混不下去了，北
上来湾区误人子弟了。可惜湾区是码农集中营，不是你南郭先生招摇撞骗的地方！
大弓科技一直致力于抄袭各个培训辅导，这两周微信朋友圈刷屏的”抄袭UXOFFER“事
件，就是大弓科技主动联系了一... 阅读全帖 |
|
c******n
发帖数: 4965 | 43 他说的 bfs vs dfs 从做题和 interview 角度看， 是没有错啊
下面“同学”说什么 所有 recursion 转成 iteration 这种扯淡的话这么长的楼居然
没有人说？ 是 tail recursion, 楼主纯粹是砸场子的， 找茬都没找对
bfs |
|
H***F
发帖数: 2501 | 44 你是托？
他说的 bfs vs dfs 从做题和 interview 角度看， 是没有错啊
下面“同学”说什么 所有 recursion 转成 iteration 这种扯淡的话这么长的楼居然
没有人说？ 是 tail recursion, 楼主纯粹是砸场子的， 找茬都没找对
bfs |
|
t******4
发帖数: 134 | 45 stack 资源比 heap 资源宝贵，
一般层数少，每层对象数量巨大，用recursion；
层数多，每层对象很少，用广度优先。
层数少，每层对象少，递归写起来更快更简洁
层数太多，每层对象巨大，我看还是优化一下存储数据结构吧
：一般bfs and dfs两个都可以用的情况下，大家用哪个？
：个人当然偏好dfs, recursion codes简练，但是怕stack overflow啊。
：Look. If you had one shot or one opportunity to seize everything you ever
wanted in one moment.
：Would you capture it or just let it slip? |
|
k******o
发帖数: 3328 | 46 The whole closing cost could be divided into NRCC (Non Recursive Closing
Cost) and RCC.
RCC (Recursive Cost), includes but not limited to home owner insurance (
hazard insurance) and property tax, etc.
Property tax will accompany you forever as long as your are the owner which
is independent of your mortgage.
When you have loan, the beneficiary of your home owner insurance is lender (
not you), therefore it is required.
Normally, in CA for standard sale, seller will pay government transfer tax,
... 阅读全帖 |
|
z****l
发帖数: 5282 | 47 ☆─────────────────────────────────────☆
SJZhai (Krazy) 于 (Fri Feb 1 02:30:03 2013, 美东) 提到:
今天莫名其妙的收到chase的信，说他们现在必须跟我终止客户关系
也就是说我的checking account会被close，而且无法终生无法恢复（whole life）
落款是chase loss prevention,真是搞不懂，我的账户都用了好多年了
有人遇到过这样的情况吗？如何waive掉这个？
打了一圈客服电话，第一个说是上个月我提取了7000块，我自己的钱为啥不能取了？
第二个说没有理由，这是他们银行的权利。
第三个说让我去branch，找personal banker
有懂行的，或者成功解决这个问题的兄弟现身说说我该怎么办？
一夜起来，突然发现帖子被顶了100多，感谢各位大哥大姐大爷大婶。我的case是这样
的，去年底，走了些iphone 5，神医们异地cash deposit一些货款我，但每次都是少于
1万。由于我也是和朋友几个一起做，神医货款到了后，我要写personal ch... 阅读全帖 |
|
z****l
发帖数: 5282 | 48 ☆─────────────────────────────────────☆
fuchl (严重缺包子) 于 (Mon Jan 7 18:56:10 2013, 美东) 提到:
http://slickdeals.net/f/5786234-American-Express-Platinum-US-10
Annual Fee 450
刚进去看了看，有。。。
☆─────────────────────────────────────☆
xmdxx1182 (卡西莫多) 于 (Mon Jan 7 19:00:26 2013, 美东) 提到:
能吃吗？
☆─────────────────────────────────────☆
Fulton (富二代) 于 (Mon Jan 7 19:02:14 2013, 美东) 提到:
可以找我换100包恰恰瓜子
☆─────────────────────────────────────☆
cocoon757 (Cindi) 于 (Mon Jan 7 19:03:26 2013, 美东) 提到:... 阅读全帖 |
|
G*******n
发帖数: 3144 | 49 谢谢！！
您转给 recursive,现金(伪币):20,收取手续费:0.2
同时附加了如下留言给 recursive. |
|
G**T
发帖数: 2610 | 50 同意。 Devil is in the details, 说的也是这个意思。
总得来说，是个系统工程。系统工程都是hierarchical & recursive的 －－ 层层次次
，蛮复杂的。但人脑，尤其懒人的脑，喜欢简化，喜欢找不用动脑的简单可执行的“原
则”。 这个诉求的本质，是要flatten a hierarchical & recursive system。
一维空间是很难表述多维空间的。 也很难理解多维空间。是以永远的争论， 永远的水
源。。。 |
|
