由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - 请教L家生成H2O水分子的题。
相关主题
● 想问一下那道H2O的多线程题● qualcomm 新鲜电面面经
● 请教一下那道H2O的题● 求教三进程间同步的问题，原题是CC150第5版的16.5
● failed bloomberg phone interview● java concurrence 例子
● two functons and two threads● Solution for interview question posted here before
● read-write locker的实现● multi-threading guru们
● 昨天onsite被问到的 multithreading 题目● LinkedIn 面经
● 又tmd的面砸了一个，还是贴贴面经● Java编程讨论：LinkedIn的H2O
● 贡献T家新鲜面经，求个bless● Quantcast电面
相关话题的讨论汇总
话题: h2o话题: thread话题: new话题: hcount
进入JobHunting版参与讨论
1 (共1页)
t*****a
发帖数: 106
1
原题如下
实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block
看到有人说可以用一个ReentrantLock和两个Condition写，但试了一下怎么都不对。有
哪位大侠能指点一下，最好贴一下code.多谢！
r****7
发帖数: 2282
2
难道不是semaphore就行么？

【在 t*****a 的大作中提到】
: 原题如下
: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
: ，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
: call O的线程返回（产生一个水分子），其他的都block
: 看到有人说可以用一个ReentrantLock和两个Condition写，但试了一下怎么都不对。有
: 哪位大侠能指点一下，最好贴一下code.多谢！
t*****a
发帖数: 106
3
看了几个帖子，走了些case不对。兄台有semaphmore的code或者pseduo code贴一下，
多谢。

【在 r****7 的大作中提到】
: 难道不是semaphore就行么？
D**C
发帖数: 6754
4
两个blockingqueue如何

【在 t*****a 的大作中提到】
: 原题如下
: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
: ，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
: call O的线程返回（产生一个水分子），其他的都block
: 看到有人说可以用一个ReentrantLock和两个Condition写，但试了一下怎么都不对。有
: 哪位大侠能指点一下，最好贴一下code.多谢！
t*****a
发帖数: 106
5
应该可以，不过写起来稍微繁琐。主要是我觉得这题还是考lock的。

【在 D**C 的大作中提到】
: 两个blockingqueue如何
D**C
发帖数: 6754
6
我觉得就是producer consumer的变形

【在 t*****a 的大作中提到】
: 原题如下
: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
: ，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
: call O的线程返回（产生一个水分子），其他的都block
: 看到有人说可以用一个ReentrantLock和两个Condition写，但试了一下怎么都不对。有
: 哪位大侠能指点一下，最好贴一下code.多谢！
D**C
发帖数: 6754
7
应该不复杂，一个size是2，一个是1，细节的想想

【在 t*****a 的大作中提到】
: 应该可以，不过写起来稍微繁琐。主要是我觉得这题还是考lock的。
c*****m
发帖数: 271
8
不知道怎么做，这种题就是设计题么？或者考查多线程的？

【在 t*****a 的大作中提到】
: 原题如下
: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
: ，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
: call O的线程返回（产生一个水分子），其他的都block
: 看到有人说可以用一个ReentrantLock和两个Condition写，但试了一下怎么都不对。有
: 哪位大侠能指点一下，最好贴一下code.多谢！
d********o
发帖数: 12
9
直接用semaphore行吗？
semH 和 semO 初始都为0
seudo code
H()
sem_post(semH)
sem_wait(semO)
O()
sem_wait(semH)
sem_wait(semH)
sem_post(semO)
sem_post(semO)
t*****a
发帖数: 106
10
我多线程不好，有一个地方不太明白。假如现在输入了三个O,然后输入了两个H，怎么
保证是一个被block的O走两次，不是两个被block的O各自走一次啊。好像发你邮箱了，
sorry

【在 d********o 的大作中提到】
: 直接用semaphore行吗？
: semH 和 semO 初始都为0
: seudo code
: H()
: sem_post(semH)
: sem_wait(semO)
: O()
: sem_wait(semH)
: sem_wait(semH)
: sem_post(semO)
相关主题
● 昨天onsite被问到的 multithreading 题目● qualcomm 新鲜电面面经
● 又tmd的面砸了一个，还是贴贴面经● 求教三进程间同步的问题，原题是CC150第5版的16.5
● 贡献T家新鲜面经，求个bless● java concurrence 例子
进入JobHunting版参与讨论
t*****a
发帖数: 106
11
主要是H函数可能是producer也可能是consumer, O函数也一样。互相为对方的producer
,也消耗对方。。。H多了，O就是consumer, O多了，H就是consumer...

