收到BA 50K邀请# Money - 海外理财
S*I
1 楼
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 00:18:17 2011, 美东) 提到:
周五面完最后一个onsite, 累的惨兮兮的, 好容易爬回家. 不管结果如何, 这段时间找
工作算是告一段落了.
下面把这段时间面试中被问到的题目整理一下, 供大家参考. 我也就不说具体是那些公
司了, 都是很典型的面试题, 到哪里都有可能会被问到.
* implement memcpy? How to improve? how to determine if a system is
32bit or 64bit?
* how is static keyword used in Java?
* a list of intervals, no overlapping and sorted, write a function to
insert an interval into the list and still keep the list sorted and no
overlapping.
* given a function on sorted dictionary to retrieve word by index,
string getWord(int i), how to implement bool findword(String). We
don't know the dictionary size.
* NxN maze, there are some obstacles, we want to walk from the upper
left corner to the bottom right corner. every step we can move up,
down, left, or right. Write a function to find out if there is a path
or not.
* there is an organization tree, tree node has some people information
and a parent pointer, but it doesn't have child pointer. Given two
nodes A and B in the tree, find the length of common path between the
path of A->root and B->root.
* what is the difference between spin lock and mutex? when to use spin
lock or mutex? should we use spin lock on uni-processor system? On
uni-processor system, there is a place in kernel where spinlock
shouldn't be used, what is that and why? How to synchronize interrupt
handler and other kernel thread?
* we create a file on disk. explain what will happen in system after
the command is issued? what is the difference between user space and
kernel space? what does "space" mean? is there any OS which doesn't
distinguish user space and kernel space?
* design search engine in an intranet.
* kernel crashes for no reason. how to find out the root cause?
* We have an administrative process in system. We want it to run
always smoothly even if the system gets overloaded. How to achieve
that?
* implement atoi
* int sqrt(int n), should return floor, e.g. sqrt(8) = 2
* given an array of integers and an integer target, find all
combinations which sum up to target. Don't output duplicates. e.g.,
[2,3,4], target is 5. then output should be [2,3], or [3,2], but not
both.
* type "ls" and enter on Linux, explain what will happen in the system
* given post order and pre order sequence of a binary tree,
reconstruct the tree
* count the number of nodes in binary tree
* There is sequence constructed in a way that we go through the
previous line and output the number of the same consecutive integer
and then that integer. So the format is like
... e.g.:
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
what is the largest number we can get in 500 lines? given a n, write
code to output n lines.
* givn a node in BST, return its successor
* design and implement connection pool
* given an array of integer and a target integer, return the number of
possible combinations whose summation is the given target. The order
of sequence matters. e.g. [2,3,4] and 5, we should return 2. One is
[2,3], and the other is [3,2].
* design a dictionary server, the request from client is a pattern
including wildcard, like **w*b*t, return the list of words matching
the pattern.
* what is context switch? why is it expensive?
一点个人体会是coding固然重要, 但是基本概念基础知识也同样重要. 面试的时候要是
这类问题答的不好, 失分会很多. 有几次我甚至能感觉出来面试官非常不爽. 所以这类
问题一定要理解透彻, 要非常的透彻.
而且很多问题其实就是基础概念的扩展, 概念理解透彻了, 解决起来就很顺了.
举个例子, 记得前几天有位兄弟贴了道题目, 大概是要实现一个类A, A维护这一个
observer list, 系统其他部分可以调用A.register/A.ungister 注册或者注销它自己
为A的observer. A还有一个changeValue方法会经常被调用, 每次调用的时候A都遍历
observer list, 调用每个observers的notifyValueChange方法通知value被update了.
要求thread safe.
像此类问题, 主要就是考察synchronization mechanism. 只要把spin lock,
semaphore, monitor这些概念搞清楚了就不难回答.
首先应该问面试官这些问题:
* uni-processor system or multi-processor system? 如果是uni-processor,
spin lock就不应该用了
* user space or kernel space? kernel里面的synchronization有它的特殊性, 需要
根据不同的context特殊处理. 所以如果面试官说是kernel space, 你接下来应该问是
什么context? interrupt context, soft interrupt context or process
context?
* access pattern? like the frequency that the data is read compared to
being modified, the duration of read or write, the contention of the
data. You should point out we need to do measurement, profiling before
doing design and implementation to find out these patterns so we can
design and implement accordingly.
这些问题一问出来, 就立刻表现出你对synchronizion相关概念的透彻理解.
具体到这个问题, 假设系统在user space, 并且是multi-processor system. 那么最简
单的方法就是用一个exclusive lock保护整个observer list. spin lock, mutex, 或
者monitor都可以用. 如果根据预先得出的access pattern, register/unregister/
changeValue执行时间非常短, 小于context switch, 那么用spin lock的话
performance会更好. 这样的设计好处是很简单, 不好的是如果竞争线程很多,
concurrency会非常差, 每次只能有一个thread在A里面.
进一步分析, 这种observer一般都是在模块初始化的时候注册, 在销毁模块的时候
unregister, 在运行的时候很少会再去改observer list, 大部分时间都是只读操作.
因为changevalue要扫描整个list, 所以read花的时间比write要长的多. 这样的话, rw
-lock就很合适了. 用两个lock, 一个read lock, 一个write lock. read lock可以同
时被多个thread获取. write lock is exclusive. 这样的话性能可以提高很多. 但是
要注意的是write starvation. 解决的办法是如果有write thread在等待队列里面, 那
么等当前所有的reader一退出, 立刻把lock给writer, 不管writer前面有多少reader.
再进一步, 我们可以应用RCU的概念实现lock-free read. 我们要保证让reader不需要
lock, 让他们或者看到write之前的状态, 或者是write之后的状态, 而不会看到中间
inconsistent data structure. 对于register, 假设p是list里面最后一个node, o是
新注册的, 那么对list的修改是 p->next = o. 所以不需要获取任何lock, reader看到
的或者p是最后一个node, 或者o是最后一个node, 总是一致的. 对于unregister方法,
我们搜索list, 找到要删除的node o 和前一个node p, p->next = o->next. 不需要
lock, reader看到是或者删除之前的list, 或者是删除之后的, 对reader来说, list数
据是一致的. 但是有一个问题要注意, 就是不能马上free那个被删掉的node, 因为
reader可能正在访问, 得等到安全的时候再回收. 如果unregister方法只会被调用很有
限的几次, 我们可以一直保存着那些被删掉的node, 直到程序退出的时候再一起回收.
或者可以设定一个足够安全的timer, 超时的时候回收内存.
这个问题回答成这个样子, 应该就比较完满了.
今天就先写道这里吧, 改天想起其他的再补充.
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Aug 29 00:43:34 2011, 美东) 提到:
好长啊，先顶再慢慢看……
☆─────────────────────────────────────☆
aixiang (passion) 于 (Mon Aug 29 00:50:46 2011, 美东) 提到:
这个赞！
☆─────────────────────────────────────☆
lustcity (说好的幸福呢？) 于 (Mon Aug 29 01:15:23 2011, 美东) 提到:
looks good
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Mon Aug 29 01:22:07 2011, 美东) 提到:
基本的算法题楼主都会么。。。
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Mon Aug 29 01:25:37 2011, 美东) 提到:
common path那题实际上是求两链表的交点吧。。。
☆─────────────────────────────────────☆
hwsim (HardWare Sim) 于 (Mon Aug 29 01:26:04 2011, 美东) 提到:
赞。
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 01:30:52 2011, 美东) 提到:
exactly
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 01:32:06 2011, 美东) 提到:
现在基本上都会, 面试的时候好多都答的一塌糊涂 ...
☆─────────────────────────────────────☆
yangcheng (牛魔王) 于 (Mon Aug 29 01:34:04 2011, 美东) 提到:
这个lock的不专门做这个很难答这么全吧，，要是面试的team也不做这个，，还不把面
试官弄的一楞一楞的
☆─────────────────────────────────────☆
speeddy (Wade) 于 (Mon Aug 29 01:40:08 2011, 美东) 提到:
答成这样子，你是tech lead还是staff title的啊？
☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Mon Aug 29 02:13:35 2011, 美东) 提到:
赞面经. 另外spin lock是不是底层才接触的东西? java学到现在没看到说spin lock,
最多看到些busy waiting的例子.
☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Mon Aug 29 02:43:23 2011, 美东) 提到:
另外那道打印的题你给的例子似乎错了吧,应该是
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
☆─────────────────────────────────────☆
airplane1022 (Pan) 于 (Mon Aug 29 09:26:30 2011, 美东) 提到:
赞思路，很有启发性
☆─────────────────────────────────────☆
homor (homor) 于 (Mon Aug 29 10:20:18 2011, 美东) 提到:
好文章， 谢谢分享，同时 bless～～～
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 11:20:07 2011, 美东) 提到:
谢谢指正, 原文已修改
☆─────────────────────────────────────☆
icookie (大饼) 于 (Mon Aug 29 11:29:32 2011, 美东) 提到:
mark ~~~
Have no idea about concurrent programming
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 11:31:43 2011, 美东) 提到:
spin lock就是busy waiting, 并不是底层才使用. pthread线程库就有spin lock.
Java最常用的synchronized keyword属于高层的同步primitive, 是用monitor+
condition variable封装实现的, 内部数据结构是看不到的. 底下看JVM具体怎么实现
了, 估计是用mutex, 这样最简单.
,
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 14:33:07 2011, 美东) 提到:
不把面试官弄晕怎么拿offer 呵呵
☆─────────────────────────────────────☆
romancity (山顶一枝草) 于 (Mon Aug 29 15:23:35 2011, 美东) 提到:
use induction to find the biggest number ?
☆─────────────────────────────────────☆
nowheresep (nowheresep) 于 (Mon Aug 29 17:48:46 2011, 美东) 提到:
mark~~~~~~~~~~~
☆─────────────────────────────────────☆
GAGAMA (GAGA) 于 (Mon Aug 29 19:11:15 2011, 美东) 提到:
mark
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Mon Aug 29 21:46:30 2011, 美东) 提到:
这个是3吧，不可能超过3
☆─────────────────────────────────────☆
running123 (running123) 于 (Mon Aug 29 23:09:27 2011, 美东) 提到:
spin lock在单CPU下本质就是关闭中断，unlock就是开启中断。所以spin lock锁住的区域不会有context switch。在多CPU里面的实现就比较复杂了，用了内存变量做标记，同时在访问这个内促变量的时候使用了lock指令来锁住总线bus从而达到原子性访问。
Linux里面的mutex和semphore的也是通过spin lock实现的。用spin lock和mutex,
semphore的关键区别在于不进行context switch。
,
☆─────────────────────────────────────☆
running123 (running123) 于 (Mon Aug 29 23:26:10 2011, 美东) 提到:
spin lock是Linux kernel里面的东西。读过Linux Kernel代码的人应该都知道，里面
很多地方使用了这个东西。
,
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 23:55:46 2011, 美东) 提到:
这个恐怕不对吧. 如果lock正被占用, semphore是要yield CPU的, spin lock busy
waiting, 怎么yield CPU?
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Tue Aug 30 00:09:28 2011, 美东) 提到:
spin lock只是一种同步原语, 不光kernel里面用, user space也用.
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Tue Aug 30 00:09:46 2011, 美东) 提到:
对
☆─────────────────────────────────────☆
speeddy (Wade) 于 (Tue Aug 30 00:31:07 2011, 美东) 提到:
linux 里面有user space 得spin lock吗？
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Tue Aug 30 00:35:07 2011, 美东) 提到:
pthread_spin_lock
☆─────────────────────────────────────☆
running123 (running123) 于 (Tue Aug 30 09:02:32 2011, 美东) 提到:
spin lock不yield CPU
☆─────────────────────────────────────☆
running123 (running123) 于 (Tue Aug 30 09:05:10 2011, 美东) 提到:
spin lock可以看做一种同步原语。不过其实里面步骤还是挺多的，特别是多CPU情况下
。早期只能在Kernel里面用，后面user space也能用了。不过kernel源代码里面可以看
到大量用spin lock的地方。
一些高效的database engine，比如postgres源代码里面也在用spin lock.
☆─────────────────────────────────────☆
Mutu (Camoranesi) 于 (Tue Aug 30 09:31:37 2011, 美东) 提到:
恩
spinlock在kernel里头用得比较多，有不少都是减小了context switch的开销
busy
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Tue Aug 30 11:16:05 2011, 美东) 提到:
那就是了, 不yield CPU, 你怎么能用spin lock 实现semaphore? 那不还是spin lock
么?
☆─────────────────────────────────────☆
kinkiguen (K_K) 于 (Tue Aug 30 13:19:43 2011, 美东) 提到:
there is an organization tree, tree node has some people information
and a parent pointer, but it doesn't have child pointer. Given two
nodes A and B in the tree, find the length of common path between the
path of A->root and B->root.
是不是追溯A,B共同的parent， 然后从哪个parent 到 root都是common path?
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Tue Aug 30 13:29:44 2011, 美东) 提到:
嗯 对 lowest common ancestor
☆─────────────────────────────────────☆
busbby (奥特曼在银行里下象棋) 于 (Tue Aug 30 14:16:49 2011, 美东) 提到:
Mark,楼主功底不错
☆─────────────────────────────────────☆
holyman (木头鬼仔) 于 (Tue Aug 30 15:21:01 2011, 美东) 提到:
MARK
☆─────────────────────────────────────☆
returning (aaaaaaaaa) 于 (Tue Aug 30 16:38:32 2011, 美东) 提到:
how to determine if a system is 32bit or 64bit?
btw: 下面这个题目到底什么规律？
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
☆─────────────────────────────────────☆
MrMila (Mr.Mila) 于 (Tue Aug 30 17:55:38 2011, 美东) 提到:
谢谢楼主！
☆─────────────────────────────────────☆
kinkiguen (K_K) 于 (Tue Aug 30 21:34:34 2011, 美东) 提到:
谢谢楼主，您申请的是什么职位，因为离毕业还有段时间，开始看着面试题了，对申请
职位很不了解。我看版里有的面经对OS要求不是很高，而您的题目算法倒不是很显著，
反而OS很多。有没有基本不怎么考OS的职位的？偶OS只知道 semaphore。。。
☆─────────────────────────────────────☆
consuming (consume) 于 (Tue Aug 30 21:37:13 2011, 美东) 提到:
How to improve? how to determine if a system is
32bit or 64bit?
sizeof(size_t) ?
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Tue Aug 30 22:34:52 2011, 美东) 提到:
上一行是1个1
上一行是2个1
上一行是1个2，1个1
上一行是1个1，1个2，2个1
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Wed Aug 31 00:11:25 2011, 美东) 提到:
呵呵 我是做OS的, 所以OS的题目会多一些了. 要是申请一般的software engineer, 应
该不会这么偏重考察OS的概念.
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Wed Aug 31 00:15:51 2011, 美东) 提到:
sizeof(pointer)
可以每次拷贝多个字节以充分利用bus的带宽. 比如说如果是32位的系统, 一次拷贝4个
字节, 64位系统每次拷贝8个字节
☆─────────────────────────────────────☆
heavyburden (nothing) 于 (Sun Sep 18 15:13:13 2011, 美东) 提到:
楼主拿到offer吗？您很牛。
☆─────────────────────────────────────☆
heavyburden (nothing) 于 (Sun Sep 18 15:13:24 2011, 美东) 提到:
楼主拿到offer吗？您很牛。
yuhanlin (Yuhan) 于 (Mon Aug 29 00:18:17 2011, 美东) 提到:
周五面完最后一个onsite, 累的惨兮兮的, 好容易爬回家. 不管结果如何, 这段时间找
工作算是告一段落了.
下面把这段时间面试中被问到的题目整理一下, 供大家参考. 我也就不说具体是那些公
司了, 都是很典型的面试题, 到哪里都有可能会被问到.
* implement memcpy? How to improve? how to determine if a system is
32bit or 64bit?
* how is static keyword used in Java?
* a list of intervals, no overlapping and sorted, write a function to
insert an interval into the list and still keep the list sorted and no
overlapping.
* given a function on sorted dictionary to retrieve word by index,
string getWord(int i), how to implement bool findword(String). We
don't know the dictionary size.
* NxN maze, there are some obstacles, we want to walk from the upper
left corner to the bottom right corner. every step we can move up,
down, left, or right. Write a function to find out if there is a path
or not.
* there is an organization tree, tree node has some people information
and a parent pointer, but it doesn't have child pointer. Given two
nodes A and B in the tree, find the length of common path between the
path of A->root and B->root.
* what is the difference between spin lock and mutex? when to use spin
lock or mutex? should we use spin lock on uni-processor system? On
uni-processor system, there is a place in kernel where spinlock
shouldn't be used, what is that and why? How to synchronize interrupt
handler and other kernel thread?
* we create a file on disk. explain what will happen in system after
the command is issued? what is the difference between user space and
kernel space? what does "space" mean? is there any OS which doesn't
distinguish user space and kernel space?
* design search engine in an intranet.
* kernel crashes for no reason. how to find out the root cause?
* We have an administrative process in system. We want it to run
always smoothly even if the system gets overloaded. How to achieve
that?
* implement atoi
* int sqrt(int n), should return floor, e.g. sqrt(8) = 2
* given an array of integers and an integer target, find all
combinations which sum up to target. Don't output duplicates. e.g.,
[2,3,4], target is 5. then output should be [2,3], or [3,2], but not
both.
* type "ls" and enter on Linux, explain what will happen in the system
* given post order and pre order sequence of a binary tree,
reconstruct the tree
* count the number of nodes in binary tree
* There is sequence constructed in a way that we go through the
previous line and output the number of the same consecutive integer
and then that integer. So the format is like
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
what is the largest number we can get in 500 lines? given a n, write
code to output n lines.
* givn a node in BST, return its successor
* design and implement connection pool
* given an array of integer and a target integer, return the number of
possible combinations whose summation is the given target. The order
of sequence matters. e.g. [2,3,4] and 5, we should return 2. One is
[2,3], and the other is [3,2].
* design a dictionary server, the request from client is a pattern
including wildcard, like **w*b*t, return the list of words matching
the pattern.
* what is context switch? why is it expensive?
一点个人体会是coding固然重要, 但是基本概念基础知识也同样重要. 面试的时候要是
这类问题答的不好, 失分会很多. 有几次我甚至能感觉出来面试官非常不爽. 所以这类
问题一定要理解透彻, 要非常的透彻.
而且很多问题其实就是基础概念的扩展, 概念理解透彻了, 解决起来就很顺了.
举个例子, 记得前几天有位兄弟贴了道题目, 大概是要实现一个类A, A维护这一个
observer list, 系统其他部分可以调用A.register/A.ungister 注册或者注销它自己
为A的observer. A还有一个changeValue方法会经常被调用, 每次调用的时候A都遍历
observer list, 调用每个observers的notifyValueChange方法通知value被update了.
要求thread safe.
像此类问题, 主要就是考察synchronization mechanism. 只要把spin lock,
semaphore, monitor这些概念搞清楚了就不难回答.
首先应该问面试官这些问题:
* uni-processor system or multi-processor system? 如果是uni-processor,
spin lock就不应该用了
* user space or kernel space? kernel里面的synchronization有它的特殊性, 需要
根据不同的context特殊处理. 所以如果面试官说是kernel space, 你接下来应该问是
什么context? interrupt context, soft interrupt context or process
context?
* access pattern? like the frequency that the data is read compared to
being modified, the duration of read or write, the contention of the
data. You should point out we need to do measurement, profiling before
doing design and implementation to find out these patterns so we can
design and implement accordingly.
这些问题一问出来, 就立刻表现出你对synchronizion相关概念的透彻理解.
具体到这个问题, 假设系统在user space, 并且是multi-processor system. 那么最简
单的方法就是用一个exclusive lock保护整个observer list. spin lock, mutex, 或
者monitor都可以用. 如果根据预先得出的access pattern, register/unregister/
changeValue执行时间非常短, 小于context switch, 那么用spin lock的话
performance会更好. 这样的设计好处是很简单, 不好的是如果竞争线程很多,
concurrency会非常差, 每次只能有一个thread在A里面.
进一步分析, 这种observer一般都是在模块初始化的时候注册, 在销毁模块的时候
unregister, 在运行的时候很少会再去改observer list, 大部分时间都是只读操作.
因为changevalue要扫描整个list, 所以read花的时间比write要长的多. 这样的话, rw
-lock就很合适了. 用两个lock, 一个read lock, 一个write lock. read lock可以同
时被多个thread获取. write lock is exclusive. 这样的话性能可以提高很多. 但是
要注意的是write starvation. 解决的办法是如果有write thread在等待队列里面, 那
么等当前所有的reader一退出, 立刻把lock给writer, 不管writer前面有多少reader.
再进一步, 我们可以应用RCU的概念实现lock-free read. 我们要保证让reader不需要
lock, 让他们或者看到write之前的状态, 或者是write之后的状态, 而不会看到中间
inconsistent data structure. 对于register, 假设p是list里面最后一个node, o是
新注册的, 那么对list的修改是 p->next = o. 所以不需要获取任何lock, reader看到
的或者p是最后一个node, 或者o是最后一个node, 总是一致的. 对于unregister方法,
我们搜索list, 找到要删除的node o 和前一个node p, p->next = o->next. 不需要
lock, reader看到是或者删除之前的list, 或者是删除之后的, 对reader来说, list数
据是一致的. 但是有一个问题要注意, 就是不能马上free那个被删掉的node, 因为
reader可能正在访问, 得等到安全的时候再回收. 如果unregister方法只会被调用很有
限的几次, 我们可以一直保存着那些被删掉的node, 直到程序退出的时候再一起回收.
或者可以设定一个足够安全的timer, 超时的时候回收内存.
这个问题回答成这个样子, 应该就比较完满了.
今天就先写道这里吧, 改天想起其他的再补充.
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Aug 29 00:43:34 2011, 美东) 提到:
好长啊，先顶再慢慢看……
☆─────────────────────────────────────☆
aixiang (passion) 于 (Mon Aug 29 00:50:46 2011, 美东) 提到:
这个赞！
☆─────────────────────────────────────☆
lustcity (说好的幸福呢？) 于 (Mon Aug 29 01:15:23 2011, 美东) 提到:
looks good
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Mon Aug 29 01:22:07 2011, 美东) 提到:
基本的算法题楼主都会么。。。
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Mon Aug 29 01:25:37 2011, 美东) 提到:
common path那题实际上是求两链表的交点吧。。。
☆─────────────────────────────────────☆
hwsim (HardWare Sim) 于 (Mon Aug 29 01:26:04 2011, 美东) 提到:
赞。
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 01:30:52 2011, 美东) 提到:
exactly
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 01:32:06 2011, 美东) 提到:
现在基本上都会, 面试的时候好多都答的一塌糊涂 ...
☆─────────────────────────────────────☆
yangcheng (牛魔王) 于 (Mon Aug 29 01:34:04 2011, 美东) 提到:
这个lock的不专门做这个很难答这么全吧，，要是面试的team也不做这个，，还不把面
试官弄的一楞一楞的
☆─────────────────────────────────────☆
speeddy (Wade) 于 (Mon Aug 29 01:40:08 2011, 美东) 提到:
答成这样子，你是tech lead还是staff title的啊？
☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Mon Aug 29 02:13:35 2011, 美东) 提到:
赞面经. 另外spin lock是不是底层才接触的东西? java学到现在没看到说spin lock,
最多看到些busy waiting的例子.
☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Mon Aug 29 02:43:23 2011, 美东) 提到:
另外那道打印的题你给的例子似乎错了吧,应该是
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
☆─────────────────────────────────────☆
airplane1022 (Pan) 于 (Mon Aug 29 09:26:30 2011, 美东) 提到:
赞思路，很有启发性
☆─────────────────────────────────────☆
homor (homor) 于 (Mon Aug 29 10:20:18 2011, 美东) 提到:
好文章， 谢谢分享，同时 bless～～～
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 11:20:07 2011, 美东) 提到:
谢谢指正, 原文已修改
☆─────────────────────────────────────☆
icookie (大饼) 于 (Mon Aug 29 11:29:32 2011, 美东) 提到:
mark ~~~
Have no idea about concurrent programming
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 11:31:43 2011, 美东) 提到:
spin lock就是busy waiting, 并不是底层才使用. pthread线程库就有spin lock.
Java最常用的synchronized keyword属于高层的同步primitive, 是用monitor+
condition variable封装实现的, 内部数据结构是看不到的. 底下看JVM具体怎么实现
了, 估计是用mutex, 这样最简单.
,
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 14:33:07 2011, 美东) 提到:
不把面试官弄晕怎么拿offer 呵呵
☆─────────────────────────────────────☆
romancity (山顶一枝草) 于 (Mon Aug 29 15:23:35 2011, 美东) 提到:
use induction to find the biggest number ?
☆─────────────────────────────────────☆
nowheresep (nowheresep) 于 (Mon Aug 29 17:48:46 2011, 美东) 提到:
mark~~~~~~~~~~~
☆─────────────────────────────────────☆
GAGAMA (GAGA) 于 (Mon Aug 29 19:11:15 2011, 美东) 提到:
mark
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Mon Aug 29 21:46:30 2011, 美东) 提到:
这个是3吧，不可能超过3
☆─────────────────────────────────────☆
running123 (running123) 于 (Mon Aug 29 23:09:27 2011, 美东) 提到:
spin lock在单CPU下本质就是关闭中断，unlock就是开启中断。所以spin lock锁住的区域不会有context switch。在多CPU里面的实现就比较复杂了，用了内存变量做标记，同时在访问这个内促变量的时候使用了lock指令来锁住总线bus从而达到原子性访问。
Linux里面的mutex和semphore的也是通过spin lock实现的。用spin lock和mutex,
semphore的关键区别在于不进行context switch。
,
☆─────────────────────────────────────☆
running123 (running123) 于 (Mon Aug 29 23:26:10 2011, 美东) 提到:
spin lock是Linux kernel里面的东西。读过Linux Kernel代码的人应该都知道，里面
很多地方使用了这个东西。
,
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 23:55:46 2011, 美东) 提到:
这个恐怕不对吧. 如果lock正被占用, semphore是要yield CPU的, spin lock busy
waiting, 怎么yield CPU?
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Tue Aug 30 00:09:28 2011, 美东) 提到:
spin lock只是一种同步原语, 不光kernel里面用, user space也用.
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Tue Aug 30 00:09:46 2011, 美东) 提到:
对
☆─────────────────────────────────────☆
speeddy (Wade) 于 (Tue Aug 30 00:31:07 2011, 美东) 提到:
linux 里面有user space 得spin lock吗？
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Tue Aug 30 00:35:07 2011, 美东) 提到:
pthread_spin_lock
☆─────────────────────────────────────☆
running123 (running123) 于 (Tue Aug 30 09:02:32 2011, 美东) 提到:
spin lock不yield CPU
☆─────────────────────────────────────☆
running123 (running123) 于 (Tue Aug 30 09:05:10 2011, 美东) 提到:
spin lock可以看做一种同步原语。不过其实里面步骤还是挺多的，特别是多CPU情况下
。早期只能在Kernel里面用，后面user space也能用了。不过kernel源代码里面可以看
到大量用spin lock的地方。
一些高效的database engine，比如postgres源代码里面也在用spin lock.
☆─────────────────────────────────────☆
Mutu (Camoranesi) 于 (Tue Aug 30 09:31:37 2011, 美东) 提到:
恩
spinlock在kernel里头用得比较多，有不少都是减小了context switch的开销
busy
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Tue Aug 30 11:16:05 2011, 美东) 提到:
那就是了, 不yield CPU, 你怎么能用spin lock 实现semaphore? 那不还是spin lock
么?
☆─────────────────────────────────────☆
kinkiguen (K_K) 于 (Tue Aug 30 13:19:43 2011, 美东) 提到:
there is an organization tree, tree node has some people information
and a parent pointer, but it doesn't have child pointer. Given two
nodes A and B in the tree, find the length of common path between the
path of A->root and B->root.
是不是追溯A,B共同的parent， 然后从哪个parent 到 root都是common path?
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Tue Aug 30 13:29:44 2011, 美东) 提到:
嗯 对 lowest common ancestor
☆─────────────────────────────────────☆
busbby (奥特曼在银行里下象棋) 于 (Tue Aug 30 14:16:49 2011, 美东) 提到:
Mark,楼主功底不错
☆─────────────────────────────────────☆
holyman (木头鬼仔) 于 (Tue Aug 30 15:21:01 2011, 美东) 提到:
MARK
☆─────────────────────────────────────☆
returning (aaaaaaaaa) 于 (Tue Aug 30 16:38:32 2011, 美东) 提到:
how to determine if a system is 32bit or 64bit?
btw: 下面这个题目到底什么规律？
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
☆─────────────────────────────────────☆
MrMila (Mr.Mila) 于 (Tue Aug 30 17:55:38 2011, 美东) 提到:
谢谢楼主！
☆─────────────────────────────────────☆
kinkiguen (K_K) 于 (Tue Aug 30 21:34:34 2011, 美东) 提到:
谢谢楼主，您申请的是什么职位，因为离毕业还有段时间，开始看着面试题了，对申请
职位很不了解。我看版里有的面经对OS要求不是很高，而您的题目算法倒不是很显著，
反而OS很多。有没有基本不怎么考OS的职位的？偶OS只知道 semaphore。。。
☆─────────────────────────────────────☆
consuming (consume) 于 (Tue Aug 30 21:37:13 2011, 美东) 提到:
How to improve? how to determine if a system is
32bit or 64bit?
sizeof(size_t) ?
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Tue Aug 30 22:34:52 2011, 美东) 提到:
上一行是1个1
上一行是2个1
上一行是1个2，1个1
上一行是1个1，1个2，2个1
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Wed Aug 31 00:11:25 2011, 美东) 提到:
呵呵 我是做OS的, 所以OS的题目会多一些了. 要是申请一般的software engineer, 应
该不会这么偏重考察OS的概念.
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Wed Aug 31 00:15:51 2011, 美东) 提到:
sizeof(pointer)
可以每次拷贝多个字节以充分利用bus的带宽. 比如说如果是32位的系统, 一次拷贝4个
字节, 64位系统每次拷贝8个字节
☆─────────────────────────────────────☆
heavyburden (nothing) 于 (Sun Sep 18 15:13:13 2011, 美东) 提到:
楼主拿到offer吗？您很牛。
☆─────────────────────────────────────☆
heavyburden (nothing) 于 (Sun Sep 18 15:13:24 2011, 美东) 提到:
楼主拿到offer吗？您很牛。
