b********6
发帖数: 35437 | 1 brute force才是真正理解问题所在，将来面对变种才有能力选择正确算法。
brute force的最大问题是重复计算，dp最大的优势是存储和使用已经有的结果。如果
你真正理解了这个问题，从brute force改成dp只需要想办法存储就行了。
背下了dp解而不知道brute force，就是告诉面试官你只会刷题，而且只刷了一种解法 |
|
发帖数: 1 | 2 不久前参加了一个onsite面试，其中一轮的面试官，出的题我一下看出来是DP。分析了
一遍，她要求我从brute force开始写代码。
写完后让我从brute force解法优化。分析了几分钟，简单写了一下。还没来得及写我
之前想的最优DP解，她跟我说时间到了。
要求写brute force算法普遍吗？ |
|
d*********e
发帖数: 352 | 3 唉，太搓了，不会optimal
会了optimal又不能一遍过
一遍过了又不能够bug free
brute force肯定要挂。
请推荐brute force可以过的公司。。 |
|
s***h
发帖数: 372 | 4 http://www.spurgeon.org/s_and_t/brutes.htm
by C. H. Spurgeon
From the June 1873 Sword and Trowel
The newspapers for the last few weeks have been a source of grievous
affliction to humane minds. The brutalities which they have recorded have
shown a diabolical refinement of cruelty which makes us blush to belong to the
race of man. When we read of a wretch driving a poor horse for miles with its
feet broken, bleeding at every step it took upon its poor stumps, we shudder
and our blood runs cold; |
|
z**********g
发帖数: 209 | 5 You're given N signed integers a[1..N].
You need to find N correct signs s[1..N] (that is, numbers s[i] = +/-1),
such that
a[1]*s[1] + a[2]*s[2] + .. + a[N]*s[N] = 0.
Assume that the solution always exists.
Example: a = {5, 7, 3, -8, 1};
then the signs are: s = {1, 1, -1, 1, -1}
because: 5 + 7 - 3 - 8 - 1 = 0
(or symmetric solution: s = {-1, -1, 1, -1, 1})
brute force 2^n. |
|
j*****y
发帖数: 1071 | 6 是这个网站上的一道 puzzle
http://www.itasoftware.com/careers/puzzle_archive.html
我是通过分别 分割 x 坐标 和 y 坐标，得到更小的 area, 实行 brute force
, 看不出来这么小的区域计算量也很大。
Strawberry Fields
Strawberries are growing in a rectangular field of length and width at most
50. You want to build greenhouses to enclose the strawberries. Greenhouses
are rectangular, axis-aligned with the field (i.e., not diagonal), and may
not overlap. The cost of each greenhouse is $10 plus $1 per unit of area
covered.
Write a program that chooses the ... 阅读全帖 |
|
m*****n
发帖数: 2152 | 7 自己写了一个brute force的solution，每次运行都是Time Limit Exceeded。自己在机
器上跑过leetcode上failed例子，小于1 second出结果。难道leetcode对时间要求这么
严格？难道非要suffix tree的解啊？ |
|
z*********8
发帖数: 2070 | 8 就算leetcode让你过了又怎样呢？ 你去任何公司面试用brute force， 都肯定被拒 |
|
g****s
发帖数: 340 | 9 稍微优化一下的brute force，就是从一个index往两边扩展的那种，
用java还是可以过的。 |
|
|
l*********o
发帖数: 736 | 11 cisco这种做硬件底层很少用到brute force
上次面juniper时 对方就要求揭批DFS在硬件实现上不靠谱 |
|
发帖数: 1 | 12 Brute force解法写了，也用几个例子测试了，应该没问题。
但是DFS递归解法优化出来的我觉得不是最优吧，用那么多stack，而且我优化的时候好
像出了个小错。两个for循环多好。。可惜没写，也完全没感觉到时间了。
面试应该还是根据面试官的引导来做，但是她引导的完全和最优解是两条路啊
我只求她给我的评价写的好点，说不定以后还面这家 |
|
发帖数: 1 | 13 来总结一下，碰到这种要求从brute force开始优化的，要优化完bug free，然后提议
还有个更好的做法，能不能也写出来。
再把最优解附上。这就无懈可击了。 |
|
C**********r
发帖数: 8189 | 14 brute force 巨慢…… 坐等达人优化。 |
|
C**********r
发帖数: 8189 | 15
瞻仰下达人。
搜了。你是说不用brute force，直接看math world的那个表吗？还是说eqn41有什么道
道？ |
|
c*******r
发帖数: 253 | 16 我对比感受了一下觉得brute在达到letoff之前有个坎，不像rally那么顺滑。换成
Force-draw curve的话应该就是满磅平台更长，蓄能更大。
因此这个“坎”增加了12fps的IBO箭速。 |
|
a***k
发帖数: 1038 | 17 【 以下文字转载自 paladin 讨论区 】
发信人: atack (小军号), 信区: paladin
标 题: 红死病 by 杰克.伦敦
发信站: BBS 未名空间站 (Sat Oct 11 07:40:15 2014, 美东)
I
The way led along upon what had once been the embankment of a railroad. But
no train had run upon it for many years. The forest on either side swelled
up the slopes of the embankment and crested across it in a green wave of
trees and bushes. The trail was as narrow as a man's body, and was no more
than a wild-animal runway.
Occasionally, a piece of rusty iron, showing through ... 阅读全帖 |
|
a***k
发帖数: 1038 | 18 I
The way led along upon what had once been the embankment of a railroad. But
no train had run upon it for many years. The forest on either side swelled
up the slopes of the embankment and crested across it in a green wave of
trees and bushes. The trail was as narrow as a man's body, and was no more
than a wild-animal runway.
Occasionally, a piece of rusty iron, showing through the forest-mold,
advertised that the rail and the ties still remained. In one place, a ten-
inch tree, bursting through... 阅读全帖 |
|
i**********e
发帖数: 1145 | 19 问题背景：
最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
expression match吧。
所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
给个例子，例如
a*b 可以match : ab, aab, aaaaaaaaaaab
写个函数:
bool match(const char *string, const char *pattern)
这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
人很倒霉被问到这题。facebook有问过这题：请参考
http://www.mitbbs.com/article_t/JobHunting/31575425.html
这题其实利用brute force就可以了，算法不难想到，但是要处理很多special case，
非常的棘手。我觉得正常人一般都回遗漏掉很多case，第一次就能写对简直就难如登天
。再加上面试的压力，我觉得没做过这题面试当场第一次就能写对的是神人。
Brute force的算法就是O... 阅读全帖 |
|
i**********e
发帖数: 1145 | 20 问题背景：
最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
expression match吧。
所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
给个例子，例如
a*b 可以match : ab, aab, aaaaaaaaaaab
写个函数:
bool match(const char *string, const char *pattern)
这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
人很倒霉被问到这题。facebook有问过这题：请参考
http://www.mitbbs.com/article_t/JobHunting/31575425.html
这题其实利用brute force就可以了，算法不难想到，但是要处理很多special case，
非常的棘手。我觉得正常人一般都回遗漏掉很多case，第一次就能写对简直就难如登天
。再加上面试的压力，我觉得没做过这题面试当场第一次就能写对的是神人。
Brute force的算法就是O... 阅读全帖 |
|
发帖数: 1 | 21 貌似alphaGo把brute force/Deep Learning与推理模型两者结合，互助互利，产生了不
错的“成熟”应用效果。请教本行大牛，可否说说您对brute force/Deep Learning的
在实际中的应用的看法，例如2017年是否有类似成熟的新应用？谢谢。
局限性，一不小心就可能出局。原因是NVDA的架构只在用brute force
拟合参数的时候有优势。而brute force注定了用NVDA训练出来的模型
只是低层次，植物性/直觉性的模型（也就是做一些专家能凭直觉进行
的判断）。不可能做出来用知识库进行推理的模型。一旦AI核心算法有
革命性突破，可能直接导致现有的NVDA架构被抛弃。而要实现创造性的
AI，必然会依靠这种突破。 |
|
i**********e
发帖数: 1145 | 22 我觉得算法固然重要，但是如果你聘请一个人完全取决于他的算法能力，那也太说不过
去了。
我觉得一个好的程序员除了需要有很好的problem solving，更重要的是他对你们公司
做的项目到底感不敢兴趣，有没有热忱。就算有幸给你聘请到，如果他天天来上班对你
们做的项目不感兴趣，那这是公司要请的人吗？
况且，一来就给面试者出DP题，我觉得作为面试题也太过了。毕竟DP题不是很多人懂，
而且要有DP的思路是需要经过不断的练习和总结才训练出来的。要知道身为面试的人会
比平时紧张，思路很容易就不清楚，然后陷入更紧张的状态。
我觉得一个好的面试题应该是有多种解法的。可以很容易想到brute force的解法，但
是也有不那么明显的方法来优化。可以先让面试者以brute force写代码（brute force
的代码不一定都很直接，也有存在很多陷阱，不容易写对的情况）。这时候面试者已经
放松一些了，才更深入地问怎么优化等等。这样我觉得能让面试者比较正常发挥自己的
水平。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
solving |
|
i**********e
发帖数: 1145 | 23 This solution works, but suffer from two problems:
1) if (j < i) continue;
can be changed to:
if (i > floor(sqrt(num))) break; // more efficient to precalculate floor
(sqrt(num)) value and store it to a variable.
2) Your total running time is O(N) (because of hs.contains(j) has a
complexity of O(sqrt(N))). However, it is no much better than a brute force.
It is only necessary for a brute force to loop from i=0 to i=sqrt(N) and j=
i to j=sqrt(N). Therefore, the brute force's method is stil... 阅读全帖 |
|
y*d
发帖数: 2226 | 24
以我10余年前玩IOI的经验
IOI的高手很难过得了GFMA的面试
IOI的题目范围非常narrow：DP+net flow+图论基础打遍天下无敌手
ICPC增加了几何题，有时有一些比较小众的图论题
不管怎么说，和这些公司面试的题目是很不一样的
我只有过一次面Facebook的时候，被问过一个80年代的ICPC的DP题
但是那个也是interviewer所有事先准备好的题目老子都答完了，还有不少时间
所以才问了这么个压箱底的题目
公司面试考的是另外一套东西：
BFS + brute force + hash table + 概率 （金融业必考）+ 若干著名算法
和IOI/ICPC/TopCoder唯一的intersection是我通常倾向于把brute force
当DP来做
同样是面非死不可那次，interviewer问我如何做regular expression匹配
我跟丫讲了如何regular expression到NFA，如何NFA到DFA
丫眼睛瞪得老大，一脸的无辜，说我只想让你写个recursive程序brute force
后来我才知道这丫是学数学出身的，没受过正规训练 |
|
b********r
发帖数: 7725 | 25 自己写的，不对大家指正。
forerunner是第一个文明种族，他们在宇宙中可以说统制了很长时间，是一种类似于人
类的生物。后来在一个星球上，他们遇到了虫族flood。这是一种寄生生物，可以将一
切生物都转化为自己的同类。forerunner于是就建造了halo，作为终级武器，可以一举
消灭宇宙中所有的flood，但同时也会毁灭其他一切生物。在建造halo的同时，他们也
造了机器人，就是那个spark，它们是为了保护halo以及为了确保halo的运行而存在的
。最终forerunner得以成功地将flood控制在一个halo中，但也基本被灭族，也并没有
开启halo毁灭宇宙。
然后就是现在，分为人类和星盟（covenant）两派。人类在不断地殖民扩张时，一天遇
到了不知名的外星生物的袭击，即星盟，导致前期开拓编队全灭。接下来是halo reach
的内容，
reach星一战，整个舰队除了秋风之墩号外全灭。每个大型战舰上都有一个中枢AI，
cortana就是秋风之墩号的AI。
星盟由很多个种族组成，主要是先知（Prophet），精英（Elite），兽人（Brutes）和
猪面怪（Grun... 阅读全帖 |
|
t******y
发帖数: 6206 | 26 从故事开始到船员死的那一段。
“I know what you want. You want a story that won’t surprise you. That will
confirm what you already know. That won’t make you see higher or further
or differently. You want a flat story. An immobile story. You want dry,
yeastless factuality.”
“Uhh…”
“You want a story without animals.”
“Yes!”
“Without tigers or orang-utans.”
“That’s right.”
“Without hyenas or zebras.”
“Without them.”
“Without meerkats or mongooses.”
“We don’t want them.”
“Without giraffes or hippopotamuses.”
“We wi... 阅读全帖 |
|
t******y
发帖数: 6206 | 27 从故事开始到船员死的那一段。
“I know what you want. You want a story that won’t surprise you. That will
confirm what you already know. That won’t make you see higher or further
or differently. You want a flat story. An immobile story. You want dry,
yeastless factuality.”
“Uhh…”
“You want a story without animals.”
“Yes!”
“Without tigers or orang-utans.”
“That’s right.”
“Without hyenas or zebras.”
“Without them.”
“Without meerkats or mongooses.”
“We don’t want them.”
“Without giraffes or hippopotamuses.”
“We wi... 阅读全帖 |
|
z*******n
发帖数: 1034 | 28 Apple Just Patched A Security Flaw In iCloud That Could've Been Used To Hack
Celebrity Accounts
James Cook
Sep. 1, 2014, 10:20 AM
Engadget reports that Apple has fixed a major bug in its Find My iPhone
software that allowed hackers to gain access to iCloud accounts. The fix
comes just hours after a hacker leaked hundreds of nude celebrity photos on
4chan in return for Bitcoin donations.
Apple's Find My iPhone login page was discovered to have been vulnerable to
so-called "brute force" ha... 阅读全帖 |
|
|
w****2
发帖数: 12072 | 30 发信人: youdu (youdu), 信区: Military
标 题: 军版各位，有没有研究过锡安长老教义？
发信站: BBS 未名空间站 (Sat Nov 26 13:15:49 2011, 美东)
对理解过去三百年很有帮助。
http://www.biblebelievers.org.au/przion1.htm#TABLE OF CONTENTS
THE PROTOCOLS DIGEST-ED
Since discourse in the Protocols is often disjointed, we have taken the
liberty of grouping quotations (from Victor Marsden's 1934 edition) in what
seems a logical order of subject. We have also tried to minimize the more
offensive ones. Contemptuous references to goyim (the unfortunate Talmudi... 阅读全帖 |
|
W**********U
发帖数: 42 | 31 这个很有用，仅以我有限的cryptography知识就可以找出很有用的应用：寻找素数。素
数在crypto中用的很多，比如public key的加密需要素数，每一个key的产生都需要寻
找素数，它所基于的理论之一主要是RSA，简单来说都是以素数为底（？是叫底吧）的
取余运算。笼统
的说，能够找到越多越大的素数意味着这套系统越安全越健壮。而搜寻大素数一直都是
一个挑战，比如这个项目一直在做的：http://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search 。这个人证明的东西给基于brute force的素数搜索的实际可行性提供了理论上的保证，既然有无穷多的素数对之间的差小于70M，也就意味着大素数的搜索不至于不可行，通俗的例子来说就是即使是brute force的搜索，我们也不需要花费遥不可及的时间来寻找下一个最大的素数。
不严谨的说（内行不要怨我把必要条件变成充分条件，通俗解释而已），如果证明了存
在差小于某个N的无穷多素数对，几乎可以模糊的认为在目前发现的最大的素数P，和P
＋N内，肯定有下一个素数。 |
|
y***u
发帖数: 7039 | 32 Death is the inevitable end for all. It is better to bring that end nearer
to those who hinder our affairs than to ourselves, to the founders of this
affair. WE EXECUTE MASONS IN SUCH WISE THAT NONE SAVE THE BROTHERHOOD CAN
EVER HAVE A SUSPICION OF IT, NOT EVEN THE VICTIMS THEMSELVES OF OUR DEATH
SENTENCE, THEY ALL DIE WHEN REQUIRED AS IF FROM A NORMAL KIND OF ILLNESS ...
.. Knowing this, even the brotherhood in its turn dare not protest. By such
methods we have plucked out of the midst of MASON... 阅读全帖 |
|
p****s
发帖数: 3184 | 33 我老最近宣扬人类社会的NP-hard理论: 人类社会的疑难杂症都至少是NP-hard的问题，
NP-hard问题的特点就是人口规模小或者复杂度低（黄仁宇所谓的中国传统那种豆腐块
整齐划一农耕社会）时并不hard，强人来点蛮力搜索brute-force efforts就能解决；
人口规模大且复杂度高的商业创新社会里，NP-hard问题有完美解的概率迅速趋于0，只
能靠公平竞争、各路人马绞尽脑汁提各种方案自然淘汰自然选择来进步。
新加坡一来弹丸之地人口规模小，二来老大强人李光耀还没死，硬是把种种NP-hard问
题先brute-force地压下来了，这么解决问题是持续不了多长时间的。 |
|
w********2
发帖数: 632 | 34 IPMI 2.0 RAKP Authentication Remote Password Hash Retrieval
More recently, Dan Farmer identified an even bigger issue with the IPMI 2.0
specification. In short, the authentication process for IPMI 2.0 mandates
that the server send a salted SHA1 or MD5 hash of the requested user's
password to the client, prior to the client authenticating. You heard that
right - the BMC will tell you the password hash for any valid user account
you request. This password hash can broken using an offline brutefor... 阅读全帖 |
|
g********2
发帖数: 6571 | 35 September 4, 2016
Analysis of FBI Reports: China more likely to have Hillary’s emails, not
Russia
By Richard Henry Lee
From an analysis of the FBI document dump (Part 1, Part 2) concerning
Hillary’s email use and her foreign travel schedule, it is apparent that
the Chinese are more likely to have gained access to Hillary’s emails than
Russia. Other countries would have had opportunities as well.
Hillary’s email server was most vulnerable from mid to late January to late
March 2009, when the emai... 阅读全帖 |
|
c**i
发帖数: 6973 | 36 From the weekly Dining sectin of Today' New York Times.
(1) Tess Taylor, Brute Force; On Small Farms, Hoof Power Returns. New York
Times, May 4, 2011 (title in print).
http://www.nytimes.com/2011/05/04/dining
/04oxen.html?scp=1&sq=brute&st=cse
Quote:
"After the Civil War, many farms switched from oxen to horses. Although
Amish and Mennonite communities continue to use horses, by World War II most
draft animals had been supplanted by machines that allowed for ever-faster
production on bigger fiel... 阅读全帖 |
|
g********d
发帖数: 203 | 37 贡献一下我的面经吧，希望能有帮助。和大家碰到的题比，我的都很简单了，但是自己
水平真的太烂，一路下来，磕磕碰碰的。
电面是去年12月的，已经忘了什么题了，好像都是和data scaling/transformation有
关的 ，挺简单的，没有要我写code。所以没什么可说的了。
Onsite 1 上个礼拜二:
第一个：ABC mm，进来就直接往white board冲。让我写一个in order binary tree iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个很应该是feedback
最差的。
第二个：白人，很friendly。一半behavior，加两道题：test anagram和字典里找所有
anagrams，没要写code，就是在纸上描述一下步骤。这个感觉最好。
第三个：白人 ，hiring manager，很down to earth。问我怎么从一个机器传... 阅读全帖 |
|
i**********e
发帖数: 1145 | 38 There are only 5 different kinds of expressions with different arrangement
of parenthesis for 4 numbers (using an example of 1,2,3,4), shown as below:
1) ((1 + 2) + (3 + 4))
2) (((1 + 2) + 3) + 4)
3) ((1 + (2 + 3)) + 4)
4) (1 + ((2 + 3) + 4))
5) (1 + (2 + (3 + 4)))
An easy way is to brute force using recursive method. Choose all possible
neighboring pairs and merge them using the operators (add, subtract...). For
example, choosing neighboring pairs of (1 and 2):
(1 + 2) + 3 + 4 --> 3 + 3 + 4
... 阅读全帖 |
|
j*******r
发帖数: 52 | 39 agree，我现在看到感觉要DP的题目都是先想brute force，然后想一下是否可以存储重
复的中间结果，把brute force转成dp。。 |
|
s*****y
发帖数: 897 | 40 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
s*****y
发帖数: 897 | 41 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include |
|
k****n
发帖数: 369 | 42 攒rp。兄弟们一起努力，共度时艰。
五轮技术加一个午饭。
第一轮主要问project。还问了怎么改进page rank算法。
这个是老本行，不过都忘差不多了。吭哧半天想起来一些，不是很爽。
最后出了一道简单coding题，就是两个dim都分别有序的
matrix，怎么查找。我先说了binary search，用master theorem估算了一下
发现是大于linear的，就说了正常的算法。然后是实现。
这个发挥一般，open questin让我准备不足。
第二轮两道比较简单的题，一个是识别一个字符串是否是一个合法的utf-8串。
因为合法utf8字符可能是变长字节的，就是1/2/3字节都有可能
先用状态机做了，看是否会跳到合法的结束，还是跳到非法状态。
写完代码经过提示才发现可以直接用一个256大小的数组判断是否合法。
弄完了之后暗骂自己，这么明显的空间换时间都没看出来。发挥太差了
第二题是设计一个数据结构存储soduku，目标是判断没有完全填好的行/列/方块
是否合法。因为有第一题地教训，我直接就往那边想了，说存三份数据，一共
才243个字节，更新的时候更新三份，方便又简洁。估计... 阅读全帖 |
|
S**I
发帖数: 15689 | 43 I think this solution is no better than brute force. :) Brute force is not bad for this problem, it is approximately linear with k.
到B
和B |
|
g*******e
发帖数: 61 | 44 昨天完成了A家的on-site, 一共四轮，最后一轮表现非常差，肯定挂掉了，继续海投吧
。之前在版上求了bless，现在攒RP，分享面经。
第一轮，美国小伙，说之前在MS，现在来A9个月了，Kindle组。目前参与A家的神秘项
目，不能讲太多项目内容，其实大家心里都知道是A的Tablet。
技术问题之前随意的聊了聊，然后问了一些很基本的CS问题。剩下20分钟，正式开始
tech question。很简单，给一本杂志，从里面剪字，看能不能找到指定的字符串。
我先给了brute force，O(n*m)，然后说如果用hash table, O(n)。然后说不让用额外
的buffer，怎么做？想了想，sort之后找substring，O(nlgn)。讨论完之后，说让我挑
其中一个写code。我说brute force简单，写的快，给了code后，挑了挑毛病，按时完
成。
第二轮，美国小伙。那个组不记得了。主要是面我OOD方面的问题。先问了我熟悉不熟
悉Java，答道还OK吧，刚想说很久不用Java了，问题直接就出来了。描述一下Java的GC
机制。说实话还真是记不太清楚了，现在主要写Pyth... 阅读全帖 |
|
h*********n
发帖数: 915 | 45 第一问谁看懂了？什么叫杂志里剪字？
发信人: glorywine (glorywine), 信区: JobHunting
标 题: Amazon On-site 最新面经
发信站: BBS 未名空间站 (Sat Sep 17 10:51:50 2011, 美东)
第一轮，给一本杂志，从里面剪字，看能不能找到指定的字符串。brute force O(n*m)
，hash table O(n)。不用额外buffer，sort后找substring，O(nlgn)。brute force写
code。
第二轮，OOD问题。描述Java的GC机制。reference counting蒙对了。设计餐馆订餐系
统。
我给了需要那些class，那些functions。指定其中一个方法，伪代码实现。
第三轮，binary tree找common ancestor。给字符串，每个字符出现的频率。从高到低
输出。
第四轮，hash table的实现。Boggle code实现，给game board，找所有valid word。 |
|
h*********n
发帖数: 915 | 46 第一问谁看懂了？什么叫杂志里剪字？
发信人: glorywine (glorywine), 信区: JobHunting
标 题: Amazon On-site 最新面经
发信站: BBS 未名空间站 (Sat Sep 17 10:51:50 2011, 美东)
第一轮，给一本杂志，从里面剪字，看能不能找到指定的字符串。brute force O(n*m)
，hash table O(n)。不用额外buffer，sort后找substring，O(nlgn)。brute force写
code。
第二轮，OOD问题。描述Java的GC机制。reference counting蒙对了。设计餐馆订餐系
统。
我给了需要那些class，那些functions。指定其中一个方法，伪代码实现。
第三轮，binary tree找common ancestor。给字符串，每个字符出现的频率。从高到低
输出。
第四轮，hash table的实现。Boggle code实现，给game board，找所有valid word。 |
|
n*******w
发帖数: 687 | 47 嗯，的确。这个dp算比较难了。
感觉google都考不到这个难度。
前面提到的brute force + cache就是dp的核心思想。dp本质上还是brute force。 |
|
S**I
发帖数: 15689 | 48 ☆─────────────────────────────────────☆
sharc (sharc) 于 (Mon Aug 22 15:15:14 2011, 美东) 提到:
刚从G家onsite归来。新鲜面经奉上。
总共5轮，4轮technical interview, 一个thesis discussion。在technical里，有编
程题，有open design。我记得的问题有：
1. 编程题：一堆字符串。找longest common prefix。
我的方法就是找最短的字符串，对它的每个字符，逐个与其他字符串对应位置比较。（
求更好方法）
2. open question: 一堆文件，size差别极大( from KB to many GB). 找出所有内
容相同的文件。
3. 编程题： 有一个observer 类，监视另一个类foo 的成员变量的值，每当那个值被
修改，就要调用 该observer.updated() 方法。需要实现 foo.registerObserver(ob)
, foo.unregisterObserver( ob )... 阅读全帖 |
|
S**I
发帖数: 15689 | 49 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 50 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