【在 D**C 的大作中提到】
: 应该不复杂，一个size是2，一个是1，细节的想想
D**C
发帖数: 6754
12
等我周二上班了写写看哈
加几个wait和notifyall就行，你在想想，我觉得可行

producer

【在 t*****a 的大作中提到】
: 主要是H函数可能是producer也可能是consumer, O函数也一样。互相为对方的producer
: ,也消耗对方。。。H多了，O就是consumer, O多了，H就是consumer...
d********o
发帖数: 12
13
是我想简单了。用mutex保护一下O进程中的两个sem_wait仿佛可以了。
不过这题用cond_var应该更高效

producer

【在 t*****a 的大作中提到】
: 主要是H函数可能是producer也可能是consumer, O函数也一样。互相为对方的producer
: ,也消耗对方。。。H多了，O就是consumer, O多了，H就是consumer...
d********o
发帖数: 12
14
H()
mutex_lock(lockH)
cntH++
if (cntH >= 2)
cond_signal(condH)
mutex_unlock(lockH)
sem_wait(semO)
O()
mutex_lock(lockH)
while(cntH < 2)
cond_wait(condH, lockH)
cntH -= 2
mutex_unlock(lockH)
sem_post(semO)
sem_post(semO)
手机打的，格式见谅。可能会有bug，我晚上有空再检查一下。

producer

【在 t*****a 的大作中提到】
: 主要是H函数可能是producer也可能是consumer, O函数也一样。互相为对方的producer
: ,也消耗对方。。。H多了，O就是consumer, O多了，H就是consumer...
t*****a
发帖数: 106
15
多谢了:)，看着应该是对的。还有个小问题，一般一个线程都是wait一个condition
variable, 这个 cond_wait(condH, lockH),可以吧condH改成global的flag吗。多线程
不是很懂。

【在 d********o 的大作中提到】
: H()
: mutex_lock(lockH)
: cntH++
: if (cntH >= 2)
: cond_signal(condH)
: mutex_unlock(lockH)
: sem_wait(semO)
: O()
: mutex_lock(lockH)
: while(cntH < 2)
u*a
发帖数: 247
16
给所有的O加一个lock是不是就解决啦？
H()
sem_post(semH)
sem_wait(semO)
O()
mutex_lock(lckO)
sem_wait(semH)
sem_wait(semH)
mutex_unlock(lckO)
sem_post(semO)
sem_post(semO)

【在 t*****a 的大作中提到】
: 我多线程不好，有一个地方不太明白。假如现在输入了三个O,然后输入了两个H，怎么
: 保证是一个被block的O走两次，不是两个被block的O各自走一次啊。好像发你邮箱了，
: sorry
t*****a
发帖数: 106
17
差不多这个意思，不过不能这么写。这么写就block其他O的生成了。大概意思就是
dragonmigo帖子里的那个方法。刚开始搞多线程，还不太清楚同时等多个cond怎么弄，
去查查库。

【在 u*a 的大作中提到】
: 给所有的O加一个lock是不是就解决啦？
: H()
: sem_post(semH)
: sem_wait(semO)
: O()
: mutex_lock(lckO)
: sem_wait(semH)
: sem_wait(semH)
: mutex_unlock(lckO)
: sem_post(semO)
u*a
发帖数: 247
18
题目不就是要把所有没有足够H的O block住么？

