y***e
发帖数: 32 | 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*******e
发帖数: 1377 | 2 判断平方数有很多可以优化，比如 末位数字 0,1,4,5,6,9 再比如 4的倍数 8的倍数加
一。
之后估计可以 手算开平方法吧。
thread safe需要注意哪些问题，有没有大牛说一说阿。 |
c*******r
发帖数: 610 | |
e***a
发帖数: 1661 | |
M*******a
发帖数: 1633 | 5 估计就是问的是二分法找sqrt
好点么牛顿法
【在 h*******e 的大作中提到】
: 判断平方数有很多可以优化，比如 末位数字 0,1,4,5,6,9 再比如 4的倍数 8的倍数加
: 一。
: 之后估计可以 手算开平方法吧。
: thread safe需要注意哪些问题，有没有大牛说一说阿。
|
r*******k
发帖数: 1423 | 6 因式分解也行
然后所有的质因子的指数都得是偶数就行
【在 M*******a 的大作中提到】
: 估计就是问的是二分法找sqrt
: 好点么牛顿法
|
r*******k
发帖数: 1423 | 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******e
发帖数: 82 | 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**********4
发帖数: 528 | 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访问。
|
g***s
发帖数: 3811 | 10 因式分解复杂度太高。
这题估计想考的是用分治法来求大数的开方。
【在 r*******k 的大作中提到】
: 因式分解也行
: 然后所有的质因子的指数都得是偶数就行
|
