vm onsite 面经 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

vm onsite 面经

vm onsite 面经# JobHunting - 待字闺中

y*e2014-07-29 07:07

1 楼

最近有裁员传闻的。
1.把一个BST转化成cycular sorted doubly linked list
给定一个target，如何在BST中要到所有pair，之和等于target
2.实现一个固定size的queue，底层要用cycular array。
如何变成thread-safe
3.实现一个hash table，支持add, get, change
如何变成thread-safe
4.给定一个integer，判断是否是一个平方数（例如1，4，9，16，...）

h*e2014-07-29 07:07

2 楼

判断平方数有很多可以优化，比如末位数字 0,1,4,5,6,9 再比如 4的倍数 8的倍数加
一。
之后估计可以手算开平方法吧。
thread safe需要注意哪些问题，有没有大牛说一说阿。

c*r2014-07-29 07:07

3 楼

mark

e*a2014-07-29 07:07

4 楼

did u answer out all?

M*a2014-07-29 07:07

5 楼

估计就是问的是二分法找sqrt
好点么牛顿法

【在 h*******e 的大作中提到】

: 判断平方数有很多可以优化，比如末位数字 0,1,4,5,6,9 再比如 4的倍数 8的倍数加
: 一。
: 之后估计可以手算开平方法吧。
: thread safe需要注意哪些问题，有没有大牛说一说阿。

r*k2014-07-29 07:07

6 楼

因式分解也行
然后所有的质因子的指数都得是偶数就行

【在 M*******a 的大作中提到】

: 估计就是问的是二分法找sqrt
: 好点么牛顿法

r*k2014-07-29 07:07

7 楼

第一个，转化完了，正好是排了序的双向链表
标准2sum的解法
转化最简单的方法，中序遍历，存到一个list里
然后遍历这个list，改left和right指针

【在 y***e 的大作中提到】

: 最近有裁员传闻的。
: 1.把一个BST转化成cycular sorted doubly linked list
: 给定一个target，如何在BST中要到所有pair，之和等于target
: 2.实现一个固定size的queue，底层要用cycular array。
: 如何变成thread-safe
: 3.实现一个hash table，支持add, get, change
: 如何变成thread-safe
: 4.给定一个integer，判断是否是一个平方数（例如1，4，9，16，...）

m*e2014-07-29 07:07

8 楼

第三题是不是这样
方法一，对hash table的add/get/change操作都加锁，且是同一把锁，可以保证thread
-safe，但是效率低下。
方法二，对每一个slot各加一把锁，效率高，缺点是锁的数量要随
着slot扩展而增加，不太现实。
方法三，参照java的ConcurrentHashMap，将hash table划分为若干个segment，比如32
，每个segment拥有一把锁和一个非thread-safe的hash table。任何key先进行一次
hash，选择对应的segment，如果两个key hash到同一个segment就争抢同一把锁，否则
它们之间没有影响。抢到锁之后就可以对非thread-safe的hash table进性具体操作。
这个方法相当于最多允许32个线程同时对hash table访问。

Z*42014-07-29 07:07

9 楼

感觉方法三很靠谱。

thread
32

【在 m******e 的大作中提到】

: 第三题是不是这样
: 方法一，对hash table的add/get/change操作都加锁，且是同一把锁，可以保证thread
: -safe，但是效率低下。
: 方法二，对每一个slot各加一把锁，效率高，缺点是锁的数量要随
: 着slot扩展而增加，不太现实。
: 方法三，参照java的ConcurrentHashMap，将hash table划分为若干个segment，比如32
: ，每个segment拥有一把锁和一个非thread-safe的hash table。任何key先进行一次
: hash，选择对应的segment，如果两个key hash到同一个segment就争抢同一把锁，否则
: 它们之间没有影响。抢到锁之后就可以对非thread-safe的hash table进性具体操作。
: 这个方法相当于最多允许32个线程同时对hash table访问。