z********i
发帖数: 568 | 1 第一次：
1)如何设计系统去处理很多的user requests。
2)implement LRU(least recently used) cache.
第二次：
1）1-100的整数，有一个数出现两次，其余的数出现一次。找到出现两次的那个数。
2）找到输入数组中所有的pair which sum up to a given value。要求考虑数重复
出现的情况。现在发现自己的程序有bug。
3）hashset vs. hashtable. 不熟悉，就回答了对hash的理解。
4) 从一个文件中找到给定的用户使用的API。文件格式如下：
user1 API1
user2 API3
user1 API2
总体感觉不难。对interviewers感觉比较舒服。希望能拿到onsite。 |
b***m
发帖数: 5987 | 2 没问题的。上次我把interviewer的题听错了都给onsite了……惭愧一个。 |
h****n
发帖数: 1093 | 3 第一次：
1)如何设计系统去处理很多的user requests。
cache，load balance？
2)implement LRU(least recently used) cache.
hash+doubly linked list？
第二次：
1）1-100的整数，有一个数出现一次，其余的数出现两次。找到仅出现一次的那个数。
XOR？
2）找到输入数组中所有的pair which sum up to a given value。要求考虑数重复
出现的情况。现在发现自己的程序有bug。
two pointers？
3）hashset vs. hashtable. 不熟悉，就回答了对hash的理解。
set没有value？
总体感觉不难。对interviewers感觉比较舒服。希望能拿到onsite。 |
h****n
发帖数: 1093 | 4 你是大牛。。。
【在 b***m 的大作中提到】
: 没问题的。上次我把interviewer的题听错了都给onsite了……惭愧一个。
|
b***m
发帖数: 5987 | 5
不是大牛，是RP爆发了。;-)
【在 h****n 的大作中提到】
: 你是大牛。。。
|
z********i
发帖数: 568 | 6 Offer?
【在 b***m 的大作中提到】
: 没问题的。上次我把interviewer的题听错了都给onsite了……惭愧一个。
|
b***m
发帖数: 5987 | 7
过完感恩节去onsite。
【在 z********i 的大作中提到】
: Offer?
|
z********i
发帖数: 568 | 8 1.1)cache, load balance. 我也回答了，但被追问怎么做load balance。最后用以前
router的记忆回答说router可以load balance to a server farm according to user
IP addresses.
1.2)Yes, hash+linked list。
2.1)可能记反了，xor好像不能用。题目可能是找到仅出现两次的那个数（其余的数仅
出现一次）。
2.2）我程序的bug是不能正确处理输入为k/2, k/2, ...,k/2 where k is the target
sum.
数。
【在 h****n 的大作中提到】
: 第一次：
: 1)如何设计系统去处理很多的user requests。
: cache，load balance？
: 2)implement LRU(least recently used) cache.
: hash+doubly linked list？
: 第二次：
: 1）1-100的整数，有一个数出现一次，其余的数出现两次。找到仅出现一次的那个数。
: XOR？
: 2）找到输入数组中所有的pair which sum up to a given value。要求考虑数重复
: 出现的情况。现在发现自己的程序有bug。
|
y********9
发帖数: 130 | |
s***y
发帖数: 203 | |
|
|
h****n
发帖数: 1093 | 11 必须是doubly linked list，否则无法在O（1）内做更新和删除操作
仅出现两次的话也一样做，因为数有范围，所以你把输入和1-100这些数做XOR，剩下的
那个数就是出现两次的数了
你这个bug是面试官指出来的么，因为2 sum题一般都是假设数都是不一样的
user
target
【在 z********i 的大作中提到】
: 1.1)cache, load balance. 我也回答了，但被追问怎么做load balance。最后用以前
: router的记忆回答说router可以load balance to a server farm according to user
: IP addresses.
: 1.2)Yes, hash+linked list。
: 2.1)可能记反了，xor好像不能用。题目可能是找到仅出现两次的那个数（其余的数仅
: 出现一次）。
: 2.2）我程序的bug是不能正确处理输入为k/2, k/2, ...,k/2 where k is the target
: sum.
:
: 数。
|
h****n
发帖数: 1093 | 12 如果是你说的那种极端情况，那么解应该有C（2，n）个，虽然这么多解都是一样的
【在 h****n 的大作中提到】
: 必须是doubly linked list，否则无法在O（1）内做更新和删除操作
: 仅出现两次的话也一样做，因为数有范围，所以你把输入和1-100这些数做XOR，剩下的
: 那个数就是出现两次的数了
: 你这个bug是面试官指出来的么，因为2 sum题一般都是假设数都是不一样的
:
: user
: target
|
z********i
发帖数: 568 | 13 上周4周5刚面完，还不知道有戏没有。
【在 s***y 的大作中提到】
: LZ2面完后几天才能收到通知啊？
|
z********i
发帖数: 568 | 14 这个有意思。doubly linked list可以O（1）内作删除吗？需要线性时间去找到要删除
的元素吧？
如果每个数都出现一次，这个方法可行。如果有的数没有出现，会有麻烦。我是用flag
数组作的。
Bug是我后来想到的。我没有用hash，是先sort，再用两个index一前一后开始找。
【在 h****n 的大作中提到】
: 必须是doubly linked list，否则无法在O（1）内做更新和删除操作
: 仅出现两次的话也一样做，因为数有范围，所以你把输入和1-100这些数做XOR，剩下的
: 那个数就是出现两次的数了
: 你这个bug是面试官指出来的么，因为2 sum题一般都是假设数都是不一样的
:
: user
: target
|
h****n
发帖数: 1093 | 15 4) 从一个文件中找到给定的用户使用的API。文件格式如下：
user1 API1
user2 API3
user1 API2
这个题要问清楚这个操作是一次调用还是多次调用吧。
一次调用的话，就遍历一下
要是多次调用的话，预处理做个hash表效率会高很多
【在 z********i 的大作中提到】
: 第一次：
: 1)如何设计系统去处理很多的user requests。
: 2)implement LRU(least recently used) cache.
: 第二次：
: 1）1-100的整数，有一个数出现两次，其余的数出现一次。找到出现两次的那个数。
: 2）找到输入数组中所有的pair which sum up to a given value。要求考虑数重复
: 出现的情况。现在发现自己的程序有bug。
: 3）hashset vs. hashtable. 不熟悉，就回答了对hash的理解。
: 4) 从一个文件中找到给定的用户使用的API。文件格式如下：
: user1 API1
|
h****n
发帖数: 1093 | 16 可以呵呵
用hash先找到object 的 reference
然后直接
obj->pre->next = obj->next;
obj->next->pre = obj->pre;
free(obj);
即可。
【在 z********i 的大作中提到】
: 这个有意思。doubly linked list可以O（1）内作删除吗？需要线性时间去找到要删除
: 的元素吧？
: 如果每个数都出现一次，这个方法可行。如果有的数没有出现，会有麻烦。我是用flag
: 数组作的。
: Bug是我后来想到的。我没有用hash，是先sort，再用两个index一前一后开始找。
|
z********i
发帖数: 568 | 17 grep "user1" a.log|cut -f 2 -d
【在 h****n 的大作中提到】
: 4) 从一个文件中找到给定的用户使用的API。文件格式如下：
: user1 API1
: user2 API3
: user1 API2
: 这个题要问清楚这个操作是一次调用还是多次调用吧。
: 一次调用的话，就遍历一下
: 要是多次调用的话，预处理做个hash表效率会高很多
|
h****n
发帖数: 1093 | 18 考shell script熟悉程度么
【在 z********i 的大作中提到】
: grep "user1" a.log|cut -f 2 -d
|
h****n
发帖数: 1093 | 19 如果那种极端情况，则解至少有C（2，n）=O(n^2)个，所以O（N）的算法肯定不行
当然了，如果要求相同结果只保存一个就好办了，O（n）那个算法也可以用，唯一的改
动就是遇到和前面相同的元素直接skip掉
flag
【在 z********i 的大作中提到】
: 这个有意思。doubly linked list可以O（1）内作删除吗？需要线性时间去找到要删除
: 的元素吧？
: 如果每个数都出现一次，这个方法可行。如果有的数没有出现，会有麻烦。我是用flag
: 数组作的。
: Bug是我后来想到的。我没有用hash，是先sort，再用两个index一前一后开始找。
|
z********i
发帖数: 568 | 20 I see. 强。当时闪了一下这个念头。但很不清楚，就放弃了。
【在 h****n 的大作中提到】
: 可以呵呵
: 用hash先找到object 的 reference
: 然后直接
: obj->pre->next = obj->next;
: obj->next->pre = obj->pre;
: free(obj);
: 即可。
|
|
|
z********i
发帖数: 568 | 21 大概这个组工作中会用一些命令吧。
【在 h****n 的大作中提到】
: 考shell script熟悉程度么
|
s*****n
发帖数: 994 | 22 1.2
class LRU{
hash_map m;
double_linked_list dll;
void add_new (T* t){
if (m.find(t) != m.end()){//already exists
Node * ptr = m[t];
if (ptr->prev)
ptr->prev->next = ptr->next;
if (ptr->next)
ptr->next->prev = ptr->prev;
ptr->next = dll.head;
dll.head = ptr;
}
//not in cache
ptr->next = dll.head;
dll.head = ptr;
Node* tail = dll.tail;
dll.tail = (dll.tail)->prev;
(dll.tail)->next = NULL;
tail.delete();
}
};
【在 z********i 的大作中提到】
: 第一次：
: 1)如何设计系统去处理很多的user requests。
: 2)implement LRU(least recently used) cache.
: 第二次：
: 1）1-100的整数，有一个数出现两次，其余的数出现一次。找到出现两次的那个数。
: 2）找到输入数组中所有的pair which sum up to a given value。要求考虑数重复
: 出现的情况。现在发现自己的程序有bug。
: 3）hashset vs. hashtable. 不熟悉，就回答了对hash的理解。
: 4) 从一个文件中找到给定的用户使用的API。文件格式如下：
: user1 API1
|
h*u
发帖数: 122 | |
l****p
发帖数: 397 | 24 即使没有重复数字，至少也得O(n*lg(n))吧？除非数组预先排好序
【在 h****n 的大作中提到】
: 如果那种极端情况，则解至少有C（2，n）=O(n^2)个，所以O（N）的算法肯定不行
: 当然了，如果要求相同结果只保存一个就好办了，O（n）那个算法也可以用，唯一的改
: 动就是遇到和前面相同的元素直接skip掉
:
: flag
|
h****n
发帖数: 1093 | 25 对的呵呵。。。要么就用hash好了
【在 l****p 的大作中提到】
: 即使没有重复数字，至少也得O(n*lg(n))吧？除非数组预先排好序
|
l****p
发帖数: 397 | 26 : 2）找到输入数组中所有的pair which sum up to a given value。要求考虑数重复
输入数组是排好序的还是无序的？
这些pair是要输出它们的值还是它们在原数组里的下标？ |
l****p
发帖数: 397 | 27 哦，对。如果没有重复，倒是可以用hash实现O(N)的算法
【在 h****n 的大作中提到】
: 对的呵呵。。。要么就用hash好了
|
x***a
发帖数: 29 | 28 记得150题上有类似的，删除用hash，linked list用来更新数据
flag
【在 z********i 的大作中提到】
: 这个有意思。doubly linked list可以O（1）内作删除吗？需要线性时间去找到要删除
: 的元素吧？
: 如果每个数都出现一次，这个方法可行。如果有的数没有出现，会有麻烦。我是用flag
: 数组作的。
: Bug是我后来想到的。我没有用hash，是先sort，再用两个index一前一后开始找。
|
