r****m
发帖数: 70 | 1 一面
问了Mutex, Semaphore
Coding:
1. 字符串是不是有效的数字
2. Compute the value of an expression in Reverse Polish order， 注意判断结果
是不是有效的
二面
1. 两种方法写Singleton
2. 按层打印二叉树，层间加分割
3. 在rotated sort array中查找一个数 |
|
s*****s
发帖数: 157 | 2 另外， mutex 和 semaphore, 一个可以recursive, 一个不行 |
|
j*****I
发帖数: 2626 | 3 看了一下，好像spinlock和mutex的一个主要区别是后者是系统维护，前者是thread自
己check. short waiting的情况下，前者比较efficient.
mutex和semaphore的区别你研究的太深了吧。any number和binary一般足够了。说多了
反而容易露马脚吧。
hold
快。 |
|
f*********d
发帖数: 140 | 4 刚才面完
三哥, 以为又会搞我的...总共38分钟,问了如下问题，感觉他是想整我来着, 结果貌似
未遂:)
前戏: 自我介绍
高潮:
1. 荷兰国旗问题, 给算法, 分析实例, 都完整的给他走了一遍 rrggbbgrbg
2. 一个建筑物，楼层有无限， 有无限多的鸡蛋，仍最少次数找出最高的那层扔下去鸡
蛋不会挂
搞了一会， 最后用类似二分的思想， 1 2 4 8 16.... 先找到区间， 再二分查找
， 我说不知道是不是最优的， 他说可以了， move on吧
3. priority inversion
不知道inversion 什么意思， 查了一下， 就瞎猜的是降低进程优先级的， 承认了
自己不懂这个概念
4. volatile
问他是不是c里面的概念， 他说是的， 然后我balabala
5. static
问他是不是c里面的概念， 他说是的， 然后我balabala
然后说在c++里面，他说够了， 就不说了。。。move on
6. mutex and semaphore
7. 什么是multi-threading
8. 让我解释recursio... 阅读全帖 |
|
n******t
发帖数: 4406 | 5 这是程序员里面不傻逼的了，还在deal semaphore和mutex这种东西，
现在大部分马工都在搞business logic或者Javascript这种破东西。 |
|
|
l*********u
发帖数: 19053 | 7 哪位给说说，俺thread用的不多，理解的对不对：
semaphore像个on／off flag，mutex lock／unlock是锁门／开门。 |
|
j*****y
发帖数: 1071 | 8 coding 前先各自聊了自己的 project.
问了一道热身题. mutex 和 semaphore 的区别，如何实现，我说用 counter
1. 判断一个string 是不是 number, 不用考虑 科学计数的情况
2. calculate reverse polish value
第二题目 pop 的时候把 顺序搞错了
应该是 a - b, 变成了 b- a
也许会挂在这个 bug 里面了 |
|
j*****y
发帖数: 1071 | 9 L 家电面感觉量很大。
对方是两个人， 上来每个人聊了自己的project, 然后让我聊自己的 project
然后做两道 coding 题目前还 问了一个 mutex 和 semaphore的区别，问如何实现他们
Iterator |
|
j*****y
发帖数: 1071 | 10 我看到的好像是用 counter,
mutex 的counter 是 start from 1
semaphore 的counter, 比如两个线程的话, start from 2
acquire 以后就 decrease the counter by 1,
release的话就 increase the counter by 1 |
|
b****g
发帖数: 192 | 11 careerCup和leetcode上都没找到 |
|
|
j*****y
发帖数: 1071 | 13 要搞懂这些 api 吧
pthread_mutex_init
pthread_mutex_create
pthread_mutex_wait
pthread_mutex_lock
pthread_mutex_unlock
pthread_mutex_signal
pthread_mutex_condition
还有 semaphore的 |
|
j*****y
发帖数: 1071 | 14 谢谢。 刚才看了 那个 consumer/producer 的 wiki, 对于 queue而已就是要对于
queue的size用 semaphore, 是吧? |
|
h****n
发帖数: 1093 | 15 其实两个binary semaphore就足够了，一个sem_full另外一个是sem_empty 初值都为0
pop操作只有在检测到queue为空的时候才去wait(sem_full)，当push一个新元素的时候
都会去notify一个等待的线程
push操作检测queue为满的时候做类似操作
如果光用mutex的话，当queue为空的话，做pop操作的线程即使拿到mutex每次都检测到
queue为空，这样子就做了很多无谓的工作，还占用了时间片
而用同步机制的话，这种情况下会被scheduler直接放进pending list里面直到被
notify避免了cpu的浪费 |
|
l*******b
发帖数: 2586 | 16 真的不牛,木有实践经验.所以也不知道这个什么地方能用上.听同学说他们公司也在用.
好玩确实觉得好玩,functional的思路总感觉解一些science里来的问题比较合适,我没
学过matlab,后来看python挺好玩,结果试了下觉得没有比c/c++更爽,随即作罢.所以一
直想找一个可以把玩的.scala速度貌似还可以,然后研究下解解小题.应该比用python/
matlab好玩,但是语法还摸不清...初始化个矩阵貌似都很头疼...另一个想看看并行的
那个actor怎么玩得,感觉比传说中的semaphore/mutex好玩一点,代码容易handle些,不
知道这个感觉是不是正确...因为不是科班出身,所以找到个能解决问题又能对自己思路
的工具就太好了. |
|
a***o
发帖数: 1182 | 17 来自主题: JobHunting版 - 新鲜电面经 思路是对的,就是怎么知道现在外面有多少个read呢?
有的semaphore是不能check value的 |
|
y***u
发帖数: 205 | 18 只用mutex会增加不必要的contention吧？是不是还是用producer/consumer，但是用一
个很大(Max Q size)的semaphore，然后动态的管理内存（区别实际Q大小和理论最大值
），这样更好？ |
|
y***u
发帖数: 205 | 19 这样head和tail的节点如果相同是不是有问题？新head指向旧tail，但是旧tail已经
dequeue了。
感觉还是用emptyslot和fullslot两个semaphore，和整个Q的mutex。返回size操作不涉
及Q里面数据更新，所以就是一个snapshot吧，不用加mutex吧？ |
|
a********3
发帖数: 228 | 20 programmer interview exposed里好像有一个用三个semaphore（分别管empty, full,
write）实现concurrent queue的题。
另外问lz，F家你从申请到schedule电面要多久？我的申请一直没人理。 |
|
g**e
发帖数: 6127 | 21 Y/N 中断重新开始，这个transaction到底是处理了还是没处理呢，收到钱了吗
多线程的时候如何保证N/N的一个记录一定只被一个线程获取？用一台机器的时候可以
用semaphore, synchronized解决(虽然效率不高)，多台机器多线程的时候呢
to
怎么
一次 |
|
d**********x
发帖数: 4083 | 22 "够用了"。。。
1. 逻辑问题，哪个写lib的人会抱怨库少？我们都是用库的。
2. c++11的标准库。。。它是比c++03强多了，但是你要是拿来和java这么多年的积累
比，还是渣。和Qt/boost比，也是渣。
举个例子，就看那个半残的string接口，我每次都有一种灭了标准委员会
的想法。你能trim吗？不能，找regexp吧。你能split吗？不能，找regexp吧。你能
tolower吗？不能，transform。你能toUtf8吗？你能fromUtf8吗？你能转URL encoding
吗？你能直接sscanf吗？连个string这么基本的东西都不好好弄一下的，固守什么什么
哲学，不引进实用的特性，就是个渣，有什么好辩护的。面对这样渣的库最后就是东一
家西一家的山寨。
好，看看c++11的新库，像模像样还引进了一个thread库，看看里面有啥，mutex，
condition，恩，不错，哎哟semaphore呢？还得老子亲自从mutex和condition山寨？坑
爹还是坑娘呢？我想要个thread pool有现成的吗？是，不难，又山寨一坨。reader/
writer ... 阅读全帖 |
|
f*******t
发帖数: 7549 | 23 用两个semaphore能完美解决这个问题吧，不用写这么复杂的程序
again |
|
d**********x
发帖数: 4083 | 24 H2O那个我写了个C的。可以改吧改吧加上对各种原子的计数。
编译的时候别忘了 -lpthread !
#include
#include
#include
#include
#include
#include
sem_t availH;
sem_t availO;
sem_t usedH;
sem_t usedO;
void* H(void*) {
sem_post(&availH);
sem_wait(&usedH);
fprintf(stderr, "H consumed.\n");
pthread_detach(pthread_self());
return NULL;
}
void* O(void*) {
sem_post(&availO);
sem_wait(&usedO);
fprintf(stderr, "O consumed.\n");
pthread_detach(... 阅读全帖 |
|
w*r
发帖数: 72 | 25 two semaphores 就够了吧
#include
#include
#include
class sem {
boost::mutex guard;
int c ;
public:
sem() : c(0) {}
void V ( int n = 1 ) {
boost::mutex::scoped_lock lock(guard);
c = c + n;
}
void P ( int n = 1) {
while ( c < n ) ;
boost::mutex::scoped_lock lock(guard);
c = c - n;
}
};
sem semh;
sem semo;
class H{
public:
void operator()() {
std::cout << "create H thread ... 阅读全帖 |
|
f*******t
发帖数: 7549 | 26 用两个semaphore能完美解决这个问题吧，不用写这么复杂的程序
again |
|
d**********x
发帖数: 4083 | 27 H2O那个我写了个C的。可以改吧改吧加上对各种原子的计数。
编译的时候别忘了 -lpthread !
#include
#include
#include
#include
#include
#include
sem_t availH;
sem_t availO;
sem_t usedH;
sem_t usedO;
void* H(void*) {
sem_post(&availH);
sem_wait(&usedH);
fprintf(stderr, "H consumed.\n");
pthread_detach(pthread_self());
return NULL;
}
void* O(void*) {
sem_post(&availO);
sem_wait(&usedO);
fprintf(stderr, "O consumed.\n");
pthread_detach(... 阅读全帖 |
|
w*r
发帖数: 72 | 28 two semaphores 就够了吧
#include
#include
#include
class sem {
boost::mutex guard;
int c ;
public:
sem() : c(0) {}
void V ( int n = 1 ) {
boost::mutex::scoped_lock lock(guard);
c = c + n;
}
void P ( int n = 1) {
while ( c < n ) ;
boost::mutex::scoped_lock lock(guard);
c = c - n;
}
};
sem semh;
sem semo;
class H{
public:
void operator()() {
std::cout << "create H thread ... 阅读全帖 |
|
f******x
发帖数: 201 | 29 不怎么懂并行的我表示，难道不是以下代码吗？
H() {
H.V
O.P
}
O() {
H.P
H.P
O.V
O.V
}
其中，H和V是两个semaphore，P是减一，V是加一。 |
|
f******x
发帖数: 201 | 30 不怎么懂并行的我表示，难道不是以下代码吗？
H() {
H.V
O.P
}
O() {
H.P
H.P
O.V
O.V
}
其中，H和V是两个semaphore，P是减一，V是加一。 |
|
w****x
发帖数: 2483 | 31 题目是reject不是offer啊~~
具体题目就不上了，大致说说感觉
1. 第一个电面是个国人，问的题目不难也不是很简单，会挣扎一下
2. 二面是问的merge k sorted list，然后写unit test程序然后聊聊数据库的基本知识
Onsite技术面是5轮：
1. 一个MSR的印度人，问得是一个merge sort的变体，先写简单的code然后再要不断改
变条件问怎么改进。卡住了他会有些提示，整个过程还是蛮愉快的，但是可能反应慢了
一点。
2. 一个印度人，他觉得答得最好。问了3个题，第一题是关于多线程的问题，64位变量
在32位操作系统多线程出的一些问题(居然说long在32位下是8个字节)，直接写出汇编
代码再分析给他听的。修改为线程安全类，然后问读操作多该怎么整提高效率，然后要
实现一个什么什么锁(你们猜的到的，最后做出来了应为我见过这题,就是那个semaphor
+ mutex)。最后问了一个用堆解决的问题。都要coding。
3. 国人。问了一个算法。一开始设计数据结构，给出了merge sort的方案，code之，
然后问有没有什么其他数据结构可以满足，想到了... 阅读全帖 |
|
K********y
发帖数: 47 | 32 （原贴见http://www.mitbbs.com/article/JobHunting/32331973_3.html）
3: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
多线程我不熟，pthread里没有现成的semaphore，所以习惯用condition variable。闭
门造车写了下面这样一个解法，显然不如版上各位给的代码简洁。但是这里有个bug我
想不明白，请教一下各位：
我的基本想法是，如果三个原子里最后一个就位的是H，则signal O，O再signal另一个
H；如果最后一个是O，则signal一个H，这个H再signal另一个H。为了区分H函数的两种
情况，我起初用了个bool signalNextH，但是会出现死锁。改成int来计数就过了（下
面的代码）。从这个症状来看，似乎是有两个O原子同时发出了signal，所以
signalNextH要用counter... 阅读全帖 |
|
d**********x
发帖数: 4083 | 33 谁说pthread里面没有现成的semaphore...
请自行google sem_t。。。 |
|
K********y
发帖数: 47 | 34 （原贴见http://www.mitbbs.com/article/JobHunting/32331973_3.html）
3: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
多线程我不熟，pthread里没有现成的semaphore，所以习惯用condition variable。闭
门造车写了下面这样一个解法，显然不如版上各位给的代码简洁。但是这里有个bug我
想不明白，请教一下各位：
我的基本想法是，如果三个原子里最后一个就位的是H，则signal O，O再signal另一个
H；如果最后一个是O，则signal一个H，这个H再signal另一个H。为了区分H函数的两种
情况，我起初用了个bool signalNextH，但是会出现死锁。改成int来计数就过了（下
面的代码）。从这个症状来看，似乎是有两个O原子同时发出了signal，所以
signalNextH要用counter... 阅读全帖 |
|
d**********x
发帖数: 4083 | 35 谁说pthread里面没有现成的semaphore...
请自行google sem_t。。。 |
|
l*******b
发帖数: 2586 | 36 Need a semaphore for the counter ? |
|
p*****p
发帖数: 379 | 37 把counter++之类的放到while的后面
把write的while条件改成r_cnt + write_cnt > 0
我觉得这样就行了，但是这代码会造成读的人多了写不进去，广播那里也有待商榷
所以把这套换成一个semaphore应该会好点 |
|
p*****2
发帖数: 21240 | 38
object
刚order了java concurrency in practice, 同时在看CC150相关章节，thinking in
java concurrency那章，以及effective java concurrency那章。简单列了一个提纲，
希望这周或者下周可以搞完。
1. How to create thread
implement Runnable
implement Callable
extends Thread
2. How to start thread
Thread pool
Thread.start
3. Synchronization
synchronized keyword
Lock
Semaphore
Immutability
volatile
java.util.concurrent.atomic
concurrent collection
4. Communiication
wait, notify, notifyall
Condition
concurrent collection
5. Common coding questions
bl... 阅读全帖 |
|
m*****n
发帖数: 204 | 39 原题见http://www.mitbbs.com/article_t/JobHunting/32331973.html
这道题不是单纯作对就好的。那里贴出的解法有些值得商榷的地方。我这里谈谈个人见
解供大家参考。
从Java的角度看这道题可以有三个考点：
对Java Synchronization and Concurrency的掌握
基本的Coding Style，要能扩展,不能写spaghetti code
有把握的话可以讨论一下Lock Free Synchronization. 这题理论上只用AtomicInteger
也行。
看到这道题之后首先应该和面试者交流一下，看是否一定要用synchronized-wait-
notify. 如果不要求就不要用了，用这个既花时间又容易出错，还显得不够up to date
。当然有人可能觉得这个考基本功非要你用那也没办法。
我的基本思路是：
- 用synchronousQueue去Block and release caller threads
- 用AtomicInterger计数
- Thread Synchronization下面再... 阅读全帖 |
|
m*****n
发帖数: 204 | 40 原题见http://www.mitbbs.com/article_t/JobHunting/32331973.html
这道题不是单纯作对就好的。那里贴出的解法有些值得商榷的地方。我这里谈谈个人见
解供大家参考。
从Java的角度看这道题可以有三个考点：
对Java Synchronization and Concurrency的掌握
基本的Coding Style，要能扩展,不能写spaghetti code
有把握的话可以讨论一下Lock Free Synchronization. 这题理论上只用AtomicInteger
也行。
看到这道题之后首先应该和面试者交流一下，看是否一定要用synchronized-wait-
notify. 如果不要求就不要用了，用这个既花时间又容易出错，还显得不够up to date
。当然有人可能觉得这个考基本功非要你用那也没办法。
我的基本思路是：
- 用synchronousQueue去Block and release caller threads
- 用AtomicInterger计数
- Thread Synchronization下面再... 阅读全帖 |
|
c*****0
发帖数: 19 | 41 如果没理解错，直接用两个semaphore不行吗
public void H() {
p1.release(1);
p2.acquire(1);
}
public void O() {
p2.release(2);
p1.acquire(2);
}
AtomicInteger
date |
|
p*****p
发帖数: 379 | 42 他家电话总是有很大的回音搞得经常有些关键词听不清楚需要重复，比较囧
1. java多线程，synchonize的用法，lock的用法，举例说明
我先举了blockingqueue的例子，后来感觉不好说明lock的问题，改用文件读写的例子
，其间说可以用AtomicInteger实现semaphore，对方表示不太确定这个说法是否对，是
我理解错了吗？
2. http methods和REST API，细节，最后抠到get和post在下层cache的区别，表示这
个没仔细研究过，缴枪
3. 算法，一个流包含了domain和对应访问量，内存有限，求top k的domain，no
aggregation，用heap做，求最好和最坏情况复杂度
好像就这些，接下来就是扯皮，说说为啥申请他家 |
|
z********i
发帖数: 568 | 43 1。binary tree where every node has a color. Calculate the number of
disjoint three adjacent nodes.
2. timer problem：use semaphore in ISR to wake up a user function call.
三个组面试。最后一个组的manager很热情。这个manager同hr最后问：salary
expectation, preferences on which of those three groups in interview。
Salary expectation: 就说接受standard package，但没有给具体数据。最后hr问了一
下我现在的工资。Manager很想我给一个数据。
Preference on which group:回答都喜欢。
不清楚该怎样回答。 |
|
b*****n
发帖数: 618 | 44 来自主题: JobHunting版 - RF 面经 姑且称为RF吧
申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
online code test，onsite和一次电面。
好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
一样，
第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
细看，还有详细的提示也要注意。
我遇到的题：
1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
或者改变激光方向（4个方向）
问激光射出矩阵之前一共经过了多少格子，如果死循环了就输出－1
2. 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度
code test过了之后我直接就安排onsite了，onsite本来安排6个人但实际上只面了5个
，题目如下：
1. 两个不一样长度的sorted array，求median。
leetcod... 阅读全帖 |
|
b*****n
发帖数: 618 | 45 来自主题: JobHunting版 - RF 面经 姑且称为RF吧
申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
online code test，onsite和一次电面。
好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
一样，
第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
细看，还有详细的提示也要注意。
我遇到的题：
1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
或者改变激光方向（4个方向）
问激光射出矩阵之前一共经过了多少格子，如果死循环了就输出－1
2. 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度
code test过了之后我直接就安排onsite了，onsite本来安排6个人但实际上只面了5个
，题目如下：
1. 两个不一样长度的sorted array，求median。
leetcod... 阅读全帖 |
|
n*****g
发帖数: 178 | 46 题目是CC150第五版16.5题，题目是这样的：
Suppose we have the following code:
public class Foo {
public Foo() { . . . }
public void first() { ... }
public void second() { ... }
public void thirdQ { ... }
The same instance of Foo will be passed to three different threads. ThreadA
will call first, threads will call second, and threadC will call third.
Design a mechanism to ensure that first is called before second and second
is called before third.
这要换成C语言来问的话，是不是等同于这样问：一个foo函数，确保foo先被first调用
，然后再被second和third调用（f... 阅读全帖 |
|
y****1
发帖数: 58 | 47 谢谢！
spinlock 没有 context switch，用他的操作需要是 atomic operation
这是最主要的吗？
谢谢 |
|
|
l*******e
发帖数: 127 | 49 还有某些情况下不允许你context switch，必须busy wait，比如kernel mode的driver
经常用。
谢谢！spinlock 没有 context switch，用他的操作需要是 atomic operation这是最
主要的吗？谢谢 |
|
|
