how to code this question of LinkedIn - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

how to code this question of LinkedIn

how to code this question of LinkedIn# JobHunting - 待字闺中

k*r2015-11-25 08:11

1 楼

System design
a. Output produce(Input input)
b. Output merge(Output o1, Output o2)
c. Now given a list of inputs List inputs, using k threads to
generate the result.
d. Queue, lock, thread safe and so on
any idea? Thanks,

b*n2015-11-25 08:11

2 楼

不知道这个为什么会算system design。
抛砖一下，这个其实就是个BlockingQueue。
用一个queue存中间的output，
每个thread 做的事情是：
blocking的取两个（lock保护，wait）
call merge（不用保护）
put回去（lock保护，signal）

k*r2015-11-25 08:11

3 楼

Thanks for your reply.
>put回去:
do you mean to put the output back to the link?
How to use the number of thread (k) in the answer?

【在 b*****n 的大作中提到】

: 不知道这个为什么会算system design。
: 抛砖一下，这个其实就是个BlockingQueue。
: 用一个queue存中间的output，
: 每个thread 做的事情是：
: blocking的取两个（lock保护，wait）
: call merge（不用保护）
: put回去（lock保护，signal）

E*t2015-11-25 08:11

4 楼

Output produce(Input input) 里面这个produce做什么？任意一个函数？

k*r2015-11-25 08:11

5 楼

I think this produce is just about to transfer input into output.

【在 E******t 的大作中提到】

: Output produce(Input input) 里面这个produce做什么？任意一个函数？

b*n2015-11-25 08:11

6 楼

对啊，再扔回到queue。
k是多少重要吗？我可能没明白你的问题。
我的理解，用k个thread是为了让merge这个可能比较开销比较大的操作并行。

【在 k****r 的大作中提到】

: Thanks for your reply.
: >put回去:
: do you mean to put the output back to the link?
: How to use the number of thread (k) in the answer?

k*r2015-11-25 08:11

7 楼

I partly understand your idea.
Do you mean to use a PriorityQueue to create two functions: producer and
consumer? In the main function, we can use producer to put all elements of
the list into this queue, and use k thread to do consumer. Each consumer
just get the first two elements of the queue to merge a new output and put
it back into the blockingQueue.
If so, do you think we could use k producers to put things into the queue?

【在 b*****n 的大作中提到】

b*n2015-11-25 08:11

8 楼

我只是说了merge的那部分，produce那部分也比较好办把。
idea是一样的，可以用两个queue，
第一个queue里开始存的都是input，
produce完的output放到第二个queue里面。
每个thread worker的逻辑是一个while(true) loop
先看一下第一个queue里面还有没有input没处理，如果还有就先处理produce，
否则就是上面的处理merge的逻辑。
其实就是个size为k的threadpool。
我可能还是没明白你说的 “use a PriorityQueue to create two functions:
producer and consumer” 是什么意思？

【在 k****r 的大作中提到】

: I partly understand your idea.
: Do you mean to use a PriorityQueue to create two functions: producer and
: consumer? In the main function, we can use producer to put all elements of
: the list into this queue, and use k thread to do consumer. Each consumer
: just get the first two elements of the queue to merge a new output and put
: it back into the blockingQueue.
: If so, do you think we could use k producers to put things into the queue?

t*r2015-11-25 08:11

9 楼

看workload,如果produce的速度比较快，用K-1个线程/lockfree queue+一个merge
thread搞应该比N个thread用各种locking快，不然lock contention太高了

【在 b*****n 的大作中提到】

: 对啊，再扔回到queue。
: k是多少重要吗？我可能没明白你的问题。
: 我的理解，用k个thread是为了让merge这个可能比较开销比较大的操作并行。

b*n2015-11-25 08:11

10 楼

对的，这个要看具体的情况，因为题目也没有提produce／merge哪个速度快，
不同情况下确实要调整解决方案，我只是提了一个比较naive的思路，假设merge开销也
很大。。

【在 t*********r 的大作中提到】

: 看workload,如果produce的速度比较快，用K-1个线程/lockfree queue+一个merge
: thread搞应该比N个thread用各种locking快，不然lock contention太高了

k*r2015-11-25 08:11

11 楼

good idea!!!
You mean the consumer could decide to process the first Queue or the second
Queue, right?
What I was saying is to define producer and consumer with this priorityQueue
. Like:
class Producer implements Runnable {
private BlockingQueue bq = null;
public Producer(BlockingQueue queue) {
this.setBlockingQueue(queue);
}
public void run() {
....
}
}
class Consumer implements Runnable {
protected BlockingQueue queue = null;
public Consumer(BlockingQueue queue) {
this.queue = queue;
}
public void run() {
....
}
}
public static void main(String[] args) throws Exception {
BlockingQueue bq = new ArrayBlockingQueue(1000);
Producer producer = new Producer(bq);
Consumer[] consumers = new Consumer[8];
for (int i = 0; i < 8; i++) {
consumers[i] = new Consumer(bq);
}
new Thread(producer).start();
for (int i = 0; i < 8; i++) {
new Thread(consumers[i]).start();
}
}
BTW, should I use k consumers like this way. I am new in concurrent things.
In addition, should I use k producers here and how if needed?

