x*********1
发帖数: 23 | 1 google 电面被拒了， 题目是 check 一个 String s 的 anagram 是否为 另一个
string t的 substring. 给的方法是 先得出 所有 s 的 anagram 然后 在check 是否
其中之一 为 t的 subString。 不知道这个做法做有什么问题？ 之后在 eclipse 上测
了下 代码， 发现有几个 typo 和 方法名用错了， 比如 insert 写成了 add。这种问
题是挂的原因么？ 感觉code 一多 又不在编译器里，又没太多检查时间，做到毫无瑕
疵真心很不容易啊。 |
m**********4
发帖数: 774 | 2 一点想法, 不知道对不对:
不需要generate所以的permutation。给一个hash(s)，比如rolling hash，但每个位置
给的权重一样。在t上做kp，所需要的complexity只是t的长度。为了防止false
positive, 可以多用几个HASH FUNCTION。
否
【在 x*********1 的大作中提到】
: google 电面被拒了， 题目是 check 一个 String s 的 anagram 是否为 另一个
: string t的 substring. 给的方法是 先得出 所有 s 的 anagram 然后 在check 是否
: 其中之一 为 t的 subString。 不知道这个做法做有什么问题？ 之后在 eclipse 上测
: 了下 代码， 发现有几个 typo 和 方法名用错了， 比如 insert 写成了 add。这种问
: 题是挂的原因么？ 感觉code 一多 又不在编译器里，又没太多检查时间，做到毫无瑕
: 疵真心很不容易啊。
|
l******6
发帖数: 340 | 3 You didn't give the answer they want.. Which is more important than bug free |
x*********1
发帖数: 23 | 4 请能仔细说说么？ 或者 类似的参考资料？ 我在做之前跟面试官确认了一下可以按我
那个方法做嘛, 他说没问题， 请问挂的原因会是算法不够高效么？还是因为code不够
干净呢
【在 m**********4 的大作中提到】
: 一点想法, 不知道对不对:
: 不需要generate所以的permutation。给一个hash(s)，比如rolling hash，但每个位置
: 给的权重一样。在t上做kp，所需要的complexity只是t的长度。为了防止false
: positive, 可以多用几个HASH FUNCTION。
:
: 否
|
x*********1
发帖数: 23 | 5 我在写之前跟面试官确认了是否可以用我说的那个方法啊？面试官说可以，之后也没问
我是否能够优化？
free
【在 l******6 的大作中提到】
: You didn't give the answer they want.. Which is more important than bug free
|
l******6
发帖数: 340 | 6 Your method is working. But not as good as they expect so they say OK but
don't move on with you.
【在 x*********1 的大作中提到】
: 我在写之前跟面试官确认了是否可以用我说的那个方法啊？面试官说可以，之后也没问
: 我是否能够优化？
:
: free
|
d**********x
发帖数: 4083 | 7 sliding window.
否
【在 x*********1 的大作中提到】
: 我在写之前跟面试官确认了是否可以用我说的那个方法啊？面试官说可以，之后也没问
: 我是否能够优化？
:
: free
|
x*********1
发帖数: 23 | 8 既然这样的话还让我写什么啊，浪费时间么不是。如果需要更加高效的算法话可以跟我
说啊，然后我可以再考虑一下嘛
【在 l******6 的大作中提到】
: Your method is working. But not as good as they expect so they say OK but
: don't move on with you.
|
d**********x
发帖数: 4083 | 9 i don't like this either.
if they directly tell you that there is an O(N) algorithm, you may realize
it immediately.
【在 x*********1 的大作中提到】
: 既然这样的话还让我写什么啊，浪费时间么不是。如果需要更加高效的算法话可以跟我
: 说啊，然后我可以再考虑一下嘛
|
x*********1
发帖数: 23 | 10 不知道想的对不对，如果这样的话，那么面试官想要的都是做过类似题的候选人了，除
非知道最优解，然后直接给出答案， 否则， 你给出个solution，面试官不满意也让你
写不就是存心挂人么。
【在 d**********x 的大作中提到】
: i don't like this either.
: if they directly tell you that there is an O(N) algorithm, you may realize
: it immediately.
|
|
|
l******6
发帖数: 340 | 11 That is why we go over leetcode over and over....
【在 x*********1 的大作中提到】
: 不知道想的对不对，如果这样的话，那么面试官想要的都是做过类似题的候选人了，除
: 非知道最优解，然后直接给出答案， 否则， 你给出个solution，面试官不满意也让你
: 写不就是存心挂人么。
|
x*********1
发帖数: 23 | 12
【在 l******6 的大作中提到】
: That is why we go over leetcode over and over....
|
x*********1
发帖数: 23 | 13 任重道远啊。
【在 l******6 的大作中提到】
: That is why we go over leetcode over and over....
|
m**********g
发帖数: 153 | 14 sliding window是否这样解：
<1>expect_occur[256] for s
<2>real_occur[256]
whenever real_occur[t[i]] > expect_occur[t[i]], clear real_occur and start
from i+1 again.
【在 d**********x 的大作中提到】
: sliding window.
:
: 否
|
d**********x
发帖数: 4083 | 15 idea is similar but not that simple....
try this problem on leetcode:
http://oj.leetcode.com/problems/substring-with-concatenation-of
and you will see if you understood it correctly.
【在 m**********g 的大作中提到】
: sliding window是否这样解：
: <1>expect_occur[256] for s
: <2>real_occur[256]
: whenever real_occur[t[i]] > expect_occur[t[i]], clear real_occur and start
: from i+1 again.
|
d**********x
发帖数: 4083 | 16 ok... anyways, 2 points:
1. we may not know where exactly i is, so we need to scan from the start of
the window until we encounter a character same as t[x]
2. when we encounter a char not in anagram, we just reset all records
【在 m**********g 的大作中提到】
: sliding window是否这样解：
: <1>expect_occur[256] for s
: <2>real_occur[256]
: whenever real_occur[t[i]] > expect_occur[t[i]], clear real_occur and start
: from i+1 again.
|
P****2
发帖数: 197 | 17 最短SNIPPETS变形吧，一样2指针2字典，O(n)扫过去
public bool IsAnagramSubString(string str, string anagram)
{
var pStart = 0;
var pEnd = 0;
var targetDict = anagram.GroupBy(p => p)
.ToDictionary(
g => g.Key,
g => g.Count()
);
var targetTotalNum = targetDict.Values.Sum();
var foundDict = targetDict.ToDictionary(p => p.Key, p => 0);
var foundTotalNum = 0;
while (pEnd < str.Length)
{
var c = str[pEnd];
if (!targetDict.ContainsKey(c))
{
foundTotalNum = 0;
foundDict = targetDict.ToDictionary(p => p.Key, p => 0);
}
else
{
foundDict[str[pEnd]]++;
foundTotalNum++;
while (foundDict[c] > targetDict[c])
{
foundDict[str[pStart]]--;
foundTotalNum--;
pStart++;
}
}
pEnd++;
if (foundTotalNum == targetTotalNum) return true;
}
return false;
} |
k*****m
发帖数: 14 | |
g*********e
发帖数: 14401 | 19 事实就是这样
【在 x*********1 的大作中提到】
: 不知道想的对不对，如果这样的话，那么面试官想要的都是做过类似题的候选人了，除
: 非知道最优解，然后直接给出答案， 否则， 你给出个solution，面试官不满意也让你
: 写不就是存心挂人么。
|
s******i
发帖数: 236 | 20 ls一些人略装B
只能说lz遇到奇葩面试官了
patpat |