【在 t*****a 的大作中提到】
: 差不多这个意思，不过不能这么写。这么写就block其他O的生成了。大概意思就是
: dragonmigo帖子里的那个方法。刚开始搞多线程，还不太清楚同时等多个cond怎么弄，
: 去查查库。
t*****a
发帖数: 106
19
加mutex是对的，不好意思，看错了。开始想着用while+wait能按顺序输出HHO,发现不
行。写了个code，贴在这
public class H2O {
private Lock lock;
private Semaphore semH;
private Semaphore semO;
H2O()
{
lock=new ReentrantLock();
semH=new Semaphore(0);
semO=new Semaphore(0);
}
public void H() throws InterruptedException
{
semH.release();
semO.acquire();
System.out.println("H");
}
public void O() throws InterruptedException
{
lock.lock();
semH.acquire();
semH.acquire();
lock.unlock();
semO.release();
semO.release();
System.out.println("O");
}
public class Hthread implements Runnable
{
public void run() {
// TODO Auto-generated method stub
try {
H();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
public class Othread implements Runnable
{
public void run() {
// TODO Auto-generated method stub
try {
O();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
public static void main(String[] args) throws InterruptedException {
H2O ho=new H2O();
new Thread(ho.new Othread() ).start();
new Thread(ho.new Othread() ).start();
new Thread(ho.new Othread() ).start();
new Thread(ho.new Othread() ).start();
new Thread(ho.new Hthread() ).start();
new Thread(ho.new Hthread() ).start();
new Thread(ho.new Hthread() ).start();
new Thread(ho.new Hthread() ).start();
new Thread(ho.new Hthread() ).start();
new Thread(ho.new Hthread() ).start();
new Thread(ho.new Hthread() ).start();
new Thread(ho.new Hthread() ).start();
}
}

【在 u*a 的大作中提到】
: 题目不就是要把所有没有足够H的O block住么？
m*v
发帖数: 6
20
是不是和blockingqueue一个道理啊？
用一个data structure去coordinate两个threads？
public class H2O {
private int hCount;
private int oCount;
public H2O() {
hCount = 0;
oCount = 0;
}
public synchronized void addH() throws InterruptedException {
if(hCount == 2 && oCount == 1) {
System.out.println("add H, H2O");
hCount = 0;
oCount = 0;
notifyAll();
}
else {
while(hCount == 2) {
System.out.println("add H block");
wait();
}
if(hCount < 2) {
System.out.println("add H, h++");
hCount++;
}
}
}
public synchronized void addO() throws InterruptedException {
if(hCount == 2 && oCount == 1) {
System.out.println("add O, H2O");
hCount = 0;
oCount = 0;
notifyAll();
}
else {
while(oCount == 1) {
System.out.println("add O block");
wait();
}
if(oCount < 1) {
System.out.println("add O, o++");
oCount++;
}
}
}
}
相关主题
● Solution for interview question posted here before● Java编程讨论：LinkedIn的H2O
● multi-threading guru们● Quantcast电面
● LinkedIn 面经● 问个multi threading code 题，同时请问高手mutil threading 编程有什么好书，网站和教程推荐？
进入JobHunting版参与讨论
r*******t
发帖数: 99
21
贴个用1个lock，两个condition实现的。Code in Python:
def H():
# 加入一个H，检查是否可以形成H2O，若可以则notify另一个H和一个O
# 若不可则wait for cvH
global nH, nO, nH2O, lock, cvH, cvO
lock.acquire()
nH += 1
if nH >= 2 and nO >= 1:
nH -= 2
nO -= 1
nH2O += 1
print 'generating H2O molecule NO.%d' % nH2O
lock.release()
cvH.acquire()
cvH.notify()
cvH.release()
cvO.acquire()
cvO.notify()
cvO.release()
else:
lock.release()
cvH.acquire()
cvH.wait()
cvH.release()
print 'H returning'
def O():
# 加入一个O，检查是否可以形成H2O，若可以则notify两个H
# 若不可则wait for cvO
global nH, nO, nH2O, lock, cvH, cvO
lock.acquire()
nO += 1
if nH >= 2 and nO >= 1:
nH -= 2
nO -= 1
nH2O += 1
print 'generating H2O molecule NO.%d' % nH2O
lock.release()
cvH.acquire()
cvH.notify()
cvH.notify()
cvH.release()
else:
lock.release()
cvO.acquire()
cvO.wait()
cvO.release()
print 'O returning'
h*****a
发帖数: 1718
22
两年之前准备面试的时候写过一个，今天正好看到了，放在下面抛砖引玉吧。
package linkedin;
import java.util.Random;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
/**
* Created with IntelliJ IDEA.
* User: halfsea
*/
public class H2O {
private int countH, countO;
private Lock lock;
private Condition condH, condO;
private int hToRelease, oToRelease;
public H2O() {
countH = 0;
countO = 0;
lock = new ReentrantLock();
condH = lock.newCondition();
condO = lock.newCondition();
}
public void h() throws InterruptedException {
lock.lock();
try {
countH++;
if (countH>=2 && countO>=1) {
System.out.println("2 H and 1 O consumed in H()");
countH-=2;
countO--;
hToRelease++;
oToRelease++;
condH.signal();
condO.signal();
while (hToRelease<=0) {
condH.await();
}
hToRelease--;
}
} finally {
lock.unlock();
}
}
public void o() throws InterruptedException {
lock.lock();
try {
countO++;
if (countH>=2 && countO>=1) {
System.out.println("2 H and 1 O consumed in O()");
countH-=2;
countO--;
hToRelease+=2;
condH.signal();
condH.signal();
} else {
while (oToRelease<=0) {
condO.await();
}
oToRelease--;
}
} finally {
lock.unlock();
}
}
public static void main(String[] args) {
int n = 300;
final H2O h2o = new H2O();
Thread[] threads = new Thread[n];
for (int i=0; i final int id = i;
threads[i] = new Thread(new Runnable() {
@Override
public void run() {
for (int j=0; j<10; j++) {
if (id %3 == 0) {
try {
h2o.o();
System.out.println(String.format("Producing
an O in thread %d", id));
} catch (InterruptedException e) {
System.out.println(String.format("Thread %d
is interrupted for O().", id));
}
} else {
try {
h2o.h();
System.out.println(String.format("Producing
an H in thread %d", id));
} catch (InterruptedException e) {
System.out.println(String.format("Thread %d
is interrupted for H().", id));
}
}
}
}
});
}
for (Thread thread : threads) {
thread.start();
}
}
}

【在 t*****a 的大作中提到】
: 原题如下
: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
: ，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
: call O的线程返回（产生一个水分子），其他的都block
: 看到有人说可以用一个ReentrantLock和两个Condition写，但试了一下怎么都不对。有
: 哪位大侠能指点一下，最好贴一下code.多谢！
S*********9
发帖数: 541
23
楼上的解法会starve。思路是对的，用java解的话就用wait/notifyAll。和read/write
lock大同小异。

【在 m*v 的大作中提到】
: 是不是和blockingqueue一个道理啊？
: 用一个data structure去coordinate两个threads？
: public class H2O {
: private int hCount;
: private int oCount;
: public H2O() {
: hCount = 0;
: oCount = 0;
: }
: public synchronized void addH() throws InterruptedException {
r****7
发帖数: 2282
24
你这里semO.release();不能保证H先被调到吧。

【在 t*****a 的大作中提到】
: 加mutex是对的，不好意思，看错了。开始想着用while+wait能按顺序输出HHO,发现不
: 行。写了个code，贴在这
: public class H2O {
: private Lock lock;
: private Semaphore semH;
: private Semaphore semO;
: H2O()
: {
: lock=new ReentrantLock();
: semH=new Semaphore(0);
H****S
发帖数: 1359
25
kinda remember someone talked about this in his blog. Here is the idea,
import java.util.concurrent._
import scala.collection.mutable
val hq = mutable.Buffer[Condition]
val oq = mutable.Buffer[Condition]
val lock = new ReentrantLock()
def h() {
lock.lock()
try {
if (hq.size >= 1 && oq.size >= 1) {
val ch = hq.last
ch.signal()
val co = oq.last
oh.signal()
hq.trimEnd(1)
oq.trimEnd(1)
println("h")
} else {
val ch = lock.newCondition
hq += ch
ch.await()
println("h")
}
} finally { lock.unlock() }
}
def o() {
lock.lock()
try {
if (hq.size >= 2) {
val ch1 :: ch2 :: Nil = hq.takeRight(2).toList
ch1.signal()
ch2.signal()
hq.trimEnd(2)
println("o")
} else {
val co = lock.newCondition
cq += co
co.await()
println("o")
}
} finally { lock.unlock() }
}

【在 t*****a 的大作中提到】
: 原题如下
: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
: ，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
: call O的线程返回（产生一个水分子），其他的都block
: 看到有人说可以用一个ReentrantLock和两个Condition写，但试了一下怎么都不对。有
: 哪位大侠能指点一下，最好贴一下code.多谢！
m*****k
发帖数: 731
26
请教大牛，
从h()看来，
如果第一个线程run h() ， 它会安静的退出，
如果第二个线程run h() ， 它会安静的退出，
如果第三个线程run o()， 怎么让两个call H和一个call O的线程返回，
这时前两个h线程已经返回，不存在了啊。
也许我曲解了题意？
强烈怀疑 h() copy/paste 掉了else，应该象o()中那样。

【在 h*****a 的大作中提到】
: 两年之前准备面试的时候写过一个，今天正好看到了，放在下面抛砖引玉吧。
: package linkedin;
: import java.util.Random;
: import java.util.concurrent.locks.Condition;
: import java.util.concurrent.locks.Lock;
: import java.util.concurrent.locks.ReentrantLock;
: /**
: * Created with IntelliJ IDEA.
: * User: halfsea
: */
D**C
发帖数: 6754
27
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.atomic.AtomicInteger;
public class H2O {
//using blocking queue, so it's easy to just have 2 h and 1 o at most,
//other threads will be blocked.
ArrayBlockingQueue hQueue = new ArrayBlockingQueue(2);
ArrayBlockingQueue oQueue = new ArrayBlockingQueue(1);
AtomicInteger hCount = new AtomicInteger();
AtomicInteger h2oCount= new AtomicInteger();
AtomicInteger hPrintCount= new AtomicInteger();
AtomicInteger oPrintCount= new AtomicInteger();
Object o = new Object();//o notifier
Object h = new Object();//h notifier
Object hPrinted = new Object();// h already print notifier
public void H() {
try {
hQueue.put(new Object());
}
catch (InterruptedException e1) {
e1.printStackTrace();
}
//wait for two hs on 'h' lock
synchronized (h) {
h.notifyAll();
while (hQueue.size() != 2) {
try {h.wait();}
catch (InterruptedException e) {
h.notifyAll();
e.printStackTrace();
}
}
}
//we know we already have 2 hs, now wait for the o on 'o' lock
synchronized (o) {
while (oQueue.size() != 1) {
try {o.wait();}
catch (InterruptedException e) {
h.notifyAll();
e.printStackTrace();
}
}
}
System.out.println("H");
hCount.incrementAndGet();
hPrintCount.incrementAndGet();
synchronized (hPrinted) {
hPrinted.notifyAll();
}
}
public void O() {
try {
oQueue.put(new Object());
}
catch (InterruptedException e1) {
e1.printStackTrace();
}
//notify the waiting 'o' lock
synchronized (o) {
o.notifyAll();
}
//we know we already have 1 o, now wait for the 2 hs.
synchronized (h) {
while (hQueue.size() != 2) {
try {
h.wait();
}
catch (InterruptedException e) {
h.notifyAll();
e.printStackTrace();
}
}
}
//this is the tricky part, we need to find a way to
//terminate/clear the queue, so that other threads can come in.
//Trick part is we need to make sure the other hs are
//indeed 'printed'
synchronized (hPrinted) {
while (hCount.get() != 2) {
try {hPrinted.wait();}
catch(InterruptedException e) {
e.printStackTrace();
}
}
hCount.set(0);
hQueue.clear();
oQueue.clear();
System.out.println("O");
oPrintCount.incrementAndGet();
h2oCount.incrementAndGet();
}
}
public void randomCall() {
int count = 100;
int hCount = 0, oCount = 0;
do {
int i = new Double(Math.random()*100).intValue();
if (i%2 == 0){
hCount++;
new Thread(new Runnable() {
@Override
public void run() { H(); }
}).start();
}
else {
oCount++;
new Thread(new Runnable() {
@Override
public void run() { O();}
}).start();
}
count--;
} while(count > 0);
try {
Thread.sleep(1000);
}
catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("Add "+hCount+" H and "+oCount+" O");
System.out.println(h2oCount+" h2o");
System.out.println(hPrintCount+" Hs");
System.out.println(oPrintCount+" Os");
}
public static void main(String[] args) {
H2O h2o = new H2O();
h2o.randomCall();
}
}
D**C
发帖数: 6754
28
I tested it, i think it works well.
1 (共1页)
进入JobHunting版参与讨论
相关主题
● Quantcast电面● read-write locker的实现
● 问个multi threading code 题，同时请问高手mutil threading 编程有什么好书，网站和教程推荐？● 昨天onsite被问到的 multithreading 题目
● 一道多线程的面试题● 又tmd的面砸了一个，还是贴贴面经
● 求问一道multithreading问题● 贡献T家新鲜面经，求个bless
● 想问一下那道H2O的多线程题● qualcomm 新鲜电面面经
● 请教一下那道H2O的题● 求教三进程间同步的问题，原题是CC150第5版的16.5
● failed bloomberg phone interview● java concurrence 例子
● two functons and two threads● Solution for interview question posted here before
相关话题的讨论汇总
话题: h2o话题: thread话题: new话题: hcount

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