【在 b*****n 的大作中提到】

: 我只是说了merge的那部分，produce那部分也比较好办把。
: idea是一样的，可以用两个queue，
: 第一个queue里开始存的都是input，
: produce完的output放到第二个queue里面。
: 每个thread worker的逻辑是一个while(true) loop
: 先看一下第一个queue里面还有没有input没处理，如果还有就先处理produce，
: 否则就是上面的处理merge的逻辑。
: 其实就是个size为k的threadpool。
: 我可能还是没明白你说的 “use a PriorityQueue to create two functions:
: producer and consumer” 是什么意思？

t*r2015-11-25 08:11

12 楼

所以说这道题我觉得是个design题，考的主要是面试者会不会去问workload的问题然后
去选最优的tradeoff

【在 b*****n 的大作中提到】

: 对的，这个要看具体的情况，因为题目也没有提produce／merge哪个速度快，
: 不同情况下确实要调整解决方案，我只是提了一个比较naive的思路，假设merge开销也
: 很大。。

k*r2015-11-25 08:11

13 楼

According to your approach, I tried to code one. Please kindly let me know,
if you see anything wrong:) (Here, I assume both produce and merge are
costly)
public class MergeOutput {
public static void main(String[] args) throws Exception {
List list = new ArrayList<>();
BlockingQueue bq1 = new ArrayBlockingQueue(1000);
BlockingQueue bq2 = new ArrayBlockingQueue(1000);
Producer producer = new Producer(bq1, list);
Consumer[] consumers = new Consumer[8];
for (int i = 0; i < 8; i++) {
consumers[i] = new Consumer(bq1, bq2);
}
new Thread(producer).start();
for (int i = 0; i < 8; i++) {
new Thread(consumers[i]).start();
}
System.out.println(bq2.peek());
}
}
class Producer implements Runnable {
private BlockingQueue bq = null;
private List list;
public Producer(BlockingQueue queue, List list) {
this.setBlockingQueue(queue);
this.list = list;
}
public void run() {
for (Integer i : list) {
try {
bq.put(i);
} catch (InterruptedException ex) {
Logger.getLogger(Producer.class.getName()).log(Level.SEVERE,
null, ex);
}
}
}
public void setBlockingQueue(BlockingQueue bq) {
this.bq = bq;
}
}
class Consumer implements Runnable {
protected BlockingQueue produce_queue = null;
protected BlockingQueue merge_queue = null;
public Consumer(BlockingQueue queue1, BlockingQueue queue2) {
this.produce_queue = queue1;
this.merge_queue = queue2;
}
public void run() {
while (!produce_queue.isEmpty() || merge_queue.size() > 1) {
try {
if (!produce_queue.isEmpty()) {
merge_queue.add(produce((Integer)produce_queue.take()));
} else {
Integer a, b;
a = (Integer)merge_queue.take();
b = (Integer)merge_queue.take();
merge_queue.put(merge(a, b));
}
} catch (InterruptedException ex) {
Logger.getLogger(Consumer.class.getName()).log(Level.SEVERE,
null, ex);
}
}

}

public Integer produce(Integer input) {
return input * 10;
}
public Integer merge(Integer input1, Integer input2) {
return input1+input2;
}
}

【在 b*****n 的大作中提到】

b*n2015-11-25 08:11

14 楼

你说的对，确实应该这么考虑。

【在 t*********r 的大作中提到】

: 所以说这道题我觉得是个design题，考的主要是面试者会不会去问workload的问题然后
: 去选最优的tradeoff

k*r2015-11-25 08:11

15 楼

Thank you for your interesting comment, but I am not very clear.
If we use two PriorityQueues as DouBean mentioned. One is for produce, the
other is for merge. Do you mean some thread working on the merge one might
wait for the output of the produce when you say lock contention? If the
produce is fast, is that fine to wait? If the produce is not fast, seems
like it is still OK.

【在 t*********r 的大作中提到】

: 看workload,如果produce的速度比较快，用K-1个线程/lockfree queue+一个merge
: thread搞应该比N个thread用各种locking快，不然lock contention太高了

r*g2015-11-25 08:11

16 楼

没看明白你们的讨论
感觉只用一个queue就行了，每次取出2个list，merge，然后放回queue的队尾，不需要
两个queue，这样下去直到只有一个element，就是最后的结果。
这里说的是两两merge list。
这个题为啥是design呢，是不是说还可以通过heap来做merge，也就是说，一次性取出
多个list，用min heap来做merge？
thanks

【在 b*****n 的大作中提到】

r*g2015-11-25 08:11

17 楼

没看明白，求指点。
是说一共两种方法：
1，每次去两个list出来merge，然后放回queue
2，每次取一堆list，用min heap来merge？
但是这里说的什么lockfree queue？
谢谢了。

【在 t*********r 的大作中提到】

: 看workload,如果produce的速度比较快，用K-1个线程/lockfree queue+一个merge
: thread搞应该比N个thread用各种locking快，不然lock contention太高了