由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 狗家面经
相关主题
G家店面贡献1个A家3面的面经,被老印坑了
updae: 明天GOOG电面, 求祝福 interview 问题这题怎么做?
Facebook interview 面经[面试题求教]remove common phrases from each sentence
请教amazon面试题面试题讨论
问三道题四个月骑驴找马终于结束,发面经回馈本版
4sum的那道题这道Amazon面试题怎么做
请教leetcode的gray code问一个java的问题
Leetcode一题(非OJ)请教一个面试算法题
相关话题的讨论汇总
话题: int话题: list话题: intarraya话题: it1话题: it2
进入JobHunting版参与讨论
1 (共1页)
R*Q
发帖数: 179
1
还不知道结果,披个马甲攒人品吧
1. 二叉树的序列化和反序列化,节点的value是String类型
2. 找两个排好序的list的共同元素
5 -> 6 -> 6 ->8
4 -> 4-> 6 -> 6 -> 8
答案是 6 -> 6 -> 8
两个list长度差不多是怎么做? 长度相差非常大时如何做?
3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了(但还是一一对应),
但是单词的顺序没有改变,比如
cat
coffee
common
变成了
dkc
dbhhzz
dbllbq
让找出的这个替换的规则(guaranteed to have a unique one)
4. 二叉树找中序后继
设计一个算法,在分布式系统中拷贝某一个节点上的某一个文件到其他所有的节点上,
要考虑时间代价和fault tolerance
5. 给定两个list of integer,问是否他们是否互相是对方的一个从排列
follow up: 如果不停的有新的list of integer过来,问是否这一列数以前出现过。
怎么存储?怎么查询?复杂度?
c*****a
发帖数: 12
2
bless!

【在 R*Q 的大作中提到】
: 还不知道结果,披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化,节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做? 长度相差非常大时如何做?
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了(但还是一一对应),
: 但是单词的顺序没有改变,比如
: cat

l*****y
发帖数: 43
3
这么一比,我好弱啊。
t*********h
发帖数: 941
4
还行啊 非常reasonable

【在 R*Q 的大作中提到】
: 还不知道结果,披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化,节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做? 长度相差非常大时如何做?
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了(但还是一一对应),
: 但是单词的顺序没有改变,比如
: cat

M********g
发帖数: 131
5
请问是ONSITE吗?还是电面?
m**********e
发帖数: 22
6
第一和第二题知道怎么解,剩下几个还没有idea。可不可以讲讲3,4,5都怎么解的

【在 t*********h 的大作中提到】
: 还行啊 非常reasonable
p*****2
发帖数: 21240
7

