p**p
发帖数: 742 | 1 这题用KMP吧。检查preprocess部分生产的array l 就可以了。如果是valid case.
preprocessing array 必然满足下面的几个条件：
1. l[n-1] 必须是最大值 (这个没必要专门检查,只要3满足就成);
2. s[0,...,n-l[n-1])就是repeating pattern;
3. l[n-1]/(length of the repeating pattern) >= 1;
4. l[n-1] % (length of the repeating pattern) == 0.
比如：
"abcabcabc" -> [0, 0, 0, 1, 2, 3, 4, 5, 6]
"abcdabcd"-> [0, 0, 0, 0, 1, 2, 3, 4]
几个false cases:
"bcdbcdbcdebcdbcdbcd" -> [0, 0, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7,
8, 9]
"ababeabab"-> [0, 0, 1, 2, 0, 1, 2, 3, 4]
code 如下：... 阅读全帖 |
|
p**p
发帖数: 742 | 2 这题用KMP吧。检查preprocess部分生产的array l 就可以了。如果是valid case.
preprocessing array 必然满足下面的几个条件：
1. l[n-1] 必须是最大值 (这个没必要专门检查,只要3满足就成);
2. s[0,...,n-l[n-1])就是repeating pattern;
3. l[n-1]/(length of the repeating pattern) >= 1;
4. l[n-1] % (length of the repeating pattern) == 0.
比如：
"abcabcabc" -> [0, 0, 0, 1, 2, 3, 4, 5, 6]
"abcdabcd"-> [0, 0, 0, 0, 1, 2, 3, 4]
几个false cases:
"bcdbcdbcdebcdbcdbcd" -> [0, 0, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7,
8, 9]
"ababeabab"-> [0, 0, 1, 2, 0, 1, 2, 3, 4]
code 如下：... 阅读全帖 |
|
W***o
发帖数: 6519 | 3 以前用Turing machine设计解决这种题的方法，呵呵，无非就是扫描，假设string
pattern，验证。。 |
|
S*******C
发帖数: 822 | 4 谢谢指正，这题难度很大，上面这么多解法只有3种是对的
贴一种比较简洁的写法，不知道怎么证明是O(N)的解法？
public boolean isMultipleDuplicate(String s) {
if (s == null || s.length() < 4)
return false;
int len = s.length();
int[] a = new int[len];
int j = 0;
for (int i = 1; i < len; i++) {
while (j > 0 && s.charAt(i) != s.charAt(j))
j = a[j - 1];
if (s.charAt(i) == s.charAt(j))
j++;
a[i] = j;
}
int patternLen ... 阅读全帖 |
|
|
G*********n
发帖数: 53 | 6 longest ascending sequence， Dp 经典题吧 |
|
|
|
|
|
d**k
发帖数: 797 | 11 晕死
我天天在版上看，怎么就没看到这个必考题呢 |
|
l********1
发帖数: 24 | 12 这个题我做了，我开始也说的是heap，然后要求提高，你应该问他similarity如何定义
，他会告诉你是(1-100)，然后他期待的其实是类似桶排序的。 |
|
l********1
发帖数: 24 | 13 这个题我做了，我开始也说的是heap，然后要求提高，你应该问他similarity如何定义
，他会告诉你是(1-100)，然后他期待的其实是类似桶排序的。 |
|
S***A
发帖数: 133 | 14 我觉得counting sort也可以啊，要是数很多的话用radix sort也行啊。
：这个题我做了，我开始也说的是heap，然后要求提高，你应该问他similarity如何定
义，他会告诉你是(1-100)，然后他期待的其实是类似桶排序的。
…… |
|
S***A
发帖数: 133 | 15 相同的值可以放在一个bucket里啊
：similarity没有相同的值才能桶排序吧？如果有最小的k个similarity都是1，怎么桶
排序？
：
：
：【 在 leetcoder1 (mitbbsCoder) 的大作中提到: 】
：: 这个题我做了，我开始也说的是heap，然后要求提高，你应该问他similarity如何
定义
：: ，他会告诉你是(1-100)，然后他期待的其实是类似桶排序的。
：
…… |
|
S***A
发帖数: 133 | 16 我觉得这道题你说出O(n)的算法就行了吧。
：假设当然是k<<n啦
：k非常小，比如10,20这种
：n非常大，几十万肯定不只，几百万至少了
：【 在 SEKKA (努力备考中......) 的大作中提到: 】
：: too optimistic，你怎么知道你的一个group会/不会cover k个值？
：: ：我大概明白了
：: ：heap没有错
…… |
|
r****s
发帖数: 1025 | 17 唯一的快速方法就是用bitmap sort，开一个2^32的bitmap（耍赖的话，勉强算
constant space?).或者开一个100的bitmap。难道那哥们比stackoverflow的anser还牛
？这样的人一般没时间做phone screening，相信我。
我觉得这个interview的问题在于，这哥们没时间准备，临时选了一道题，自己也没看
懂，就忙着过来问了，紧接着google了一下，就SB了，然后就没有然后了。 |
|
d**k
发帖数: 797 | 18 感觉还可以，说很快会给答复，面试官是个很帅的白人小伙子，很和蔼
是web组，所以开始问得是web题目
What core types are available in JavaScript?
A: string, number, object, null, undefined, boolean
Can you describe closure? and example?
A Describe出来了，但是example写的不好，就不贴le。是个挂点。
Alert a string after a 10 second delay
A：setTimeout(function(){‘alert(“msg”)}, 10000);
这个很惭愧，API的记得不清楚，面试管很nice的抛了个API连接过来。是个挂点。
evaluate the following expression, and explain == vs ===
“1” == 1 true
“1” === 1 false
“1” == true true
“1” === true false
Name some security th... 阅读全帖 |
|
|
p*******e
发帖数: 933 | 20 如果面试前在这个版做过功课,这个题太高频了啊
怎么就挂了呢 |
|
a***n
发帖数: 623 | 21 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
扩展是，求一个最小区间，囊括了一个set of words。
这个问题在实际中也有很直接的应用：
比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
洁的snippets且包括了所有term？
倒排索引应该能想到。
扩展问题解法就是贪心，不需要DP。 |
|
c*******r
发帖数: 610 | 22 auyin 说得是对的，其实就是inverted index的简单版本吧。
基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
索引
之间的最小值，就是两个词之间的最小距离了。
glassdoor上面原题 |
|
|
|
|
p*******e
发帖数: 933 | 26 如果面试前在这个版做过功课,这个题太高频了啊
怎么就挂了呢 |
|
a***n
发帖数: 623 | 27 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
扩展是，求一个最小区间，囊括了一个set of words。
这个问题在实际中也有很直接的应用：
比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
洁的snippets且包括了所有term？
倒排索引应该能想到。
扩展问题解法就是贪心，不需要DP。 |
|
c*******r
发帖数: 610 | 28 auyin 说得是对的，其实就是inverted index的简单版本吧。
基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
索引
之间的最小值，就是两个词之间的最小距离了。
glassdoor上面原题 |
|
|
|
|
t*******e
发帖数: 274 | 32 第一题中的equal条件有什么陷阱么？还是说和leetcode上那道search 2D matrix是一
样的？ |
|
j*****8
发帖数: 3635 | 33 第一题，按照cc150的解法，从右上角开始向左或向下二分查找的话，针对这个首尾可
能相等的情况不需要额外的 处理把 |
|
l*****a
发帖数: 14598 | 34 没看清题？这个期待什么结果
1
/
2 3
4 |
|
l*****a
发帖数: 14598 | 35 原题已经告诉你有equal的情况
所以你的code不能得分 |
|
y**********a
发帖数: 824 | 36
改了一下第一题。
boolean equal(int[][]mx, int i, int j) {
int m=mx.length,n=mx[0].length;
if (i<0||j>=m*n||j<0||i>=m*n) return false;
return mx[i/n][i%n]==mx[j/n][j%n];
}
int binarySearchBound(int[][]mx, int k, boolean lower) {
for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
int mid=l+(r-l)/2;
if (mx[mid/n][mid%n]==k) {
if (lower)
if (!equal(mx, mid, mid-1)) return mid;
e... 阅读全帖 |
|
l****s
发帖数: 75 | 37 第二题其实就是一个reverse linked list的变种。
TreeNode* flipUpsideDown2(TreeNode* root)
{
if (!root) return NULL;
TreeNode* dummy = new TreeNode(0);
dummy->left = root;
TreeNode* right = root->right;
root = root->left;
dummy->left->left = NULL;
dummy->left->right = NULL;
while (root)
{
TreeNode* tmp = root;
root = root->left;
tmp->left = right;
right = tmp->right;
tmp->right = dummy->left;
dummy->left = tmp;
}
root... 阅读全帖 |
|
s**x
发帖数: 7506 | 38 第一题估计出题的人都晕了， 你自己想想吧， 就是不折不扣的 binary search. 2D
array in that case is exactly 1D sorted array! no trick at all, exactly the
same.
1 2 3
4 5 6
is the same as 1 2 3 4 5 6! |
|
p*****2
发帖数: 21240 | 39 第二题这样怎么样
TreeNode dfs(TreeNode node, TreeNode parent){
if(node==null) return null;
TreeNode left_res = dfs(node.left,node);
if(parent!=null){
node.left = parent.right;
node.right = parent;
}
return left_res!=null?left_res:node;
}
TreeNode convert(TreeNode root){
return dfs(root,null);
} |
|
|
|
t*******e
发帖数: 274 | 42 第一题中的equal条件有什么陷阱么？还是说和leetcode上那道search 2D matrix是一
样的？ |
|
j*****8
发帖数: 3635 | 43 第一题，按照cc150的解法，从右上角开始向左或向下二分查找的话，针对这个首尾可
能相等的情况不需要额外的 处理把 |
|
l*****a
发帖数: 14598 | 44 没看清题？这个期待什么结果
1
/
2 3
4 |
|
l*****a
发帖数: 14598 | 45 原题已经告诉你有equal的情况
所以你的code不能得分 |
|
y**********a
发帖数: 824 | 46
改了一下第一题。
boolean equal(int[][]mx, int i, int j) {
int m=mx.length,n=mx[0].length;
if (i<0||j>=m*n||j<0||i>=m*n) return false;
return mx[i/n][i%n]==mx[j/n][j%n];
}
int binarySearchBound(int[][]mx, int k, boolean lower) {
for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
int mid=l+(r-l)/2;
if (mx[mid/n][mid%n]==k) {
if (lower)
if (!equal(mx, mid, mid-1)) return mid;
e... 阅读全帖 |
|
l****s
发帖数: 75 | 47 第二题其实就是一个reverse linked list的变种。
TreeNode* flipUpsideDown2(TreeNode* root)
{
if (!root) return NULL;
TreeNode* dummy = new TreeNode(0);
dummy->left = root;
TreeNode* right = root->right;
root = root->left;
dummy->left->left = NULL;
dummy->left->right = NULL;
while (root)
{
TreeNode* tmp = root;
root = root->left;
tmp->left = right;
right = tmp->right;
tmp->right = dummy->left;
dummy->left = tmp;
}
root... 阅读全帖 |
|
s**x
发帖数: 7506 | 48 第一题估计出题的人都晕了， 你自己想想吧， 就是不折不扣的 binary search. 2D
array in that case is exactly 1D sorted array! no trick at all, exactly the
same.
1 2 3
4 5 6
is the same as 1 2 3 4 5 6! |
|
p*****2
发帖数: 21240 | 49 第二题这样怎么样
TreeNode dfs(TreeNode node, TreeNode parent){
if(node==null) return null;
TreeNode left_res = dfs(node.left,node);
if(parent!=null){
node.left = parent.right;
node.right = parent;
}
return left_res!=null?left_res:node;
}
TreeNode convert(TreeNode root){
return dfs(root,null);
} |
|
|
