H******7
发帖数: 1728 | 1 beanbun 大牛给讲讲设计题你怎么回答的吧？比如k-v design.比如web crawler
design.都拿到offer了回答肯定有过人之处。 |
A*******e
发帖数: 2419 | 2 沙发。
【在 H******7 的大作中提到】
: beanbun 大牛给讲讲设计题你怎么回答的吧？比如k-v design.比如web crawler
: design.都拿到offer了回答肯定有过人之处。
|
y*****e
发帖数: 712 | |
b*****n
发帖数: 618 | 4 没有过人之处，另外我不是大牛，这个版上藏龙卧虎。
distributed kv store和web crawler是system design里面最基本的题目吧，
看看现在比较流行的几个framework就可以了，比如HBase，Cassandra。
web crawler其实看考什么细节，每个人问的东西会不一样，design的题目其实是你既
要知道可能的问题是什么，还要知道怎么解决。。
比如web crawler IO会是问题，因为从网络上上下载网页会很慢，怎么能尽量不让IO
block |
b**********5
发帖数: 7881 | 5 那你说怎么让IO不block？ 问async http client？ thread pool？ 多个machine去下
载不同的URL？
【在 b*****n 的大作中提到】
: 没有过人之处，另外我不是大牛，这个版上藏龙卧虎。
: distributed kv store和web crawler是system design里面最基本的题目吧，
: 看看现在比较流行的几个framework就可以了，比如HBase，Cassandra。
: web crawler其实看考什么细节，每个人问的东西会不一样，design的题目其实是你既
: 要知道可能的问题是什么，还要知道怎么解决。。
: 比如web crawler IO会是问题，因为从网络上上下载网页会很慢，怎么能尽量不让IO
: block
|
b*****n
发帖数: 618 | 6 差不多，其实跟dropbox那个题目一样。
可以把整个crawl过程分解成多步，分别用专门的thread pool去做。
【在 b**********5 的大作中提到】
: 那你说怎么让IO不block？ 问async http client？ thread pool？ 多个machine去下
: 载不同的URL？
|
b**********5
发帖数: 7881 | 7 Dropbox要写runnable code， 你怎么写的？ 能写个pseudo code 么？
其他问题你怎么回答？ 比如怎么判断两个documents相似？
【在 b*****n 的大作中提到】
: 差不多，其实跟dropbox那个题目一样。
: 可以把整个crawl过程分解成多步，分别用专门的thread pool去做。
|
A*******e
发帖数: 2419 | 8 dropbox哪个题目啊？
【在 b*****n 的大作中提到】
: 差不多，其实跟dropbox那个题目一样。
: 可以把整个crawl过程分解成多步，分别用专门的thread pool去做。
|
b*****n
发帖数: 618 | 9 Dropbox那个我写的比较简单，就是分成parse document，download document两步，每
步用单独的threadpool，download完了就submit一个request另一个pool里面，你如果
想自己control request queue也可以。
两个documents相似这个我直接答的minhashing但是他们应该是用不同的方法。
【在 b**********5 的大作中提到】
: Dropbox要写runnable code， 你怎么写的？ 能写个pseudo code 么？
: 其他问题你怎么回答？ 比如怎么判断两个documents相似？
|
b**********5
发帖数: 7881 | 10 好几家公司问他web crawler design的题目， 还有G家问他怎么判断两个document相似
。。 如果不是我知道他以前在rocketfuel工作， 我还以为是和我以前一个team的人。
。。 他还做storm， 和我做的东西都很相似。。。
【在 A*******e 的大作中提到】
: dropbox哪个题目啊？
|
|
|
b**********5
发帖数: 7881 | 11 parse document？ 就是把你download完的html document里不同tag里的东西那出来？
你直接答了minhash， 要不要解释minhash怎么弄？ 还是就一句话完了？ 面试官没问
你还有没有其他方法?
【在 b*****n 的大作中提到】
: Dropbox那个我写的比较简单，就是分成parse document，download document两步，每
: 步用单独的threadpool，download完了就submit一个request另一个pool里面，你如果
: 想自己control request queue也可以。
: 两个documents相似这个我直接答的minhashing但是他们应该是用不同的方法。
|
b*****n
发帖数: 618 | 12 大牛，你哪里高就？
你怎么会没有offer？不可思议啊
【在 b**********5 的大作中提到】
: 好几家公司问他web crawler design的题目， 还有G家问他怎么判断两个document相似
: 。。 如果不是我知道他以前在rocketfuel工作， 我还以为是和我以前一个team的人。
: 。。 他还做storm， 和我做的东西都很相似。。。
|
b**********5
发帖数: 7881 | 13 我觉得你回答， 还要download， download完， 还要parse， 别搞不同threadpool。
。 用storm做算了。。。 storm全都帮你handle。。。
【在 b*****n 的大作中提到】
: Dropbox那个我写的比较简单，就是分成parse document，download document两步，每
: 步用单独的threadpool，download完了就submit一个request另一个pool里面，你如果
: 想自己control request queue也可以。
: 两个documents相似这个我直接答的minhashing但是他们应该是用不同的方法。
|
b*****n
发帖数: 618 | 14 是的，把download完的document的link都拿出来，因为是简单的版本我都没写检验link
是不是已经crawl过了，直接就扔过去就完了。
minhash稍微解释一下就可以了，另外面试官直接说了他们怎么搞的，就没再往下问这
个问题，不要再问我他们怎么搞的了。。其实我并没有完全听懂
【在 b**********5 的大作中提到】
: parse document？ 就是把你download完的html document里不同tag里的东西那出来？
: 你直接答了minhash， 要不要解释minhash怎么弄？ 还是就一句话完了？ 面试官没问
: 你还有没有其他方法?
|
b**********5
发帖数: 7881 | 15 你以前做什么的？ 和我以前做的东西， 简直一膜一样啊。。。
link
【在 b*****n 的大作中提到】
: 是的，把download完的document的link都拿出来，因为是简单的版本我都没写检验link
: 是不是已经crawl过了，直接就扔过去就完了。
: minhash稍微解释一下就可以了，另外面试官直接说了他们怎么搞的，就没再往下问这
: 个问题，不要再问我他们怎么搞的了。。其实我并没有完全听懂
|
b*****n
发帖数: 618 | 16 其实我当时确实这么想的，但问题是storm你没法马上写出能运行的code
【在 b**********5 的大作中提到】
: 我觉得你回答， 还要download， download完， 还要parse， 别搞不同threadpool。
: 。 用storm做算了。。。 storm全都帮你handle。。。
|
b*****n
发帖数: 618 | 17 我做的跟这个没什么关系，只是面试题而已
【在 b**********5 的大作中提到】
: 你以前做什么的？ 和我以前做的东西， 简直一膜一样啊。。。
:
: link
|
b**********5
发帖数: 7881 | 18 恩， 我觉得用storm也就说说而已， 面试时候写code， 那点时间， 能写出runnable
的function， 很牛了
【在 b*****n 的大作中提到】
: 其实我当时确实这么想的，但问题是storm你没法马上写出能运行的code
|
b**********5
发帖数: 7881 | 19 仍然是设计一个cocurrent环境下的time leased cache，但是有些
区别，假如delete操作是一个daemon thread来做不用太多考虑，但是get(key)操作的
逻辑是如果key不在cache里面，需要一个非常expensive的操作把对应value load进来
，如何让这个load的操作对同一个key尽量少发生，需要写代码实现。
这个题目， 你怎么答的? 不怎么看懂题目。。。 |
b**********5
发帖数: 7881 | 20 是不是就是说， 一个key在load的时候， 检查一下是否有相同的key，已经在load的了
？
【在 b**********5 的大作中提到】
: 仍然是设计一个cocurrent环境下的time leased cache，但是有些
: 区别，假如delete操作是一个daemon thread来做不用太多考虑，但是get(key)操作的
: 逻辑是如果key不在cache里面，需要一个非常expensive的操作把对应value load进来
: ，如何让这个load的操作对同一个key尽量少发生，需要写代码实现。
: 这个题目， 你怎么答的? 不怎么看懂题目。。。
|
|
|
b*****n
发帖数: 618 | 21 是这个意思。如果有相同的key已经在load了，其他的读操作要等load完了之后再进行。
【在 b**********5 的大作中提到】
: 是不是就是说， 一个key在load的时候， 检查一下是否有相同的key，已经在load的了
: ？
|
b**********5
发帖数: 7881 | 22 那还要你写code？ 你能写个你当时写的code看看么？ pseudocode也行啊
行。
【在 b*****n 的大作中提到】
: 是这个意思。如果有相同的key已经在load了，其他的读操作要等load完了之后再进行。
|
b**********5
发帖数: 7881 | 23 6. how to design a system to automatically detect hotspot on geo graph, a
hotspot is an area such that 打车的request远多于available driver的数量
这个你怎么回答的？ request此时， availabl driver都需要remember他们的location
， 你用geohash 作为key？ 但肯定又不能只是compare相同的key， 而是要compare一
个区域是不是hotspot |
b*****n
发帖数: 618 | 24 这个题目的关键是，key不能直接来做lock，因为equals的key可能是不同的object，所
以答案有点作弊嫌疑，需要用一个concurrenthashmap来maintain key跟对应的lock的
关系，然后假设create new object是相对来说比较cheap的操作（这个我当时持保留意
见。。），所以可以用concurrenthashmap的putIfAbsent这个method create一个新
object作为lock这样搞，真正的code根本没几行。
【在 b**********5 的大作中提到】
: 那还要你写code？ 你能写个你当时写的code看看么？ pseudocode也行啊
:
: 行。
|
b*****n
发帖数: 618 | 25 思路基本是一样的，允许存在误差，不用很完美。
关键是找一种hash，能够比较好的做range query就行了。
这个题目当时比较偏向于问设计整个workflow，直接上storm。。。
location
【在 b**********5 的大作中提到】
: 6. how to design a system to automatically detect hotspot on geo graph, a
: hotspot is an area such that 打车的request远多于available driver的数量
: 这个你怎么回答的？ request此时， availabl driver都需要remember他们的location
: ， 你用geohash 作为key？ 但肯定又不能只是compare相同的key， 而是要compare一
: 个区域是不是hotspot
|
b**********5
发帖数: 7881 | 26 那你是用什么hash？ 怎么做range query呢？ 我觉得workflow不是很难啊？ 难点就是
怎么hash， 怎么range query。。。
你的这题的storm 的topology是怎么设计的呢？
【在 b*****n 的大作中提到】
: 思路基本是一样的，允许存在误差，不用很完美。
: 关键是找一种hash，能够比较好的做range query就行了。
: 这个题目当时比较偏向于问设计整个workflow，直接上storm。。。
:
: location
|
b**********5
发帖数: 7881 | 27 没懂你什么意思？
我们现在要remember whether a key is already being loaded using the slow http
request。 那就用concurrent hashmap， 如果putIfAbsent成功的话， 就call 那个
slow http request。 如果不成功的话， 就说明已经有其他人在call 那个slow http
request了， 所以就等。
为什么还要create new object？ 你用了concurrent hash map， 就是存那个key不就
行了？
我不大懂的就是， 如果已经有别人在call 那个slow request， 那我应该怎么等结果
？
【在 b*****n 的大作中提到】
: 这个题目的关键是，key不能直接来做lock，因为equals的key可能是不同的object，所
: 以答案有点作弊嫌疑，需要用一个concurrenthashmap来maintain key跟对应的lock的
: 关系，然后假设create new object是相对来说比较cheap的操作（这个我当时持保留意
: 见。。），所以可以用concurrenthashmap的putIfAbsent这个method create一个新
: object作为lock这样搞，真正的code根本没几行。
|
b**********5
发帖数: 7881 | 28 那其他的操作， 怎么知道load完了？
行。
【在 b*****n 的大作中提到】
: 是这个意思。如果有相同的key已经在load了，其他的读操作要等load完了之后再进行。
|
A*******e
发帖数: 2419 | 29 完全没看懂啊。
1. equals的key可能是不同的object，这是什么意思？
2. 用一个concurrenthashmap来maintain key跟对应的lock的关系，前面不是说key不
能做lock？
3. putIfAbsent创建object怎么做lock？
【在 b*****n 的大作中提到】
: 这个题目的关键是，key不能直接来做lock，因为equals的key可能是不同的object，所
: 以答案有点作弊嫌疑，需要用一个concurrenthashmap来maintain key跟对应的lock的
: 关系，然后假设create new object是相对来说比较cheap的操作（这个我当时持保留意
: 见。。），所以可以用concurrenthashmap的putIfAbsent这个method create一个新
: object作为lock这样搞，真正的code根本没几行。
|
b**********5
发帖数: 7881 | |
|
|
m******3
发帖数: 346 | 31 顶一个，好多system design的题目不会，进来学习！ |
b*****n
发帖数: 618 | 32 你想的复杂了，其实真正需要的就是每个key一个锁，这样的话不需要锁整个cache，对
每个key load这个操作只要被这个key对应的锁保护起来就行了。
然后如果这样的话，唯一需要解决的问题是，key自己本身不能直接作为锁来用，原因
就是equals()的key并不一定是同一个object，这里需要的是equals的key应该对应的是
同一个锁就行。
所以这里需要一个concurrenthashmap来存key跟对应的锁的map，然后锁就用new
Object() new ReentrantLock() whatever都可以。
http
http
【在 b**********5 的大作中提到】
: 没懂你什么意思？
: 我们现在要remember whether a key is already being loaded using the slow http
: request。 那就用concurrent hashmap， 如果putIfAbsent成功的话， 就call 那个
: slow http request。 如果不成功的话， 就说明已经有其他人在call 那个slow http
: request了， 所以就等。
: 为什么还要create new object？ 你用了concurrent hash map， 就是存那个key不就
: 行了？
: 我不大懂的就是， 如果已经有别人在call 那个slow request， 那我应该怎么等结果
: ？
|
g*****g
发帖数: 34805 | 33 如果key是String，用intern()就可以当锁。
【在 b*****n 的大作中提到】
: 你想的复杂了，其实真正需要的就是每个key一个锁，这样的话不需要锁整个cache，对
: 每个key load这个操作只要被这个key对应的锁保护起来就行了。
: 然后如果这样的话，唯一需要解决的问题是，key自己本身不能直接作为锁来用，原因
: 就是equals()的key并不一定是同一个object，这里需要的是equals的key应该对应的是
: 同一个锁就行。
: 所以这里需要一个concurrenthashmap来存key跟对应的锁的map，然后锁就用new
: Object() new ReentrantLock() whatever都可以。
:
: http
: http
|
b*****n
发帖数: 618 | 34 1. HashMap判断key相同用的是equals()不是==，所以你可能用不同的object做key来
get，但是他们是相同的key
2. 所以需要一个map来存相同的key跟他们对应的唯一的一个lock的对应关系
3. object本身不就是monitor吗，直接synchronized(object)
如果不满意一定要用ReentrantLock也可以。
【在 A*******e 的大作中提到】
: 完全没看懂啊。
: 1. equals的key可能是不同的object，这是什么意思？
: 2. 用一个concurrenthashmap来maintain key跟对应的lock的关系，前面不是说key不
: 能做lock？
: 3. putIfAbsent创建object怎么做lock？
|
b*****n
发帖数: 618 | 35 还是老牛厉害
其实就是这个意思，只不过扩展到了不一定非要是string的key
【在 g*****g 的大作中提到】
: 如果key是String，用intern()就可以当锁。
|
z****e
发帖数: 54598 | 36
inverted index
【在 b*****n 的大作中提到】
: 还是老牛厉害
: 其实就是这个意思，只不过扩展到了不一定非要是string的key
|
b*****n
发帖数: 618 | 37 比如z-like order
不用很复杂。。。这个应该是他们还没做的东西，
面试的时候不用指望这种细节都很完美吧，没搞过geo的恐怕都需要回去查查资料大概
需要怎么做。
前面需要service tier把不同的event stream到Kafka，然后storm只是based on time
和geo hash做aggregation，可以提供不同的granularity，然后把结果存到任何一个
database或者kv store就行了。
【在 b**********5 的大作中提到】
: 那你是用什么hash？ 怎么做range query呢？ 我觉得workflow不是很难啊？ 难点就是
: 怎么hash， 怎么range query。。。
: 你的这题的storm 的topology是怎么设计的呢？
|
e********3
发帖数: 229 | 38 Time leased cache 那道题的code是这样吗?如下:
假设KEY没有collision的话就应该用get()就完,但是按照大牛说的情况就应该用
getConcurrent.是这样么?
private Map cache = new HashMap();
private Map keyLock = new HashMap();
public V get(K key) {
synchronized(key) {
if (cache.containsKey(key)) {
return cache.get(key);
} else {
return loadValueWithKey(key);
}
}
}
public V getConcurrent(K key) {
ReentrantLock lock;
if (keyLock.containsKey(key)) {
lock = keyLock.get(key);
} else {
lock = new ReentrantLock();
keyLock.put(key, lock);
}
lock.lock();
V value;
if (cache.containsKey(key)) {
value = cache.get(key);
} else {
value = loadValueWithKey(key);
}
lock.unlock();
return value;
} |
e********3
发帖数: 229 | 39 Time leased cache 那道题的code是这样吗?如下:
假设KEY没有collision的话就应该用get()就完,但是按照大牛说的情况就应该用
getConcurrent.是这样么?
private Map cache = new HashMap();
private Map keyLock = new HashMap();
public V get(K key) {
synchronized(key) {
if (cache.containsKey(key)) {
return cache.get(key);
} else {
return loadValueWithKey(key);
}
}
}
public V getConcurrent(K key) {
ReentrantLock lock;
if (keyLock.containsKey(key)) {
lock = keyLock.get(key);
} else {
lock = new ReentrantLock();
keyLock.put(key, lock);
}
lock.lock();
V value;
if (cache.containsKey(key)) {
value = cache.get(key);
} else {
value = loadValueWithKey(key);
}
lock.unlock();
return value;
} |
b**********5
发帖数: 7881 | 40 哎， 看了这答案， 觉得自己差距啊。。。 现在面试， 光刷题还不够。。还真要知道
这种memcache， hbase， cassandra的implementation， 我自己刷题， 还刷不好。。。
【在 b*****n 的大作中提到】
: 你想的复杂了，其实真正需要的就是每个key一个锁，这样的话不需要锁整个cache，对
: 每个key load这个操作只要被这个key对应的锁保护起来就行了。
: 然后如果这样的话，唯一需要解决的问题是，key自己本身不能直接作为锁来用，原因
: 就是equals()的key并不一定是同一个object，这里需要的是equals的key应该对应的是
: 同一个锁就行。
: 所以这里需要一个concurrenthashmap来存key跟对应的锁的map，然后锁就用new
: Object() new ReentrantLock() whatever都可以。
:
: http
: http
|
|
|
d******v
发帖数: 801 | |
b*****n
发帖数: 618 | 42 你这为啥需要有两个method呢，只是要实现一个get(key) method，这个method在
concurrent下要能工作，还要满足要求。
另外你的load这一步在哪里呢。。
);
【在 e********3 的大作中提到】
: Time leased cache 那道题的code是这样吗?如下:
: 假设KEY没有collision的话就应该用get()就完,但是按照大牛说的情况就应该用
: getConcurrent.是这样么?
: private Map cache = new HashMap();
: private Map keyLock = new HashMap();
: public V get(K key) {
: synchronized(key) {
: if (cache.containsKey(key)) {
: return cache.get(key);
: } else {
|
e********3
发帖数: 229 | 43 第一个method是说在没有concurrent的情况下是这样的.然后因为现在有concurrent,所
以就是第二个method.你可以忽略掉第一个Method直接看第二个.
load那一步在第二个Method里.在if else里面.我重新贴一次.
public class TimeLeasedCache {
private Map cache = new HashMap();
private Map keyLock = new HashMap();
public V getConcurrent(K key) {
ReentrantLock lock;
if (keyLock.containsKey(key)) {
lock = keyLock.get(key);
} else {
lock = new ReentrantLock();
keyLock.put(key, lock);
}
lock.lock();
V value;
if (cache.containsKey(key)) {
value = cache.get(key);
} else {
value = loadValueWithKey(key);
}
lock.unlock();
return value;
}
public V loadValueWithKey(K key) {
//Load value...
return null;
}
} |
b*****n
发帖数: 618 | 44 你的前几句
if(keyLock.containsKey(key)) {
...
}else {
...
}
会有race condition,你这样写没办法保证这个操作是atomic的。
这里keyLock必须是concurrenthashmap
然后需要用putIfAbsent才能保证atomacity
);
【在 e********3 的大作中提到】
: 第一个method是说在没有concurrent的情况下是这样的.然后因为现在有concurrent,所
: 以就是第二个method.你可以忽略掉第一个Method直接看第二个.
: load那一步在第二个Method里.在if else里面.我重新贴一次.
: public class TimeLeasedCache {
: private Map cache = new HashMap();
: private Map keyLock = new HashMap();
:
: public V getConcurrent(K key) {
: ReentrantLock lock;
: if (keyLock.containsKey(key)) {
|
e********3
发帖数: 229 | 45 多谢指正.已改:
private Map cache = new HashMap();
private ConcurrentHashMap keyLock = new
ConcurrentHashMap();
public V getConcurrent(K key) {
ReentrantLock lock = new ReentrantLock();
keyLock.putIfAbsent(key, lock);
lock.lock();
V value;
if (cache.containsKey(key)) {
value = cache.get(key);
} else {
value = loadValueWithKey(key);
}
lock.unlock();
return value;
}
|
s*****e
发帖数: 1679 | |
x*****n
发帖数: 195 | 47 大家来讨论下这两题吧，不确定考点在哪里。。。
1. 有意思的题目1，设计Bi-directional LRU cache data structure，既可以lookup
key to get value，也可以lookup value to get key，还支持set(key, value)操作，
后面又加了条件，concurrent的情况下，会有什么问题，如何改进，假如set这个操作
的频率远远小于get这个操作的频率，需要写代码实现。
维护key-》value，value-》key两个hashtable，其他跟场景的concurrent lru一样么？
4. 有意思的题目2，设计caltrain system，要实现caltrain上车下车刷卡扣钱整个功
能，assume每个station都跟一个central server相连，要处理如果有network
partition怎么办，eventually车费还是要charge到账户上，但是不能影响partition的
station正常运作。要处理某些人下车没刷卡怎么办，followup可以非常多
这个是智力题么。。。能不能把刷卡器放到车厢里，像bus那样，或者卡里面记录信息
？否则各个电脑在隔离的network里没法通信啊 |
J*******o
发帖数: 741 | |
J*******o
发帖数: 741 | |
b******g
发帖数: 77 | 50 推荐chris manning 教授的Introduction to information retrieval
看19和20章
http://www-nlp.stanford.edu/IR-book/
web crawler的基本知识都涵盖了。比如，如何做DNS resolution；如何判断两个网页
是否有重复内容；如何实现politeness（不要hit 一个网站太频繁）；如何实现，高质
量的网页（nytimes)crawl间隔短，低质量的间隔时间长。
【在 H******7 的大作中提到】
: beanbun 大牛给讲讲设计题你怎么回答的吧？比如k-v design.比如web crawler
: design.都拿到offer了回答肯定有过人之处。
|
