|
a*******1
发帖数: 17 | 2 几个关于m*m matrix的问题，看看有没有更好的算法：
1. 在一个row/col sorted matrix，寻找一个数，O(m)，从最左上角开始，如果target
大，往下走；如果target小，往左走。
2. 在一个row/col sorted matrix，寻找第k大的数，我能想到的是用Young Tableau，
然后类似于Heap，每次取出最大的数，然后Heapify matrix，直到取出第K大的数。
Time complexity是 k*O(m)，O(1) space。但是这样会破坏matrix的结构。因为每次
Heapify，matrix都变动过了。有没有更好的算法？我一直想用Divide and Conquer,
取matrix中心的那个数作为pivot，然后就不知道该怎么办了。
3. 基于问题2，那如何sort entire matrix? 当然也可以用Young, Time O(m3)? 有没
有更好的办法？
4. 如果是任意一个matrix，如何sort呢？比如sort成一个：
1 2 3 4
5 6 7 8
9 10 11 ... 阅读全帖 |
|
l*****a
发帖数: 14598 | 3 I assume that is KMP for strstr |
|
m****v
发帖数: 84 | 4 不要考虑大数相乘的复杂度？如果不用这个质数的方法来做，有没有其他比较好的解法
呢？
觉得方块那道题可以用KMP的方法来套，没有仔细想；但也可能是行不通的。
bless lz
K
1 |
|
P********i
发帖数: 172 | 5 Phone 1:
:
What is “static” variable?
How can many instance share a resource
What is deadlock, how to prevent it?
Compare whether two strings s1, s2 are equal, inside a huge set of string.
Normal way is to compare each character one by one, but it is O( n ) time
complexity. What type of short circuit can u think?
One short circuit is to use the length, since s1.len <> s2. len , then
return false. Anything else you can think of in the similar way?
My answers:
Hashtable? No, need extra spac... 阅读全帖 |
|
|
t*****s
发帖数: 416 | 7 确实没考虑连续重复字符的情况。KMP的具体算法记不清了，还得回去好好复习去。
need extra space. |
|
g***s
发帖数: 3811 | 8 Based on KMP
请zkss, 先谢过
★ Sent from iPhone App: iReader Mitbbs 6.81 - iPhone Lite |
|
g**e
发帖数: 6127 | 9 first make it right, then make it fast.
要。 |
|
|
r*******e
发帖数: 7583 | 11 exactly
我碰到一道老题，不使用额外空间交换两个变量的值
直接说用XOR swap，interviewer都没听说过，表示怀疑
于是只好先说用加减法做交换，然后指出溢出问题，然后再详细解释XOR的正确性
法。
为什
要我
复杂
本身
找个 |
|
h*****1
发帖数: 74 | 12 也许直接写brute force 的就好了。
我也是看大家的面经提到string match， 自己专门写了个，但没有debug。
请问大家，碰到这种情形能要求另外一人来重新interview吗。真是心有不甘。 |
|
|
g*********s
发帖数: 1782 | 14 just learn the lesson and move on.
the cs job market is still highly competitive. there are many openings. but
there are much more candidates.
be well prepared, and sometimes u also need some luck. |
|
|
h*****1
发帖数: 74 | 16 更可恶的是，他说我的code 还是C style。 就因为我的函数声明有underscore？ |
|
h*****1
发帖数: 74 | 17 更可恶的是，他说我的code 还是C style。 就因为我的函数声明有underscore？ |
|
d****2
发帖数: 6250 | 18 never show off. all regular hiring is for code monkey. |
|
g*********s
发帖数: 1782 | 19 why not post out ur code?
str_cmp() or strCmp() really means nothing. |
|
h*****1
发帖数: 74 | 20 int kmp_next(const char* pattern, int n)
{
int nex = 0;
for (int i = n; i >=0; --i)
{
int j = i;
int nn = n;
while(pattern[j--] == pattern[nn--])
{
++nex;
if (-1 == j)
return nex;
}
}
}
int kmp_match(const char* s, const char* p)
{
int slen = strlen(s);
int plen = strlen(p);
if (plen > slen) return -1;
int nex = 0;
int i = 0;
int j = 0;
while (i < slen && j < plen)
{
... 阅读全帖 |
|
|
|
f****4
发帖数: 1359 | 23 我给interviewer问到过用temp交换和用XOR交换哪个效率高的问题
被告知，编译器对temp交换有优化：两个变量的指针，入stack，后出stack |
|
|
|
c**y
发帖数: 172 | 26 XOR only works for int, long and char (unsigned and signed).
For other types, temp is the way to go. |
|
d*******r
发帖数: 208 | 27 第一眼看就有越界。
nn＝n pattern［nn］不是越界么？如果定义n是pattern的长度的话 |
|
h*****1
发帖数: 74 | 28 这里n是0, 1, 2, ..., size-1. 永远也到不了边界。看看调用函数就知道了。
真正的问题是应该将 j = i 改成 j = i-1 才work。 |
|
h*****1
发帖数: 74 | 29 你需要看 MIT introduction to algorithms |
|
p*********a
发帖数: 61 | 30 你觉得 senior 的面试和 junior 的面试是一样的？
也让你写个 string match?
验。 |
|
y***m
发帖数: 7027 | 31 恩，很多情况下是一样的，interviewer会无视你之前的level
从junior题一直考到senior... |
|
h*****1
发帖数: 74 | 32 这个我不知道。但是若你是senior连junior 的题都不能答上来，我不知道interviewer
会怎么看你。 |
|
y***m
发帖数: 7027 | 33 comfort//
市场供大于求决定了应聘者只能迎合面试者的口味,当是一个练兵演习过程吧
要。 |
|
d****2
发帖数: 6250 | 34
interviewer
interviewer傻逼，end of discussion. |
|
g***s
发帖数: 3811 | 35 个人觉得KPM算法没有必要熟到能写出来。
只要告诉面试官你知道有这个算法并且知道复杂度就可以了。然后写一个其它简单的算
法即使用O(mn)。 |
|
g**e
发帖数: 6127 | 36 boyer-moore is faster but more complicate to implement. |
|
f******7
发帖数: 941 | 37 always give naive algorithms first. when ask, then analyze and show
improved one. otherwise, interviewer would think you remember the code.
that's the really bad thing. |
|
t*****s
发帖数: 416 | 38 比如
1.1检查一个串有没有重复字符如果charset小的话根据抽屉原理时间是O(1)
4.7检查一个小的二叉树是不是一个大二叉树的子树可以当字符串用KMP |
|
b*****n
发帖数: 482 | 39
Cool, it's a clever move. It will solve the scenarios where the string
length is larger than 256 (assume the char set is ASCII). You will still
need to do some necessary work for the case of string length less than
256.
That was a solution without using extra memory. KMP is great when you
already have two strings, while in this case, what you've got are two
trees (need extra memory to convert them into strings) and the data might
not be characters. |
|
f*****w
发帖数: 2602 | 40 还不知道接下来结果怎么样 不过还是趁有空先回馈一下版面
第一次
居然是大牛Andrew Ng的学生；
为什么要FB
如果来了FB 最想做的事情 project 会是什么
然后问了个简历上的问题
然后 两个技术问题 很简单的
1. 实现一个strstr() 我说我可写不出KMP， 他说没事没事 就写个普通的就好
2. 给定一个没有通往父节点的连接的BST, 找到大于x的最小的那个节点。 我很stupid
地卡了很
久 最后给了一个不是很好的答案(O(lgn*lgn))。 他最后告诉我了更好的方法, 这个方
法确实比
我的好很多,lgN时间O(1)空间 就可以了。
我以为我挂了，但是有了第二次
这次好一些
1) 为什么FB
2) 简历上的好几个问题
3) 技术问题是找一个binary tree的叶子的最少depth。 我很stupid地给了个递归方法
。他说
不行啊， 要是很不balance的话，效率会很低。 我又很stupid的说那我会randomize每
次递归
的时候是左子树还是右子树，这样average 复杂度会低一些。
他忍无可忍了，说他expect something li... 阅读全帖 |
|
g******0
发帖数: 221 | 41 We used this book for our class: Introduction to Algorithm by CLRS.
Is there any other books people use for preparing for job interviews? Or is
this enough?
What data structures/algorithms do we have to know for interviews? Here is a
list I compiled. linked list, stack, queue, array, heap, bst, quick sort,
merge sort, radix sort(?), insertion sort(?), DFS, BFS, Dijkstra's(?), max
flow/min cut(?), KMP(?), suffix tree(?).
(?) indicates the items which I don't know if is required.
Any suggestion to... 阅读全帖 |
|
g**u
发帖数: 583 | 42 马上就要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 with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F ... 阅读全帖 |
|
F**r
发帖数: 84 | 43 suffix tree O(n), construct new string S~S^, where ~ is a character
not in S, and S^ is the reverse of S. then consider odd and even
substring separately, very similar.
for substring center at j, where 0<=j
can tell you LCP of two string in O(1), so complexity to find
maximum palindrome is O(n).
I think straight forward approach or DP or KMP is more reasonable
solution for this problem during the interview.
in O(n) |
|
F**r
发帖数: 84 | 44 for 32.1-4, use the same idea as KMP plus wild string matching, complexity
is O(n*k), n is the length of the searching text, k is the number of the
wild characters in the pattern string.
for 32.2-3, use the idea in image processing. sliding window |
|
|
|
g**e
发帖数: 6127 | 47 我开始也以为KMP变一下可以，仔细想了一下似乎不行 |
|
x******2
发帖数: 546 | 48 我觉得LZ的第二题的题目里的substring是指可以跳跃的字串，而kmp解决的必须是连续
的字串。
你的方法不能handle字符跳跃的问题
match的字符对 |
|
s******n
发帖数: 226 | 49 最近被问道：
假定有millions of files 找到所有含给定word的file
我回答的是KMP算法，被否了，说不能扫描所有文件，然后就傻了... |
|
|
