x*******5
发帖数: 152 | 1 证明也许比较难，但是我是这样做的：
/*Description: given three arrays A, B,C, find three indices i,j, k such that
the value l=max((a-b),(b-c), (c-a)) is minimized
Input: vector a, vector b, vector c
Output: void
K.O.: sorting, merge sort variant
*/
int Array::Find_value_brute(vector a, vector b, vector c){
int n=a.size(),m=b.size(),p=c.size(),l=INT_MAX;
for(int i=0;i
for(int j=0;j
for(int k=0;k
int ta=abs(a[i]-b[j]),tb=abs(b[j]-c[k]),tc=ab... 阅读全帖 |
|
l***i
发帖数: 1309 | 2 sweep line algorithm can do O(nlogn), or you can brute force to try all O(n^
2) pairs to check intersection. |
|
l*****a
发帖数: 559 | 3 感觉中等。
对stdin，stdout不熟，写加调试用了3/4的时间。
碰上encode，decode的那一题，brute force解决了。 |
|
g*****e
发帖数: 282 | 4 普通tree的话只能brute force把两个paths都先找出来了吧？ |
|
g*****e
发帖数: 282 | 5 普通tree的话只能brute force把两个paths都先找出来了吧？ |
|
h********e
发帖数: 1972 | 6 来自主题: JobHunting版 - 问一道老题 这题硬算是dp也行。。算是贪心也行。。面试就爱考这种ad hoc的算法。一般都是有几
种套路，脑子要转的比较快就能知道那种适用了。。多看点题目想想吧。没什么好办法
。。这种题目无非就是那种最大substring sum的题目的变种。有时候一个指针就够了
，有时候要用两个。有时候还要用stack。。一般找出单调性，也就是哪些计算在brute
force的时候不必要重复，就能想到O(n)算法了。。 |
|
w***y
发帖数: 6251 | 7 来自主题: JobHunting版 - 问一道老题 多谢指点了!
我再多看看题目, 好好总结一下套路
brute |
|
o******a
发帖数: 90 | 8 这周一去onsite了一个在湾区的小游戏公司，回来后跟HR通了电话，大概意思是onsite
是过了，但是因为我的OPT七月才开始，之前他们不能让我工作（我说unpaid行不，他
们说不行，要工作就要pay），结果没有拿到offer。。。这个也怪我，之前不是很明白
，以为只要unpaid就什么时候都可以工作，现在才发现原来OPT开始的时间太晚也是个
Deal Breaker。。。想请教一下坛子里的大牛有没有遇到过这样的问题？如果要是7月
份开始工作的话，现在找工作是不是有点早了。。。？我现在主要找的都是小公司，大
公司像Google，Facebook，Microsoft之类都已经木有戏了。。。如果哪位大牛有过这
方面经验或者了解一二，欢迎指点迷津，小弟感激不尽。
虽然开始逛本版不久，但还是看了很多面经，现在也回报一下社会吧！题都比较简单，
大家也就简单看一下。
1。设计一个算法，判断五子棋谁赢了。输入是一个棋盘，黑白子已经摆好，只要判断
输出boolean就行。follow－up：用什么方式改进brute－force的递归？
2。设计题。假设一个手机游戏，有地图的那种，屏幕只能显示整个地... 阅读全帖 |
|
t********e
发帖数: 143 | 9 Brute force: since there are just max 6 steps, at each steps, try all
possible valid moves, max 10 valid moves at each step because only one
direction is valid between 2 towers. Hard part is how to optimize. |
|
j****b
发帖数: 108 | 10 说最多6步可能是因为它测试用的输入是特殊制定的。。。不是啥input都能6步搞定。
。。
有道理啊 brute force，反正只有6步，学习了！ |
|
m****i
发帖数: 650 | 11 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
这个除了 brute force还有啥好的方法 |
|
a********m
发帖数: 15480 | 12 dp计算本身和brute force没大区别，只是复杂度提高而且是可以计算出来的，只要公
式对资源够，不可能挂。LP印象中是逼近为基础的吧，约束条件也不是那么容易写和修
改的。
快不快看情况了，dp多数容易问题都是o(n)到o(n^2)。当然特别复杂的不好说了。 |
|
C***U
发帖数: 2406 | 13 brute force的算法我写过 大概3秒中能算出来 |
|
p*****2
发帖数: 21240 | 14 来自主题: JobHunting版 - 要去面试了
面试的时候我可能这么说。
1. brute force
2. binary search
3. 把横边和竖边纪录下来，去match ＋ 剪枝
4. 要hint |
|
l*********8
发帖数: 4642 | 15 来自主题: JobHunting版 - 要去面试了 brute force: O(n^4) ?
DP : O(n^2) time, O(n^2) space ? |
|
w***y
发帖数: 6251 | 16 来自主题: JobHunting版 - 要去面试了 DP是的
brute force, 我还真没想明白怎么做//汗 |
|
l*********8
发帖数: 4642 | 17 来自主题: JobHunting版 - 要去面试了 brute force: Time O(n^4), Space O(1)
for (int x=0; x < N-1; x++)
for (int y=0; y < N-1; y++)
for (int width=1; width < N-1-max(x,y) ; width++)
{
for (int i=0; i
{
check the value of a[x+i][y], a[x][y+i], a[x+width-1][y+i],
a[x+i, y+width-1];
}
} |
|
f**********2
发帖数: 2401 | 18 如果subarray是指的位置连续的integer，正解。其实就是遍历所有可能，brute force？ |
|
|
p*****2
发帖数: 21240 | 20
brute force感觉要O(n^3)
这题如果能达到n^2应该就是最佳答案了吧？ |
|
l***i
发帖数: 1309 | 21 折腾了几个月终于算结束了intern申请了。本文target audience是有兴趣做software
engineer，俗称码工的同学，大牛和其他方向人士请绕行。同时感谢job板各位大牛分
享经验。
总结：就像之前有个F和G一起拿下的同学说的，经验就是做题。
因为有同学在MSFT和AMZN，大概去年年底就有recruiter联系了。不过那时候还没跟老
板说好，就没回。后来到了2月终于老板点头了，然后开始撒网海投。
Twitter是最快给消息的，大概当天就说要interview了。可能这个来的太容易也太快了
，一面就挂了。虽然不服气不过确实写的太烂了。
后来等来了F，G，A的面世，M不知道为什么就没消息了。其他投了没消息的还有
salesforce，dropbox，quora，当然后面两个没理我也好理解。另外面挂了一个小公司
，quixey。最后拿到了G，准备去mountain view了。各位准备或者即将去G的同学，希
望有机会在mountain view见见。
面世题目板上都有，另外我碰到的题都不难，那些什么O(1)空间O(n)时间的题一个都没
有，都是一看就知道算法，然后就是怎... 阅读全帖 |
|
s*********5
发帖数: 514 | 22 如果只有4个数字的话，一共24个顺序X64种变化，brute force OK了吧 |
|
s*********5
发帖数: 514 | 23 如果只有4个数字的话，一共24个顺序X64种变化，brute force OK了吧 |
|
s*********5
发帖数: 514 | 24 如果只有4个数字的话，一共24个顺序X64种变化，brute force OK了吧 |
|
|
|
p*****2
发帖数: 21240 | 27 图有没有回路？我第一想法就是DFS做brute force。 |
|
i**********e
发帖数: 1145 | 28 刚把这题加进 OJ 里了，解法还挺多的。
brute force 的 O(N^2) 应该是过不了 large tests 的。
"Largest Rectangle in Histogram"
Given n non-negative integers representing the histogram's bar height where
the width of each bar is 1, find the area of largest rectangle in the
histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2
,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10. |
|
p*****2
发帖数: 21240 | 29 这题想了想还没太好思路 面是肯定挂
刚把这题加进 OJ 里了，解法还挺多的。brute force 的 O(N^2) 应该是过不了 large
tests 的。"Largest Rectangle in Hist........
★ Sent from iPhone App: iReader Mitbbs Lite 7.52 |
|
|
s*******f
发帖数: 1114 | 31 1. get index of s1 in s2, for each char in s1, mark position is s2.
here "tiger" in "itreg" is [1, 0, 4, 3, 2]
stops和posts is: 2 3 1 0 4
//For duplication, always pick nearer one first. I use "set" to deal with
duplication in code.
At first I use brute force here with O(n square). But when using
hash_map >, it goes to O(n), or queue hm[256]
.no need to use "set" for duplication.
2. rule for eat: you can eat neighbour if your high or low bound
can "touch" neighbour.
here [1,... 阅读全帖 |
|
G******i
发帖数: 5226 | 32 ☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Thu Jul 14 15:07:18 2011, 美东) 提到:
之前面的 Google，今天 recruiter 打来说我的 feedback 有两个非常好，但是也有一
到两个 poor feedback。 recruiter 说，下个星期二会进行 feedback review，应该
会有很多讨论（应该是指我在 borderline）。他说这时候最能帮到我的就是一些
references，google 里面的人的 references 如果足够 strong 的话，可以扭转局势。
不知道有没有已在 Google 工作的 xdjm 愿意帮忙 refer 一把。相信这里很多人都知
道我做的网站 ihas1337code，除了自己不断学习和总结面试题之外，也听说帮到了很
多人甚至拿到 offer，这里我替他们感到欣慰和开心。
如果你在 Google 工作的话，而且不怀疑我的编程能力，然后又愿意帮忙 refer，请站
内我。小弟在此无限感激！
... 阅读全帖 |
|
|
l***i
发帖数: 1309 | 34 brute force with 8! is the solution. |
|
|
h****e
发帖数: 928 | 36 没有了，只是有空的时候看一些趣味数学之类的。
做这样的题目brute-force都算不出的时候，只好放狗搜看
这种等式有什么特性。
做出ProjectEuler的题目以后可以看看论坛上的其他人的
解答，有的甚至是用汇编，或者J, K之类的冷门语言写的。
记得有一小孩才14岁。 |
|
w****x
发帖数: 233 | 37 一直在本版潜水，收获良多。 面试的题目基本都是本版或几本面试书里的。
去之前有看Programming Pearls, career cup 150, Programming Interview Exposed.
还有版上零零星星的题，包括MITBBS 面试题整理（这个没全看).
说几个也许有用也许没用的经验。
1。至少G家推迟面试跟你拿到offer好像没什么关系。我店面，onsite各推了一个多月。
2。有的面试人一上来就直接要你写题。这种情况可以先不考虑最优解（除非你知道最
优解）。 先写个brute force的，再优化。这样不会太紧张。即使后面的写不出来，你
也答对了一半。
3。大部分面试人会问你一个问题。我都是先回答怎么做，被要求写code的时候再开始
写。有的时候要先陈清一下问题。比如记录最近1分钟内页面被访问的次数。
我就先问他是不是要exactly 1分钟内, 他就很高兴地说不用。他要说是我还真不知道
怎么做。
4。设计题，尽量往design pattern 上面靠。listener/Observer pattern, Model-
View-Controller (现... 阅读全帖 |
|
Z*****Z
发帖数: 723 | 38 挺有意思的小题儿。
假设主串长度为M，模式串长度为N，一般N << M.
brute force的算法就是从主串的每一位开始找，worst case O（M2）
给模式串里面的每个位置用一个指针记录上次搜索到的位置，很容易就改进成O（MN）
的。
还没想到O（M+N）的算法。期待牛人解惑。。。 |
|
s******0
发帖数: 19 | 39 一个数组a1,a2,a3...an,b1,b2,b3...bn, 怎么in place地转化成
a1,b1,a2,b2,a3,b3...an,bn
除了O(n2)的brute force觉得想不出其他解法:(
谢谢！ |
|
a*******8
发帖数: 110 | 40 O(k^2)的brute force算法附上：
String getCommon(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int maxLength = Math.min(m, n);
while (maxLength > 0) {
if (s1.substring(m - maxLength).compareTo(s2.substring(0,
maxLength)) == 0) {
return s1.substring(m - maxLength);
}
--maxLength;
}
return "";
} |
|
a*******8
发帖数: 110 | 41 面试时的String match题，如果要求比brute force更好的解的话，都可以考虑这个。
看了半天Wiki，才弄明白。。。
//KMP algorithm
//Reference WIKI: //http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
String getCommon(String s1, String s2) {
int maxLength = Math.min(s1.length(), s2.length());
int[] table = buildFailureTable(s2, maxLength);
int m = s1.length() - maxLength;
int i = 0;
while (m + i < s1.length()) {
if (s1.charAt... 阅读全帖 |
|
h****e
发帖数: 928 | 42 不是大牛。我做PE也只是兴趣而已，并且试着用不同的编程语言来
解题，并不求对面试有什么用。它上面的题目的确是你只要给出正确
的答案就可以了，没有速度的要求。当然到后面题目难的话brute-force
就解不出来了，那时你就得找找看看相关的数学背景知识。别人的解答
只有你做出来以后才能够看到，有的人用的是很冷门的编程语言，代码
非常短，很开眼界的。:) |
|
p*****2
发帖数: 21240 | 43 最简单的解法就是brute force，如果b不大的话。
要不就把所有的排列得出来，后边再加0。 |
|
g****y
发帖数: 240 | 44 18.11 不是DP。
pre_processing的过程是DP，但是主程序不是DP，就是一般的brute force。
纳。 |
|
t*****e
发帖数: 53 | 45 Given n sets of choices: (1,2,3), (2,3,4), (4,5) You pick one element from
each set of choices. Generate all possible picking.
I wonder if there is trick to this problem. It seems brute force solution
can solve it. any optimized solutions? |
|
g**e
发帖数: 6127 | 46 今天直接被bar raiser批了，谁告诉你我们一定要optimal solution? 背包问题只要能
给brute force就可以了，getMedian只要O(n)就可以了。 |
|
z****o
发帖数: 78 | 47
正好反了，每次都是先横后竖。 考虑两种就brute force了。 |
|
d**e
发帖数: 6098 | 48 说一下我们组一个Sr面试的侧重面
1. if he/she can code (brute force is highly acceptable. i assume he want
bug free code.)
2. communication skill
3. when 1) is okay, discuss and analyze to find out an optimal solution |
|
l*****a
发帖数: 559 | 49 The short url has to be unique, so the short url can be used as key. The
long url will be used as value.
The reason to use short url as key but not auto increment id is to prevent
ppl from getting the long url by brute force.
How to generate unique short url can be the follow up question. |
|
p*****2
发帖数: 21240 | 50 来自主题: JobHunting版 - 请问G一题 按照板上大牛的理论， brute force搞出来就行了吧？
N个数里边选N/2个，使得和最接近sum/2。复杂度
N*(N-1)*(N-2)*(N/2+1) |
|
