h******8
发帖数: 55 | 1 fail了，说说记得的吧
- You have two arrays X and Y. Each are having say M and N elements already
sorted increasingly. We have to find the k-th largest one of the whole set
M + N elements.
- Simple regular expression match，可以match的符号只有3种：
a-z : match a-z
a+ : match any numbers of a
.+ : repeat 1 - arbitrary times
和没用过regex的同学解释一下 例如
a+b 可以match : ab, aab, aaaaaaaaaaab
b.+b 可以match : bb, bab, b12345b
- boggle puzzle 找到里面所有的单词，写code
- Given preorder of a binary tree,... 阅读全帖 |
|
n*******w
发帖数: 687 | 2 都很经典啊。
二维排序矩阵搜索，在leetcode看过各种详细解法。最快是logN。
regex跟boggle都可以递归写出很graceful的代码。
already
set |
|
j*********2
发帖数: 1 | 3 求regex跟boggle都可以递归写出很graceful的代码 |
|
S*******e
发帖数: 379 | 4 把matrix每个格子作为起始点，递归尝试每个方向，用一个extra matrix记录到过的点。
每visit一个点，跟字典比较是不是合法的单词。
如果字典保存在trie里，递归的时候可以terminate的早一点。
有其他更好的解法吗？ |
|
S*******e
发帖数: 379 | 5 顶一下，哪位大牛能帮忙confirm一下？
点。 |
|
S*******e
发帖数: 379 | 6 把matrix每个格子作为起始点，递归尝试每个方向，用一个extra matrix记录到过的点。
每visit一个点，跟字典比较是不是合法的单词。
如果字典保存在trie里，递归的时候可以terminate的早一点。
有其他更好的解法吗？ |
|
S*******e
发帖数: 379 | 7 顶一下，哪位大牛能帮忙confirm一下？
点。 |
|
|
|
g**e
发帖数: 6127 | 10 算法是基本的，我们公司在你列的这几个里面算是最差的，但是我认识的几个SDE3
pricipal算法都是刚刚的。我的大大老板50多岁，manager做了十多年，写个boggle算
法一气呵成。这些东西都是死的，看看书做做题就能很快提高。真正做project，调jvm
的经验是实实在在积累的。
我个人觉得算法好更重要的是表现一种态度。工作中态度决定一切 |
|
s*********0
发帖数: 89 | 11 怎么我去年全是算法题？我面的是seattle的，是不是跟总部不一样？另外，是不是总
部的面试简单一些？
也发一个去年的g家面经吧
- 给字符串，里边是几个单词中间没空格，输出所有可能的句子。
- two sorted array, find the k-th largest number
- a variant of boggle puzzle
- given preorder of a binary tree, print all inorders
- regex
- given the statics of letter frequency, redesign the cellphone key layout s
.t. the expected number of presses is minimized.
真心觉得不容易啊。当然主要是我水平不行，挂了。 |
|
|
d**e
发帖数: 6098 | 13 全fail了，呵呵，没什么成功经验。
1 - medtronic, LA
recruiter打电话来的，对着单子上的技术问题语言特点一个一个问，她什么也不懂，
所以有疑问也没得商量，当然我也有几个答得不好。最后不了了之。
2 - hulu, LA
电面1，跟glassdoor上面几乎没什么区别，都是问烂的题，merge sort, LRU, 还有两
个算法，给code问是做什么的，我遇到的是anagram和circle detection in
linkedlist.
电面2, 分割字符串，定义了一些rule
有三对分割符,我忘了是给什么了，但应该不太重要，就假定给的是(),{},[]，然后这
六个符如果是连续两个重复就是escaping，下面是一些例子
abc(cde)efg -> abc, cde, efg
(abc){cde}[efg] -> abc, cde, efg
(((ab))c)cd{{}}e[efg)]]] -> (ab)c, cd{}e, efg)]
没做出来，第二天一大早就被拒了。
3 - wireless generation, NYC
电面，是一个engine... 阅读全帖 |
|
a*******y
发帖数: 1040 | 14 回来了 with mixed feeling
题目都不难，但是第三个有点坑坑爸爸，最后做错来了，这哥们好像有点没follow，我
觉得code应该work，回来路上想到有个bug，result没push到vector里，日
但是感觉那个code不elegant，那哥们说应该用另外一个helper function来做
recursive，我agree，但是个人感觉我写的应该work，总体感觉这个做的不是100% 牛
逼，第一个第二个应该没什么问题，第四个是design，难说结果怎么样，那个门也不知
道是太nice还是觉得我傻逼，过程中每个东西我刚一想，他就说答案，比如说应该大概
多少内存，他马上说10g,我说应该用hash，他马上说对，可以用hashcode来hash first
letter and second letter，唉，难说
题目都不难， level order print BT，哥们不让用两个queue也不让用两个variable，
还好我立马想到用token作为一个dummy node，在想什么时候push dummy node时候犹豫
了下，最后还是做出来了，写完有... 阅读全帖 |
|
g****y
发帖数: 240 | 15 boggle game. 基本上就是trie + recursion。 |
|
L**********g
发帖数: 15 | 16 找工总算告一段落了，从精华版中获得不少帮助，也想把自己的经验教训与大家分享一
下。
背景
如果不算实习，我有国内两年这里一年工作经验 ＋ master。毕业工作后，在组里越做
越没劲，遂开始准备跳槽。
准备
我前后断断续续共准备了4个月吧，也走了些弯路。最初，我粗略地过了一下
programming interview exposed，CLRS。话说CLRS真是精髓，值得一读再读。然后，
我就开始零零散散地做一些题目，从 careercup，glassdoor，code jam上找些题目来
写。后来，我才发现了mit这个版和leetcode，其中题目的质量和针对性都高很多，后
悔没有早点知道。
面试
1. G
这是我最后悔的一次了。。。当时准备的很不充分，有recuriter来搭讪，就apply了，
结果是电面就挂了。题目是实现大整数的乘法和加法，我虽然最后实现了，但是用了不
必要的递归，思路也有点混乱，于是挂掉。
2. L
在g悲剧之后，奋发了一阵，经朋友推荐，拿到了他家的电面。总共两轮电面 ＋
onsite （5面），还记得的题目有：
1. two sum
2. design to... 阅读全帖 |
|
s****a
发帖数: 794 | 17 感谢大家的祝福！
NV面试的内容主要是这个组工作中遇到的问题，比如怎么样balance gpu cpu的
workload什么的。估计没有工作经验的话几乎无从下手。
google和MS的面试都是比较传统的那种技术面试，题目也都比较正常，似乎对以前做过
的project都比较感兴趣，说了很多而且一遍遍的说。。。题目比如去掉数组中重复的
项，把一个sentence里的所有词都反过来一下，boggle，设计个扫雷，基本上也就是这
种常规的问题。微软有一个人很喜欢问脑筋急转弯来活跃气氛，连问了三个，都是很傻
的那种。。。
背景主要是graphics所以面试的主要也都是图形学相关的，希望对大家有用 |
|
H**********y
发帖数: 7928 | 18 赞！
cong~~~
感谢大家的祝福！
NV面试的内容主要是这个组工作中遇到的问题，比如怎么样balance gpu cpu的
workload什么的。估计没有工作经验的话几乎无从下手。
google和MS的面试都是比较传统的那种技术面试，题目也都比较正常，似乎对以前做过
的project都比较感兴趣，说了很多而且一遍遍的说。。。题目比如去掉数组中重复的
项，把一个sentence里的所有词都反过来一下，boggle，设计个扫雷，基本上也就是这
种常规的问题。微软有一个人很喜欢问脑筋急转弯来活跃气氛，连问了三个，都是很傻
的那种。。。
背景主要是graphics所以面试的主要也都是图形学相关的，希望对大家有用 |
|
s*********3
发帖数: 65 | 19 找工作中从MITBBS得到很多信息。很多人都很热心帮忙，特别是hua5018。希望我的资
料也能帮到一些人。
背景：EECS，BSMS，学校还行，专业排名一般，去年暑假在一小公司INTERN。面试准备
不充分。
申请的公司及结果：
英特尔 –接受Offer
艾匹克 –拒Offer
Storm8 - 拒 Onsite
亚麻 – 拒Phone interview
古歌 – 拒Phone interview
微软 - OCR被拒 （boggle game）
高通 - phone interview 被拒 （OS）
MathWorks - phone interview 被拒 （就聊天）
Quantcast –做题被拒
Zygna - phone interview 被拒 （就聊天）
彭博 – 申请被拒
WalmartLab - 没回音
Square - 没回音
苹果 - 没回音
甲骨文- 没回音
亚虎 - 没回音
摩根斯坦利- 没回音
高盛- 没回... 阅读全帖 |
|
f*******t
发帖数: 7549 | 20 不难啊，boggle方向无所谓了，面试官知道你能写代码就行了 |
|
j******2
发帖数: 362 | 21 从不同的位置出发的路径互相之间是没关系的吧？所以不同路径之间不需要记录
visited node吧？trie里就算有相同段但是如果起始字符不同也完全不在同一条branch
上吧？ |
|
j******2
发帖数: 362 | 22 是不是
n*n*pow(8, n*n)
感觉好恐怖 |
|
|
|
j******2
发帖数: 362 | 25 是不是
n*n*pow(8, n*n)
感觉好恐怖 |
|
|
|
b*******l
发帖数: 590 | 28 顶一下，我也想知道这个问题的答案，哪位大侠给个说法？ |
|
t*******3
发帖数: 734 | 29 一个naive的计算方法：
对于n*n的格子：
sum_{i=1,n^2}(n*n)*n*4^(i-1)=n^2 pow(4,n^2)
跟你的很接近。当然我的是上下左右4个方向。 如果对角线算起来，就是n^2 pow(8,n^
2). |
|
|
t*******3
发帖数: 734 | 31 我写错了。 我多写了n^2.
我的结果跟你的是一样地。
不过这个计算方法是有错误的。
尤其是等word长度比较大的时候。 不是指数形式。 而是最多power级。因为要考虑一
些点已经visit过了。 |
|
n*******w
发帖数: 687 | 32 用big O表示的话，基本是lz说的那样。
最长word可能没有n平方那么长，指数上的n平方可以写成 min(n^2, word_limit)
可以用各种数据结构帮助剪枝。暴利递归解n=4大概是5分钟数量级。
tries可以到0.3s。上次看到有面试官问剪枝可以优化多少倍。最后答案是至少1000倍
以上。
听说过最快的是做到0.1s。大概就是把1M个单词文件读进内存的速度。解4*4几乎不需
要时间。 |
|
b*******l
发帖数: 590 | 33 怎么利用数据库结构的帮助剪枝啊？大侠能否给个标准答案？我看网上的算法好像都是
那种很慢的。我自己运行了一下，真的很慢啊。
在下先谢过了。 |
|
n*******w
发帖数: 687 | 34 标准答案算不上。可以说说我test过的数据结构吧。
1. 最黄最暴力的就是从matrix的任一位置开始，8个方向能走的全试试，走一步看走过
的路径组成单词是不是在dictionary里边。即使当前路径不是valid单词，也要继续往
下走。n=4运行时间数量级在5分钟。假设dictionary是1百万个单词量级
2. 稍微不那么黄的暴力解法是，对于dictionary里边的每个单词，去matrix里边走看
能不能走通。感觉上单词百万级会更慢，实际上可以降低运行时间到一分钟之内。原因
是，每个单词去走的时候，不需要每走一步就检测是不是合法单词，不合法直接退出，
大量的剪枝了。
3. 把dictionary建trie，这样在matrix里边每走一步都检查trie是不是能往下走。如
果当前prefix就已经invalid了，那这条路就不可能走出单词了。运行时间几乎等于建
trie的时间，大概是0.3s量级。
建trie的过程大概是建立一个27叉树，分别存a-z（不考虑case）以及结束标志比如$。
每个node不用存字符本身，存一个bool值就行。true表示这个路径存在否则不存在。相
当于把... 阅读全帖 |
|
|
b******n
发帖数: 823 | 36 店面：
Input: Sorted array, int k， Output: All pairs of indices (i,j) such that A[
j] - A[i] = k
这个很简单，俩指针了事，然后问如果有dup的情况怎么办。
onsite 4轮，都是常规题：
1. 问research, 怎么group anagrams together
2. most freq char in str，很简单，ct[256]搞定，
然后问了一堆扩展和特殊情况，这人一看就很geek
what if str is empty, what to return
what if just to find most freq alphabetic char
如果有一个upper case char 和一个lower case char出现相同多次，你的程序
output哪一个
how to output all most freq chars instead of just one
what if utf8
3. sorted array to bst
... 阅读全帖 |
|
c******5
发帖数: 84 | 37 昨天刚面的，今天知道挂了。。。
第一轮: 实现一个简化版的boggle game，给定一个dictionary，我用dfs做的
第二轮：给一个int array, 不用division,replace each element with the
multiplication of all elements other than that element
第三轮:给一个method char[] read(int n)，读入n个字符，输出到数组中，让实现一
个String readline()，字符流以null结尾
第四轮：实现method: int getNthPrime(int n)，找出第n个质数，n从0开始，这题没
打好，想错了，用了sieve of eratosthenes.
唉，感觉面试时一旦想错了如果面试官不提示的话，就万劫不复了。。。 |
|
|
x**********8
发帖数: 22 | 39 回答一下上面的几个问题
1.我是找的software engineering FT 职位，"秒了"就是很快给出算法，然后如果他没
和你进一步讨论就开始写
2.都是要写代码的，除了那个大小堆的是他说只用说一下思路。用hashmap的地方不用
自己建，因为我用的是java，所以直接用的hashmap<>的写的
3.card design基本是150上原题
4.十字路口 design是模拟一个路口，有车来，有车走，一个时间只能有一个车通过，
还有一些具体的小要求，都是写代码的
5.最大质数就是O(n)算法，刚某楼给出的算法比我当时写的稍微强一点
6.boggle啥玩意不是很懂。。 |
|
l****i
发帖数: 2772 | 40 CS fresh PhD. 西雅图，已经接到HR电话，悲剧，攒RP，发面经。
第一轮，2个人。每个人先介绍了几分钟。给题，boggle，先让我分析怎么解决。代码
写到8个方向递归的时候，被打断，说知道我后面会怎么写了，让我先分析这个程度的
复杂度，他们有其他问题要问。最后15分钟，问了一大堆behavior，关于team work的
一类的问题，有矛盾怎么解决，team里有人不干活，team里有人和你不同意见等等，要
求给出一些以前经历的例子。
第二轮，老美白人。开始问了很多object oriented的问题。abstract class，
interface，什么情况下如何选择，inheritance VS composition等等。然后一个
coding，按行统计词频，不难，hashtable解决。 写code的中间，问了很多次复杂度，
基本上我写一行code，他会问一下这一行的复杂度。然后给了一个OOD，一个tree的结
构，计算表达式。然后又出了一题OOD，题目还没解释完，外面的第3轮人就敲门了。
第三轮，南美或者欧洲女。这一轮我很崩溃。第一轮，按层遍历二叉树。直接问我，你... 阅读全帖 |
|
e********5
发帖数: 422 | 41 我去amazon也是问的boggle题，写错了，改了半天才对；也是一个design题，做的一般
；我还不是cs的，很但最后拿到offer了。感觉你这面试很奇怪啊 没有HR么？没有你
hiring manager么？
有时候做题要多问问，做一堆数找啥的题目，主动问是不是sorted都是很自然的。估计
你一听题，就赶紧埋头写，然后面试官问你是不是见过，你表现得又有点awkward。让
人感觉到你太紧张了，交流不畅。我觉得你6个onsite全悲剧，是不是也有这方面原因
。去面试不是去光被人检查的。interview嘛，双方看对方合不合适，自信一点，机会
会来的。 |
|
h****n
发帖数: 1093 | 42 第三轮那人期望你用1到N用求和公式减去实际的和
CS fresh PhD. 西雅图，已经接到HR电话，悲剧，攒RP，发面经。第一轮，2个人。每
个人先介绍了几分钟。给题，boggle，先让我分析怎么解决。代码写到8个方向递归的.
....... |
|
d**e
发帖数: 6098 | 43 应该是这样吧。。。
另外应该边走边查字典，字典没有这个prefix了就应该做early return。
^n |
|
|
g*******s
发帖数: 2963 | 45 啊～～忘了early prune tree了 555555555 |
|
|
|
b****g
发帖数: 192 | 48 我刚做完这道题。
开始没用递归，我自己写了queue记录访问的位置、已得到的word。
后来又用递归写了一个，简单多了。 |
|
l****i
发帖数: 2772 | 49 trie的node里，加一个boolean判断。T表示一个合法单词的结尾。F表示没有合法单词
。 |
|
h*****a
发帖数: 1718 | 50 哦，是boggle吧？第一次被面到这个题的时候写的很滥。 |
|
