S**********r
发帖数: 1410 | 1 上周报了一下"Passed Hiring Committee"后收到不少同学来信问面经和Fresh的区别，
抱歉没有时间一一回复，在这分享一点经验，但无具体题目due to NDA.
电话面试：15 分钟介绍Experience, 30分钟实现一个C的库函数(此处略去6个字符:-），first brute force, then optimize. 第二天通知安排OnSite.
Onsite:
前两人偏算法和编程，难度中等，关键是算法要表述清楚，编程要一气呵成。
后两人偏系统和设计，实际相关，没见过，关键是不要慌，当他是同事，一起讨论解决。
OnSite后感觉有90%把握，但仍继续看书做题保持状态，以备万一需要2nd Onsite.
两星期后通知过了Hiring Committee.
准备要充分，我业余准备了四个月直到有八成把握才联系Google:
Programming Pearls要看第二版（buy a hard copy，the PDF on web is just a
dump from its website): Updated problems, added a cha... 阅读全帖 |
|
r*******e
发帖数: 7583 | 2 赞分享
10年+经验的都需要4个月准备
我等小虾米越看越绝望啊
），first brute force, then optimize. 第二天通知安排OnSite.
决。
/C
to- |
|
s********k
发帖数: 6180 | 3 非常感谢，我看网上说狗狗今年招聘更倾向有企业经验的人？他们的码农面试更多是解
决实际问题，甚
至不是技术方面的，而是市场策略销售方面的？不知道楼主有没有这样的感觉？
），first
brute force, then optimize. 第二天通知安排OnSite.
决。 |
|
l*****a
发帖数: 14598 | 4
），first
brute force, then optimize. 第二天通知安排OnSite.
it is strstr, haha
决。 |
|
m*******d
发帖数: 40 | 5 google在大量招聘Engineer:
http://www.jobguideweb.com/it-jobs/google.html
所以准备了
四个月，直到有八成把握才联系Google（如被拒一年左右不能再申请），可能有些
Overkill,
不过总比准备不足被Kill好 :-)
for warm up. 要看第二版: Updated old problems, added new problems,
added a chapter for Strings, C/C++ style code instead of PASCAL
style in 1st edition. （Buy a hard copy，the PDF on web is just a
dump from its website)
pseudo code instead of hard-to-read style in earlier editions.
悉常考题型及算法以外的知识点。
brute force, then optimize. |
|
i**********e
发帖数: 1145 | 6 我今天写的代码，通过了我的一些随机数据测试（与 brute force 的方法进行比较）。
基于我上次贴的方法，有一些错误，造成一些混乱，不好意思。
1) First, we store the contiguous sum from the first element to a cumulative
array called cum[], where cum[i] = cum[i-1] + A[i-1], and cum[0] = 0. Using
the cum[] array, we can easily find the contiguous sum from i to j, A[i...j
] = cum[j+1] - cum[i], i <= j. Here is an easy trap to fall into, you MUST
define cum[0] = 0 and the size of the cum[] array must be n+1, or else it
would miss including the first element in the c... 阅读全帖 |
|
g*****k
发帖数: 623 | 7 Your solution is actually the same as ibread's solution.
in ibread's solutio's last step, j starts from n to 0, so binary search
in the sorted cum array s.t. cum[i]<= cum[j]-k. Once you find i, you just
get the smallest index by min_index[i].
min_index[i]= min{k | cum[k]
j-min_index[i] is the length of the subarray starting at min_index[i]+1.
我今天写的代码，通过了我的一些随机数据测试（与 brute force 的方法进行比较）。
基于我上次贴的方法，有一些错误，造成一些混乱，不好意思。
1) First, we store the contiguous sum from the first element to a cumul... 阅读全帖 |
|
g*********s
发帖数: 1782 | 8 the order of number is fixed?
looks like a brute force. first construct a tree with these numbers as
leaf node and unknown operators as internal node. then traverse it. |
|
f*********i
发帖数: 197 | 9 刚刚从西雅图回来，飞了整整一天，其实游戏那道题目，bitmap估计是最好的数据结构
了，和大家讨论的一致。
关键的问题是，如何判断是否可以放入board，我提出的方法是最naive的brute force
，就是单纯的比较，没有用DY，因为我当时实在想不起来了。看老印的意思，是可以用
DY来做的。 |
|
l*****a
发帖数: 14598 | 10 先说brute force的
逐渐慢慢想出来最优
另外其实大家都很清楚这种情况，所以说并非题做对了就给offer |
|
c********0
发帖数: 112 | 11 题目的意思就是 有一个函数f(i,j)，以一段数组的起点和终点的index作为输入，返回
一个值. 然后我们的任务是把这个数组分成三段，让这三段的和尽可能的小 (每一段都
有一个起始和终止的index,所以都对应一个f(i,j)的值 )。
Brute force的解法：
起点设为0，对于任意i
起点设为i 对于任意j （j>i）
计算 S = f(0,i) + f（i,j）+ f(j, N)
记录最小的S，这样调用的N^2次的f(i,j),如果用一个表把f(i,j)记下来可以调用
N^2/2次 但是还是O(N^2) |
|
c********0
发帖数: 112 | 12 就是没有说数组A的性质啊。。。
我还问了 f(a,b)有啥特点 说没有特点。。。
我觉得就是brute force的尝试。。。 没有其他方法了吗 |
|
e*****e
发帖数: 1275 | 13 俺滴思路就是brute force 算出所有f(i, j)
然后DP
不知道还有其他办法没有 |
|
z**********g
发帖数: 209 | 14 抛砖引玉一下
Some questions:
1. find PI using simulation
monte carlo simulation
2. design a cache (interface, implements different cache strategies)
LRU hashtable + double linked list
3. judge whether two integer arrays are the same after sorting, e.g., {1,2,3
} is the same as {1,3,2}
Any O(n) approach?
bitmap
what if the range of the integers in the arrays are huge?
hashtable
4.
if a tree can be converted to the other by only swaping the labels between s
ibling nodes, then the two trees are considere... 阅读全帖 |
|
s******a
发帖数: 35 | 15 第二面，基础的technical 问题。记得不是很清楚了 会把记得的都写上
四个部分。
数据结构： 用pointer需要注意的？什么是recursion并且举例子。array sort？这题
我没听太清楚，不知道他到底想要什么..其余的不记得了。。。都很基础。
C++：virtual; deconstructor是不是每次都要virtual；static,function
overloading，不记得了。。。
java： string && string buffer;Interface vs Abstract Class;Inheritance;
Multithreading等等，不记得了。。
数学: brute force; maximum flow minimum cut;不记得了。。。
祝大家好运。 |
|
F**********r
发帖数: 237 | 16 版上的题，但是考古找不到讨论了。。。大家看看怎么做好？只能想到brute force的
。。。。
Given a document and a query of K words, how do u find the smallest window
that covers all the words at least once in that document? (given you know
the inverted lists of all K words, that is, for each word, you have a list
of all its occurrrences). |
|
|
y******5
发帖数: 43 | 18 Thank you.
Some quick thoughts about 6 and 7:
Possible input:
"0"
"+123"
"-123"
"+-123"
"0x123f"
"12.3"
non-number chars
Anything else?
Brute Force with improvements:
1. only consider odd numbers (except 2)
2. for current number, only check to its sqrt
3. for current number, only check prime numbers which are not more than its
sqrt |
|
e****a
发帖数: 449 | 19 问题就是给一个整数,表示成n个整数的平方和,n最小, 要求这几个整数. brute force
是先找
n的平方根,然后递归. 如果整数很大, 如何提高效率 一些case是 12=4+4+4
10017=10000+4+1,好像如果是像前者比较平均的,用递归效率就不高? 到这肯定是算法
题了,应该和写程序无关了吧. 现在我也不care了,什么乱七八糟的 :)
NND 拉格朗日定理 我要是知道 还可以和他扯扯..... 不过这题应该不怎么普遍,原来
没见过. |
|
|
j**l
发帖数: 2911 | 21 I did not realize that Brute Force method should be used first, and tried to use Greedy and the idea of Coin problem instead. I eventually got stuck. I finally told him that it should be NPC, but I did not realize that it is a variation of the classic Knapsack problem and let him know. I think he gave bad feedback to the hiring committee.
3) 最不济，也要想到暴力穷举法，比如comon2010的例子，可对x, y, z作三重循环穷举比较。如果这个都不能先说出来，然后又想不到1)或者2), 面试官那里肯定几乎不得分了。 |
|
h*****1
发帖数: 74 | 22 也许直接写brute force 的就好了。
我也是看大家的面经提到string match， 自己专门写了个，但没有debug。
请问大家，碰到这种情形能要求另外一人来重新interview吗。真是心有不甘。 |
|
r*******y
发帖数: 1081 | 23 5. brute force is acceptable ?
i) |
|
n********7
发帖数: 73 | 24 刚才开车回家的路上接到A的recruiter的电话，问神马时候可以电话三面，我说两周以
后行不行，
她说不行，然后我说那就下周吧，周三以后随便神马时候都可以……依照他们的风格，
肯定会安排在周
三，这几天就狂啃一下书吧。唉偏偏这个时候project又是最忙的时候。昨天还开会说
这一个月都不
准假，没办法…………
发一下前两次的面筋，之前发过一个一面的，因为太调侃所以被鄙视了，这次认真地写
一次：
一面：老美，人很好的geek，题目也不难
1. 写/读 code输入n输出3的n次方，比如输入4，输出3，9，27，81。写了一个brute
force
的，我菜啊~~！！
2. 讨论复杂度，假如输入10000之类大数字会怎么样。答错……
3. 问机器可以表示最大数是多少？基本上也答错~~~~
4. 设计一个服装仓库系统，有哪些类和方法。大概说了一下，都是很基本的。
5. 问熟悉哪些数据结构，答linkedlist，tree，hashtable等等。问关于hashtable的
内容。
6. 问怎么从一个大文件里找出一个电话号码，说用regular expression，他说是，在
linux里... 阅读全帖 |
|
h*******0
发帖数: 68 | 25 I have a solution which takes about 50 seconds for the 8x7 matrix. The brute
force recursive DFS takes more than 200 minutes on the same machine. The C+
+ code is given below.
[root@cli-linux ~]# ./findPaths
Searching...
Total 301716 paths found in 53 seconds. |
|
|
g**u
发帖数: 583 | 27 请问大家一个区间overlap的问题：
比如说 我们有如下的区间：
[1, 5], [2, 6], [3, 7], [8, 10], [9, 11]
如果是判断是否有overlap的话， 可以sort stating point, 然后用类似merge的方法
来确定是否有overlap( O(nlog n) )；
如何找到所有的overlap的区间呢？
用brute force就是O(n^2)的解法， 有没有更快的呢？
谢谢 |
|
m********l
发帖数: 4394 | 28 基本上DP就是Brute Force的一种
不过可以用DP的问题要重算很多东西
为了节省资源， 把要重算的东西存起来 |
|
m******m
发帖数: 19 | 29 lz能说说第一轮电面第3题：find the common node of two binary trees.的思路么
brute force：先遍历A树,将所有节点存入hashset,然后遍历B树，check当前节点是否
在hashset
出现，如果是return true.
此外，lz能讲下onsite的最后一题么，不是很明白啊~ |
|
M*****e
发帖数: 568 | 30
Depends the size of the Alphabet, and the length of the second string.
If the alphabet is small (e.g., English char), create a hash table for that
- O(size of alphabet * len_string1). If the second string is small, (e.g.,
1 char), brute force search on the first string - O(len_string1 * len_
string2). If both are large, sort the second string, and go over the first
string while binary look up each char in the sorted second string - O(lg(len
_string2) * (len_string2 + len_string1)). |
|
q******8
发帖数: 848 | 31 貌似每步都还要check一下是不是palindrome，所以还是o(n3),和brute force没区别。
有linear的算法吗 |
|
r******n
发帖数: 170 | 32 follow up 一下这家的面试，很快给了我2电面,最近告诉我悲剧。
2面是个senior SDE
问了4题，都是常见题：
1.如何design vending machine? 我大概说的key class为product, payment, machine
。follow up的questions如，如何知道还剩多少coke之类的
2. 如何design chess game? 如何知道谁赢了？board是否该为个class等。
3. find common longest substring in two strings.似乎是个DP经典问题。
http://en.wikipedia.org/wiki/Longest_common_substring_problem
我当时只说了brute force的方法，被要求优化
4.如何搜索遍历一个棋盘，假设只能走4领域。要求:不能重复访问已经走过的node.我说的遍历，通过visited flag防止重复。结果要求不能做visited flag，他给了提示后，原来算是mark previous node，然后不往回走。事后想想认为这样... 阅读全帖 |
|
s*****n
发帖数: 5488 | 33 写个简单好理解的brute force版得。
int superCool(int y){
int lower = 2;
while ( lower < y)
lower *=2;
int upper = lower;
lower = uppder/2;
for (int i = 3; i < y/3; i++){
int guess = i;
while ( i < y)
guess *= i;
if (guess < upper)
upper = guess;
guess /= i;
if ( guess > lower)
lower = guess;
}
return math.Abs(lower - y) > math.Abs(upper - y) ? upper : lower;
}
|
|
f**********t
发帖数: 1001 | 34 有没有更好的做法？
Brute force method:
sort the array using any existed sort algorithm, just treating the array as
normal array. The best time complexity is O(nlogn)
Method2:
Among M sorted array, select the smallest number from one array, move the
pointer to the next integer of the array. repeat this routine, until all
integers are put into order.
For each integer in the output array, it's compared M times. the time
complexity is O(n*M)
The code is listed below:
void nwaymergesort(int* arr, int* out, in... 阅读全帖 |
|
h**********d
发帖数: 4313 | 35 公司名就不说了，不是大公司
不过效率极高，从hr联系我到拿到offer，3周不到。。。（一个重要的原因是我一开始
就跟他说我有学校offer了，他问我prefer学校还是industry，我赶紧说当然industry
更好~）
电面1， SW director
问了interface vs abstract class， encapsulation（为啥要用，我解释了privacy,
protect data, 他似乎不是很满意。。）, exception throw的overridden为什么不能
throw更多exception， SQL语句， 问文件如果不打开如何知道有多少行（我说用linux
command.... 想了以下, cat -n|tail ? 不过他没说啥貌似听到用command很满意。。
。）
后来还做了coding assesment， OO Design, 一个小时，写了7个class，用了delegate
pattern，自我感觉比较牛叉的design （LOL）
果然director 发信来说他们都很enjoy我的homework，哈哈哈（这还用说么）
电... 阅读全帖 |
|
a**********2
发帖数: 340 | 36 a. 一个Collection, 一个Collection, Person有 PersonId 和 name
， Color有colorName 和 personID
要求输出每个PersonName & colorName 组合
心想这也太简单了。。。说了3种方法，从brute force到用hashmap，最后O(n+m)
不太明白这题，求组合怎么做到O(n+m)? |
|
k*j
发帖数: 153 | 37 2 solutions
1.brute force, complexity O(m*n), m is the length of the pattern, n is the
length of the string
2. KMP O(m+n) |
|
s*****y
发帖数: 897 | 38 Should we write the kmp during the interview? Or just write the brute force? |
|
i**********e
发帖数: 1145 | 39 我一开始也想多传一个参数进去，但是其实直接看下个字符就可以了。
1）如果下个字符是 '*' 的话，那此字符必须 match pattern 字符。
2）如果下个字符不是 '*' 的话，那就做 brute force matching，一个一个 match 直
到字符与所 matched 字符不一样为止。
NULL |
|
i**********e
发帖数: 1145 | 40 我一开始也想多传一个参数进去，但是其实直接看下个字符就可以了。
1）如果下个字符是 '*' 的话，那此字符必须 match pattern 字符。
2）如果下个字符不是 '*' 的话，那就做 brute force matching，一个一个 match 直
到字符与所 matched 字符不一样为止。
NULL |
|
b******4
发帖数: 1873 | 41 那个答案是这样做的
先把所有相同长度的words放在一个array中，然后你有N个array, N代表最长的words长度
可知最大的rectangle 的大小应该是所有长度为n的words组成的，既n x n大小
然后确定从哪两个bag拿words，假设bag A words length = x, bag B words length =
y
那么就开始从x * y最大且不超过 n x n这么大的情况开始
基本上是brute force的解决方法 |
|
k*j
发帖数: 153 | 42 某刚上市公司onsite。已经被拒了。奉献面经攒rp.
1。hosting manager来介绍他们的项目。no technical question，但这个时候应该多
讨论，刚看一本面试书说应该listen和ask questions的时间一半一半。我当时见缝插
针问了几个问题，别人就很开心，说good question之类的。不知道这轮对最后评分有
没有影响。建议去之前先了解他们的产品。
2。给一个string,老pattern换成新pattern。不用in place。感觉不太考算法，但要注
重coding细节。特殊input之类的要考虑好。第二题是长string output成每行K个字符
的题。这题考思路。
3。most interesting project
4。 open question,如何改进他们产品，可以用什么算法
5。讲research，之前用过什么算法云云（半小时）。然后编程，如何对稀疏矩阵求dot
plot。写class。他是想用linkedlist来存储pair。而不是用vector来存。
6。 如何判断2个linkedlist相交，在哪相交。编程之美上有... 阅读全帖 |
|
B*******1
发帖数: 2454 | 43 Yes. I think Brute force could solve it.
Could we use dp? could not figure out the dp function. |
|
B*******1
发帖数: 2454 | 44 But I think we could still use brute force. Is it? |
|
x****3
发帖数: 62 | 45 Find the longest palindrome in a string.
这题出现频率很高。 一直没看到简洁的答案。 我能想到就Brute force, O(n^2). 有
个错的简单的解法（倒序后的字符串和原字符串， longest common substring.
counter example, "abcxacba"）
有人指点下吗？ 谢谢 |
|
g*****i
发帖数: 2162 | 46 第一题和经典题看上去像,但这里是求最长的子数组,还是有明显区别.而且bruteforce
只要O(N^2),dp复杂度肯定不会低于这个.我在想有没有nlogn的解法,但觉得挺难.O(N)
应该很难,举个例子吧.数组是: 1 2 3 4 5 100 -200. MaxSum=109. 用sliding window
的话到了-200还得往左扩张.
第二题你给我启发了,确实这个思路,dp其实复杂度还太高,可以用binary search更快的
找出如何分割,类似以前讨论过的paint问题,我怎么没想到呢,唉.
第四题看来只能brute force一个个尝试了?
element |
|
g*****i
发帖数: 2162 | 47 如果非负的话,一个sliding window就解决原问题了吧.
看来这题有负数只能brute force了 |
|
S**I
发帖数: 15689 | 48 a brute force solution to the third problem:
1. Let n = 0, m = 1;
2. Find all permutations of i, j and k such that i+j+k = m. Compute product
of 2^i * 3^j * 5^k of each permutation, put all the products in a set S.
3. Suppose the number of permutations found in the previous step is p (it
can be shown that p = (m+1)*(m+2)/2); then m++, n += p.
4. If k > n, go back to step 2; otherwise, the kth number in set S is the
solution. |
|
r******n
发帖数: 170 | 49 其实是第一次面big name，题目除reference counting那个，都写出来了，不过有2次
被挑到问题，然后我修改的。的确觉得已经很lucky，题目跟之前报的简单很多，可惜
还是挂了，自己觉得实力也没到。
我对电话号码那题还想请教下，我当时回答的用trie,一个n位长的号码，worst case就
是O(10N),那人似乎表示了赞同，这是正解？
字符串没空格断词那题，当时答的brute force的方法；然后简单提了些优化的思路。
这题版上有讨论过吗？
剧是不需要理由的。 |
|
B*******1
发帖数: 2454 | 50 How to find a number of 10 digits (non repeated digits) which is a perfect
square? perfect square examples: 9 (3x3) 16 (4x4) 25(5x) etc. Ten digit
number example 1,234,567,890
我只想到用brute force,用0-9 permute 5位数字，然后求平方，看得出来的数字是不
是perfect square,有更加好的办法吗？
thanks |
|