第二题
(def a '(5 6 6 8))
(def b '(4 4 6 6 8))
(defn f [a, b, c]
(let [aa (first a) bb (first b)]
(if (and aa bb)
(cond
(< aa bb) (f (rest a) b c)
(> aa bb) (f a (rest b) c)
:default (f (rest a) b (cons aa c)))
c)))
(println (reverse (f a b ()) ))

【在 m**********e 的大作中提到】
: 第一和第二题知道怎么解,剩下几个还没有idea。可不可以讲讲3,4,5都怎么解的
w******j
发帖数: 185
8
不算太难
bless
p****o
发帖数: 46
9
cool. 什么编程语言?第二题, 上个c++:
using namespace std;
list intersect(list intList1, list intList2){
list::const_iterator it1 = intList1.begin();
list::const_iterator it2 = intList2.begin();
list intList3;
while((it1 != intList1.end()) && (it2 != intList2.end())) {
if (*it1 == *it2) {
intList3.push_back(*it1);
++it1;
++it2;
} else if (*it1 < *it2) {
++it1;
} else {
++it2;
}
}
return intList3;
}
};
// test case
int main()
{
int ints1[] = {5, 6, 6, 8};
int ints2[] = {4, 4, 6, 6, 8};
list list1 (ints1, ints1 + sizeof(ints1) / sizeof(int) );
list list2 (ints2, ints2 + sizeof(ints2) / sizeof(int) );
list list3 = intersect(list1, list2);
for(list::const_iterator it=list3.begin(); it!=list3.end(); ++it) {
cout << *it << endl;
}
}
第三题, 不知道有什么门道,按要求直接写了一个,不知道是不是太麻烦了
#include
#include
#include
using namespace std;
typedef map Table;
typedef list StrList;
typedef list::const_iterator ItList;
typedef string::iterator ItStr;
class Solution {
public:
Table findTable(StrList strList1, StrList strList2){
Table table;
for(ItList it1=strList1.begin(), it2=strList2.begin();
it1 != strList1.end(), it2 != strList2.end(); ++it1, ++it2) {
string str1 = *it1;
string str2 = *it2;
for(ItStr itstr1 = str1.begin(), itstr2 = str2.begin();
itstr1 != str1.end(), itstr2 != str2.end(); ++itstr1, ++
itstr2) {
table[*itstr1] = *itstr2;
}
}
return table;
}
};
// test case
int main()
{
Table table;
StrList strList1;
strList1.push_back("cat");
strList1.push_back("coffee");
strList1.push_back("common");
StrList strList2;
strList2.push_back("dkc");
strList2.push_back("dbhhzz");
strList2.push_back("dbllbq");
Solution s;
table = s.findTable(strList1, strList2);
for(Table::const_iterator it=table.begin();it!=table.end();++it) {
cout << it->first << "->" << it->second < }
}

【在 p*****2 的大作中提到】
:
: 第二题
: (def a '(5 6 6 8))
: (def b '(4 4 6 6 8))
: (defn f [a, b, c]
: (let [aa (first a) bb (first b)]
: (if (and aa bb)
: (cond
: (< aa bb) (f (rest a) b c)
: (> aa bb) (f a (rest b) c)

f*******b
发帖数: 520
10
第三题应该只给你变化后的字典吧。

【在 p****o 的大作中提到】
: cool. 什么编程语言?第二题, 上个c++:
: using namespace std;
: list intersect(list intList1, list intList2){
: list::const_iterator it1 = intList1.begin();
: list::const_iterator it2 = intList2.begin();
: list intList3;
: while((it1 != intList1.end()) && (it2 != intList2.end())) {
: if (*it1 == *it2) {
: intList3.push_back(*it1);
: ++it1;

相关主题
4sum的那道题贡献1个A家3面的面经,被老印坑了
请教leetcode的gray code这题怎么做?
Leetcode一题(非OJ)[面试题求教]remove common phrases from each sentence
进入JobHunting版参与讨论
s*w
发帖数: 729
11
这个第二题解的很棒,我记得在哪里看过一个差点的解法:先 merge 同时加一个标签
,然后再扫一遍,看相邻标签是否不一样
一个表很长,另一个很短的情况下,似乎该用 hash table(或者 bloom filter , 如
果能容忍少量错误) 存短表,扫描长表。有没有更好的办法?
第三题估计不是要求查表,是手动找规律

【在 p****o 的大作中提到】
: cool. 什么编程语言?第二题, 上个c++:
: using namespace std;
: list intersect(list intList1, list intList2){
: list::const_iterator it1 = intList1.begin();
: list::const_iterator it2 = intList2.begin();
: list intList3;
: while((it1 != intList1.end()) && (it2 != intList2.end())) {
: if (*it1 == *it2) {
: intList3.push_back(*it1);
: ++it1;

m**********e
发帖数: 22
12
第3,第4还是没有搞清怎么做。哪位大侠指点下?
第5题我写了一个C#的:
// Determine whether 2 arrays have the same elements with different
orders.
public bool CommonArray(int[] intArrayA, int[] intArrayB)
{
Dictionary dict = new Dictionary();
int n = intArrayA.Length;
int m = intArrayB.Length;
int i;
for (i = 0; i < n; ++i)
{
int value;
if (dict.TryGetValue(intArrayA[i], out value))
{
value++;
dict[intArrayA[i]] = value;
}
else
{
dict.Add(intArrayA[i], 1);
}
}
for (i = 0; i < m; ++i)
{
int value;
if (dict.TryGetValue(intArrayA[i], out value))
{
value--;
dict[intArrayA[i]] = value;
}
else
{
return false;
}
}
foreach (var item in dict)
{
if (item.Value != 0)
{
return false;
}
}
return true;
}

【在 s*w 的大作中提到】
: 这个第二题解的很棒,我记得在哪里看过一个差点的解法:先 merge 同时加一个标签
: ,然后再扫一遍,看相邻标签是否不一样
: 一个表很长,另一个很短的情况下,似乎该用 hash table(或者 bloom filter , 如
: 果能容忍少量错误) 存短表,扫描长表。有没有更好的办法?
: 第三题估计不是要求查表,是手动找规律

l*n
发帖数: 529
13
第三题,又见toposort。

【在 R*Q 的大作中提到】
: 还不知道结果,披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化,节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做? 长度相差非常大时如何做?
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了(但还是一一对应),
: 但是单词的顺序没有改变,比如
: cat

l*n
发帖数: 529
14
第二题除非是ArrayList,否则怎么搞都绕不过List的O(n)限制啊。

【在 R*Q 的大作中提到】
: 还不知道结果,披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化,节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做? 长度相差非常大时如何做?
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了(但还是一一对应),
: 但是单词的顺序没有改变,比如
: cat

e***s
发帖数: 799
15
马克
s*********g
发帖数: 3
16
学习学习
4
g*******n
发帖数: 214
17
lz,最后一题没理解,能不能举个例子?
谢谢

【在 R*Q 的大作中提到】
: 还不知道结果,披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化,节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做? 长度相差非常大时如何做?
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了(但还是一一对应),
: 但是单词的顺序没有改变,比如
: cat

m*******i
发帖数: 34
18
是不是先要得到 所有Orig[x]< Orig [y] 的matrix, 然后再根据 它建立一个
direct graph,
最后做top sort, 第一个是‘a', 第二个是’b', and so on?

【在 l*n 的大作中提到】
: 第三题,又见toposort。
m*******i
发帖数: 34
19
但是怎么来建matrix 和graph 比较effective呢? 不清楚

【在 m*******i 的大作中提到】
: 是不是先要得到 所有Orig[x]< Orig [y] 的matrix, 然后再根据 它建立一个
: direct graph,
: 最后做top sort, 第一个是‘a', 第二个是’b', and so on?

A***g
发帖数: 1816
20
这是电面?你牛啊,一个小时能做这么多题
相关主题
面试题讨论问一个java的问题
四个月骑驴找马终于结束,发面经回馈本版请教一个面试算法题
这道Amazon面试题怎么做脸家电话面试面筋
进入JobHunting版参与讨论
g*********e
发帖数: 14401
21
字典那题除了这个被改动的新字典,还有其他已知信息吗?
r******j
发帖数: 92
22
第五题可以先把每个list排序
a*****a
发帖数: 46
23
请问这个用toposort怎么解?能解释一下么?谢谢!

【在 l*n 的大作中提到】
: 第三题,又见toposort。
a*****a
发帖数: 46
24
4. 二叉树找中序后继
设计一个算法,在分布式系统中拷贝某一个节点上的某一个文件到其他所有的节点上,
要考虑时间代价和fault tolerance
这个是一个题还是两个题?
拷贝那个题,能用multicase么?
5. 给定两个list of integer,问是否他们是否互相是对方的一个从排列
follow up: 如果不停的有新的list of integer过来,问是否这一列数以前出现过。
怎么存储?怎么查询?复杂度?
还是不太明白“从排列”是怎么定义的。。。
1 2 3 4 和2 4,算从排列么?

【在 R*Q 的大作中提到】
: 还不知道结果,披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化,节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做? 长度相差非常大时如何做?
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了(但还是一一对应),
: 但是单词的顺序没有改变,比如
: cat

l*n
发帖数: 529
25
比如
cat
coffee
common
变成了
dkc
dbhhzz
dbllbq
那么就有k 需要你排出个“身高”顺序来。最小的就是a,最大的就是z。

【在 a*****a 的大作中提到】
: 请问这个用toposort怎么解?能解释一下么?谢谢!
d****n
发帖数: 233
26
Interesting, 可是原题好像没有说新的单词也是按原单词的顺序sort的呀?

【在 l*n 的大作中提到】
: 比如
: cat
: coffee
: common
: 变成了
: dkc
: dbhhzz
: dbllbq
: 那么就有k: 需要你排出个“身高”顺序来。最小的就是a,最大的就是z。

R*Q
发帖数: 179
27
因为签了NDA,题目不便说的太细,简要回答一下上面各楼的问题
.是onsite一共五轮
.第三题topological sort是正确的方向,楼上有版友已经给出了不错的解释
.语言其实无所谓,这些题没有什么语言相关的
.第五题的重排列就是说两列数除了顺序可能不同元素完全相同
.第四个没说清楚应该说是两道题,找中序后继要求写代码,设计算法那个不用

【在 R*Q 的大作中提到】
: 还不知道结果,披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化,节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做? 长度相差非常大时如何做?
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了(但还是一一对应),
: 但是单词的顺序没有改变,比如
: cat

p*****3
发帖数: 488
28

"两个排好序的list", 你确定是list不是array??
最后一题排序然后trie??

【在 R*Q 的大作中提到】
: 还不知道结果,披个马甲攒人品吧
: 1. 二叉树的序列化和反序列化,节点的value是String类型
: 2. 找两个排好序的list的共同元素
: 5 -> 6 -> 6 ->8
: 4 -> 4-> 6 -> 6 -> 8
: 答案是 6 -> 6 -> 8
: 两个list长度差不多是怎么做? 长度相差非常大时如何做?
: 3. 有一个字典因为某种原因每个字符都被替换成一个别的字符了(但还是一一对应),
: 但是单词的顺序没有改变,比如
: cat

p*****2
发帖数: 21240
29
第五题
(defn f [list1, list2]
(= (sort list1) (sort list2)))
(f '(1 3 2 4) '(2 4 1 3))
p*****2
发帖数: 21240
30
第五题第二问
(defn isPresent [lists, list]
(contains? lists (sort list)))
(defn add [lists, list]
(conj lists (sort list)))
相关主题
出一道我发明的题,难度算简单吧。updae: 明天GOOG电面, 求祝福 interview 问题
一道有关String的面试题Facebook interview 面经
G家店面请教amazon面试题
进入JobHunting版参与讨论
m**********e
发帖数: 22
31
你的第四个题还是没有明白什么意思。什么是二叉树找中序后序?是给一个二叉树,让
输出一个中序序列,还有再输出一个后序序列?
第四题设计算法的题你是怎么回答的?

【在 R*Q 的大作中提到】
: 因为签了NDA,题目不便说的太细,简要回答一下上面各楼的问题
: .是onsite一共五轮
: .第三题topological sort是正确的方向,楼上有版友已经给出了不错的解释
: .语言其实无所谓,这些题没有什么语言相关的
: .第五题的重排列就是说两列数除了顺序可能不同元素完全相同
: .第四个没说清楚应该说是两道题,找中序后继要求写代码,设计算法那个不用

s****n
发帖数: 70
32
排序的话代价略高了,如果用Hashmap来做的话是O(n)的,如果有很多很多的Incoming
list的话,最好的办法应该是先计算整个list的hash code(比如sha1, md5),效率高很多

【在 p*****2 的大作中提到】
: 第五题
: (defn f [list1, list2]
: (= (sort list1) (sort list2)))
: (f '(1 3 2 4) '(2 4 1 3))

l****o
发帖数: 315
33
第五题有什么理由不用minimum slide window吗?
a*****a
发帖数: 46
34
哦,明白了,多谢指点!我一开始忘记字典里词都是有序的。。。 -__-
这样确实是用toposort就可以解,也不需要旧词典信息。看了toposort还是很重要的,
需要仔细扣一下的呢。我还以为属于有点儿偏不太会考的呢。唉,学习无止境啊。

【在 l*n 的大作中提到】
: 比如
: cat
: coffee
: common
: 变成了
: dkc
: dbhhzz
: dbllbq
: 那么就有k: 需要你排出个“身高”顺序来。最小的就是a,最大的就是z。

a********9
发帖数: 129
35
原来如此!新词典也是排好了的!感谢!

【在 l*n 的大作中提到】
: 比如
: cat
: coffee
: common
: 变成了
: dkc
: dbhhzz
: dbllbq
: 那么就有k: 需要你排出个“身高”顺序来。最小的就是a,最大的就是z。

a********9
发帖数: 129
36
第一问数char的个数?
第二问先排序再放进hashtable?

【在 p*****2 的大作中提到】
: 第五题第二问
: (defn isPresent [lists, list]
: (contains? lists (sort list)))
: (defn add [lists, list]
: (conj lists (sort list)))

1 (共1页)
进入JobHunting版参与讨论
相关主题
请教一个面试算法题问三道题
脸家电话面试面筋4sum的那道题
出一道我发明的题,难度算简单吧。请教leetcode的gray code
一道有关String的面试题Leetcode一题(非OJ)
G家店面贡献1个A家3面的面经,被老印坑了
updae: 明天GOOG电面, 求祝福 interview 问题这题怎么做?
Facebook interview 面经[面试题求教]remove common phrases from each sentence
请教amazon面试题面试题讨论
相关话题的讨论汇总
话题: int话题: list话题: intarraya话题: it1话题: it2