m**********w
发帖数: 60 | 1 电面， 中国大哥， 问了一题，就是给read4k，实现read any bytes. 读大文件时如何
优化
onsite:
1， 美国人， 给一个词，判断是不是Palindome,
然后扩展问，给一个字典，找出所有对 单词，这两个单词可以组成一个palindom,
然后有问，可以组合任意个单词，怎么找到最长的可能的palindom
2, 中国大哥， 问了 permutation 和几种变体
3, 问现在的项目和resume
4, 美国人， 系统设计，设计各系统能返回 top 10 listened songs from your
friends.
今天收到据信，说coding可以，但是design没过。感谢FB的中国大哥，可惜自己能力有
限。 |
y***n
发帖数: 1594 | 2 read4k这题可不可讲一下，对我们这种文科生转行还是蛮难的。 |
z**a
发帖数: 69 | 3 Onsite 第一轮这题有什么好办法么，我只先到了brute force...而且任意个单词的时
候，如果有单词类似'a'这样的在字典里，那不是长度无上限了？ |
M*******a
发帖数: 1633 | |
M*******a
发帖数: 1633 | 5 比如bob这个词就可以 bobbobobobobobobob......bobob?
估计要规定不能重复用word。
或者就是所有找到的互为palindrome的word首尾相连就行了？
【在 z**a 的大作中提到】
: Onsite 第一轮这题有什么好办法么，我只先到了brute force...而且任意个单词的时
: 候，如果有单词类似'a'这样的在字典里，那不是长度无上限了？
|
z**a
发帖数: 69 | 6 应该是不能重复吧，不然第二问中找到的单词对就能组成无限长的palindrome string
了。
不过还是想不到有什么好办法啊。不知道LZ怎么回答的。
【在 M*******a 的大作中提到】
: 比如bob这个词就可以 bobbobobobobobobob......bobob?
: 估计要规定不能重复用word。
: 或者就是所有找到的互为palindrome的word首尾相连就行了？
|
M*******a
发帖数: 1633 | 7 所有找到的互为palindrome的word首尾相连就行了？
string
【在 z**a 的大作中提到】
: 应该是不能重复吧，不然第二问中找到的单词对就能组成无限长的palindrome string
: 了。
: 不过还是想不到有什么好办法啊。不知道LZ怎么回答的。
|
z**a
发帖数: 69 | 8 不一定要互为palindrome啊，“aba”，如果“a”，“ba“分别在字典里，他们的组合
也是合法的啊。 |
M*******a
发帖数: 1633 | 9 对我知道
可以再就是找一个word的reverse看是不是能有其他word组成，这就是常见的word
break面试题。
把word break和互为palindrome的联在一起就够长了吧
当然还有abcde, fghi, ihgfe, dcba的情况
【在 z**a 的大作中提到】
: 不一定要互为palindrome啊，“aba”，如果“a”，“ba“分别在字典里，他们的组合
: 也是合法的啊。
|
m**********w
发帖数: 60 | 10 一个单词只能用一次，
【在 z**a 的大作中提到】
: Onsite 第一轮这题有什么好办法么，我只先到了brute force...而且任意个单词的时
: 候，如果有单词类似'a'这样的在字典里，那不是长度无上限了？
|
|
|
M*******a
发帖数: 1633 | 11 您老这题怎么答得？
【在 m**********w 的大作中提到】
: 一个单词只能用一次，
|
m**********w
发帖数: 60 | 12 第二个问我说每两个单词连起来试下，他说要O(n)的，然后我说可以把所有单词建成个
Trie，然后在对把每个单词reverse 一下，去Trie找匹配的prefix, 如果找到并且剩下
的postfix还是palindorm就可以了，然后他说可以，就让我写了代码
至于第三问，我也没啥思路， 就说按刚才同样思路，找到一个prefix匹配后，拿剩下
的部分在去找，比如刚才那个例子，
abcde, fghi, ihgfe, dcba
dcba 匹配abcde, 还剩下e
fghi 匹配ihgfe, 也还剩下e，那然后这四个单词就可以连在一起了，就这样继续。
也没让写代码,
【在 M*******a 的大作中提到】
: 您老这题怎么答得？
|
f*****n
发帖数: 2126 | 13 居然还要system design。绝对无法过啊 |
j*****8
发帖数: 3635 | 14
这个剩下的postfix是什么意思？如果两个词可以组成palindorm的话，其中一个应该和
另外一个的reverse完全一样阿？
【在 m**********w 的大作中提到】
: 第二个问我说每两个单词连起来试下，他说要O(n)的，然后我说可以把所有单词建成个
: Trie，然后在对把每个单词reverse 一下，去Trie找匹配的prefix, 如果找到并且剩下
: 的postfix还是palindorm就可以了，然后他说可以，就让我写了代码
: 至于第三问，我也没啥思路， 就说按刚才同样思路，找到一个prefix匹配后，拿剩下
: 的部分在去找，比如刚才那个例子，
: abcde, fghi, ihgfe, dcba
: dcba 匹配abcde, 还剩下e
: fghi 匹配ihgfe, 也还剩下e，那然后这四个单词就可以连在一起了，就这样继续。
: 也没让写代码,
|
M*****D
发帖数: 22 | 15 设计各系统能返回 top 10 listened songs from your
friends.
这个设计题有什么好的思路吗。。
我的想法：需要在每个朋友的歌单里面建立一个已听歌曲的list，然后计数，然后当我
去那数据的时候，尝试合并相同歌曲的counter，然后按counter排列？
这样子的话会形成相当庞大的数据（不管是存在cache还是存在db里），因为每首歌在
每个朋友那儿都有instance，有更好的思路吗 |
m**********w
发帖数: 60 | 16 不一定要一样，比如 abcdefe 和 dcba 就是长度不一样，但连起来是palindorm
【在 j*****8 的大作中提到】
:
: 这个剩下的postfix是什么意思？如果两个词可以组成palindorm的话，其中一个应该和
: 另外一个的reverse完全一样阿？
|
r*******k
发帖数: 1423 | 17 干脆还是每个用户自己维护一个song的list
再维护一个朋友的song的list的aggregation
当用户播放一首歌，需要更新所有朋友的list
当两个人unfriend，自己的朋友list minus 朋友的自己的list
【在 M*****D 的大作中提到】
: 设计各系统能返回 top 10 listened songs from your
: friends.
: 这个设计题有什么好的思路吗。。
: 我的想法：需要在每个朋友的歌单里面建立一个已听歌曲的list，然后计数，然后当我
: 去那数据的时候，尝试合并相同歌曲的counter，然后按counter排列？
: 这样子的话会形成相当庞大的数据（不管是存在cache还是存在db里），因为每首歌在
: 每个朋友那儿都有instance，有更好的思路吗
|
c*******r
发帖数: 610 | 18 多谢分享。
f确实是不简单啊。
能不能问问你设计题到底怎么答的？是不是说对任何一个脸书用户，返回他／她朋友听
过歌曲的top 10啊？ 有哪些特殊的需求呢？ |
c*******r
发帖数: 610 | 19 第一题第二问不知道可不可以这么考虑：
给定任何一个单词，向左或者向右扩展，使得原单词本身变为一个palindrome，然后用
hash table检查向左或者向右插入的单词是否在字典里？ 如果原单词本身就已经是
palindrome了，那么就要特殊处理一下了。
不知道这题可不可以从这个里面学到点什么东西 ： http://www.quora.com/Algorithms/What-are-different-algorithm-for-converting-a-string-into-palindrome-string-except-appending-the-reverse-of-same-string-method
只是大概思路，请多讨论指教。
另外，read4k实现 read any bytes的思路到底是怎么搞的？ 这是老题，但是我是一头
雾水啊。多谢！ |
B***n
发帖数: 84 | 20 abcde 和 ffffedcba 可以组成 palindrom,
具体来说把ffffedcba reverse 得到 abcdeffff
然后在字典里找到abcde 剩下的postfix 就是 ffff, 是一个palindorm, 所以abcde 和
ffffedcba 可以组成 palindrom
【在 j*****8 的大作中提到】
:
: 这个剩下的postfix是什么意思？如果两个词可以组成palindorm的话，其中一个应该和
: 另外一个的reverse完全一样阿？
|
|
|
S******1
发帖数: 216 | 21 楼主这个面经我感觉电面我就挂了，
FB面试难度的variance很大啊！ |
t*******e
发帖数: 274 | 22 电面那题，网上看到一种解法，这是正解么？
我有点不明白的是假如只有200bytes, 通过read4096之后是不是应该返回200（<4096）
作为结果?
public class read_4096_bytes {
public int read4096(char[] buf) {
return 4096;
}
public int read(int n, char[] buf) {
int totalRead = 0;
for (int i = 0; i < n / 4096; ++i) {
char[] tbuf = new char[4096];
int tRead = read4096(tbuf);
totalRead += copyTo(buf, totalRead, tbuf, tRead);
if (tRead < 4096) {
return totalRead;
}
}
char[] tbuf = new char[4096];
int tRead = read4096(tbuf);
totalRead += copyTo(buf, totalRead, tbuf, Math.min(tRead, n % 4096));
return totalRead;
}
private int copyTo(char[] buf, int start, char[] tbuf, int num_read) {
for (int i = 0; i < num_read; ++i) {
buf[start + i] = tbuf[i];
}
return num_read;
}
} |
U***A
发帖数: 849 | |
m**********w
发帖数: 60 | 24 如果只读200byte，那么剩下的就要buffer起来等下次读
【在 t*******e 的大作中提到】
: 电面那题，网上看到一种解法，这是正解么？
: 我有点不明白的是假如只有200bytes, 通过read4096之后是不是应该返回200（<4096）
: 作为结果?
: public class read_4096_bytes {
: public int read4096(char[] buf) {
: return 4096;
: }
: public int read(int n, char[] buf) {
: int totalRead = 0;
: for (int i = 0; i < n / 4096; ++i) {
|
m**********w
发帖数: 60 | 25 我开始写的代码跟楼上的一个兄弟写的类似，就是总是先读到local buffer里再copy到
目标buffer里。
其实对于一次读很多byte的，比如read(4GB),只是最开始的一些bytes和结尾的bytes需
要通过local buffer转存下，其他的直接循环调用read4k直接读就行了。
当然他给我的函数原型都是用C写的，牵涉到buffer copy，不知道Java下是不是就没这
个问题了
【在 U***A 的大作中提到】
: read4K读打文件优化怎么搞？
|
U***A
发帖数: 849 | 26 那个palindome第三问怎么搞？很难想明白。 |
W*********y
发帖数: 481 | |
l********s
发帖数: 358 | 28 我随手写了点java code，不知道对不对，其实就是需要个4K bytes的临时buffer暂存
一下。
// Given read4K(char[] buffer)
int read(char[] array, int N) {
char[] buffer;
int start = 0;
int end = 0;
int p = 0;
array = new char[N];
while (N > 0) {
if (start == end) { // Read next 4K bytes
start = 0; end = read4K(buffer);
}
if (end == 0) break;
int size = Math.max(N, end - start);
for (; start < size; start++) array[p++] = buffer[i];
N -= size;
}
}
但我不理解楼主提到的大文件优化问题，楼主能不能展开说说。
【在 m**********w 的大作中提到】
: 如果只读200byte，那么剩下的就要buffer起来等下次读
|
l********s
发帖数: 358 | 29 对于onsite第一题，我的思路是：
1. Create a HashMap for dictionary.
2. for each word， find its palindrome substring started with, and check if
the reverse
of the rest substring exists in the HashMap
比如"cbcab"，它的starting palindrome substring是"cbc"，然后在dictionary里查
找"ba"。 |
s******i
发帖数: 236 | |
|
|
t*******e
发帖数: 274 | 31 总共只有200 bytes， 读完之后为什么还有剩下的？
【在 m**********w 的大作中提到】
: 如果只读200byte，那么剩下的就要buffer起来等下次读
|
m**********w
发帖数: 60 | 32 你这句：
array[p++] = buffer[start++];
假设N = 4GB, 那就是要把4GB内容先都拷贝到buffer, 然后再从buffer拷贝到array.
实际上不需要，大多数内容可以直接让read4k读到目标array里，不需要经过buffer，
减少一次memcpy.
【在 l********s 的大作中提到】
: 我随手写了点java code，不知道对不对，其实就是需要个4K bytes的临时buffer暂存
: 一下。
: // Given read4K(char[] buffer)
: int read(char[] array, int N) {
: char[] buffer;
: int start = 0;
: int end = 0;
: int p = 0;
: array = new char[N];
: while (N > 0) {
|
