logo
Redian新闻
>未名空间
>PDA - 掌中宝
>
中英混输语音输入那个个好
avatar
中英混输语音输入那个个好# PDA - 掌中宝
d*f
1 楼
是在电话的package里面还是单独一张卡？没找到，靠
avatar
s*y
2 楼
两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
但是还是悲剧了，anyway， move on了。 发一下记得的题目，
电面：
1. 给一个二叉树，返回它的镜像
实现一个 thread-safe blocking queue
2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
Onsite:
第一个: 给两个单词， 比如head, tail: 找到一个最短的转换，从head到tail，每
次只能变一个字母，path上的word都必须是有效的英文单词，我用的Graph shortest
path
第二个: memcpy: 源区域和目标区域可能有重叠
BST 插入和删除操作实现
BST iterator 实现
3: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
4: Given a social graph, find if there is a path between two persons with at
most 2 steps (3rd level connection), how to handle it in distributed way (
large graph stored at a large number of nodes, minimize cross-communication)

5: 设计题: a restful server with 4GB,
given a request such as: http://seq=4?len=60?xxxxdata
the system will store the binary data with that sequence number.
given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.
multiple clients calling simutaneous
what data structure, concurrency, locking, etc..
avatar
l*s
3 楼
rt
avatar
w*o
4 楼

单独的一张卡

【在 d********f 的大作中提到】
: 是在电话的package里面还是单独一张卡？没找到，靠
avatar
l*h
5 楼
多谢分享，听说现在onsite直接用电脑写程序了？
avatar
c*s
6 楼
Touchpal?
avatar
d*f
7 楼
我靠，不在里面怎么办？

【在 w******o 的大作中提到】
:
: 单独的一张卡
avatar
a*o
8 楼
h2o怎么做的?

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
w*o
9 楼
call it

【在 d********f 的大作中提到】
: 我靠，不在里面怎么办？
avatar
w*x
10 楼
答得不错啊，怎么也给据了？
avatar
s*y
11 楼
没有，我是在白板上写的~

【在 l**h 的大作中提到】
: 多谢分享，听说现在onsite直接用电脑写程序了？
avatar
s*y
12 楼
我也不是很清楚，面试官当场给的反馈大多都还比较positive，可能code写的不是很
clean，我在白板上写的可能有点乱，或是设计题答得他们不是太满意。

【在 w****x 的大作中提到】
: 答得不错啊，怎么也给据了？
avatar
s*y
13 楼
这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
H线程和1个O线程
class h20{
int numOfH, numOfO;
int mutexO, mutexH;
public void H(){
synchronized(this){
if(++numOfH >= 2 && numOfO >= 1) {
mutexO += 1;
mutexH += 2;
numOfH -= 2;
numOfO -= 1;
this.notifyAll();
}
while(mutexH <= 0) {
this.wait();
}
mutexH--;
}
}
public void O(){
synchronized(this){
if(++numOfO >= 1 && numOfH >= 2) {
mutexO += 1;
mutexH += 2;
numOfH -= 2;
numOfO -= 1;
this.notifyAll();
}
while(mutexO <= 0) {
this.wait();
}
mutexO--;
}
}
}

【在 a***o 的大作中提到】
: h2o怎么做的?
avatar
r*i
14 楼
谢谢分享，对我来说，题目都不简单啊。
avatar
w*x
15 楼

不同公司bar真的太不一样了。
我一朋友面Intuit， 3个onsite面试一行代码都没要写就过了。
不过她以前在国内做空姐的...

【在 s******y 的大作中提到】
: 我也不是很清楚，面试官当场给的反馈大多都还比较positive，可能code写的不是很
: clean，我在白板上写的可能有点乱，或是设计题答得他们不是太满意。
avatar
M*5
16 楼
非常感谢！学习了。。。

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
l*h
17 楼
设计题你怎么做的，需要考虑的东西很多。还有，url里面根本就不能放binary data吧？

【在 s******y 的大作中提到】
: 我也不是很清楚，面试官当场给的反馈大多都还比较positive，可能code写的不是很
: clean，我在白板上写的可能有点乱，或是设计题答得他们不是太满意。
avatar
d*x
18 楼
base 64 or just percent encoding

吧？

【在 l**h 的大作中提到】
: 设计题你怎么做的，需要考虑的东西很多。还有，url里面根本就不能放binary data吧？
avatar
s*y
19 楼
呵呵，人家这先天条件是我这等wsn没法比的。
开个玩笑，你朋友肯定有其他过人之处。
年轻的时候觉得会写几行代码很厉害，现在自己觉得有太多的东西比技术重要的多

【在 w****x 的大作中提到】
:
: 不同公司bar真的太不一样了。
: 我一朋友面Intuit， 3个onsite面试一行代码都没要写就过了。
: 不过她以前在国内做空姐的...
avatar
k*x
20 楼
qiu pp

【在 w****x 的大作中提到】
:
: 不同公司bar真的太不一样了。
: 我一朋友面Intuit， 3个onsite面试一行代码都没要写就过了。
: 不过她以前在国内做空姐的...
avatar
f*t
21 楼
觉得不太对。synchronized method只允许一个instance吧，这样你怎么让两个H()同时
执行？

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
y*g
22 楼
mobile 有一轮是

【在 l**h 的大作中提到】
: 多谢分享，听说现在onsite直接用电脑写程序了？
avatar
s*y
23 楼
调用 this.wait() 时 java 会自动unlock， 等wait返回时，会require lock again
， 所以在当前线程sleep期间，其它线程是可以进来的。
这是我对java wait() 函数的理解，难道不对？

【在 f*******t 的大作中提到】
: 觉得不太对。synchronized method只允许一个instance吧，这样你怎么让两个H()同时
: 执行？
avatar
h*i
24 楼
这个你倒是对的，但是程序还是不对numOfH,还有numOfO就看见减了，都没有加的地方。

again

【在 s******y 的大作中提到】
: 调用 this.wait() 时 java 会自动unlock， 等wait返回时，会require lock again
: ， 所以在当前线程sleep期间，其它线程是可以进来的。
: 这是我对java wait() 函数的理解，难道不对？
avatar
f*t
25 楼
用两个semaphore能完美解决这个问题吧，不用写这么复杂的程序

again

【在 s******y 的大作中提到】
: 调用 this.wait() 时 java 会自动unlock， 等wait返回时，会require lock again
: ， 所以在当前线程sleep期间，其它线程是可以进来的。
: 这是我对java wait() 函数的理解，难道不对？
avatar
d*x
26 楼
我觉得得用多个。
如果只是将O作为consumer，H作为producer的话，O() {P(H); P(H); V(useH); V(useH
);}貌似会引起饥饿，设想两个O()都等在第2个P(H)上。。。其实H的量是足够的
我能想到的办法是加一个线程作为consumer，每次consume两个H和一个O

【在 f*******t 的大作中提到】
: 用两个semaphore能完美解决这个问题吧，不用写这么复杂的程序
:
: again
avatar
Y*f
27 楼
BST 添加和删除要保持平衡吗？

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
l*a
28 楼
先存后看
bless

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
f*t
29 楼
我又看错题了。。。

useH

【在 d**********x 的大作中提到】
: 我觉得得用多个。
: 如果只是将O作为consumer，H作为producer的话，O() {P(H); P(H); V(useH); V(useH
: );}貌似会引起饥饿，设想两个O()都等在第2个P(H)上。。。其实H的量是足够的
: 我能想到的办法是加一个线程作为consumer，每次consume两个H和一个O
avatar
P*b
30 楼
多线程那道，那个大侠给来个C++的？

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
d*x
31 楼
H2O那个我写了个C的。可以改吧改吧加上对各种原子的计数。
编译的时候别忘了 -lpthread !
#include
#include
#include
#include
#include
#include
sem_t availH;
sem_t availO;
sem_t usedH;
sem_t usedO;
void* H(void*) {
sem_post(&availH);
sem_wait(&usedH);
fprintf(stderr, "H consumed.\n");
pthread_detach(pthread_self());
return NULL;
}
void* O(void*) {
sem_post(&availO);
sem_wait(&usedO);
fprintf(stderr, "O consumed.\n");
pthread_detach(pthread_self());
return NULL;
}
void* H2O(void*) {
while(1) {
sem_wait(&availO);
sem_wait(&availH);
sem_wait(&availH);

sem_post(&usedO);
sem_post(&usedH);
sem_post(&usedH);

fprintf(stderr, "H2O created.\n");
}
return NULL;
}
int main() {
sem_init(&availH, 0, 0);
sem_init(&availO, 0, 0);
sem_init(&usedH, 0, 0);
sem_init(&usedO, 0, 0);
pthread_t consumer_id;
pthread_create(&consumer_id, NULL, H2O, NULL);
while(1) {
int p = rand() % 3;
if (p == 0) {
pthread_t o_id;
pthread_create(&o_id, NULL, O, NULL);
} else {
pthread_t h_id;
pthread_create(&h_id, NULL, H, NULL);
}
}

return 0;
}

【在 P*******b 的大作中提到】
: 多线程那道，那个大侠给来个C++的？
avatar
s*y
32 楼
不需要，就是最简单的bst 插入删除

【在 Y********f 的大作中提到】
: BST 添加和删除要保持平衡吗？
avatar
w*x
33 楼

bst删除非常tricky啊，楼主能写对证明功底不错

【在 s******y 的大作中提到】
: 不需要，就是最简单的bst 插入删除
avatar
g*e
34 楼
用两个queue。调用H和O的直接enqueue。另起一个consumer thread，每次enqueue都
triger consumer thread，如果HQ.size>2, OQueue.size>1, 从H queue拿两个，O
queue拿一个，返回。
扩展到多个consumer thread的情况，三个方法：
1. 如果不够2H 1O就丢回queue里去。效率不高，容易造成live lock
2. 加个锁，每次保证只有一个consumer从两个queue里面取。同样，效率不高
3. 整个scheduling thread, monitor两个queue的size，达到至少2H 1O就triger一个
consumer去干活。缺点: single point of failure，当然这个好解决。

useH

【在 d**********x 的大作中提到】
: 我觉得得用多个。
: 如果只是将O作为consumer，H作为producer的话，O() {P(H); P(H); V(useH); V(useH
: );}貌似会引起饥饿，设想两个O()都等在第2个P(H)上。。。其实H的量是足够的
: 我能想到的办法是加一个线程作为consumer，每次consume两个H和一个O
avatar
P*b
35 楼
恩。这个方法不错

【在 g**e 的大作中提到】
: 用两个queue。调用H和O的直接enqueue。另起一个consumer thread，每次enqueue都
: triger consumer thread，如果HQ.size>2, OQueue.size>1, 从H queue拿两个，O
: queue拿一个，返回。
: 扩展到多个consumer thread的情况，三个方法：
: 1. 如果不够2H 1O就丢回queue里去。效率不高，容易造成live lock
: 2. 加个锁，每次保证只有一个consumer从两个queue里面取。同样，效率不高
: 3. 整个scheduling thread, monitor两个queue的size，达到至少2H 1O就triger一个
: consumer去干活。缺点: single point of failure，当然这个好解决。
:
: useH
avatar
b*m
36 楼
少了个判断，被唤醒后还要在看一下
是不是＜0

：我也不是很清楚，面试官当场给的反馈大多都还比较positive，可能code写的不是很
：clean，我在白板上写的可能有点乱，或是设计题答得他们不是太满意。
：
：【 在 wwwyhx (wwwyhx) 的大作中提到: 】
：: 答得不错啊，怎么也给据了？
：
：
……

【在 s******y 的大作中提到】
: 不需要，就是最简单的bst 插入删除
avatar
w*r
37 楼
two semaphores 就够了吧
#include
#include
#include
class sem {
boost::mutex guard;
int c ;
public:
sem() : c(0) {}
void V ( int n = 1 ) {
boost::mutex::scoped_lock lock(guard);
c = c + n;
}
void P ( int n = 1) {
while ( c < n ) ;
boost::mutex::scoped_lock lock(guard);
c = c - n;
}

};
sem semh;
sem semo;
class H{
public:
void operator()() {
std::cout << "create H thread \n";
sleep(random()%10);
semh.V( 1 );
semo.P( 1 ) ;
}
};
class O{
public:
void operator()(){
std::cout << "create O thread \n";
sleep(random()%10);
semh.P( 2 ) ;
semo.V( 2 ) ;
std::cout << "got one H2O \n";
}
};
int main(){
H h[200];
O o[100];
std::vector < boost::thread* > v ;
for ( int i = 0 ; i<100; i++ ) {
v.push_back(new boost::thread ( h[i*2] )) ;
v.push_back(new boost::thread ( h[i*2+1] )) ;
v.push_back(new boost::thread ( o[i] ) );
}
for ( std::vector::iterator it = v.begin(); it != v.end(
); it++){
(*it)->join();
delete (*it);
}

}
avatar
e*s
38 楼
问个很弱的问题,blocking queue不是就已经thread-safe吗? 怎么实现thread-safe
blocking queue?
找到下面JAVA代码,好像很标准的样子.
public class BlockingQueue {
private List queue = new LinkedList();
private int limit = 10;
public BlockingQueue(int limit){
this.limit = limit;
}
public synchronized void enqueue(Object item)
throws InterruptedException {
while(this.queue.size() == this.limit) {
wait();
}
if(this.queue.size() == 0) {
notifyAll();
}
this.queue.add(item);
}
public synchronized Object dequeue()
throws InterruptedException{
while(this.queue.size() == 0){
wait();
}
if(this.queue.size() == this.limit){
notifyAll();
}
return this.queue.remove(0);
}
}
avatar
x*0
39 楼
mark
avatar
b*e
40 楼
没关系。我跟你讲，L是个印窝。去了也没意思。你这个面试的是什么？至少是
Principal Engineer。我很负责任的告诉你，LinkedIn所有的Engineer加一起，顶多有
1%能把这些题全做出来，那还是可劲往高里说的。你要是真觉得这些题都不难，F/G那
是刚刚的。你这个纯粹是被黑了。术业有专攻，你这篇里什么都有，数据结构，算法，
并行，系统，汇编。干屁呢。你真找一工作，在今后的三年里你八成连双重循环都用不
上。Mark my words.

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
s*y
41 楼
是这个意思，面试官就是强调一下我实现的这个queue要保证thread-safe

【在 e***s 的大作中提到】
: 问个很弱的问题,blocking queue不是就已经thread-safe吗? 怎么实现thread-safe
: blocking queue?
: 找到下面JAVA代码,好像很标准的样子.
: public class BlockingQueue {
: private List queue = new LinkedList();
: private int limit = 10;
: public BlockingQueue(int limit){
: this.limit = limit;
: }
: public synchronized void enqueue(Object item)
avatar
s*y
42 楼
多谢安慰~

【在 b***e 的大作中提到】
: 没关系。我跟你讲，L是个印窝。去了也没意思。你这个面试的是什么？至少是
: Principal Engineer。我很负责任的告诉你，LinkedIn所有的Engineer加一起，顶多有
: 1%能把这些题全做出来，那还是可劲往高里说的。你要是真觉得这些题都不难，F/G那
: 是刚刚的。你这个纯粹是被黑了。术业有专攻，你这篇里什么都有，数据结构，算法，
: 并行，系统，汇编。干屁呢。你真找一工作，在今后的三年里你八成连双重循环都用不
: 上。Mark my words.
avatar
e*s
43 楼
楼主，能不能给一下这题的code
第一个: 给两个单词， 比如head, tail: 找到一个最短的转换，从head到tail，每
次只能变一个字母，path上的word都必须是有效的英文单词，我用的Graph shortest
path
avatar
b*n
44 楼
感觉在硅谷去哪都是印窝 还是找个钱多的实际 可惜FLG都进不去
avatar
f*t
45 楼
leetcode word ladder

【在 e***s 的大作中提到】
: 楼主，能不能给一下这题的code
: 第一个: 给两个单词， 比如head, tail: 找到一个最短的转换，从head到tail，每
: 次只能变一个字母，path上的word都必须是有效的英文单词，我用的Graph shortest
: path
avatar
b*f
46 楼
写了个H2O Java的，不知道对不对，大家帮忙看看
h_count = 0;
void H() {
synchronized(h_count) {
h_count++;
if(h_count == 2) {
h_sem.release();
h_count = 0;
}
}
o_sem.acquire();
}
void O() {
h_sem.acquire();
o_sem.release(2);
}
avatar
c*t
47 楼
多谢！以你的水平，offer 很快回来的。
求问如何每次只唤醒2个H线程和1个O线程？java has no way to wake up or notify a
specific thread.

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
s*y
48 楼
object.notify() 好像就是每次只唤醒一个在这个object上wait的线程，但是不保证那
个线程被唤醒。 我当时的思路是定义两个object, H和O线程wait 在不同的object上，
这样就可以notify两次H和一次O了。 当时面试官说这种方法可以的， 哎，

a

【在 c********t 的大作中提到】
: 多谢！以你的水平，offer 很快回来的。
: 求问如何每次只唤醒2个H线程和1个O线程？java has no way to wake up or notify a
: specific thread.
avatar
c*t
49 楼
嗯，明白了，多谢！

【在 s******y 的大作中提到】
: object.notify() 好像就是每次只唤醒一个在这个object上wait的线程，但是不保证那
: 个线程被唤醒。 我当时的思路是定义两个object, H和O线程wait 在不同的object上，
: 这样就可以notify两次H和一次O了。 当时面试官说这种方法可以的， 哎，
:
: a
avatar
c*t
50 楼
实测了一下这个方法，好像不行哦

【在 s******y 的大作中提到】
: object.notify() 好像就是每次只唤醒一个在这个object上wait的线程，但是不保证那
: 个线程被唤醒。 我当时的思路是定义两个object, H和O线程wait 在不同的object上，
: 这样就可以notify两次H和一次O了。 当时面试官说这种方法可以的， 哎，
:
: a
avatar
l*h
51 楼
实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
写了个Java版本的，大家指教:
import java.util.*;
import java.util.concurrent.*;
public class ThreadH2OSema {
private final Semaphore hCalled = new Semaphore(0);
private final Semaphore hUsed = new Semaphore(0);
private final Semaphore oCalled = new Semaphore(0);
private final Semaphore oUsed = new Semaphore(0);
public void H() {
try {
hCalled.release();
System.out.println("One H created");
hUsed.acquire();
}
catch(InterruptedException e) {
System.out.println("Interrupted..");
}
}
public void O() {
try {
oCalled.release();
System.out.println("One O created");
oUsed.acquire();
}
catch(InterruptedException e) {
System.out.println("Interrupted..");
}
}
public void H2O() {
int i = 1;
while(true) {
try {
hCalled.acquire(2);
oCalled.acquire(1);
hUsed.release(2);
oUsed.release(1);
System.out.println(i + " H2O created..");
i++;
}
catch(InterruptedException e) {
System.out.println("Interrupted..");
break;
}
}
}
private static class Caller extends Thread {
private ThreadH2OSema h2o;
public Caller(ThreadH2OSema h2o) {
this.h2o = h2o;
}
public void run() {
Random r = new Random();
// Call H() or O() randomly
if (r.nextBoolean()) h2o.H();
else h2o.O();
}
}

private static class Creator extends Thread {
private ThreadH2OSema h2o;
public Creator(ThreadH2OSema h2o) {
this.h2o = h2o;
}
public void run() {
h2o.H2O();
}
}
public static void main(String[] args) {
ThreadH2OSema h2o = new ThreadH2OSema();
Thread creator = new Creator(h2o);
creator.start();

Thread[] threads = new Thread[3];
for (int i = 0; i < threads.length; i++) {
threads[i] = new Caller(h2o);
threads[i].start();
}
try {
for (int i = 0; i < threads.length; i++) {
threads[i].join();
}
}
catch(InterruptedException e) {
System.out.println("Interrupted..");
}
}
}
avatar
p*p
52 楼
这只要在notify外面套上synchronized就行了

object

【在 c********t 的大作中提到】
: 实测了一下这个方法，好像不行哦
avatar
c*t
53 楼
en, 这个好，用semaphore，一个线程专门负责检测semaphore来create h2o, 是不是像
observer？

【在 l**h 的大作中提到】
: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
: ，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
: call O的线程返回（产生一个水分子），其他的都block。
: 写了个Java版本的，大家指教:
: import java.util.*;
: import java.util.concurrent.*;
: public class ThreadH2OSema {
: private final Semaphore hCalled = new Semaphore(0);
: private final Semaphore hUsed = new Semaphore(0);
: private final Semaphore oCalled = new Semaphore(0);
avatar
c*t
54 楼
不懂，不是一个object, synchronized有什么用？而且本来notify就在synchronized
block里。能不能给个简单的codes?
多谢！

【在 p*****p 的大作中提到】
: 这只要在notify外面套上synchronized就行了
:
: object
avatar
p*2
55 楼

LZ的这个程序如果有H1, O threads, 然后进入H2
H2 notify H1 and O then wait. 是不是这个样子的？这样就没有产生H2O

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
p*2
56 楼

貌似原题要求只有两种threads？

【在 g**e 的大作中提到】
: 用两个queue。调用H和O的直接enqueue。另起一个consumer thread，每次enqueue都
: triger consumer thread，如果HQ.size>2, OQueue.size>1, 从H queue拿两个，O
: queue拿一个，返回。
: 扩展到多个consumer thread的情况，三个方法：
: 1. 如果不够2H 1O就丢回queue里去。效率不高，容易造成live lock
: 2. 加个锁，每次保证只有一个consumer从两个queue里面取。同样，效率不高
: 3. 整个scheduling thread, monitor两个queue的size，达到至少2H 1O就triger一个
: consumer去干活。缺点: single point of failure，当然这个好解决。
:
: useH
avatar
p*2
57 楼

貌似不行吧？

【在 b*******f 的大作中提到】
: 写了个H2O Java的，不知道对不对，大家帮忙看看
: h_count = 0;
: void H() {
: synchronized(h_count) {
: h_count++;
: if(h_count == 2) {
: h_sem.release();
: h_count = 0;
: }
: }
avatar
p*2
58 楼

用两个Condition是不是一样的？

【在 s******y 的大作中提到】
: object.notify() 好像就是每次只唤醒一个在这个object上wait的线程，但是不保证那
: 个线程被唤醒。 我当时的思路是定义两个object, H和O线程wait 在不同的object上，
: 这样就可以notify两次H和一次O了。 当时面试官说这种方法可以的， 哎，
:
: a
avatar
p*2
59 楼

好像是有这个问题。看来还是得用Condition吧？

【在 c********t 的大作中提到】
: 不懂，不是一个object, synchronized有什么用？而且本来notify就在synchronized
: block里。能不能给个简单的codes?
: 多谢！
avatar
p*2
60 楼

按照原题的意思好像只能由H，O两个method的吧？

【在 c********t 的大作中提到】
: en, 这个好，用semaphore，一个线程专门负责检测semaphore来create h2o, 是不是像
: observer？
avatar
o*d
61 楼
看过去比较清晰

【在 d**********x 的大作中提到】
: H2O那个我写了个C的。可以改吧改吧加上对各种原子的计数。
: 编译的时候别忘了 -lpthread !
: #include
: #include
: #include
: #include
: #include
: #include
: sem_t availH;
: sem_t availO;
avatar
M*k
62 楼
面试模特？？

【在 w****x 的大作中提到】
:
: bst删除非常tricky啊，楼主能写对证明功底不错
avatar
o*d
63 楼
mark

【在 l**h 的大作中提到】
: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
: ，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
: call O的线程返回（产生一个水分子），其他的都block。
: 写了个Java版本的，大家指教:
: import java.util.*;
: import java.util.concurrent.*;
: public class ThreadH2OSema {
: private final Semaphore hCalled = new Semaphore(0);
: private final Semaphore hUsed = new Semaphore(0);
: private final Semaphore oCalled = new Semaphore(0);
avatar
m*n
64 楼
Your code can be improved in several ways
- The two methods H() and O() are almost symmetric. A single reusable code
segment would look better.
- This can be implemented with two atomicintegers. Synchronized is too heavy
weight
- Use SynchronousQueue or your own Queue for releasing threads. Notify(All)
does not protect against starvation

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
c*t
65 楼
二爷，那如果只能用两个method, 有java解法了吗？

【在 p*****2 的大作中提到】
:
: 按照原题的意思好像只能由H，O两个method的吧？
avatar
c*m
66 楼
最后那个系统设计题，能有大牛给个意见吗？
avatar
a*e
67 楼
请问 3-step connection是怎么做的？

【在 s******y 的大作中提到】
: 不需要，就是最简单的bst 插入删除
avatar
f*m
68 楼
那位大俠能給個下面两题的解法？
2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
我的想法：
（1）HashMap里装的value type是一个class,这个class的member包括elementhe 和map。
（2）HashMap里装的value type是一个指针，这个指针的类型可以是elementhe 或map
。不过不太确定如何转化指针类型。
4: Given a social graph, find if there is a path between two persons with at
most 2 steps (3rd level connection), how to handle it in distributed way (
large graph stored at a large number of nodes, minimize cross-communication)
我的想法：
把原social graph分块，从弱的edge切开？
多谢。

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
l*a
69 楼
这种题一般都是两个iterator吧。
第一个Iterator用于外层,第二个用于内层。注意第二层是element或者empty map的情
况即可

map。
map
at

【在 f*********m 的大作中提到】
: 那位大俠能給個下面两题的解法？
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: 我的想法：
: （1）HashMap里装的value type是一个class,这个class的member包括elementhe 和map。
: （2）HashMap里装的value type是一个指针，这个指针的类型可以是elementhe 或map
: 。不过不太确定如何转化指针类型。
: 4: Given a social graph, find if there is a path between two persons with at
: most 2 steps (3rd level connection), how to handle it in distributed way (
avatar
s*y
70 楼
两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
但是还是悲剧了，anyway， move on了。 发一下记得的题目，
电面：
1. 给一个二叉树，返回它的镜像
实现一个 thread-safe blocking queue
2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
Onsite:
第一个: 给两个单词， 比如head, tail: 找到一个最短的转换，从head到tail，每
次只能变一个字母，path上的word都必须是有效的英文单词，我用的Graph shortest
path
第二个: memcpy: 源区域和目标区域可能有重叠
BST 插入和删除操作实现
BST iterator 实现
3: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
4: Given a social graph, find if there is a path between two persons with at
most 2 steps (3rd level connection), how to handle it in distributed way (
large graph stored at a large number of nodes, minimize cross-communication)

5: 设计题: a restful server with 4GB,
given a request such as: http://seq=4?len=60?xxxxdata
the system will store the binary data with that sequence number.
given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.
multiple clients calling simutaneous
what data structure, concurrency, locking, etc..
avatar
l*h
71 楼
多谢分享，听说现在onsite直接用电脑写程序了？
avatar
a*o
72 楼
h2o怎么做的?

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
w*x
73 楼
答得不错啊，怎么也给据了？
avatar
s*y
74 楼
没有，我是在白板上写的~

【在 l**h 的大作中提到】
: 多谢分享，听说现在onsite直接用电脑写程序了？
avatar
s*y
75 楼
我也不是很清楚，面试官当场给的反馈大多都还比较positive，可能code写的不是很
clean，我在白板上写的可能有点乱，或是设计题答得他们不是太满意。

【在 w****x 的大作中提到】
: 答得不错啊，怎么也给据了？
avatar
s*y
76 楼
这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
H线程和1个O线程
class h20{
int numOfH, numOfO;
int mutexO, mutexH;
public void H(){
synchronized(this){
if(++numOfH >= 2 && numOfO >= 1) {
mutexO += 1;
mutexH += 2;
numOfH -= 2;
numOfO -= 1;
this.notifyAll();
}
while(mutexH <= 0) {
this.wait();
}
mutexH--;
}
}
public void O(){
synchronized(this){
if(++numOfO >= 1 && numOfH >= 2) {
mutexO += 1;
mutexH += 2;
numOfH -= 2;
numOfO -= 1;
this.notifyAll();
}
while(mutexO <= 0) {
this.wait();
}
mutexO--;
}
}
}

【在 a***o 的大作中提到】
: h2o怎么做的?
avatar
r*i
77 楼
谢谢分享，对我来说，题目都不简单啊。
avatar
w*x
78 楼

不同公司bar真的太不一样了。
我一朋友面Intuit， 3个onsite面试一行代码都没要写就过了。
不过她以前在国内做空姐的...

【在 s******y 的大作中提到】
: 我也不是很清楚，面试官当场给的反馈大多都还比较positive，可能code写的不是很
: clean，我在白板上写的可能有点乱，或是设计题答得他们不是太满意。
avatar
M*5
79 楼
非常感谢！学习了。。。

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
l*h
80 楼
设计题你怎么做的，需要考虑的东西很多。还有，url里面根本就不能放binary data吧？

【在 s******y 的大作中提到】
: 我也不是很清楚，面试官当场给的反馈大多都还比较positive，可能code写的不是很
: clean，我在白板上写的可能有点乱，或是设计题答得他们不是太满意。
avatar
d*x
81 楼
base 64 or just percent encoding

吧？

【在 l**h 的大作中提到】
: 设计题你怎么做的，需要考虑的东西很多。还有，url里面根本就不能放binary data吧？
avatar
s*y
82 楼
呵呵，人家这先天条件是我这等wsn没法比的。
开个玩笑，你朋友肯定有其他过人之处。
年轻的时候觉得会写几行代码很厉害，现在自己觉得有太多的东西比技术重要的多

【在 w****x 的大作中提到】
:
: 不同公司bar真的太不一样了。
: 我一朋友面Intuit， 3个onsite面试一行代码都没要写就过了。
: 不过她以前在国内做空姐的...
avatar
k*x
83 楼
qiu pp

【在 w****x 的大作中提到】
:
: 不同公司bar真的太不一样了。
: 我一朋友面Intuit， 3个onsite面试一行代码都没要写就过了。
: 不过她以前在国内做空姐的...
avatar
f*t
84 楼
觉得不太对。synchronized method只允许一个instance吧，这样你怎么让两个H()同时
执行？

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
y*g
85 楼
mobile 有一轮是

【在 l**h 的大作中提到】
: 多谢分享，听说现在onsite直接用电脑写程序了？
avatar
s*y
86 楼
调用 this.wait() 时 java 会自动unlock， 等wait返回时，会require lock again
， 所以在当前线程sleep期间，其它线程是可以进来的。
这是我对java wait() 函数的理解，难道不对？

【在 f*******t 的大作中提到】
: 觉得不太对。synchronized method只允许一个instance吧，这样你怎么让两个H()同时
: 执行？
avatar
h*i
87 楼
这个你倒是对的，但是程序还是不对numOfH,还有numOfO就看见减了，都没有加的地方。

again

【在 s******y 的大作中提到】
: 调用 this.wait() 时 java 会自动unlock， 等wait返回时，会require lock again
: ， 所以在当前线程sleep期间，其它线程是可以进来的。
: 这是我对java wait() 函数的理解，难道不对？
avatar
f*t
88 楼
用两个semaphore能完美解决这个问题吧，不用写这么复杂的程序

again

【在 s******y 的大作中提到】
: 调用 this.wait() 时 java 会自动unlock， 等wait返回时，会require lock again
: ， 所以在当前线程sleep期间，其它线程是可以进来的。
: 这是我对java wait() 函数的理解，难道不对？
avatar
d*x
89 楼
我觉得得用多个。
如果只是将O作为consumer，H作为producer的话，O() {P(H); P(H); V(useH); V(useH
);}貌似会引起饥饿，设想两个O()都等在第2个P(H)上。。。其实H的量是足够的
我能想到的办法是加一个线程作为consumer，每次consume两个H和一个O

【在 f*******t 的大作中提到】
: 用两个semaphore能完美解决这个问题吧，不用写这么复杂的程序
:
: again
avatar
Y*f
90 楼
BST 添加和删除要保持平衡吗？

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
l*a
91 楼
先存后看
bless

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
f*t
92 楼
我又看错题了。。。

useH

【在 d**********x 的大作中提到】
: 我觉得得用多个。
: 如果只是将O作为consumer，H作为producer的话，O() {P(H); P(H); V(useH); V(useH
: );}貌似会引起饥饿，设想两个O()都等在第2个P(H)上。。。其实H的量是足够的
: 我能想到的办法是加一个线程作为consumer，每次consume两个H和一个O
avatar
P*b
93 楼
多线程那道，那个大侠给来个C++的？

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
d*x
94 楼
H2O那个我写了个C的。可以改吧改吧加上对各种原子的计数。
编译的时候别忘了 -lpthread !
#include
#include
#include
#include
#include
#include
sem_t availH;
sem_t availO;
sem_t usedH;
sem_t usedO;
void* H(void*) {
sem_post(&availH);
sem_wait(&usedH);
fprintf(stderr, "H consumed.\n");
pthread_detach(pthread_self());
return NULL;
}
void* O(void*) {
sem_post(&availO);
sem_wait(&usedO);
fprintf(stderr, "O consumed.\n");
pthread_detach(pthread_self());
return NULL;
}
void* H2O(void*) {
while(1) {
sem_wait(&availO);
sem_wait(&availH);
sem_wait(&availH);

sem_post(&usedO);
sem_post(&usedH);
sem_post(&usedH);

fprintf(stderr, "H2O created.\n");
}
return NULL;
}
int main() {
sem_init(&availH, 0, 0);
sem_init(&availO, 0, 0);
sem_init(&usedH, 0, 0);
sem_init(&usedO, 0, 0);
pthread_t consumer_id;
pthread_create(&consumer_id, NULL, H2O, NULL);
while(1) {
int p = rand() % 3;
if (p == 0) {
pthread_t o_id;
pthread_create(&o_id, NULL, O, NULL);
} else {
pthread_t h_id;
pthread_create(&h_id, NULL, H, NULL);
}
}

return 0;
}

【在 P*******b 的大作中提到】
: 多线程那道，那个大侠给来个C++的？
avatar
s*y
95 楼
不需要，就是最简单的bst 插入删除

【在 Y********f 的大作中提到】
: BST 添加和删除要保持平衡吗？
avatar
w*x
96 楼

bst删除非常tricky啊，楼主能写对证明功底不错

【在 s******y 的大作中提到】
: 不需要，就是最简单的bst 插入删除
avatar
g*e
97 楼
用两个queue。调用H和O的直接enqueue。另起一个consumer thread，每次enqueue都
triger consumer thread，如果HQ.size>2, OQueue.size>1, 从H queue拿两个，O
queue拿一个，返回。
扩展到多个consumer thread的情况，三个方法：
1. 如果不够2H 1O就丢回queue里去。效率不高，容易造成live lock
2. 加个锁，每次保证只有一个consumer从两个queue里面取。同样，效率不高
3. 整个scheduling thread, monitor两个queue的size，达到至少2H 1O就triger一个
consumer去干活。缺点: single point of failure，当然这个好解决。

useH

【在 d**********x 的大作中提到】
: 我觉得得用多个。
: 如果只是将O作为consumer，H作为producer的话，O() {P(H); P(H); V(useH); V(useH
: );}貌似会引起饥饿，设想两个O()都等在第2个P(H)上。。。其实H的量是足够的
: 我能想到的办法是加一个线程作为consumer，每次consume两个H和一个O
avatar
P*b
98 楼
恩。这个方法不错

【在 g**e 的大作中提到】
: 用两个queue。调用H和O的直接enqueue。另起一个consumer thread，每次enqueue都
: triger consumer thread，如果HQ.size>2, OQueue.size>1, 从H queue拿两个，O
: queue拿一个，返回。
: 扩展到多个consumer thread的情况，三个方法：
: 1. 如果不够2H 1O就丢回queue里去。效率不高，容易造成live lock
: 2. 加个锁，每次保证只有一个consumer从两个queue里面取。同样，效率不高
: 3. 整个scheduling thread, monitor两个queue的size，达到至少2H 1O就triger一个
: consumer去干活。缺点: single point of failure，当然这个好解决。
:
: useH
avatar
b*m
99 楼
少了个判断，被唤醒后还要在看一下
是不是＜0

：我也不是很清楚，面试官当场给的反馈大多都还比较positive，可能code写的不是很
：clean，我在白板上写的可能有点乱，或是设计题答得他们不是太满意。
：
：【 在 wwwyhx (wwwyhx) 的大作中提到: 】
：: 答得不错啊，怎么也给据了？
：
：
……

【在 s******y 的大作中提到】
: 不需要，就是最简单的bst 插入删除
avatar
w*r
100 楼
two semaphores 就够了吧
#include
#include
#include
class sem {
boost::mutex guard;
int c ;
public:
sem() : c(0) {}
void V ( int n = 1 ) {
boost::mutex::scoped_lock lock(guard);
c = c + n;
}
void P ( int n = 1) {
while ( c < n ) ;
boost::mutex::scoped_lock lock(guard);
c = c - n;
}

};
sem semh;
sem semo;
class H{
public:
void operator()() {
std::cout << "create H thread \n";
sleep(random()%10);
semh.V( 1 );
semo.P( 1 ) ;
}
};
class O{
public:
void operator()(){
std::cout << "create O thread \n";
sleep(random()%10);
semh.P( 2 ) ;
semo.V( 2 ) ;
std::cout << "got one H2O \n";
}
};
int main(){
H h[200];
O o[100];
std::vector < boost::thread* > v ;
for ( int i = 0 ; i<100; i++ ) {
v.push_back(new boost::thread ( h[i*2] )) ;
v.push_back(new boost::thread ( h[i*2+1] )) ;
v.push_back(new boost::thread ( o[i] ) );
}
for ( std::vector::iterator it = v.begin(); it != v.end(
); it++){
(*it)->join();
delete (*it);
}

}
avatar
e*s
101 楼
问个很弱的问题,blocking queue不是就已经thread-safe吗? 怎么实现thread-safe
blocking queue?
找到下面JAVA代码,好像很标准的样子.
public class BlockingQueue {
private List queue = new LinkedList();
private int limit = 10;
public BlockingQueue(int limit){
this.limit = limit;
}
public synchronized void enqueue(Object item)
throws InterruptedException {
while(this.queue.size() == this.limit) {
wait();
}
if(this.queue.size() == 0) {
notifyAll();
}
this.queue.add(item);
}
public synchronized Object dequeue()
throws InterruptedException{
while(this.queue.size() == 0){
wait();
}
if(this.queue.size() == this.limit){
notifyAll();
}
return this.queue.remove(0);
}
}
avatar
x*0
102 楼
mark
avatar
b*e
103 楼
没关系。我跟你讲，L是个印窝。去了也没意思。你这个面试的是什么？至少是
Principal Engineer。我很负责任的告诉你，LinkedIn所有的Engineer加一起，顶多有
1%能把这些题全做出来，那还是可劲往高里说的。你要是真觉得这些题都不难，F/G那
是刚刚的。你这个纯粹是被黑了。术业有专攻，你这篇里什么都有，数据结构，算法，
并行，系统，汇编。干屁呢。你真找一工作，在今后的三年里你八成连双重循环都用不
上。Mark my words.

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
s*y
104 楼
是这个意思，面试官就是强调一下我实现的这个queue要保证thread-safe

【在 e***s 的大作中提到】
: 问个很弱的问题,blocking queue不是就已经thread-safe吗? 怎么实现thread-safe
: blocking queue?
: 找到下面JAVA代码,好像很标准的样子.
: public class BlockingQueue {
: private List queue = new LinkedList();
: private int limit = 10;
: public BlockingQueue(int limit){
: this.limit = limit;
: }
: public synchronized void enqueue(Object item)
avatar
s*y
105 楼
多谢安慰~

【在 b***e 的大作中提到】
: 没关系。我跟你讲，L是个印窝。去了也没意思。你这个面试的是什么？至少是
: Principal Engineer。我很负责任的告诉你，LinkedIn所有的Engineer加一起，顶多有
: 1%能把这些题全做出来，那还是可劲往高里说的。你要是真觉得这些题都不难，F/G那
: 是刚刚的。你这个纯粹是被黑了。术业有专攻，你这篇里什么都有，数据结构，算法，
: 并行，系统，汇编。干屁呢。你真找一工作，在今后的三年里你八成连双重循环都用不
: 上。Mark my words.
avatar
e*s
106 楼
楼主，能不能给一下这题的code
第一个: 给两个单词， 比如head, tail: 找到一个最短的转换，从head到tail，每
次只能变一个字母，path上的word都必须是有效的英文单词，我用的Graph shortest
path
avatar
b*n
107 楼
感觉在硅谷去哪都是印窝 还是找个钱多的实际 可惜FLG都进不去
avatar
f*t
108 楼
leetcode word ladder

【在 e***s 的大作中提到】
: 楼主，能不能给一下这题的code
: 第一个: 给两个单词， 比如head, tail: 找到一个最短的转换，从head到tail，每
: 次只能变一个字母，path上的word都必须是有效的英文单词，我用的Graph shortest
: path
avatar
b*f
109 楼
写了个H2O Java的，不知道对不对，大家帮忙看看
h_count = 0;
void H() {
synchronized(h_count) {
h_count++;
if(h_count == 2) {
h_sem.release();
h_count = 0;
}
}
o_sem.acquire();
}
void O() {
h_sem.acquire();
o_sem.release(2);
}
avatar
c*t
110 楼
多谢！以你的水平，offer 很快回来的。
求问如何每次只唤醒2个H线程和1个O线程？java has no way to wake up or notify a
specific thread.

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
s*y
111 楼
object.notify() 好像就是每次只唤醒一个在这个object上wait的线程，但是不保证那
个线程被唤醒。 我当时的思路是定义两个object, H和O线程wait 在不同的object上，
这样就可以notify两次H和一次O了。 当时面试官说这种方法可以的， 哎，

a

【在 c********t 的大作中提到】
: 多谢！以你的水平，offer 很快回来的。
: 求问如何每次只唤醒2个H线程和1个O线程？java has no way to wake up or notify a
: specific thread.
avatar
c*t
112 楼
嗯，明白了，多谢！

【在 s******y 的大作中提到】
: object.notify() 好像就是每次只唤醒一个在这个object上wait的线程，但是不保证那
: 个线程被唤醒。 我当时的思路是定义两个object, H和O线程wait 在不同的object上，
: 这样就可以notify两次H和一次O了。 当时面试官说这种方法可以的， 哎，
:
: a
avatar
c*t
113 楼
实测了一下这个方法，好像不行哦.主要是因为H object thread不能notify O object
的waiting threads.同理O object thread不能notify H object的waiting threads.导
致满足条件的时候，也不能唤醒对方。
还有什么办法吗？

【在 s******y 的大作中提到】
: object.notify() 好像就是每次只唤醒一个在这个object上wait的线程，但是不保证那
: 个线程被唤醒。 我当时的思路是定义两个object, H和O线程wait 在不同的object上，
: 这样就可以notify两次H和一次O了。 当时面试官说这种方法可以的， 哎，
:
: a
avatar
l*h
114 楼
实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
写了个Java版本的，大家指教:
import java.util.*;
import java.util.concurrent.*;
public class ThreadH2OSema {
private final Semaphore hCalled = new Semaphore(0);
private final Semaphore hUsed = new Semaphore(0);
private final Semaphore oCalled = new Semaphore(0);
private final Semaphore oUsed = new Semaphore(0);
public void H() {
try {
hCalled.release();
System.out.println("One H created");
hUsed.acquire();
}
catch(InterruptedException e) {
System.out.println("Interrupted..");
}
}
public void O() {
try {
oCalled.release();
System.out.println("One O created");
oUsed.acquire();
}
catch(InterruptedException e) {
System.out.println("Interrupted..");
}
}
public void H2O() {
int i = 1;
while(true) {
try {
hCalled.acquire(2);
oCalled.acquire(1);
hUsed.release(2);
oUsed.release(1);
System.out.println(i + " H2O created..");
i++;
}
catch(InterruptedException e) {
System.out.println("Interrupted..");
break;
}
}
}
private static class Caller extends Thread {
private ThreadH2OSema h2o;
public Caller(ThreadH2OSema h2o) {
this.h2o = h2o;
}
public void run() {
Random r = new Random();
// Call H() or O() randomly
if (r.nextBoolean()) h2o.H();
else h2o.O();
}
}

private static class Creator extends Thread {
private ThreadH2OSema h2o;
public Creator(ThreadH2OSema h2o) {
this.h2o = h2o;
}
public void run() {
h2o.H2O();
}
}
public static void main(String[] args) {
ThreadH2OSema h2o = new ThreadH2OSema();
Thread creator = new Creator(h2o);
creator.start();

Thread[] threads = new Thread[3];
for (int i = 0; i < threads.length; i++) {
threads[i] = new Caller(h2o);
threads[i].start();
}
try {
for (int i = 0; i < threads.length; i++) {
threads[i].join();
}
}
catch(InterruptedException e) {
System.out.println("Interrupted..");
}
}
}
avatar
p*p
115 楼
这只要在notify外面套上synchronized就行了

object

【在 c********t 的大作中提到】
: 实测了一下这个方法，好像不行哦.主要是因为H object thread不能notify O object
: 的waiting threads.同理O object thread不能notify H object的waiting threads.导
: 致满足条件的时候，也不能唤醒对方。
: 还有什么办法吗？
avatar
c*t
116 楼
en, 这个好，用semaphore，一个线程专门负责检测semaphore来create h2o, 是不是像
observer？

【在 l**h 的大作中提到】
: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
: ，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
: call O的线程返回（产生一个水分子），其他的都block。
: 写了个Java版本的，大家指教:
: import java.util.*;
: import java.util.concurrent.*;
: public class ThreadH2OSema {
: private final Semaphore hCalled = new Semaphore(0);
: private final Semaphore hUsed = new Semaphore(0);
: private final Semaphore oCalled = new Semaphore(0);
avatar
c*t
117 楼
不懂，不是一个object, synchronized有什么用？而且本来notify就在synchronized
block里。能不能给个简单的codes?
多谢！

【在 p*****p 的大作中提到】
: 这只要在notify外面套上synchronized就行了
:
: object
avatar
p*2
118 楼

LZ的这个程序如果有H1, O threads, 然后进入H2
H2 notify H1 and O then wait. 是不是这个样子的？这样就没有产生H2O

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
p*2
119 楼

貌似原题要求只有两种threads？

【在 g**e 的大作中提到】
: 用两个queue。调用H和O的直接enqueue。另起一个consumer thread，每次enqueue都
: triger consumer thread，如果HQ.size>2, OQueue.size>1, 从H queue拿两个，O
: queue拿一个，返回。
: 扩展到多个consumer thread的情况，三个方法：
: 1. 如果不够2H 1O就丢回queue里去。效率不高，容易造成live lock
: 2. 加个锁，每次保证只有一个consumer从两个queue里面取。同样，效率不高
: 3. 整个scheduling thread, monitor两个queue的size，达到至少2H 1O就triger一个
: consumer去干活。缺点: single point of failure，当然这个好解决。
:
: useH
avatar
p*2
120 楼

貌似不行吧？

【在 b*******f 的大作中提到】
: 写了个H2O Java的，不知道对不对，大家帮忙看看
: h_count = 0;
: void H() {
: synchronized(h_count) {
: h_count++;
: if(h_count == 2) {
: h_sem.release();
: h_count = 0;
: }
: }
avatar
p*2
121 楼

用两个Condition是不是一样的？

【在 s******y 的大作中提到】
: object.notify() 好像就是每次只唤醒一个在这个object上wait的线程，但是不保证那
: 个线程被唤醒。 我当时的思路是定义两个object, H和O线程wait 在不同的object上，
: 这样就可以notify两次H和一次O了。 当时面试官说这种方法可以的， 哎，
:
: a
avatar
p*2
122 楼

好像是有这个问题。看来还是得用Condition吧？

【在 c********t 的大作中提到】
: 不懂，不是一个object, synchronized有什么用？而且本来notify就在synchronized
: block里。能不能给个简单的codes?
: 多谢！
avatar
p*2
123 楼

按照原题的意思好像只能由H，O两个method的吧？

【在 c********t 的大作中提到】
: en, 这个好，用semaphore，一个线程专门负责检测semaphore来create h2o, 是不是像
: observer？
avatar
o*d
124 楼
看过去比较清晰

【在 d**********x 的大作中提到】
: H2O那个我写了个C的。可以改吧改吧加上对各种原子的计数。
: 编译的时候别忘了 -lpthread !
: #include
: #include
: #include
: #include
: #include
: #include
: sem_t availH;
: sem_t availO;
avatar
M*k
125 楼
面试模特？？

【在 w****x 的大作中提到】
:
: bst删除非常tricky啊，楼主能写对证明功底不错
avatar
o*d
126 楼
mark

【在 l**h 的大作中提到】
: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
: ，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
: call O的线程返回（产生一个水分子），其他的都block。
: 写了个Java版本的，大家指教:
: import java.util.*;
: import java.util.concurrent.*;
: public class ThreadH2OSema {
: private final Semaphore hCalled = new Semaphore(0);
: private final Semaphore hUsed = new Semaphore(0);
: private final Semaphore oCalled = new Semaphore(0);
avatar
m*n
127 楼
Your code can be improved in several ways
- The two methods H() and O() are almost symmetric. A single reusable code
segment would look better.
- This can be implemented with four atomicintegers. Synchronized is too
heavy
weight, at least use locks.
- Use SynchronousQueue or your own Queue for releasing threads. Notify(All)
does not protect against starvation

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
c*t
128 楼
二爷，那如果只能用两个method, 有java解法了吗？

【在 p*****2 的大作中提到】
:
: 按照原题的意思好像只能由H，O两个method的吧？
avatar
c*m
129 楼
最后那个系统设计题，能有大牛给个意见吗？
avatar
a*e
130 楼
请问 3-step connection是怎么做的？

【在 s******y 的大作中提到】
: 不需要，就是最简单的bst 插入删除
avatar
f*m
131 楼
那位大俠能給個下面两题的解法？
2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
我的想法：
（1）HashMap里装的value type是一个class,这个class的member包括elementhe 和map。
（2）HashMap里装的value type是一个指针，这个指针的类型可以是elementhe 或map
。不过不太确定如何转化指针类型。
4: Given a social graph, find if there is a path between two persons with at
most 2 steps (3rd level connection), how to handle it in distributed way (
large graph stored at a large number of nodes, minimize cross-communication)
我的想法：
把原social graph分块，从弱的edge切开？
多谢。

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
l*a
132 楼
这种题一般都是两个iterator吧。
第一个Iterator用于外层,第二个用于内层。注意第二层是element或者empty map的情
况即可

map。
map
at

【在 f*********m 的大作中提到】
: 那位大俠能給個下面两题的解法？
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: 我的想法：
: （1）HashMap里装的value type是一个class,这个class的member包括elementhe 和map。
: （2）HashMap里装的value type是一个指针，这个指针的类型可以是elementhe 或map
: 。不过不太确定如何转化指针类型。
: 4: Given a social graph, find if there is a path between two persons with at
: most 2 steps (3rd level connection), how to handle it in distributed way (
avatar
f*m
133 楼
多谢。还是有些不明白。大牛能给个code吗？
这题是让自己写个hashmap class吧，不是用lib里的hash吧？
（1）若是用lib里边存在的hash：
那么外层的iterator是什么类型呢？ 比如，unordered_map::iterator
Outter_it?跑到内层后如何知道内层的类型，要在外层给每个内层都加上type信息吗？
(2)若是要自己写hash class，没什么好思路，请大牛指点。
非常感谢。

【在 l*****a 的大作中提到】
: 这种题一般都是两个iterator吧。
: 第一个Iterator用于外层,第二个用于内层。注意第二层是element或者empty map的情
: 况即可
:
: map。
: map
: at
avatar
P*t
134 楼
题目很有意思。H2O那道，我觉得可以这么来解。维持两个QUEUE，
每个QUEUE里放个EVENT OBJECT来Wait. e.g.:
deque hqueue;
deque oqueue;
mutex qmutex;
void Acquire(bool isH) {
event* e = new event();
qmutex.lock();
if (isH) hqueue.push_back(e)
else oqueue.push_back(e);
if (hqueue.size() >= 2 && oqueue.size() > 0) {
hqueue.front()->set();
hqueue.pop_front();
hqueue.front()->set();
hqueue.pop_front();
oqueue.front()->set();
oqueue.pop_front();
}
qmutex.unlock();

e->wait();
delete e;
}
void H() {
Acquire(true);
}
void O() {
Acquire(false);
}

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
s*r
135 楼
对于新手确实很难的，尤其是那个design，没有类似的项目经验，新生很难把握，错了
很正常
那个嵌套Map，就是JSON里面常见的例子，但新生恐怕没见过JSON长什么样子，拿来考
新手，有些过了

【在 b***e 的大作中提到】
: 没关系。我跟你讲，L是个印窝。去了也没意思。你这个面试的是什么？至少是
: Principal Engineer。我很负责任的告诉你，LinkedIn所有的Engineer加一起，顶多有
: 1%能把这些题全做出来，那还是可劲往高里说的。你要是真觉得这些题都不难，F/G那
: 是刚刚的。你这个纯粹是被黑了。术业有专攻，你这篇里什么都有，数据结构，算法，
: 并行，系统，汇编。干屁呢。你真找一工作，在今后的三年里你八成连双重循环都用不
: 上。Mark my words.
avatar
n*i
136 楼
h2o那题为了不唤醒所有线程，可以用两个锁实现，不知道对不对
public class H2o {
Integer h, o;
public void o() {
boolean match = false;
synchronized(o) {
synchronized(h) {
if (h >= 2) {
h -= 2;
match = true;
} else {
o++;
}
}
if (!match)
o.wait();
}
if (match) {
h.notify();
h.notify();
}
}
public void h() {
boolean match = false;
synchronized(h) {
synchronized(o) {
if (h > 0 && o > 0) {
h--;
o--;
match = true;
} else {
h++;
}
}
if (!match)
h.wait();
}
if (match) {
h.notify();
o.notify();
}
}
}
avatar
m*i
137 楼
的确很难
avatar
s*x
138 楼
Mark

★ 发自iPhone App: ChineseWeb 7.8

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
s*n
139 楼
不必。 你用两个lock容易死锁。
一个lock+ 两个condition搞定。

【在 n****i 的大作中提到】
: h2o那题为了不唤醒所有线程，可以用两个锁实现，不知道对不对
: public class H2o {
: Integer h, o;
: public void o() {
: boolean match = false;
: synchronized(o) {
: synchronized(h) {
: if (h >= 2) {
: h -= 2;
: match = true;
avatar
n*i
140 楼
恩，重新写了一下
public class H2o {
int h, o;
Lock lock;
Condition condh, condo;
public H2o() {
lock = new ReentrantLock();
condh = lock.newcondition();
condo = lock.newcondition();
}
public void o() {
boolean match = false;
lock.lock();
if (h >= 2) {
h -= 2;
match = true;
} else {
o++;
condo.await();
}
lock.unloack();
if (match) {
condh.signal();
condh.signal();
}
}
public void h() {
boolean match = false;
lock.lock();
if (h > 0 && o > 0) {
h--;
o--;
match = true;
} else {
h++;
condh.await();
}
lock.unlock();
if (match) {
condh.signal();
condh.signal();
}
}
}

【在 s*****n 的大作中提到】
: 不必。 你用两个lock容易死锁。
: 一个lock+ 两个condition搞定。
avatar
s*n
141 楼
unlock必须放在finally, exception safe.
conidtion必须放入while循环check
await需要catch interupptedexpcetion
最后，i doubt程序逻辑实际部队。因为你wakeup two threads.然后一个进去后，另外
一个会被while重新放到队列中。

【在 n****i 的大作中提到】
: 恩，重新写了一下
: public class H2o {
: int h, o;
: Lock lock;
: Condition condh, condo;
: public H2o() {
: lock = new ReentrantLock();
: condh = lock.newcondition();
: condo = lock.newcondition();
: }
avatar
s*r
142 楼
多谢分享！

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
w*0
143 楼
mark,赞lz面经
avatar
n*i
144 楼
多谢，大侠帮忙看看对不对，exception不知道如何catch，直接抛出了
public class H2o {
int freeh, freeo, boundh, boundo;
Lock lock;
Condition condh, condo;
public H2o() {
freeh = freeo = boundh = boundo = 0;
lock = new ReentrantLock();
condh = lock.newcondition();
condo = lock.newcondition();
}
public void o() throws InterruptedException {
lock.lock();
try {
if (freeh >= 2) {
freeh -= 2;
boundh += 2;
condh.signal();
condh.signal();
} else {
freeo++;
while (boundo == 0)
condo.await();
boundo--;
}
} finally {
lock.unloack();
}
}
public void h() throws InterruptedException{
lock.lock();
try {
if (freeh >= 1 && freeo >= 1) {
freeh--; boundh++;
freeo--; boundo++;
condh.signal();
condo.signal();
} else {
freeh++;
while (boundh == 0)
condh.await();
boundh--;
}
} finally {
lock.unlock();
}
}
}

【在 s*****n 的大作中提到】
: unlock必须放在finally, exception safe.
: conidtion必须放入while循环check
: await需要catch interupptedexpcetion
: 最后，i doubt程序逻辑实际部队。因为你wakeup two threads.然后一个进去后，另外
: 一个会被while重新放到队列中。
avatar
m*k
145 楼
难道不是producer (H), consumer (O) 问题么？
number of slots = 2,
H thread waits when seeing number of full slots = 2,
O thread waits when seeing number of full slots < 2,
when H thread increases full slots by 1, notify() once,
when O thread decreases full slots by 2, notify() twice,
O1, h1, h2,
yes, h1 will wake up O1, so what?, O1 will go to wait again, then h2 will
wake up O1 again, and h2O is produced, all threads finish.
O1, h1, h2 都等待 直到 h4 or O4 来才让他们产生h2o
does not make any sense. who will do this in production???

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
e*n
146 楼
这还是fresh的面试题？！楼主肯定是被黑了，前面一个同学说的很对，包含那么多东
西的lz答的还不错还能悲剧，纯粹是被黑啊！以lz的水平肯定能很快拿一好offer的！
bless～
avatar
r*m
147 楼
H notify 一次，O notify 两次
class H2OLock{
int o = 0;
int h = 0;
public synchronized void callH() throws InterruptedException{
if(h < 1 || o < 1){
h++;
wait();
}
if(o>0){
o--;
notify();
}
System.out.println("H");
}

public synchronized void callO() throws InterruptedException{
if(h < 2){
o++;
wait();
}
h = h-2;
System.out.println("O");
notify();
notify();
}
}
avatar
s*e
148 楼
支持一下。
avatar
f*p
149 楼
人家又不是非要面码农

【在 s******y 的大作中提到】
: 呵呵，人家这先天条件是我这等wsn没法比的。
: 开个玩笑，你朋友肯定有其他过人之处。
: 年轻的时候觉得会写几行代码很厉害，现在自己觉得有太多的东西比技术重要的多
avatar
A*g
150 楼
mark下
avatar
n*s
151 楼
int counter[2]; // count[0] count of O; count[1] count of H
int toRunH ;
int toRunO ;
void H( ){
sync(counter){
if(counter[0]>=1 && count[1]==2){
toRunH = 2;toRunO = 1;
counter.notifyAll();

}
count[1]++;
do{
counter.wait()
}while(toRunH==0)
toRunH--;
}
}
void O( ){
sync(counter){
if(counter[0]==1 && count[1]>=2){
toRunH = 2;toRunO = 1;
counter.notifyAll();

}
count[0]++;
do{
counter.wait()
}while(toRunO==0)
toRunO--;
}
}
avatar
m*p
152 楼
http://see.stanford.edu/materials/icsppcs107/23-Concurrency-Exa
the answer to the h2o problem.

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
m*i
153 楼
mark
avatar
p*u
154 楼
mark
avatar
s*u
156 楼
题目好难啊，想问下lz是什么职位。。
avatar
g*e
157 楼

...

【在 w****x 的大作中提到】
:
: bst删除非常tricky啊，楼主能写对证明功底不错
avatar
h*u
158 楼
用了两个blocking queue, 还请大侠指教！
import java.util.concurrent.LinkedBlockingQueue;
public class H2O {
LinkedBlockingQueue hQueue = new LinkedBlockingQueue();
LinkedBlockingQueue oQueue = new LinkedBlockingQueue();
Object o = new Object();
public void h() throws InterruptedException {
hQueue.put(Thread.currentThread());
synchronized (o){
System.out.println(Thread.currentThread().getName() + ".h,
notify");
o.notify();
}
synchronized (this){
System.out.println(Thread.currentThread().getName()+".h, going
to wait");
this.wait();
}
}
public void o() throws InterruptedException {
oQueue.put(Thread.currentThread());
synchronized (o){
System.out.println(Thread.currentThread().getName() + ".o,
notify");
o.notify();
}
synchronized (this){
System.out.println(Thread.currentThread().getName()+".o, going
to wait");
this.wait();
}
}
public String pop() throws InterruptedException {
while(true){
synchronized (o){
o.wait();
}
if(hQueue.size() >= 2 && oQueue.size() >= 1){
Thread h = hQueue.take();
synchronized (h){
h.notify();
}
Thread h2 = hQueue.take();
synchronized (h2){
h2.notify();
}
Thread o = oQueue.take();
synchronized (o){
o.notify();
}
System.out.println("H2O");
}
}
}
class hThread implements Runnable{
public void run(){
try {
h();
} catch (InterruptedException e) {
e.printStackTrace(); //To change body of catch statement
use File | Settings | File Templates.
}
}
}
class oThread implements Runnable{
public void run(){
try {
o();
} catch (InterruptedException e) {
e.printStackTrace(); //To change body of catch statement
use File | Settings | File Templates.
}
}
}
class Monitor implements Runnable{
public void run(){
try {
pop();
} catch (InterruptedException e) {
e.printStackTrace(); //To change body of catch statement
use File | Settings | File Templates.
}
}
}
public static void main(String[] args) throws InterruptedException {
H2O t = new H2O();
new Thread(t.new Monitor()).start();
new Thread(t.new hThread()).start();
new Thread(t.new hThread()).start();
new Thread(t.new oThread()).start();
new Thread(t.new hThread()).start();
new Thread(t.new hThread()).start();
new Thread(t.new oThread()).start();
new Thread(t.new hThread()).start();
new Thread(t.new oThread()).start();
}
}
avatar
f*m
159 楼
多谢。还是有些不明白。大牛能给个code吗？
这题是让自己写个hashmap class吧，不是用lib里的hash吧？
（1）若是用lib里边存在的hash：
那么外层的iterator是什么类型呢？ 比如，unordered_map::iterator
Outter_it?跑到内层后如何知道内层的类型，要在外层给每个内层都加上type信息吗？
(2)若是要自己写hash class，没什么好思路，请大牛指点。
非常感谢。

【在 l*****a 的大作中提到】
: 这种题一般都是两个iterator吧。
: 第一个Iterator用于外层,第二个用于内层。注意第二层是element或者empty map的情
: 况即可
:
: map。
: map
: at
avatar
P*t
160 楼
题目很有意思。H2O那道，我觉得可以这么来解。维持两个QUEUE，
每个QUEUE里放个EVENT OBJECT来Wait. e.g.:
deque hqueue;
deque oqueue;
mutex qmutex;
void Acquire(bool isH) {
event* e = new event();
qmutex.lock();
if (isH) hqueue.push_back(e)
else oqueue.push_back(e);
if (hqueue.size() >= 2 && oqueue.size() > 0) {
hqueue.front()->set();
hqueue.pop_front();
hqueue.front()->set();
hqueue.pop_front();
oqueue.front()->set();
oqueue.pop_front();
}
qmutex.unlock();

e->wait();
delete e;
}
void H() {
Acquire(true);
}
void O() {
Acquire(false);
}

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
s*r
161 楼
对于新手确实很难的，尤其是那个design，没有类似的项目经验，新生很难把握，错了
很正常
那个嵌套Map，就是JSON里面常见的例子，但新生恐怕没见过JSON长什么样子，拿来考
新手，有些过了

【在 b***e 的大作中提到】
: 没关系。我跟你讲，L是个印窝。去了也没意思。你这个面试的是什么？至少是
: Principal Engineer。我很负责任的告诉你，LinkedIn所有的Engineer加一起，顶多有
: 1%能把这些题全做出来，那还是可劲往高里说的。你要是真觉得这些题都不难，F/G那
: 是刚刚的。你这个纯粹是被黑了。术业有专攻，你这篇里什么都有，数据结构，算法，
: 并行，系统，汇编。干屁呢。你真找一工作，在今后的三年里你八成连双重循环都用不
: 上。Mark my words.
avatar
n*i
162 楼
h2o那题为了不唤醒所有线程，可以用两个锁实现，不知道对不对
public class H2o {
Integer h, o;
public void o() {
boolean match = false;
synchronized(o) {
synchronized(h) {
if (h >= 2) {
h -= 2;
match = true;
} else {
o++;
}
}
if (!match)
o.wait();
}
if (match) {
h.notify();
h.notify();
}
}
public void h() {
boolean match = false;
synchronized(h) {
synchronized(o) {
if (h > 0 && o > 0) {
h--;
o--;
match = true;
} else {
h++;
}
}
if (!match)
h.wait();
}
if (match) {
h.notify();
o.notify();
}
}
}
avatar
m*i
163 楼
的确很难
avatar
s*x
164 楼
Mark

★ 发自iPhone App: ChineseWeb 7.8

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
s*n
165 楼
不必。 你用两个lock容易死锁。
一个lock+ 两个condition搞定。

【在 n****i 的大作中提到】
: h2o那题为了不唤醒所有线程，可以用两个锁实现，不知道对不对
: public class H2o {
: Integer h, o;
: public void o() {
: boolean match = false;
: synchronized(o) {
: synchronized(h) {
: if (h >= 2) {
: h -= 2;
: match = true;
avatar
n*i
166 楼
恩，重新写了一下
public class H2o {
int h, o;
Lock lock;
Condition condh, condo;
public H2o() {
lock = new ReentrantLock();
condh = lock.newcondition();
condo = lock.newcondition();
}
public void o() {
boolean match = false;
lock.lock();
if (h >= 2) {
h -= 2;
match = true;
} else {
o++;
condo.await();
}
lock.unloack();
if (match) {
condh.signal();
condh.signal();
}
}
public void h() {
boolean match = false;
lock.lock();
if (h > 0 && o > 0) {
h--;
o--;
match = true;
} else {
h++;
condh.await();
}
lock.unlock();
if (match) {
condh.signal();
condh.signal();
}
}
}

【在 s*****n 的大作中提到】
: 不必。 你用两个lock容易死锁。
: 一个lock+ 两个condition搞定。
avatar
s*n
167 楼
unlock必须放在finally, exception safe.
conidtion必须放入while循环check
await需要catch interupptedexpcetion
最后，i doubt程序逻辑实际部队。因为你wakeup two threads.然后一个进去后，另外
一个会被while重新放到队列中。

【在 n****i 的大作中提到】
: 恩，重新写了一下
: public class H2o {
: int h, o;
: Lock lock;
: Condition condh, condo;
: public H2o() {
: lock = new ReentrantLock();
: condh = lock.newcondition();
: condo = lock.newcondition();
: }
avatar
s*r
168 楼
多谢分享！

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
w*0
169 楼
mark,赞lz面经
avatar
n*i
170 楼
多谢，大侠帮忙看看对不对，exception不知道如何catch，直接抛出了
public class H2o {
int freeh, freeo, boundh, boundo;
Lock lock;
Condition condh, condo;
public H2o() {
freeh = freeo = boundh = boundo = 0;
lock = new ReentrantLock();
condh = lock.newcondition();
condo = lock.newcondition();
}
public void o() throws InterruptedException {
lock.lock();
try {
if (freeh >= 2) {
freeh -= 2;
boundh += 2;
condh.signal();
condh.signal();
} else {
freeo++;
while (boundo == 0)
condo.await();
boundo--;
}
} finally {
lock.unloack();
}
}
public void h() throws InterruptedException{
lock.lock();
try {
if (freeh >= 1 && freeo >= 1) {
freeh--; boundh++;
freeo--; boundo++;
condh.signal();
condo.signal();
} else {
freeh++;
while (boundh == 0)
condh.await();
boundh--;
}
} finally {
lock.unlock();
}
}
}

【在 s*****n 的大作中提到】
: unlock必须放在finally, exception safe.
: conidtion必须放入while循环check
: await需要catch interupptedexpcetion
: 最后，i doubt程序逻辑实际部队。因为你wakeup two threads.然后一个进去后，另外
: 一个会被while重新放到队列中。
avatar
m*k
171 楼
难道不是producer (H), consumer (O) 问题么？
number of slots = 2,
H thread waits when seeing number of full slots = 2,
O thread waits when seeing number of full slots < 2,
when H thread increases full slots by 1, notify() once,
when O thread decreases full slots by 2, notify() twice,
O1, h1, h2,
yes, h1 will wake up O1, so what?, O1 will go to wait again, then h2 will
wake up O1 again, and h2O is produced, all threads finish.
O1, h1, h2 都等待 直到 h4 or O4 来才让他们产生h2o
does not make any sense. who will do this in production???

【在 s******y 的大作中提到】
: 这是我当时写的代码, 返回的线程没有顺序要求，只要每次保证有2个H线程和一个O线
: 程返回就行了。 然后面试官又问我每次都wake up所有当前等待的线程，然后这些线程
: 竞争，最后只有三个能过。 如果线程很多的话，比如1000个H线程，会怎么样， 我说
: 会多消耗CPU，因为大多数线程会被唤醒然后又sleep。 解决方法是可以每次只唤醒2个
: H线程和1个O线程
: class h20{
: int numOfH, numOfO;
: int mutexO, mutexH;
: public void H(){
: synchronized(this){
avatar
e*n
172 楼
这还是fresh的面试题？！楼主肯定是被黑了，前面一个同学说的很对，包含那么多东
西的lz答的还不错还能悲剧，纯粹是被黑啊！以lz的水平肯定能很快拿一好offer的！
bless～
avatar
r*m
173 楼
H notify 一次，O notify 两次
class H2OLock{
int o = 0;
int h = 0;
public synchronized void callH() throws InterruptedException{
if(h < 1 || o < 1){
h++;
wait();
}
if(o>0){
o--;
notify();
}
System.out.println("H");
}

public synchronized void callO() throws InterruptedException{
if(h < 2){
o++;
wait();
}
h = h-2;
System.out.println("O");
notify();
notify();
}
}
avatar
s*e
174 楼
支持一下。
avatar
f*p
175 楼
人家又不是非要面码农

【在 s******y 的大作中提到】
: 呵呵，人家这先天条件是我这等wsn没法比的。
: 开个玩笑，你朋友肯定有其他过人之处。
: 年轻的时候觉得会写几行代码很厉害，现在自己觉得有太多的东西比技术重要的多
avatar
A*g
176 楼
mark下
avatar
n*s
177 楼
int counter[2]; // count[0] count of O; count[1] count of H
int toRunH ;
int toRunO ;
void H( ){
sync(counter){
if(counter[0]>=1 && count[1]==2){
toRunH = 2;toRunO = 1;
counter.notifyAll();

}
count[1]++;
do{
counter.wait()
}while(toRunH==0)
toRunH--;
}
}
void O( ){
sync(counter){
if(counter[0]==1 && count[1]>=2){
toRunH = 2;toRunO = 1;
counter.notifyAll();

}
count[0]++;
do{
counter.wait()
}while(toRunO==0)
toRunO--;
}
}
avatar
m*p
178 楼
http://see.stanford.edu/materials/icsppcs107/23-Concurrency-Exa
the answer to the h2o problem.

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
m*i
179 楼
mark
avatar
p*u
180 楼
mark
avatar
s*u
182 楼
题目好难啊，想问下lz是什么职位。。
avatar
g*e
183 楼

...

【在 w****x 的大作中提到】
:
: bst删除非常tricky啊，楼主能写对证明功底不错
avatar
h*u
184 楼
用了两个blocking queue, 还请大侠指教！
import java.util.concurrent.LinkedBlockingQueue;
public class H2O {
LinkedBlockingQueue hQueue = new LinkedBlockingQueue();
LinkedBlockingQueue oQueue = new LinkedBlockingQueue();
Object o = new Object();
public void h() throws InterruptedException {
hQueue.put(Thread.currentThread());
synchronized (o){
System.out.println(Thread.currentThread().getName() + ".h,
notify");
o.notify();
}
synchronized (this){
System.out.println(Thread.currentThread().getName()+".h, going
to wait");
this.wait();
}
}
public void o() throws InterruptedException {
oQueue.put(Thread.currentThread());
synchronized (o){
System.out.println(Thread.currentThread().getName() + ".o,
notify");
o.notify();
}
synchronized (this){
System.out.println(Thread.currentThread().getName()+".o, going
to wait");
this.wait();
}
}
public String pop() throws InterruptedException {
while(true){
synchronized (o){
o.wait();
}
if(hQueue.size() >= 2 && oQueue.size() >= 1){
Thread h = hQueue.take();
synchronized (h){
h.notify();
}
Thread h2 = hQueue.take();
synchronized (h2){
h2.notify();
}
Thread o = oQueue.take();
synchronized (o){
o.notify();
}
System.out.println("H2O");
}
}
}
class hThread implements Runnable{
public void run(){
try {
h();
} catch (InterruptedException e) {
e.printStackTrace(); //To change body of catch statement
use File | Settings | File Templates.
}
}
}
class oThread implements Runnable{
public void run(){
try {
o();
} catch (InterruptedException e) {
e.printStackTrace(); //To change body of catch statement
use File | Settings | File Templates.
}
}
}
class Monitor implements Runnable{
public void run(){
try {
pop();
} catch (InterruptedException e) {
e.printStackTrace(); //To change body of catch statement
use File | Settings | File Templates.
}
}
}
public static void main(String[] args) throws InterruptedException {
H2O t = new H2O();
new Thread(t.new Monitor()).start();
new Thread(t.new hThread()).start();
new Thread(t.new hThread()).start();
new Thread(t.new oThread()).start();
new Thread(t.new hThread()).start();
new Thread(t.new hThread()).start();
new Thread(t.new oThread()).start();
new Thread(t.new hThread()).start();
new Thread(t.new oThread()).start();
}
}
avatar
P*d
185 楼
MARK
avatar
p*2
186 楼
这道题好像用actor比较好做
avatar
P*d
187 楼
MARK
avatar
p*2
188 楼
这道题好像用actor比较好做
avatar
s*m
189 楼
请问 第四题是怎么做的

【在 r****m 的大作中提到】
: H notify 一次，O notify 两次
: class H2OLock{
: int o = 0;
: int h = 0;
: public synchronized void callH() throws InterruptedException{
: if(h < 1 || o < 1){
: h++;
: wait();
: }
: if(o>0){
avatar
y*g
190 楼
好难啊，，回不去了

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
g*v
191 楼
请问楼主有multi threading background么，
怎么2个multi threading的题目？

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
n*n
192 楼
不用看。这么长代码肯定不对。

【在 h**u 的大作中提到】
: 用了两个blocking queue, 还请大侠指教！
: import java.util.concurrent.LinkedBlockingQueue;
: public class H2O {
: LinkedBlockingQueue hQueue = new LinkedBlockingQueue();
: LinkedBlockingQueue oQueue = new LinkedBlockingQueue();
: Object o = new Object();
: public void h() throws InterruptedException {
: hQueue.put(Thread.currentThread());
: synchronized (o){
: System.out.println(Thread.currentThread().getName() + ".h,
avatar
h*4
193 楼
public class H2O {

static final Lock LOCK = new ReentrantLock();
static final Condition ENOUGH_H = LOCK.newCondition();
static final Condition ENOUGH_O = LOCK.newCondition();
static int H = 0;
static int O = 0;
static void check() {
if (H >= 2 && O >= 1) {
ENOUGH_H.signal();
ENOUGH_H.signal();
ENOUGH_O.signal();
H -= 2;
O -= 1;
}
}

public static void h() {
LOCK.lock();
try {
check();
++H;
ENOUGH_H.awaitUninterruptibly();
} finally {
LOCK.unlock();
}
}

public static void o() {
LOCK.lock();
try {
check();
++O;
ENOUGH_O.awaitUninterruptibly();
} finally {
LOCK.unlock();
}
}
}
avatar
f*x
194 楼
不怎么懂并行的我表示，难道不是以下代码吗？
H() {
H.V
O.P
}
O() {
H.P
H.P
O.V
O.V
}
其中，H和V是两个semaphore，P是减一，V是加一。
avatar
i*u
195 楼
Mark

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
f*n
196 楼
mark
avatar
k*a
197 楼
我的思路：
Onsite:
第一个: 给两个单词， 比如head, tail: 找到一个最短的转换，从head到tail，每
次只能变一个字母，path上的word都必须是有效的英文单词，我用的Graph shortest
path
这个题是word ladder I吧
第二个: memcpy: 源区域和目标区域可能有重叠
BST 插入和删除操作实现
BST iterator 实现
这个是基本数据结构题，BST删除麻烦些，iterator用transverse的中序思路写吧。
3: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
这个大家讨论过了。我感觉用信号量之类的东东？
4: Given a social graph, find if there is a path between two persons with at
most 2 steps (3rd level connection), how to handle it in distributed way (
large graph stored at a large number of nodes, minimize cross-communication)
这个是用双向bfs，找两个人朋友圈的交集？
5: 设计题: a restful server with 4GB,
given a request such as: http://seq=4?len=60?xxxxdata
the system will store the binary data with that sequence number.
given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.
multiple clients calling simutaneous
这个的数据结构是双向链表+map？只读不锁，读写互锁。这个服务可以删除seq么？还
是只能增加？
avatar
s*m
198 楼
请问 第四题是怎么做的

【在 r****m 的大作中提到】
: H notify 一次，O notify 两次
: class H2OLock{
: int o = 0;
: int h = 0;
: public synchronized void callH() throws InterruptedException{
: if(h < 1 || o < 1){
: h++;
: wait();
: }
: if(o>0){
avatar
y*g
199 楼
好难啊，，回不去了

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
g*v
200 楼
请问楼主有multi threading background么，
怎么2个multi threading的题目？

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
n*n
201 楼
不用看。这么长代码肯定不对。

【在 h**u 的大作中提到】
: 用了两个blocking queue, 还请大侠指教！
: import java.util.concurrent.LinkedBlockingQueue;
: public class H2O {
: LinkedBlockingQueue hQueue = new LinkedBlockingQueue();
: LinkedBlockingQueue oQueue = new LinkedBlockingQueue();
: Object o = new Object();
: public void h() throws InterruptedException {
: hQueue.put(Thread.currentThread());
: synchronized (o){
: System.out.println(Thread.currentThread().getName() + ".h,
avatar
h*4
202 楼
public class H2O {

static final Lock LOCK = new ReentrantLock();
static final Condition ENOUGH_H = LOCK.newCondition();
static final Condition ENOUGH_O = LOCK.newCondition();
static int H = 0;
static int O = 0;
static void check() {
if (H >= 2 && O >= 1) {
ENOUGH_H.signal();
ENOUGH_H.signal();
ENOUGH_O.signal();
H -= 2;
O -= 1;
}
}

public static void h() {
LOCK.lock();
try {
check();
++H;
ENOUGH_H.awaitUninterruptibly();
} finally {
LOCK.unlock();
}
}

public static void o() {
LOCK.lock();
try {
check();
++O;
ENOUGH_O.awaitUninterruptibly();
} finally {
LOCK.unlock();
}
}
}
avatar
f*x
203 楼
不怎么懂并行的我表示，难道不是以下代码吗？
H() {
H.V
O.P
}
O() {
H.P
H.P
O.V
O.V
}
其中，H和V是两个semaphore，P是减一，V是加一。
avatar
i*u
204 楼
Mark

【在 s******y 的大作中提到】
: 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
: project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
: 但是还是悲剧了，anyway， move on了。 发一下记得的题目，
: 电面：
: 1. 给一个二叉树，返回它的镜像
: 实现一个 thread-safe blocking queue
: 2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
: 嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
: 似树遍历一样的方法
: Onsite:
avatar
f*n
205 楼
mark
avatar
k*a
206 楼
我的思路：
Onsite:
第一个: 给两个单词， 比如head, tail: 找到一个最短的转换，从head到tail，每
次只能变一个字母，path上的word都必须是有效的英文单词，我用的Graph shortest
path
这个题是word ladder I吧
第二个: memcpy: 源区域和目标区域可能有重叠
BST 插入和删除操作实现
BST iterator 实现
这个是基本数据结构题，BST删除麻烦些，iterator用transverse的中序思路写吧。
3: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
这个大家讨论过了。我感觉用信号量之类的东东？
4: Given a social graph, find if there is a path between two persons with at
most 2 steps (3rd level connection), how to handle it in distributed way (
large graph stored at a large number of nodes, minimize cross-communication)
这个是用双向bfs，找两个人朋友圈的交集？
5: 设计题: a restful server with 4GB,
given a request such as: http://seq=4?len=60?xxxxdata
the system will store the binary data with that sequence number.
given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.
multiple clients calling simutaneous
这个的数据结构是双向链表+map？只读不锁，读写互锁。这个服务可以删除seq么？还
是只能增加？
avatar
y*3
207 楼
嵌套Map的题有没有说支持多少层？如果是无限层，c++的数据结构怎么定义的？
相关阅读
不用再从国内带盒子了，nexus player足以surface pro 4 待机很费电啊你们要做trade in的，便宜电话来了verizon店里trade in被审查要求提供ssn复印件和id吓死麒麟950！Galaxy S7曝皇帝版：14核心GPUWindows TH升级后发现最大的好处是ios怎么这么差。装个风云直播花了一天。950xl plus dock出来了聊聊夏普水晶手机 (转载)ipad 2以上，bestbuy trade in promoeBay上的解锁是不是都是坑?Verizon trade in is $300 or $600?H2O 激活要等几天？chat 居然 50 多人排队buy a $45 straighttalk plan and get one free无线路由可以当repeater用吗？哪位能给写一个R+的免费plan攻略？小米跑鞋，带蓝牙！deal? ARRIS SBG6580 Refurbished for $34.99 at staplesG4什么毛病用听筒放音乐？black friday 有什么手机的deal吗？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。