x****r
发帖数: 99 | 1 在fb主页申请的工作，之前第二面完发过一个帖 上周五facebook的第三轮面试
总共长度45分钟，约的是下午2点，因为他打电话迟了15分钟，3点他有会就结束了
0-10 min:
他先向我做了5分钟的自我介绍，讲了讲自己做的东西，然后叫我介绍一下自己，又问了一点
简历上的东西
11-13 min:
接下来就说会问一个分析的问题和一个coding的题目，然后问如何在一个无限长的stream
里面找到前1000大的，因为是非常常见的题目，就和他说了一下用min heap，分析了一下复
杂度，很快就进入coding了
13 - 40 min:
问了一道我没有准备过的coding题目，simple regular expression match，可以match
的符号只有3种：
a-z : match a-z
. : match any
* : repeat 0 - arbitrary times
和没用过regex的同学解释一下 例如
a*b 可以match : b, ab, aab, aaaaaa |
x******3
发帖数: 245 | |
S******a
发帖数: 862 | 3 onsite跟谷歌差不多，
除去之前的参观等活动一共3个人，每人45min，基本纯做题
比谷歌简单，我是没有被问到DP, 更没有飘逸问题
又问了一点
stream
了一下复
【在 x****r 的大作中提到】
: 在fb主页申请的工作，之前第二面完发过一个帖 上周五facebook的第三轮面试
: 总共长度45分钟，约的是下午2点，因为他打电话迟了15分钟，3点他有会就结束了
: 0-10 min:
: 他先向我做了5分钟的自我介绍，讲了讲自己做的东西，然后叫我介绍一下自己，又问了一点
: 简历上的东西
: 11-13 min:
: 接下来就说会问一个分析的问题和一个coding的题目，然后问如何在一个无限长的stream
: 里面找到前1000大的，因为是非常常见的题目，就和他说了一下用min heap，分析了一下复
: 杂度，很快就进入coding了
: 13 - 40 min:
|
r****o
发帖数: 1950 | 4 Bless
又问了一点
stream
了一下复
【在 x****r 的大作中提到】
: 在fb主页申请的工作，之前第二面完发过一个帖 上周五facebook的第三轮面试
: 总共长度45分钟，约的是下午2点，因为他打电话迟了15分钟，3点他有会就结束了
: 0-10 min:
: 他先向我做了5分钟的自我介绍，讲了讲自己做的东西，然后叫我介绍一下自己，又问了一点
: 简历上的东西
: 11-13 min:
: 接下来就说会问一个分析的问题和一个coding的题目，然后问如何在一个无限长的stream
: 里面找到前1000大的，因为是非常常见的题目，就和他说了一下用min heap，分析了一下复
: 杂度，很快就进入coding了
: 13 - 40 min:
|
l****6
发帖数: 1180 | |
f****4
发帖数: 1359 | 6 啥是 飘逸问题？
【在 S******a 的大作中提到】
: onsite跟谷歌差不多，
: 除去之前的参观等活动一共3个人，每人45min，基本纯做题
: 比谷歌简单，我是没有被问到DP, 更没有飘逸问题
:
: 又问了一点
: stream
: 了一下复
|
x****r
发帖数: 99 | 7 同问哈
不知道要不要准备design类的题目呢
【在 f****4 的大作中提到】
: 啥是 飘逸问题？
|
d*******8
发帖数: 785 | 8 Bless, 加油加油@@
又问了一点
stream
了一下复
【在 x****r 的大作中提到】
: 在fb主页申请的工作，之前第二面完发过一个帖 上周五facebook的第三轮面试
: 总共长度45分钟，约的是下午2点，因为他打电话迟了15分钟，3点他有会就结束了
: 0-10 min:
: 他先向我做了5分钟的自我介绍，讲了讲自己做的东西，然后叫我介绍一下自己，又问了一点
: 简历上的东西
: 11-13 min:
: 接下来就说会问一个分析的问题和一个coding的题目，然后问如何在一个无限长的stream
: 里面找到前1000大的，因为是非常常见的题目，就和他说了一下用min heap，分析了一下复
: 杂度，很快就进入coding了
: 13 - 40 min:
|
s*********e
发帖数: 36 | |
x****r
发帖数: 99 | |
|
|
t*******e
发帖数: 29 | |
K******g
发帖数: 1870 | 12 为什么找到前1000大的，用min heap？不是用max heap吗？
又问了一点
stream
了一下复
【在 x****r 的大作中提到】
: 在fb主页申请的工作，之前第二面完发过一个帖 上周五facebook的第三轮面试
: 总共长度45分钟，约的是下午2点，因为他打电话迟了15分钟，3点他有会就结束了
: 0-10 min:
: 他先向我做了5分钟的自我介绍，讲了讲自己做的东西，然后叫我介绍一下自己，又问了一点
: 简历上的东西
: 11-13 min:
: 接下来就说会问一个分析的问题和一个coding的题目，然后问如何在一个无限长的stream
: 里面找到前1000大的，因为是非常常见的题目，就和他说了一下用min heap，分析了一下复
: 杂度，很快就进入coding了
: 13 - 40 min:
|
b******v
发帖数: 1493 | 13 每次新来的元素和1000个里面最小的比较
【在 K******g 的大作中提到】
: 为什么找到前1000大的，用min heap？不是用max heap吗？
:
: 又问了一点
: stream
: 了一下复
|
s*********e
发帖数: 36 | 14 每来一个新数插入min heap， 再删掉min heap当前最小值（就是root），这样保证小
的数始终会被
排除。当所有的数都过一遍后，最后留在size 1000的min heap里的，就是最大的1000
个了
【在 K******g 的大作中提到】
: 为什么找到前1000大的，用min heap？不是用max heap吗？
:
: 又问了一点
: stream
: 了一下复
|
c****l
发帖数: 1280 | 15 飘逸问题?
【在 S******a 的大作中提到】
: onsite跟谷歌差不多，
: 除去之前的参观等活动一共3个人，每人45min，基本纯做题
: 比谷歌简单，我是没有被问到DP, 更没有飘逸问题
:
: 又问了一点
: stream
: 了一下复
|
g*********s
发帖数: 1782 | 16 引用：
simple regular expression match，可以match 的符号只有3种：
a-z : match a-z
. : match any
* : repeat 0 - arbitrary times
和没用过regex的同学解释一下 例如
a*b 可以match : b, ab, aab, aaaaaaaaaaab
b.*b 可以match : bb, bab, b12345b
public static bool IsMatch(char[] str, char[] pattern)
我用的是最笨的方法，扫描pattern，然后递归的match剩下的str和剩下的pattern
疑问：
这里"a-z"也是一种要处理的模式吗？比如说输入串可能是"[a-z]*"？如果这样好像麻
烦不少。
又问了一点
stream
了一下复
【在 x****r 的大作中提到】
: 在fb主页申请的工作，之前第二面完发过一个帖 上周五facebook的第三轮面试
: 总共长度45分钟，约的是下午2点，因为他打电话迟了15分钟，3点他有会就结束了
: 0-10 min:
: 他先向我做了5分钟的自我介绍，讲了讲自己做的东西，然后叫我介绍一下自己，又问了一点
: 简历上的东西
: 11-13 min:
: 接下来就说会问一个分析的问题和一个coding的题目，然后问如何在一个无限长的stream
: 里面找到前1000大的，因为是非常常见的题目，就和他说了一下用min heap，分析了一下复
: 杂度，很快就进入coding了
: 13 - 40 min:
|
j*****u
发帖数: 1133 | 17 写的比较乱，应该还有更clean的
static bool IsMatch(string str, string pattern)
{
if (str == null)
throw new ArgumentNullException("str");
if (string.IsNullOrEmpty(pattern))
throw new ArgumentException("pattern null or emptry.");
return MatchRec(str, pattern, 0, 0);
}
static bool MatchRec(string str, string pattern, int sIndex, int pIndex)
{
if (pIndex == pattern.Length)
{
return sIndex == str.Length;
}
char p = pattern[pIndex];
bool isStar = pIndex < pattern.Length - 1 && pattern[pIndex + 1] == '*';
int nextPIndex = isStar ? pIndex + 2 : pIndex + 1;
bool match; // whether or not current str-char matches current pattern-
char without star
if (sIndex == str.Length)
match = false;
else
{
char c = str[sIndex];
if (p >= 'a' && p <= 'z')
match = c == p;
else if (p == '.')
match = true;
else
throw new FormatException("Pattern in bad format.");
}
if (isStar)
{
if (match) // current match: move either p or s cursor
return MatchRec(str, pattern, sIndex, nextPIndex) || MatchRec(
str, pattern, sIndex + 1, pIndex);
else // current not match: move pattern cursor
return MatchRec(str, pattern, sIndex, nextPIndex);
}
else // must match current and must move both cursors.
return match && MatchRec(str, pattern, sIndex + 1, nextPIndex);
}
Test cases passed:
Debug.Assert(IsMatch("abc", "abc"));
Debug.Assert(!IsMatch("abc", "abcd"));
Debug.Assert(!IsMatch("abc", "abd"));
Debug.Assert(IsMatch("abc", "..."));
Debug.Assert(!IsMatch("abc", ".."));
Debug.Assert(IsMatch("b", "a*b"));
Debug.Assert(IsMatch("ab", "a*b"));
Debug.Assert(IsMatch("aab", "a*b"));
Debug.Assert(IsMatch("aaaaaaaaaab", "a*b"));
Debug.Assert(!IsMatch("aaaaaaaaaa", "a*b"));
Debug.Assert(!IsMatch("cb", "a*b"));
Debug.Assert(!IsMatch("aaaaaaaaaabc", "a*b"));
Debug.Assert(IsMatch("bb", "b.*b"));
Debug.Assert(IsMatch("bab", "b.*b"));
Debug.Assert(IsMatch("b12345b", "b.*b"));
Debug.Assert(IsMatch("", "a*b*c*"));
Debug.Assert(IsMatch("aaaa", "a*b*c*"));
Debug.Assert(IsMatch("bb", "a*b*c*"));
Debug.Assert(IsMatch("ccccc", "a*b*c*"));
Debug.Assert(!IsMatch("d", "a*b*c*")); |
c******n
发帖数: 4965 | 18 这个老题大家都说用min heap,
其实为啥不用最stupid 的插入呢？
反正1000 的size 是固定的， heap 跟array move 没有太大差别
1000
【在 s*********e 的大作中提到】
: 每来一个新数插入min heap， 再删掉min heap当前最小值（就是root），这样保证小
: 的数始终会被
: 排除。当所有的数都过一遍后，最后留在size 1000的min heap里的，就是最大的1000
: 个了
|
j*****u
发帖数: 1133 | 19 怎么array 插入？keep array sorted？
现在array里是1..1000
1001来了怎么办？
【在 c******n 的大作中提到】
: 这个老题大家都说用min heap,
: 其实为啥不用最stupid 的插入呢？
: 反正1000 的size 是固定的， heap 跟array move 没有太大差别
:
: 1000
|
q******8
发帖数: 848 | 20
又问了一点
stream
了一下复
请问lz是做了他们的puzzle才拿到面试的吗？
【在 x****r 的大作中提到】
: 在fb主页申请的工作，之前第二面完发过一个帖 上周五facebook的第三轮面试
: 总共长度45分钟，约的是下午2点，因为他打电话迟了15分钟，3点他有会就结束了
: 0-10 min:
: 他先向我做了5分钟的自我介绍，讲了讲自己做的东西，然后叫我介绍一下自己，又问了一点
: 简历上的东西
: 11-13 min:
: 接下来就说会问一个分析的问题和一个coding的题目，然后问如何在一个无限长的stream
: 里面找到前1000大的，因为是非常常见的题目，就和他说了一下用min heap，分析了一下复
: 杂度，很快就进入coding了
: 13 - 40 min:
|
|
|
l*****a
发帖数: 14598 | 21 别问了
楼主承诺的面经到现在还没问世呢
【在 q******8 的大作中提到】
:
: 又问了一点
: stream
: 了一下复
: 请问lz是做了他们的puzzle才拿到面试的吗？
|
g*********s
发帖数: 1782 | 22 13 - 40 min:
问了一道我没有准备过的coding题目，simple regular expression match，可以
match
的符号只有3种……
我研究了一下，似乎如果有*匹配的话，递归是不行的，需要自动机算法
。不知道你是怎么实现的？
又问了一点
stream
了一下复
【在 x****r 的大作中提到】
: 在fb主页申请的工作，之前第二面完发过一个帖 上周五facebook的第三轮面试
: 总共长度45分钟，约的是下午2点，因为他打电话迟了15分钟，3点他有会就结束了
: 0-10 min:
: 他先向我做了5分钟的自我介绍，讲了讲自己做的东西，然后叫我介绍一下自己，又问了一点
: 简历上的东西
: 11-13 min:
: 接下来就说会问一个分析的问题和一个coding的题目，然后问如何在一个无限长的stream
: 里面找到前1000大的，因为是非常常见的题目，就和他说了一下用min heap，分析了一下复
: 杂度，很快就进入coding了
: 13 - 40 min:
|
g*********s
发帖数: 1782 | 23 你能解释一下吗？太长了，也没看懂。
【在 j*****u 的大作中提到】
: 写的比较乱，应该还有更clean的
: static bool IsMatch(string str, string pattern)
: {
: if (str == null)
: throw new ArgumentNullException("str");
: if (string.IsNullOrEmpty(pattern))
: throw new ArgumentException("pattern null or emptry.");
: return MatchRec(str, pattern, 0, 0);
: }
: static bool MatchRec(string str, string pattern, int sIndex, int pIndex)
|
j********x
发帖数: 2330 | 24 这个是错误的
很简单的没有考虑回溯的情况
【在 j*****u 的大作中提到】
: 写的比较乱，应该还有更clean的
: static bool IsMatch(string str, string pattern)
: {
: if (str == null)
: throw new ArgumentNullException("str");
: if (string.IsNullOrEmpty(pattern))
: throw new ArgumentException("pattern null or emptry.");
: return MatchRec(str, pattern, 0, 0);
: }
: static bool MatchRec(string str, string pattern, int sIndex, int pIndex)
|
i*******s
发帖数: 558 | 25 I think it's right. Can you give counter examples to prove it wrong?
【在 j********x 的大作中提到】
: 这个是错误的
: 很简单的没有考虑回溯的情况
|
a******p
发帖数: 157 | 26 regular express = DFA,
DFA should solve it easily |
j********x
发帖数: 2330 | 27 我是错的
MatchRec(str, pattern, sIndex, nextPIndex) || MatchRec(
str, pattern, sIndex + 1, pIndex);
这里实际上枚举了所有可能的matching path
it wrong?
【在 i*******s 的大作中提到】
: I think it's right. Can you give counter examples to prove it wrong?
|
s******c
发帖数: 1920 | 28 请问，regex不会出现括号之类的吧？比如(ab)*a |
