d***e
发帖数: 793 | 1 We are not finding the longest substring here. so any longest subsequence
will do.
This method scans twice which is O(n) and use no buffer only integer
variables which O(1)space.
void getSubseq(int *array, int len){
int maxLen = 0;
int ctZero = 0, ctOne = 0;
for(int i=0;i
printf("%d ", array[i]);
if(array[i]==0) {
ctZero++;
}
else ctOne++;
int min = ctOne
if(min>maxLen){
maxLen ... 阅读全帖 |
|
p********7
发帖数: 549 | 2 You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space
algorithm to find the maximum sub sequence which has equal number of 1s and
0s.
Examples
1) 10101010
The longest sub sequence that satisfies the problem is the input itself
2)1101000
The longest sub sequence that satisfies the problem is 110100
我想到一个办法，不知道是否正确
1.因为不知道1和0谁多，不好执行算法，所以先遍历一次统计下1和0数量，选少的那个
做标准
2.想统计10，想到的办法就是如果是1就+1,如果是0就-1，如果sum ＝＝ 0就统计一次
长度，这样我们发现似乎对于上面例子这个办法可以work，不过如果上面的string反置
，这个办法就不work了，因为以为后面的0太多，而 |
|
c********v
发帖数: 21 | 3 请教第3题怎么做？
assume a retangle 1 to n
form a graph M[n*n], if rect i intersect with j, then M[i,j] and M[j,i]=1
othwise =0
Then get a longest path of between rect i,j
assume path[i] is the longest path ending at rect i
Is this correct?
矩形都重叠。 |
|
f****n
发帖数: 208 | 4 If you model this way, the answer is not the longest path, but the shape.
Since it wants the rectangles that all overlapping. In the following setup,
the answer is (1, 2, 5)
The longest path is 3,1,2,4,5
Rect ID (Overlap with ID)
1 (2, 3, 5)
2 (1, 4, 5)
3 (1)
4 (2, 5)
5 (1, 2, 4) |
|
i**9
发帖数: 351 | 5 来自主题: JobHunting版 - 最长回文串 我觉得是对的，有人认为是错的是觉得(find longest common substring of A and B,
自动认为是longest palindromic不对) |
|
c*********7
发帖数: 19373 | 6 这个是求longest common string。我这里要求的是翻转。比如DP中 12356321可能就把
123算作翻转的longest common string.而在这里却不符合要求。 |
|
y******5
发帖数: 43 | 7 感觉是要两个树同时BFS，而且对两个对应点，假设A和B（A在树1，B在树2，A和B同层
且label相
等），的两组子节点做如下处理：首先剔除不是两边都有的点；对两组子节点求
longest common
pattern，每个点把到它为止的Longest Common Pattern值和父节点的值相加并保存,而
且还要
加上父节点左sibling所求的LCP值，同时保存父节点指针。当这一层所有子节点处理完
毕，将合格
的子节点enqueue，如果queue size大于0，进入下一层；否则，从最大值开始回溯。
说得很乱，见谅。
if
one
same) |
|
j***y
发帖数: 2074 | 8
我也感觉用map是个不错的选择，不过下面的代码有些不明白：
－－－
} else {
if (curr > longest)
longest = curr;
curr = i - m[c];
index = m[c]+1;
m[c] = i;
－－－
可以加点注释或者说明吗？谢谢。 |
|
|
r********r
发帖数: 2912 | 9 I think the solution is wrong. The longest subsequence algorithm given on
wikipedia works.
For instance, the sequence is
40 70 50 60
Starting from 40, the solution can only detect two increasing subsequence
40 70 and 50 60 that are not longest
atop
person
the
compute
, |
|
r********r
发帖数: 2912 | 10 I think the solution is wrong. The longest subsequence algorithm given on
wikipedia works.
For instance, the sequence is
40 70 50 60
Starting from 40, the solution can only detect two increasing subsequence
40 70 and 50 60 that are not longest
atop
person
the
compute
, |
|
r*******e
发帖数: 7583 | 11 1. "abcdefg" -> "abcdef" -> "gabcdef", the distance is 2
deletion and the addtion are counted as 2 edits, not a single one
2. one can build a (basic) suffix tree for the string txt1$txt2#, where `$'
is a special terminator for txt1 and `#' is a special terminator for txt2.
The longest common substring is indicated by the deepest fork node that has
both `$...' and `...#' (no $) beneath it.
The longest palindrome of txt[1..n] can be found in O(n) time, by building
the suffix tree for txt$reverse(t... 阅读全帖 |
|
b**********r
发帖数: 91 | 12
`$'
txt2.
has
building
for the case:
abcdxyzdcba
What's the longest palindrome?, the longest common string for txt and
reverse(txt) is abcd, but it's not palindrome |
|
r*******e
发帖数: 7583 | 13 the longest common string of txt and reverse(txt) is not necessarily the
longest palindrome (I didn't say that in my last post)
we still need to check the positions
the length of the common string plus the lengths of the portions before $/#
in the two child nodes should be equal to strlen(txt). |
|
r*******e
发帖数: 7583 | 14 1. "abcdefg" -> "abcdef" -> "gabcdef", the distance is 2
deletion and the addtion are counted as 2 edits, not a single one
2. one can build a (basic) suffix tree for the string txt1$txt2#, where `$'
is a special terminator for txt1 and `#' is a special terminator for txt2.
The longest common substring is indicated by the deepest fork node that has
both `$...' and `...#' (no $) beneath it.
The longest palindrome of txt[1..n] can be found in O(n) time, by building
the suffix tree for txt$reverse(t... 阅读全帖 |
|
b**********r
发帖数: 91 | 15
`$'
txt2.
has
building
for the case:
abcdxyzdcba
What's the longest palindrome?, the longest common string for txt and
reverse(txt) is abcd, but it's not palindrome |
|
r*******e
发帖数: 7583 | 16 the longest common string of txt and reverse(txt) is not necessarily the
longest palindrome (I didn't say that in my last post)
we still need to check the positions
the length of the common string plus the lengths of the portions before $/#
in the two child nodes should be equal to strlen(txt). |
|
g**u
发帖数: 583 | 17 求祝福，刚面完Google第一轮。
电话面试没有NDA，所以把记得的题目记下来
太紧张了，发挥的很差。。。
Interviewer迟了3分钟， 没什么口音，估计是老美。面试一开始就上Google doc，
上来就要求写2个factorial的实现。
写了factorial的定义，马上写了个recursive的实现，说了边界检查，说了overflow，
然后开始写， 结果， 居然一急之下把base case给忘写了（哭死）。。。第二个写了
个iterative的实现，解释tail recursion可以马上改写成iterative的
接着是问一个非常大的文件里面有很多string，每行一个，问如何去重？ 说了hash和
sort的2种方法，比较了time and space complexity
接着是问了 set of strings, how to sort？问了memmory的限制，问了string的长度
分布，提出可以quick sort， 要求说明原理和时间空间复杂度，被追问还有其他方法
， 脑子犯傻，说了radix sort(大忌， 不要说自己不彻底清楚的东西)，说了基本原理... 阅读全帖 |
|
f*********i
发帖数: 197 | 18 A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bianry tree找两个节点的最
小公共父亲, 一开始是允许有父节点的,然后扩展到没有父亲节点,我给了O(nlogn)解法
public static BinaryTree tree_least_comm... 阅读全帖 |
|
h**********s
发帖数: 20 | 19 longest palindrome 用这个方法是不对的吧，貌似讨论了不少了
比如 s = abcefcba
转过来 abcfecba
longest common substring = abc？ |
|
b**********r
发帖数: 91 | 20 Can't input Chinese, My situation was riding donkey and looking for
horse.
Interviewed several companies small or big, followings are some of the
questions as a return for what I benefit from here
(1) topological sort
(2) given an array of stock prices, find the best trading strategy.
(3) given a stream of points, find the top 10 points closest to the
origin
(4) given a BST, divide it by a given value
(5) print all the diagonals of a matrix
(6) check if 2 strings are anagram
(7) max subarray
(8)... 阅读全帖 |
|
g*****i
发帖数: 2162 | 21 bless?楼主什么背景? fresh graduate吗?
第一题我觉得不需要完整的suffix tree,因为题目只要找longest prefix,所以就把每
个string的插入一次就可以了,还可以记录当前的longest prefix的长度来加速. 另外
linear suffix tree construction好像很复杂吧.
第二题如果文件在memory放不下怎么办呢?
第四题每个server的os image都一样吗?如果一样的话应该是类似找一个快速扩散的方法
第七题这种多线程题没经验的总觉得很麻烦啊,楼主说的unblock型是什么意思? |
|
B*******1
发帖数: 2454 | 22 不是我贴怪题，而是大部分题都会做了，这些是不会的。都是careercup上面看到的。
这题不是怪题阿，你如果google "longest arithmetic progression"就可以看到这篇
paper里面http://theory.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf 一开始前言说则么用dp了，但是我没有完全看懂里面某些部分。所以上来问问这里有没有高人有更加好的方法
我想到了一个，把这个array转化成2维空间的点，然后求每2个点的斜率，longest
arithmetic progression 就是一条直线上面的点，最后找出出现最多的斜率就好了。
似乎复杂度跟dp一样。 |
|
x****3
发帖数: 62 | 23 Find the longest palindrome in a string.
这题出现频率很高。 一直没看到简洁的答案。 我能想到就Brute force, O(n^2). 有
个错的简单的解法（倒序后的字符串和原字符串， longest common substring.
counter example, "abcxacba"）
有人指点下吗？ 谢谢 |
|
g*****i
发帖数: 2162 | 24 **********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You went
to the bookshop but fail to find, you have 5 minutes, what will you do?
you have to test 10... 阅读全帖 |
|
g*****i
发帖数: 2162 | 25 **********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You went
to the bookshop but fail to find, you have 5 minutes, what will you do?
you have to test 10... 阅读全帖 |
|
b*******y
发帖数: 232 | 26 longest increasing subsequence吧
不在其列的就是需要删掉的
然后可以找出多个longest increasing subsequence
re |
|
p*******o
发帖数: 3564 | 27 www.careercup.com/question?id=11978701f
Given an array of integers, find the longest subsequence of elements which
monotonically increases. for ex. array = {1 4 8 2 5 7 3 4 6}, the longest
subsequence = {1 2 3 4 6}
I have explained him about O(N^2) with O(1) space algorithm but the
interview is expecting O(N log N). Could any one help me explaining the
algorithm in detail ? |
|
l*****n
发帖数: 577 | 28 从cacreecup上看来的，amzon家的新题
Write a program that reads a file containing a sorted list of words (one
word per line, no spaces, all lower case), then identifies the longest word
in the file that can be constructed by concatenating copies of shorter words
also found in the file.
For example, if the file contained:
cat
cats
catsdogcats
catxdogcatsrat
dog
dogcatsdog
hippopotamuses
rat
ratcatdogcat
The answer would be 'ratcatdogcat' - at 12 letters, it is the longest word
made up of other words in the l... 阅读全帖 |
|
i******n
发帖数: 94 | 29 find the longest run number within a sorted array.
For example:
1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
the longest long number is 8
do it with O(log(n)), constant space. |
|
i******n
发帖数: 94 | 30 find the longest run number within a sorted array.
For example:
1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
the longest long number is 8
do it with O(log(n)), constant space. |
|
m*******m
发帖数: 82 | 31 Interview Questions：
Redefine a function (signature given) to write data to a new replacement for
an antiquated database (which you previously designed)
Answer Question：
Write a function to return the longest common prefix between two strings.
//java code
String GetCommonPrefix(String a, String b)
{
char[] aChar = a.toCharArray();
char[] bChar = b.toCharArray();
int startIndex = 0;
//choose short length as the end index
int needLength= aChar.length>bChar.length?bChar.length:aChar.lengt... 阅读全帖 |
|
l*********8
发帖数: 4642 | 32 1. BST Optimal Binary Search Tree Problem
2. COV Optimal Covering problem
3. ILP integer linear programming
4. KS Knapsack Problem
5. LCS Longest Common Subsequences
6. LSP Longest Simple path Problem
7. MCM Matrix chain multiplication
8. ODP Optimal Distribution Problem
9. SCP Stagecoach Problem
10. SPA Shortest Path in a Acyclic graph
11. SPC Shortest Path in a Cyclic graph
12. TSP Travelling salesman problem |
|
i**********e
发帖数: 1145 | 33 F:
3Sum
Add Binary
Combination Sum
Count and Say
Divide Two Integers
Edit Distance
Implement strStr()
Letter Combinations of a Phone Number
Longest Palindromic Substring
Merge Intervals
Multiply Strings
Next Permutation
Permutations, Permutations II
Regular Expression Matching
Remove Duplicates
Remove Element
Search in Rotated Sorted Array
String to Integer (atoi)
Sqrt(x)
Substring with Concatenation of All Words
Trapping Rain Water
Unique Paths, Unique Paths II
G:
3Sum
Climbing Stairs
Container... 阅读全帖 |
|
U*****R
发帖数: 60 | 34 昨天和Yelp打了个电话。
对方先问了简历上的东西和项目，接着是一些常见technical小问题
1）从打www.google.com到你看到网页发生了什么
2）process和thread区别是什么，fork做了什么，父进程和子进程的代码一样否
3）mysql query很慢的时候需要做什么，我说explain；又问index好为什么不给每个
column都建一个index
接着一道coding题目
Find the longest substring with non-repeating characters.
for example: ""->0, "a"->1, "aaa"->1, "baabababa"->2, "abcda"->4
面试官没有说要给出time complexity和space complexity上的限制，我就假设这些都
是越少越好。
[更新]此题已解，做法参照http://www.leetcode.com/2011/05/longest-substring-without-repeating-characters.html
请大牛指点一下这道题!!
我的解... 阅读全帖 |
|
s*********5
发帖数: 514 | 35 关于课程排序，如果是这样的：
a1, a2 -> b1 （上b1之前，要先上a1, a2)
a3, a4 -> b2
a5, a6 -> b3
b1, b2, b3 -> c1
BUT a4, b3, ONLY available in semester 4 (S4)
然后每个学期只能上2节课，
(starting no incoming edge: a1, a2, a3, a4, a5, a6)
S1: a1, a2 (a3, a4, a5, a6, b1)
S2: a5, a6 (a3, a4, b1, b3)
S3: b1, a3 (a4, b3)
S4: a4, b3 (b2)
S5: b2
S6: c1
这样用什么算法？
我想的是先找出longest link, 就是找出需要最久才能完成的那个link, 然后reduce
its length, then update the length, and continue
这里的关键是如何计算longest link, 我认为每个课程（node)要有其在每个level（
l... 阅读全帖 |
|
j******2
发帖数: 362 | 36 没人对这俩问题感兴趣吗？还是答案太显而易见
tree |
|
i***h
发帖数: 12655 | 37 suffix array is much easier to implement |
|
j******2
发帖数: 362 | 38 DP用的就是suffix array吧？用generalized suffix tree是另一种，不过还是决定把
它搞搞清楚了。好像很多DP问题都可以用suffix tree来搞。 |
|
i***h
发帖数: 12655 | 39 DP和suffix array没什么直接关系吧 |
|
i***h
发帖数: 12655 | 40 不用DP,
suffix array排序, 然后过一遍就行了
array |
|
j******2
发帖数: 362 | 41 那个。。。过一遍，用到了前面的结果，不是就叫DP的吗？
还是我对DP的理解又错拉 |
|
C***U
发帖数: 2406 | 42 你应该google一下suffix array及算法 |
|
|
|
C***U
发帖数: 2406 | 45 是有些麻烦。。。。我觉得现场写不太可能把。
我的算法课的project就是做linear time suffix array construction + wavelet
tree 来实现string match
当然大牛可能有很简单的 办法实现 |
|
|
i***h
发帖数: 12655 | 47 用C++ STL, 还好了
下面的代码少了最后一步, 也没有sanity check
但也不难
当然效率不是最好的
#include
#include
#include
#include
using namespace std;
bool
compstr(char* a, char* b)
{
return strcmp(a,b)<0;
}
void
suffixArray(char *a, char *b)
{
char *m = (a>b)? a-1 : b-1;
char* suffix[strlen(a)+strlen(b)];
for(int i = 0; i
suffix[i] = a+i;
}
for(int i=0; i
suffix[strlen(a)+i] = b+i;
}
sort(suffix, suffix+strlen(a)+strlen(b), comp... 阅读全帖 |
|
|
w*********0
发帖数: 48 | 49 有几个蛮常见的
longest increasing subsequence 有O(nlogn)的 我只能写到O(n^2)的 O(nlogn)基本
只能靠背
longest palindrome substring 有O(n)的
还有就是经典的KMP，这个貌似还好
这种题目 需要背下来最优解么。。。。 |
|
s********s
发帖数: 49 | 50 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
后开始做题，让merge k 个 sorted list，用heap做了。
第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
。顺便请教一下大家两个困扰我挺久的问题：
(1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
因为我想明年一毕业就能直接去美国工作，这样的话势必要在明年三四月的时候找好
full time了吧，不然的话h1b神马的是不是会有问题？我这样的情况怎么样规划好一点
？求建议啊！
(2) 像这次面我的两... 阅读全帖 |
|
