v******l
发帖数: 60 | 1 两个阿三面的，比较难听懂，但他们也算耐心。感觉不难，但也不在状态，估计面得一
般。
一共3题：
1. 层序打印 binary tree
2. 实现 BlockingQueue 的 take() 和 put()
public interface BlockingQueue
{
/** Retrieve and remove the head of the queue, waiting if no elements
are present. */
T take();
/** Add the given element to the end of the queue, waiting if necessary
for space to become available. */
void put (T obj);
}
3. 实现一共 TwoSum interface
public interface TwoSum {
/**
* Stores @param input in an internal data structure.
*/
void store(int input);
/**
* Returns true if there is any pair of numbers in the internal data
structure which
* have sum @param val, and false otherwise.
* For example, if the numbers 1, -2, 3, and 6 had been stored,
* the method should return true for 4, -1, and 9, but false for 10, 5,
and 0
*/
boolean test(int val);
} |
f*******w
发帖数: 1243 | |
p***y
发帖数: 637 | 3 不事先练熟了不可能做完啊
或者准备个答案库，但照着敲也要时间啊
是不是人人在网上查答案，把bar抬高了
【在 f*******w 的大作中提到】
: 现在都觉得电面45分钟做三题也不咋地了么…
|
w*****5
发帖数: 75 | |
w**********h
发帖数: 31 | 5 赶紧google了一下第二题，是用wait() 和notify() 来实现吗？还有没有其他比较好的
实现方式？ |
l*****a
发帖数: 14598 | 6 经典的producer/consumer问题
用三个semaphore...
【在 w**********h 的大作中提到】
: 赶紧google了一下第二题，是用wait() 和notify() 来实现吗？还有没有其他比较好的
: 实现方式？
|
s*****r
发帖数: 43070 | 7 两个吧
这题有点偏难，因为太基础了，很少会考到
【在 l*****a 的大作中提到】
: 经典的producer/consumer问题
: 用三个semaphore...
|
g**e
发帖数: 6127 | 8 大牛，一个ReentrantLock两个condition就行啦
好的
【在 l*****a 的大作中提到】
: 经典的producer/consumer问题
: 用三个semaphore...
|
g**e
发帖数: 6127 | 9 最近被考了一个，还要求写lockfree的版本
【在 s*****r 的大作中提到】
: 两个吧
: 这题有点偏难，因为太基础了，很少会考到
|
l*****a
发帖数: 14598 | 10 不会用condition只会semaphore
中间那个换成lock/mutex都可
【在 g**e 的大作中提到】
: 大牛，一个ReentrantLock两个condition就行啦
:
: 好的
|
|
|
l*****a
发帖数: 14598 | 11 这个还难
去查查以前你们厂考的那个什么H2O
【在 s*****r 的大作中提到】
: 两个吧
: 这题有点偏难，因为太基础了，很少会考到
|
M*****M
发帖数: 20 | 12 第三题
内部数据结构用BST，不用array?以便void store(int input)时lgN？
boolean test(int val)内部先inorder BST,然后two sum？ |
y**********u
发帖数: 6366 | 13 1个Mutex，2个semaphore, not_full和not_empty吧
【在 s*****r 的大作中提到】
: 两个吧
: 这题有点偏难，因为太基础了，很少会考到
|
h*******0
发帖数: 270 | 14 刚刚看了下这个：https://twitter.github.io/scala_school/concurrency.html
所以可不可以这样呢？
public interface BlockingQueue
{
/** Retrieve and remove the head of the queue, waiting if no elements
are present. */
T take()｛
this.synchronized{
...
}
｝
/** Add the given element to the end of the queue, waiting if necessary
for space to become available. */
void put (T obj){
this.synchronized{
...
}
}
} |
v******l
发帖数: 60 | 15 两个阿三面的，比较难听懂，但他们也算耐心。感觉不难，但也不在状态，估计面得一
般。
一共3题：
1. 层序打印 binary tree
2. 实现 BlockingQueue 的 take() 和 put()
public interface BlockingQueue
{
/** Retrieve and remove the head of the queue, waiting if no elements
are present. */
T take();
/** Add the given element to the end of the queue, waiting if necessary
for space to become available. */
void put (T obj);
}
3. 实现一共 TwoSum interface
public interface TwoSum {
/**
* Stores @param input in an internal data structure.
*/
void store(int input);
/**
* Returns true if there is any pair of numbers in the internal data
structure which
* have sum @param val, and false otherwise.
* For example, if the numbers 1, -2, 3, and 6 had been stored,
* the method should return true for 4, -1, and 9, but false for 10, 5,
and 0
*/
boolean test(int val);
} |
f*******w
发帖数: 1243 | |
p***y
发帖数: 637 | 17 不事先练熟了不可能做完啊
或者准备个答案库，但照着敲也要时间啊
是不是人人在网上查答案，把bar抬高了
【在 f*******w 的大作中提到】
: 现在都觉得电面45分钟做三题也不咋地了么…
|
w*****5
发帖数: 75 | |
w**********h
发帖数: 31 | 19 赶紧google了一下第二题，是用wait() 和notify() 来实现吗？还有没有其他比较好的
实现方式？ |
l*****a
发帖数: 14598 | 20 经典的producer/consumer问题
用三个semaphore...
【在 w**********h 的大作中提到】
: 赶紧google了一下第二题，是用wait() 和notify() 来实现吗？还有没有其他比较好的
: 实现方式？
|
|
|
s*****r
发帖数: 43070 | 21 两个吧
这题有点偏难，因为太基础了，很少会考到
【在 l*****a 的大作中提到】
: 经典的producer/consumer问题
: 用三个semaphore...
|
g**e
发帖数: 6127 | 22 大牛，一个ReentrantLock两个condition就行啦
好的
【在 l*****a 的大作中提到】
: 经典的producer/consumer问题
: 用三个semaphore...
|
g**e
发帖数: 6127 | 23 最近被考了一个，还要求写lockfree的版本
【在 s*****r 的大作中提到】
: 两个吧
: 这题有点偏难，因为太基础了，很少会考到
|
l*****a
发帖数: 14598 | 24 不会用condition只会semaphore
中间那个换成lock/mutex都可
【在 g**e 的大作中提到】
: 大牛，一个ReentrantLock两个condition就行啦
:
: 好的
|
l*****a
发帖数: 14598 | 25 这个还难
去查查以前你们厂考的那个什么H2O
【在 s*****r 的大作中提到】
: 两个吧
: 这题有点偏难，因为太基础了，很少会考到
|
M*****M
发帖数: 20 | 26 第三题
内部数据结构用BST，不用array?以便void store(int input)时lgN？
boolean test(int val)内部先inorder BST,然后two sum？ |
y**********u
发帖数: 6366 | 27 1个Mutex，2个semaphore, not_full和not_empty吧
【在 s*****r 的大作中提到】
: 两个吧
: 这题有点偏难，因为太基础了，很少会考到
|
h*******0
发帖数: 270 | 28 刚刚看了下这个：https://twitter.github.io/scala_school/concurrency.html
所以可不可以这样呢？
public interface BlockingQueue
{
/** Retrieve and remove the head of the queue, waiting if no elements
are present. */
T take()｛
this.synchronized{
...
}
｝
/** Add the given element to the end of the queue, waiting if necessary
for space to become available. */
void put (T obj){
this.synchronized{
...
}
}
} |
f**********t
发帖数: 1001 | 29 class BlockingQueue {
const size_t kBufSize = 10;
// string _buf(10, '\0'); // have to use = for in-place member
initialization
string _buf = string(kBufSize, '\0');
size_t _head = 0, _tail = 0;
condition_variable _cv;
mutex _mx;
public:
/** Retrieve and remove the head of the queue, waiting if no elements
are present. */
char take() {
unique_lock lg(_mx);
_cv.wait(lg, [this](){return _head != _tail;});
char res = _buf[_head];
_head = (1 + _head) % kBufSize;
_cv.notify_one();
return res;
}
/** Add the given element to the end of the queue, waiting if necessary
for space to become available. */
char put (char obj) {
unique_lock ul(_mx);
_cv.wait(ul, [this](){return (_tail + 1) % kBufSize != _head;});
_buf[_tail] = obj;
_tail = (1 + _tail) % kBufSize;
_cv.notify_one();
return obj;
}
};
BlockingQueue bq;
void consumer() {
while (1) {
cout << "take:" << bq.take() << endl << flush;
this_thread::sleep_for (std::chrono::seconds(2));
}
}
void producer() {
while (1) {
cout << "put:" << bq.put(rand() % 26 + 'a') << endl << flush;
this_thread::sleep_for (std::chrono::seconds(1));
}
}
void BlockingQueueTest() {
thread t0(consumer);
thread t1(producer);
t0.join();
t1.join();
} |
i*****h
发帖数: 1534 | |
|
|
c*****m
发帖数: 271 | 31 能不能讲第三题怎么做呢？要twosum得排好序才能O(N)，关键是用什么数据结构来保证
store()是O(lgn)的呢？
【在 v******l 的大作中提到】
: 两个阿三面的，比较难听懂，但他们也算耐心。感觉不难，但也不在状态，估计面得一
: 般。
: 一共3题：
: 1. 层序打印 binary tree
: 2. 实现 BlockingQueue 的 take() 和 put()
: public interface BlockingQueue
: {
: /** Retrieve and remove the head of the queue, waiting if no elements
: are present. */
: T take();
|
s******d
发帖数: 9806 | 32 BST + double linked list. i.e., each node has prev/next/left/right.
Rebalancing the tree is a problem, any ideas?
【在 c*****m 的大作中提到】
: 能不能讲第三题怎么做呢？要twosum得排好序才能O(N)，关键是用什么数据结构来保证
: store()是O(lgn)的呢？
|
M****w
发帖数: 11 | 33 Just use Hashtable with key= number, value= appear times of number will be
easier
【在 s******d 的大作中提到】
: BST + double linked list. i.e., each node has prev/next/left/right.
: Rebalancing the tree is a problem, any ideas?
|
e***n
发帖数: 42 | 34 第三题:
1. brutalforce：maintain a set to store all the pairwise sums, construction:
O(n^2), lookup O(1), space O(n^2);
2. sorted list: construction O(n*logn), lookup O(n), space O(n).
行不? |
s******d
发帖数: 9806 | 35 hashtable is unordered, how do you come up with the twoSum then?
why you need appear times btw?
【在 M****w 的大作中提到】
: Just use Hashtable with key= number, value= appear times of number will be
: easier
|
e***n
发帖数: 42 | 36 第二题：
public class BlockingQueueImpl implements BlockingQueue{
Queue q = new LinkedList();
int cap = 10;
long timeOut = 1000;
@Override
public Object take() {
while(q.isEmpty()){
try {
this.wait(timeOut);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
Object rst = q.poll();
this.notifyAll();
return rst;
}
@Override
public void put(Object obj) {
while(q.size()==cap){
try{
this.wait(timeOut);
} catch (InterruptedException e){
e.printStackTrace();
}
}
q.offer((T) obj);
}
} |
c***r
发帖数: 280 | 37 关于第二题blocking queue,网上找到个code觉得不错，1个mutex, 1个condition
variable.
原贴在这：
http://www.fgdsb.com/2015/01/03/provider--consumer/
template class block_queue {
condition_variable _cond;
mutex _mutex;
std::queue _data;
public:
void push(const T& value) {
unique_lock l(_mutex);
_data.push(value);
l.unlock();
_cond.notify_one();
}
T pop() {
unique_lock l(_mutex);
_cond.wait(l, [&](){ return !_data.empty(); });
auto item = _data.front();
_data.pop();
return item;
}
};
int main() {
block_queue q;
int itemNum = 10;
thread pro([&]{
for(int i = 0; i < itemNum; ++i) {
q.push(i);
printf("push:%dn",i);
}
});
thread cus([&]{
for(int i = 0; i < itemNum; ++i) {
int n = q.pop();
printf("pop:%dn",n);
}
});
cus.join();
pro.join();
return 0;
}
【在 v******l 的大作中提到】
: 两个阿三面的，比较难听懂，但他们也算耐心。感觉不难，但也不在状态，估计面得一
: 般。
: 一共3题：
: 1. 层序打印 binary tree
: 2. 实现 BlockingQueue 的 take() 和 put()
: public interface BlockingQueue
: {
: /** Retrieve and remove the head of the queue, waiting if no elements
: are present. */
: T take();
|
m********8
发帖数: 36 | 38 unordered没关系吧， 我们只需要返回找到没有。
appear times 是可能一个数字用两次。 比如 2+2=4， 如果不记录次数的话判断不出
。 但可能用一个boolean作为flag也能记录， 剩点空间？
大牛们能不能帮忙看看这样行不？ 谢谢！
我用c++写的。
struct TwoSum {
/**
* Stores @param input in an internal data structure.
*/
public:
void store(int input){
map[input]++;
}
/**
* Returns true if there is any pair of numbers in the internal data
structure which
* have sum @param val, and false otherwise.
* For example, if the numbers 1, -2, 3, and 6 had been stored,
* the method should return true for 4, -1, and 9, but false for 10, 5,
and 0
*/
bool test(int val){
for(auto it=map.begin(); it != map.end(); it++){
int cur = it->first;
if(cur+cur == val){
if(map[cur] >1)
return true;
else
continue;
}
else if(map.find(val-cur) != map.end())
return true;
}
return false;
}
private:
unordered_map map;
};
【在 s******d 的大作中提到】
: hashtable is unordered, how do you come up with the twoSum then?
: why you need appear times btw?
|
s*******m
发帖数: 228 | 39 求代码。
【在 l*****a 的大作中提到】
: 经典的producer/consumer问题
: 用三个semaphore...
|
