m**q
发帖数: 189 | 1 感觉第一个是trie + backtracking或者DP啊？
直接brute force貌似是指数级的吧，hash table怎么做？ |
|
S**I
发帖数: 15689 | 2 子数组里的元素连续的话，有n个元素的数组只有n(n+1)/2个子数组，brute force也是
polynomial的。 |
|
g*****i
发帖数: 2162 | 3 书里给了两个答案吧,第二个是你说的256的数组,第一个就类似brute force比较,没用
额外空间.
extra |
|
|
D*******e
发帖数: 151 | 5 I only know brute force, O(N^3)
If we can sort it, it can be solved in O(N^2), which is optimal |
|
i**d
发帖数: 357 | 6 you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
只能想到brute force的方法。有什么好的办法来做么？
谢谢了。 |
|
i**d
发帖数: 357 | 7 you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
只能想到brute force的方法。有什么好的办法来做么？
谢谢了。 |
|
g*****i
发帖数: 2162 | 8 可以去火鸡办的google group问这个问题啊.
复杂度测试的时候只要在规定时间里跑完所有测试就可以了,所以brute force是常用的.
时间和分数是直接相关的
程序只有fail了任一一个测试,比赛的时候就是0分. |
|
S**I
发帖数: 15689 | 9 ☆─────────────────────────────────────☆
fengzhongdi (fzd) 于 (Fri May 27 14:30:18 2011, 美东) 提到:
A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bian... 阅读全帖 |
|
w****x
发帖数: 2483 | 10 说DFS的无非就是preprocessing把字典做成图
如果字典的单词是trie tree组织, 要找可以列出所有组合, 一个个在trie中找, 代价
比较大, 可以做为第一个brute force的解答
还有一种方法是做签名
aabcda => a3b1c1d1 <=abacda
签名就是hash, 比如我给出a1b2c3, 在o(1)时间就可以找出所有同样签名的单词
对于一个给定单词, 比如damp的签名是a1b0c0d1...m1..p1...
列举所有签名 |
|
|
f********e
发帖数: 166 | 12 1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 2 3 4
5 6 7
9
左上部分建max heap, 9 is the max
8
10 11 12
13 14 15 16
右下部分建min heap,8 is the min
median = 8/9
但这个方法挺奇怪的
时间复杂度O(logN),heapify
空间复杂度O(N^2)
brute force solution:
time complexity: O(N^2),遍历矩阵
期待大牛给个更好的 |
|
l******c
发帖数: 2555 | 13 the question is to find the shortest distance from v to the original node in
the MST.
brute force, calculate the distance, sort, Vlog(V) |
|
K*****k
发帖数: 430 | 14 大公司的码工面试题范围广阔，千变万化，再怎么准备都会有盲点。面试官真要考倒一个人，不要太简单。
感觉就象要在16番棋挑战卡斯帕罗夫一样难，要实力到了才行，偶然赢他一局，却输他N局不行，不如求稳，13平2胜足以拿到offer。现在还是信心不够，生怕哪一轮面试开局不利，全局皆输。
还恳请给些复习的建议。比如比KMP差的常规Brute Force法求子串是否也要苦练反复纸上写？就怕不练，到时白板写这个都可能写不好，所谓眼高手低。 |
|
K*****k
发帖数: 430 | 15 是在我完成经典算法后他才说要是全部是负数怎么办...
不过还是经验不足.如果事先没有看过，现场又不能灵光一闪,首先能想到的肯定还是比
较笨的方法,包括Brute-Force的方法。 |
|
n*******w
发帖数: 687 | 16 这个感觉比较好点。
乍看是O(m!)，m是input string的长度。
不过查dictionary剪枝了，会很快。
存个O(N^2)的二位数组再dfs有点占空间。算是brute force了。
N是dictionary中words数量。
不白板code可以考虑图，不然不好写。 |
|
n*******w
发帖数: 687 | 17 这个感觉比较好点。
乍看是O(m!)，m是input string的长度。
不过查dictionary剪枝了，会很快。
存个O(N^2)的二位数组再dfs有点占空间。算是brute force了。
N是dictionary中words数量。
不白板code可以考虑图，不然不好写。 |
|
n*******w
发帖数: 687 | 18 这个是正确的方向。一时找不出最优解，先brute force都行。你多点时间考虑或者实
现过程中能找到思路。
这个题应该不是语言的问题。用c或java基本也没差太多。
但是感觉你有些不清晰的地方。list用array还是linkedlist；合并的时候只要比较end
就行了，（start是先排好序的）这个逻辑要清晰。
interval的问题算是面试中比较繁琐的问题。 |
|
n*******w
发帖数: 687 | 19 这个是正确的方向。一时找不出最优解，先brute force都行。你多点时间考虑或者实
现过程中能找到思路。
这个题应该不是语言的问题。用c或java基本也没差太多。
但是感觉你有些不清晰的地方。list用array还是linkedlist；合并的时候只要比较end
就行了，（start是先排好序的）这个逻辑要清晰。
interval的问题算是面试中比较繁琐的问题。 |
|
s******n
发帖数: 3946 | 20 第三题，先得问明白，每个人可以有2个parents吧，血缘关系多少代以内，不是很简单
。brute force之外还有后什么好办法？ |
|
|
c********1
发帖数: 52 | 22 这个题我也碰到过
估计最好的方法就是brute force加
cache一下吧
n^2次调用blackbox是少不了的吧 |
|
n*******w
发帖数: 687 | 23 这么比肯定是前者，好得多。
brute force + cache就是dp。 |
|
p*****2
发帖数: 21240 | 24 第二题除了brute force以外还有啥好办法吗？ |
|
|
|
c****m
发帖数: 179 | 27 I also thinks your code is the brute-force way with recursion.
If you want to do DP for this problem, you should have another hashmap for
memorisation to save the computation. |
|
l*********y
发帖数: 142 | 28 如果两个tree 的size 是 m 和 n， brute force 的话是 O（mn）
有O（m+n）的吗？ |
|
k***t
发帖数: 276 | 29 interviewstreet上的。brute-force很straightforward。
有没有妙招降复杂度？
===================================================
Vertical Sticks
Given array of integers Y=y1,...,yn, we have n line segments such that
endpoints of segment i are (i, 0) and (i, yi). Imagine that from the top of
each segment a horizontal ray is shot to the left, and this ray stops when
it touches another segment or it hits the y-axis. We construct an array of n
integers, v1, ..., vn, where vi is equal to length of ray shot from the top... 阅读全帖 |
|
p*****2
发帖数: 21240 | 30
我不懂KMP，也没用KMP。看了下wiki上的KMP，试了试，没什么感觉。最后就是用brute
force。 |
|
|
o**********t
发帖数: 406 | 32 没错，复杂与入门，是个相对概念。
举例说，现在都觉得 max sum subsequence 是个入门问题，但是 1977 年这个问题刚
出来的时候，都觉得很难，直到 1984 年线性解法公布，才有一种哇靠原来如此。别忘
了整个学术界花了七年才解决这个问题。如果从未背过或见过，面试时要在 20 分钟内
解出来，天下能有几人？
最早在 interview 时出这题，是考察申请人的推导能力，能否从 brute force 里观察
出线索，做一点优化。结果被用烂了，搞得所有人都知道答案，只好另寻新题。水涨船高，搞得题目越来越难，很多 online puzzle 或者 topcoder 上的问题，作为 interview 题，要求 20 分钟内白版写出无 bug，非常变态。
那么，面试究竟是考什么？考谁见过的题多？还是考一个人在遇到陌生问题的时候，有
合理的推导能力？
红黑树的旋转或者最大流。
人的题对你来说都是“第一次见到的复杂算法”，那至少说明你准备的很差。 |
|
k***t
发帖数: 276 | 33 Given a sorted array of n integers, pick up k elements so that the minimum
difference between consecutive elements is maximum (that is choose the
elements to maximize the quantity min(a[i+1] - a[i]))
==============================
Recursive backtracking? 不过好像是brute-force的方法。
感觉上是从n个柱子里选n-k个拔掉，选C(n, n-k)种里使k-1个区间中最小的最大。 |
|
w***c
发帖数: 8 | 34 我唯一能想到的只有brute-force,但提交上去总是超时，不知各位大牛有没有好的思路
，谢谢了。 |
|
S**I
发帖数: 15689 | 35 ☆─────────────────────────────────────☆
libei (Bei) 于 (Wed Jan 11 15:43:39 2012, 美东) 提到:
面试官是Google+组的，
一上来她说看到我简历上的一篇测试自动化的文章，读了一遍，感觉"very
informative"，让后让我介绍一下相关经验。让我小高兴了一下。
第一题是coding，做的还算顺利，后来她评价说所有的cases都覆盖到了。可能算是过
关吧。
第二题我想复杂了，然后在她提示下才解决。自我感觉很不好。其实sort一下就差不多
了，不过我往复杂的树结构想去了。虽然树结构确实能解决这个问题，不过当时我解释
得很不清楚。反正很不爽。
最后瞎聊时间，她说我提到的测试自动化实践和Google内部的基本完全一样blahblah。
。。，不过我觉得这点也算不上加分吧，是个人进google一段时间后都能学会。就怕她
觉得我想问题太复杂，直接negative。
大家有啥建议想法？？
☆─────────────────────────────────────☆
peking2 (myfac... 阅读全帖 |
|
e***s
发帖数: 799 | 36 如题，
DP： time O(n*m) space O(n*m）
BF: time O(n*m) space O(1)
为什么我看那本屌书说DP更好，还没说理由。是不是我傻B了，求拍～ |
|
|
e***s
发帖数: 799 | 38 果然是我傻B，BF 是O(min(m,n)*m*n); |
|
e***s
发帖数: 799 | 39 来自主题: JobHunting版 - 电面犯二了 Bless.楼主别急嘛,也不一定挂,就算挂了，A家不打打G家！
我的解法是顺序遍历其中一个BST，然后再另一个BST上逐个找，找的同时用HASHSET放
每一个NODE的VALUE。找下一个的时候现在HASHSET上找。
个人觉得比较BRUTE FORCE。
求牛B解法。 |
|
|
|
|
b*****c
发帖数: 1103 | 43 可以问问liuchang和sjtu_pigoneand，他们全做了 |
|
N*****8
发帖数: 253 | 44 prefix tree不就是trie吗？
我当时还被考到过matrix find word的问题，之前没看到过，当场楞了一下然后先谢了
一个brute force的，然后被面试官提醒用trie来优化。 |
|
j****b
发帖数: 108 | 45 没想到什么特别巧的办法，brute force ＋ hashmap？
public static void main(String[] args) {
String l[] = { "fooo", "barr", "wing", "ding", "wing" };
Map map = new HashMap();
for (int i = 0; i < l.length; i++){
if(map.containsKey(l[i]))
map.put(l[i], map.get(l[i]) +1);
else
map.put(l[i], 1);
}
String s = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
int len = l[0].lengt... 阅读全帖 |
|
j****b
发帖数: 108 | 46 没想到什么特别巧的办法，brute force ＋ hashmap？
public static void main(String[] args) {
String l[] = { "fooo", "barr", "wing", "ding", "wing" };
Map map = new HashMap();
for (int i = 0; i < l.length; i++){
if(map.containsKey(l[i]))
map.put(l[i], map.get(l[i]) +1);
else
map.put(l[i], 1);
}
String s = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
int len = l[0].lengt... 阅读全帖 |
|
a****a
发帖数: 186 | 47 Print all the increasing subsequence from the given range 54782369862345 ..
ex: 5,7,8,9; 4,7,8,9; 2,3,6,9 ..
这个题除了brute forth解法外，还有什么巧妙的解法吗？欢迎大家赐教~ |
|
i**********e
发帖数: 1145 | 48 第二题还有另一个思路是用 divide and conquer。不过 heap 的解法比较好写代码。其实这题 brute force 写起来更要复杂，很多繁琐的 case 要考虑周到。
还有一个变种，就是 merge k-sorted lists，这道题还要稍微 tricky 一些，但思路一样。
Merge k Sorted Lists 这道题收集在这里了，制造了一些测试数据，方便大家测试代
码。
http://www.leetcode.com/onlinejudge |
|
x*******5
发帖数: 152 | 49 顶大牛
。其实这题 brute force 写起来更要复杂，很多繁琐的 case 要考虑周到。
路一样。 |
|
x*******5
发帖数: 152 | 50 证明也许比较难，但是我是这样做的：
/*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... 阅读全帖 |
|
