j**l
发帖数: 2911 | 1 下午接到recruiter的电话，说feedbacks pretty good, however, hiring committee
觉得不够great enough, 没有达到他们的hiring bar, 要至少半年后才可以重新申请．
因为NDA, 具体的题目不能透露．
面了5个人，没有我准备的难，其中一个NPC的题目我用Greedy和DP想了很久未果，结果
他竟然提示我就用Brute Force做，无语。另外考到的是二分查找的变体，树遍历，简
单字符串题，还有BST的操作，CLRS的重点章节就够用了。甚至PIE书看熟也就有70%的
把握了。Large Scale也很简单，基本思想点到就可以了。另外关于简历，做过的
projects和behavior的也问的比较多
第一轮是个小印，问了二分查找的变体，我的idea完全正确，但在具体写代码的时候在
一个小细节耗费了不少时间，导致他没时间给第二题了。他用一个test case 发现了一
个bug, 然后我说了一个改正方案，结果他说不好，给了个他的方案。我在所有面试结
束后发现他的方案和我的原始方案一样也不对，又在大厅里和他讨论了一下，他觉 |
|
C*Y
发帖数: 736 | 2 I was asked this question in a well-known small company yesterday. We can
prove that, the largest palindrome that are the product of two 2-
digit numbers is 9009 (because 9009 = 99 * 91). Now the question is, how to
find the largest palindrome number that are the product of two 3-digit
numbers?
I just googled this question. All I can found is a brute force algorithm, by
exhaustively testing every number that can be made from the product of two
3-digit
numbers to see if it is a palindrome and rec |
|
g****n
发帖数: 431 | 3 1. 按你的方法，排序是不需要的
2. 你的方法本质上只是brute遍历的一种实现，时间复杂度仍然是(2^n)，没有任何改进
each
1)=S(m) |
|
g**e
发帖数: 6127 | 4 分解质因数的时间说不定比brute force还长 |
|
d**e
发帖数: 6098 | 5 为什么要用笨法子呢？
brute force应该没问题啊。我没具体验证，我想大概应该是这样，
从string_1的第一个char开始循环，比如index是i，和string_2的
第一个char开始比较，index是j，遇到相同，侧两个string的index
都增一，否则看是否得到最长的的substring，然后string_1的index
复位回i，j侧增一，直到j=length(string_2)，然后到下一热循环(i+1)
下面为伪码
int len1 = length(string_1)
int len2 = length(string_2)
int max_len = 0
int left_idx = -1
int right_idx = -1
for i = 0 to len1 - 1
loop
k = i
tmp_max_len = 0
for(j = 0; j < len2 - 1; )
if string_1[k] == string_2[j]
then
k++
j++
|
|
l******4
发帖数: 729 | 6 greedy, hill climbing 最环情况是brute force，但实际上可能最快 |
|
h**6
发帖数: 4160 | 7 既然输入都在1~10之间，用brute force就可以解决了，一共2^10 = 1024种情况 |
|
g****n
发帖数: 431 | 8 这个夹挤好像有问题吧：先说用这个办法解决2个数sum的情况。假设排好序的数组是：
[1,10,11,12,13,14,15,...,22,23,25], sum是25。唯一解是10+15。如果用2个指针，
第一个
指向1，第二个遍历到25时发现sum超过25，然后第一个指向10，这时第二个指针不论从
哪个方向开始查
找，都需要O(n)时间。这个办法总的时间是O(n^2)，属于brute force。 |
|
s****n
发帖数: 1237 | 9 这个问题我觉得他也没有讲清楚，所以我以我的理解来阐述题目。
每个seq里面的字符应该是可以重复的
另外第一步你考虑整个str,只有C(N,N)=1种。
但是如果你说在(0,x)里面的时候，就有C(N,x)种组合，这个复杂度和我brute force有
点象 |
|
|
w*****3
发帖数: 101 | 11 这题不大可能有线形解,
brute force ,O（n2）
0看成-1 第一遍扫过,序列长度减去最后一个值的绝对值就是理论上存在的最长序列L,
然后用相隔为L-1的两个指针p1,p2同时遍历,直到*p2 = 0 或者*p1 == *p2
如果没有就缩小间距直到2
最坏情况序列如下：
1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1
1 0 1 2 3 2 3 4 5 4 5 6 7 6
n 序列， 多出n/2 ，从间隔n/2扫描到间隔为2 O（n2） |
|
e******a
发帖数: 176 | 12 我感觉这个不对啊。A和B里每一个element 都要有一个指针，这个指针指向相对于该
element自身来
说，在对面数组里的当前位置。所以这个brute force 的复杂度是1+2+3+...+k = O(k
^2). 如
果用min heap, 是 log1+log2+...+logk =k(logk) |
|
A*********r
发帖数: 564 | 13 为了这道题，专门复习了一下dp,并且把两个帖子的回复都仔细研读了一遍，现在来总
结一下吧。
原题：给定M个数字的从1到N的整数数组，找出一个大小为K的子集，这个子集
的半径定义为最小的pair Distance，让找出最大半径的这样的子集。
首先说如果是brute force, 要从M个数中选出K个数，然后计算每个K子集的半径，找到
最大的那个，复杂度为 C(M,K), 算是exponential的了。。
然后很显然这是个optimization problem (maximize the radius),所以可以考虑用DP.
用DP的最重要的就是找到如何从已知的optimal subproblem, 推导出当前的optimal
state. 对于这个题，就是如何从已知的optimal (K-1)元素的子集的， 得到含有K元素
的optimal的子集。
在回复很多人都知道这一点，如果没有特殊的约束条件，这两个子集可以完全不一样，
也构不成DP中的subproblem了。所以我们要先sort输入数组，这样保证了每一个pair
distance involving i and previo |
|
p********7
发帖数: 549 | 14 2个数,先查 sum - a[i] 是否在hashtable里面,如果在就返回true,如果不在就插入a[i
] O(N)
3个数,有点不同,因为3个数有可能是一样的,这样查起来会有问题,所以先排序,处理了
特殊的有2个数重复,或者三个数重复的情况,再查 sum - a[i] - a[j]是不是在,复杂读
是O(N^2)
k个数就更复杂了,复杂度接近brute force 复杂度O(N^(k-1)) |
|
i**********e
发帖数: 1145 | 15 二叉树是面试里常见的问题种类，大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌握好。
Determine if a Binary Tree is a Binary Search Tree
这题很常见，microsoft,amazon, google的面试都有人被问过。这题也是二叉树的好题
，必须得对BST的定义搞清楚。有一个常见的陷阱，就是把current node的value和left
node, right node比较；这是不正确的解法。也有一个很容易想到的brute force解法
，但是每个node会被遍历很多次。正确的优解是 （O(N)解，N=number of nodes)有两
种，面试者必须对这题熟悉。
Binary Search Tree In-Order Traversal Iterative Solution
这题应该是 google 电面经常问的问题吧。我那时候就是google电面没答好这问题，所
以就fail了，超级后悔啊。强烈推荐的问题。In-Order traversal能很轻松地用递 |
|
A*********r
发帖数: 564 | 16 都是DP.
第一个很简单，对每一个高度，分别记录能够到达的最左和最右的坐标，最后最大的那个就是。。
Let L(i)=R(i)=i at first, then
更新 L(i)=L(i-1) while H[i]<=H[j] j=i-1..0
更新 R(i)=R(i+1) while H[i]<=H[j] j=i+1..n
最后max { H[i]*(R(i)-L(i)) } 就是最大的矩形。这个算法不是最优的。。
第二个比较复杂，brute force 估计要用O(n^3), 最好貌似可以做到O(n^2).
参见 http://www.drdobbs.com/184410529
heights
find |
|
h**k
发帖数: 3368 | 17 第一题的算法不对。按你这个思路，对于H[i]，你必须比较所有的H[j]和H[i]，来找到
高度为H[i]的矩形的左右边界。这样复杂度是O(n^2)。正确算法是用stack。
第二题的brute force是O(n^6)，最后利用第一题的思路，可以到O(n^2)。 |
|
p********7
发帖数: 549 | 18 求2维矩阵里面最大和的子矩阵的和。
-1 -2 3
3 2 -2
1 1 -1
最大和的是 7
没想到除了brute force还有什么办法 |
|
h***o
发帖数: 1494 | 19 Input:
1. an array of characters
2. a bunch of scores, for each
a. start (start position in the array)
b. end (end position in the array)
c. score (score is not related to the content of the substring or
length of the substring)
Scores could be overlapped.
Output:
all scores (there is no overlap on them) that have the maximum sum.
For example
Input:
"abcdedfhijk"
start: 1 end: 3 score: 5
start: 0 end: 10 score: 8
start: 5 end:6 score 4
Output:
start: 1 end: 3 score: 5
start: 5 end:6 sco... 阅读全帖 |
|
i**********e
发帖数: 1145 | 20 Are you going to interview candidates soon?
StrStr implementation is much easier to solve compared to wildcard matching.
Although the wildcard matching is a very tricky question, Facebook had asked
this question before:
http://www.mitbbs.com/article_t/JobHunting/31575425.html
If you have taken part in Google Codejam before, you will know how fast
those crazy smart people solve problems within minutes. To solve this
problem using nothing but paper and pencil + without bugs in 20 minutes is
very v... 阅读全帖 |
|
j*****g
发帖数: 223 | 21 写的好，是一格比较搞的题目。
But so far I haven't seen your brute force solution O(N*M) yet...Perhaps I
missed it?
J |
|
j*****g
发帖数: 223 | 22 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
j*****g
发帖数: 223 | 23 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
z****n
发帖数: 1379 | 24 刚刚从了google的offer，base 116k，bonus 15%, stock unit 160, relocation
7500。由于签了保密协议，具体的面试题就不详细透漏了，都是很基本的算法题，
先说算法，再coding，没有长老级别的难题，也没问什么其他东西，就是算法。听
说最近google招人很多，大家好好准备算法，现在进google真的没有以前想象的那
么难了。
开始找工作以来就在这个版上取经，收益良多，所以也想分享一下自己找工作的经
验，回馈版面。
我是fresh cs phd，学校排名50左右，找工作开始就将目标定在硅谷，因为喜欢那
里的天气和中餐，初期也会投些其他地方的大公司，积累积累面试经验。一共拿到
了A，O，BB，G，M五家大公司的onsite，也许是被人看出来了只想去硅谷，A和BB的
onsite都挂了 ^_^ 拿到了O和G的，M由于时间太晚决定从了G就没去。另外还有些其
他中小公司的电面，感觉中小公司的电面太注重实际经验和语言细节，对我这种fr
esh学生来说，反而不如大公司的电面好通过。
下面说些我复习准备时的经验，版面上各种复习资料经验已经非常多，... 阅读全帖 |
|
c***2
发帖数: 838 | 25 Using brute-force
========================
Input Array:
-45 -85 -1 -37 -21 -11 -5 52 -57 46
comparisons=21
longest_inc_sub_bf:
length=5
startIdx=3
Sub-array:
-37 -21 -11 -5 52
Input Array:
-85 -57 -45 -37 -21 -11 -5 -1 46 52
comparisons=10
longest_inc_sub_bf:
length=10
startIdx=0
Sub-array:
-85 -57 -45 -37 -21 -11 -5 -1 46 52
Input Array:
52 46 -1 -5 -11 -21 -37 -45 -57 -85
comparisons=10
longest_inc_sub_bf:
length=1
startIdx=0
Sub-array:
52 |
|
c***2
发帖数: 838 | 26 /* longest contiguous increasing sub-array : brute-force */
int longest_inc_sub_bf(int array[], int size, int *start)
{
int max,len,i;
int from,max_from;
int comparisons=0;
max=len=1;
max_from=from=0;
i=0;
while(1){
i=from;
while((i=array[i])){
i++;
len++;
comparisons++;
}
comparisons++;
if(len>max) {
max_from=from;
max=len;
... 阅读全帖 |
|
n******n
发帖数: 49 | 27 发Yahoo MS Amazon面经
我碰到的 也都是一些还算中规中矩的题 所以 也算是来给各位找工作的打打气！
Yahoo 电面 印度人
1.电话键盘上1-》abc 2->cde... 现在来一堆数，未知长度，比如123456..... 请输出
序列可能对应的所有字符串
比如 123 输出acf, acg, ach, bcf...
2.检测链表是否有环
3.sql语句
employee(id(primary key),name)
employee_bonus(id(primary key), bonus) （现在觉得这题 似乎有点问题，因为他和
我说 id可以对应多个bonus, 那这还算是primary key吗。。。）
请写sql 输出name和这个人bonus总和。
MS on campus interview - first round
1. 简历问题
2. 给一个字符串检测是否是valid ip address, 这题他似乎是想看看我的思路，我说
regular express, 他说要code, 我就写了一些，解释了一下。总之，这题真要追究起
来，细节颇多，但因为我们每个... 阅读全帖 |
|
n******n
发帖数: 49 | 28 发Yahoo MS Amazon面经
我碰到的 也都是一些还算中规中矩的题 所以 也算是来给各位找工作的打打气！
Yahoo 电面 印度人
1.电话键盘上1-》abc 2->cde... 现在来一堆数，未知长度，比如123456..... 请输出
序列可能对应的所有字符串
比如 123 输出acf, acg, ach, bcf...
2.检测链表是否有环
3.sql语句
employee(id(primary key),name)
employee_bonus(id(primary key), bonus) （现在觉得这题 似乎有点问题，因为他和
我说 id可以对应多个bonus, 那这还算是primary key吗。。。）
请写sql 输出name和这个人bonus总和。
MS on campus interview - first round
1. 简历问题
2. 给一个字符串检测是否是valid ip address, 这题他似乎是想看看我的思路，我说
regular express, 他说要code, 我就写了一些，解释了一下。总之，这题真要追究起
来，细节颇多，但因为我们每个... 阅读全帖 |
|
g*****e
发帖数: 282 | 29 都看了一遍，其实只是改进了的brute search。文本一大复杂度就不得了了。有更好的
方法么？ |
|
l********y
发帖数: 1327 | 30 有一个int array，10000个元素，里面放有数字0到100，但是缺少某一个数字，问怎么
样最优求出这个数字。就比如里面有0，1，2，。。。99，100各多少次，但是缺少3这
样的情况。
我只知道brute force，但是不知道如何找出最优化解。 |
|
k*p
发帖数: 1526 | 31 我觉得brute force挺好，至少scan一遍，不如scan的时候记下个数 |
|
s*****n
发帖数: 5488 | 32 你的brute force是啥。用个bitmap.如果有就bit[1] = 1,otherwise, bit[i] = 0
这个几乎最快了吧。 |
|
l********y
发帖数: 1327 | 33 brute force 解法:
int a[10000]已知
int i;
int j;
for(i = 0;i < 100;i++){
for(j = 0;j < 10000;j++){
if(a[j] == i)break;
}
if(j == 10000){
cout << "i is the missing number " << i << endl;
break;
}
}
O(n^2)复杂度，被提示还有更优化解，大概是sort以后binary之类，但是不明白具体，郁闷啊 |
|
x**y
发帖数: 70 | 34 brute force 是扫描每一行,遍历整个 matrix, O(N^2). interviewer 说有更好的. 你
的好像不对, 第一, 扫描多次, 第二, 应该和SUM 无关. |
|
c***2
发帖数: 838 | 35 This is O(n^2), (brute-force)
I am asking for O(n)
product=a[0]*...a[n-1]
b[i]=product/a[i]
[i |
|
b*****n
发帖数: 143 | 36 Problems 8.10 on page 85:
Find a subarray whose sum is closest to a
given value t.
I can only think of a brute-force method:
fist build the cumulation array, then scan
from first element to the last element. Each
scan is O(n). So the solution is O(n^2). I
wonder whether there is a better solution.
Thanks. |
|
J******8
发帖数: 132 | 37 The question is not hard. But I missed two key points.
The details below.
==========================================================
/*
example
char *words[] = {"foo", "bar", "baz", NULL};
setup(words);
1) First step:
isMember("foo") -> true
isMember("garply") -> false
2) Second step:
isMember("f.o") -> true
isMember("..") -> false
*/
#include
#include
#include
char *words[] = {"foo", "bar", "baz", "caz","cat",NULL};
int num=0;
void print_words(void)
{
int i=0... 阅读全帖 |
|
|
g*****n
发帖数: 21 | 39 There's a book and each sentence consists of several words. How to find the
minimal set of words which can used by the reader to understand half of
total number of the sentences. Each sentence is readable if the reader know
all the words.
I can only think of brute force solution -- do word counting on every
possible collection of half number of sentences and choose the minimal. But
that's exponential C(n,n/2).
Any better solution?
Thanks |
|
b*****e
发帖数: 474 | 40 A* works (of course only for very small size problems):
Each word is a 0, 1 variable x_i.
Solution is (x_0, x_1, .... x_n)
start state: (0, 0, 0....)
step: change one 0 to 1. cost:1
heuristic: median value of all #of unknown words for each sentence.
it should be 0 when half of sentences are totally recognized.
If number of sentences is small (say 20), then I think the brute force
method is not bad, as it requires not much space at all. |
|
l*****a
发帖数: 14598 | 41 你说的已经是最优了
还有：
1)brute force: O(n^3)
2)the way to find combination of 3 items ,then judge the sum.
but we can sort at first ,then 效率会高些
但是也是O(n^3)
sea |
|
i**********e
发帖数: 1145 | 42 我也尝试解一解这题，不知道是不是跟各位大侠的解法一样，欢迎讨论。
假设定义：
4A 为 连敲 4 次 A，
2D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V,将之前的 A X 2，
3D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V,将之前的 A X 3.
f(N) 为最优解.
n <= 7, 那么 f(n) = n.
n = 8, f(n) = 3A3D = 9.
n = 9, f(n) = 3A4D = 12.
n = 10, f(n) = 4A4D = 16.
n = 11, f(n) = 4A5D = 20.
n = 12, f(n) = 5A5D = 25.
n = 13, f(n) = 5A6D = 30.
n = 14, f(n) = 6A6D = 36.
思路很明显，就是要求 a*b = n-2, 并且 a 和 b 相乘为最大值。
注意了，
n = 15, f(n) = 6A7D = 42？
这是错的，因为当 n = 15,
f(n) = 3A4D4D = 48.
n = 16, f(n) = 4A4D4D = ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 43 It's trivial to do a brute force search.
There are also mathematical properties that you can take advantage on.
However, assume you don't know these properties, how to write a program to
do this efficiently?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
of
1
only |
|
B********n
发帖数: 384 | 44 觉得有道理，感觉分析清楚了程序很简单。另外输入很小，用brute force也没什么问
题。M <= 9, 9! = 362880，可以作为验证。
bool StringCompare (string s1, string s2)
{
return ( (s1+s2) < (s2+s1) );
}
void PrintLeastOrder(vector words)
{
sort(words.begin(), words.end(), StringCompare);
for (int i = 0; i < words.size(); i++)
cout << words[i].c_str();
cout << "\n";
}
Output
cupfacebookforhackerstudentsstudious
duzklvrawqrc
dyroiymybeaxeyubxzdr
bwjibwjibwjijp
dcyihopjijliuiuy
This |
|
P********l
发帖数: 452 | 45 No. In java, the hashset does not preserve the original input order. There
is another set called linkedhashset has this property.
It is brute force but the complexity is o(sqrt(n)). Because it just scan one
through 1 to sqrt(n).
then |
|
h**********d
发帖数: 4313 | 46 好吧，这可以算brute force的了，谢谢 |
|
i**********e
发帖数: 1145 | 47 其实那题 merge k sorted arrays 是再也经典不过的题。
还有，其实你选择用 brute force 来写反而更难，很多细节要处理，要一次写对比较
麻烦。
相反的，用 heap 来做就反而容易多了，而且解法更优。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
iterator class，想了半天没有想出最好的解法，脑子有点晕，也没套到什么有用的
hint。后来觉得时间不多了，我就说我就写个蠢一点吧，总比什么都没写好，她说顺便
吧。我最后把整个tree给扒下来放到了arraylist里，真的很dump的解法。。。。这个
很应该是feedback |
|
g********d
发帖数: 203 | 48 我觉得这个heap的node必须也记录来自哪个array吧，不然要去重新查的话，不是变成
brute force了嘛。 |
|
g*********s
发帖数: 1782 | 49 brute-force?
blocks
R
3} |
|
D*********y
发帖数: 876 | 50 说个brute force的解法，可以直接用原来的算法
输出结果放在一个二维array里，
然后把重复的去掉
简单来说就是用两个index
一个指向当前读到的string
一个指向unique string的结尾
每读到一个unique string，就把它加到之前的unique string结尾去
坐等高人给出复杂度更小的解法
估计就得改动原来的算法了 |
|
