k*****y
发帖数: 744 | 1 考虑六种从小到大排列的可能情况，每种找出最小的distance，再一起比较。
import random
# generate random data
data = [[],[],[]]
for i in range(0,3):
N = random.randint(5, 10)
for j in range(0, N):
data[i].append(random.randrange(0, 1000))
data[i].sort()
#=============================
test_cases = [(0,1,2), (0,2,1),
(1,0,2), (1,2,0),
(2,0,1), (2,1,0)]
pos = [[] for i in range(len(test_cases))]
dist = [1000000]*len(test_cases)
def LowerBound(x, queueID, start):
for i in range( st... 阅读全帖 |
|
a********r
发帖数: 218 | 2 For questions 1-4, assume that an array stores integers and has a maximum
size of 100. The array is used to store two distinct data structures, BOTH
a queue and a stack. The answer should be written in C or C++ and should
not use any existing data structure libraries.
1.Write a function that pushes an integer into the stack.
2.Write a function that pops an integer from the stack.
3.Write a function that enqueues an integer into the queue.
4.Write a function that dequeues an integer from the qu... 阅读全帖 |
|
s*******f
发帖数: 1114 | 3 1. get index of s1 in s2, for each char in s1, mark position is s2.
here "tiger" in "itreg" is [1, 0, 4, 3, 2]
stops和posts is: 2 3 1 0 4
//For duplication, always pick nearer one first. I use "set" to deal with
duplication in code.
At first I use brute force here with O(n square). But when using
hash_map >, it goes to O(n), or queue hm[256]
.no need to use "set" for duplication.
2. rule for eat: you can eat neighbour if your high or low bound
can "touch" neighbour.
here [1,... 阅读全帖 |
|
p*****o
发帖数: 1285 | 4 我的完整的方法是这样的。用两个辅助数据结构，一个hashtable, 每个节点是个固定
长度的queue，长度是该字符在T中的数量，存放T字符在目前序列中的位置。另一个是
queue, 用来存目前序列中属于T的字符的顺序，以方便寻找下一序列起点。不用queue
直接用尾指针也可以，但会增加一些比较。 |
|
j********e
发帖数: 1192 | 5 我上面说错了，可以加一个变量表示几个child。
我给的答案和peking2的一样，就是DFS。Write就比较容易了，多写一个int
表示几个children。
读的时候，用了个queue，读到某个节点时，如果它有k个children，那么
queue里最后k个就是它的children了。queue的最大长度应该是O(logN*K),
(最多K个children) |
|
l****i
发帖数: 230 | 6 这周周二的onsite，一共五轮面试。安排比较混乱，其中一个interviewer，我干等了
半个小时，no show。联系HR，才知道这个interviewer已经休假5个月。所以后来又加
了一个interviewer。
感觉google的面试根本不考虑candidate的背景和经历，只考coding。我有朋友做到了
CS Top-4的正教授，去google面试仍然是一样的流程。这个确实让人非常frustrated。
1. Thesis discussion：老印，data base出身，鸡同鸭讲，面得很费劲，互相感觉都
不是很好。
2. 老中，coding：给一个N个node的BST，给一个Key，返回与key最接近的m个node(m
).
我开始说可以做inorder traverse，用一个priority queue保存跟key最近的m个value
，复杂度O(n)；存在average O(log n)的算法，但不好写。结果还是被要求写O(log n)
的code。
这个算法不是很难(不确定是不是最优)，但是在30分钟写出来确实不容易。
我的基本思路还是用priority... 阅读全帖 |
|
v*******a
发帖数: 14 | 7 【 以下文字转载自 Programming 讨论区 】
发信人: violetmma (苏苏), 信区: Programming
标 题: 问个OO题
发信站: BBS 未名空间站 (Sun Jul 1 17:08:17 2012, 美东)
A software subsystem of an air-traffic control system is defined to manage a
queue of aircraft (AC) in an airport. The aircraft queue is managed by a
process which responds to three types of requests:
system boot used to start the system.
enqueue aircraft used to insert a new AC into the system.
dequeue aircraft used to remove an AC from the system.
AC’s have at least (but a... 阅读全帖 |
|
l****i
发帖数: 230 | 8 用priority queue是O(n log(k))吧，每次对queue做一次update(或插入或删除或更新)
都是log(k),总共循环n次(对数组做一次scan)，所以是n log(k),k是左后找到的子集和
的大小(priority queue的大小) |
|
p******9
发帖数: 47 | 9 来自主题: JobHunting版 - 问几道题目 第三题是150题上的题，为每个质数构建一个Queue，每次出几个queue中最小的数，然
后将这个数和这几个质数相乘，放回queue中，注意处理重复。 |
|
w**********6
发帖数: 800 | 10 Single people maintain a priority queue of potential dating candidates—
mentally if not explicitly. One’s impression on meeting a new person maps
directly to an attractiveness or desirability score. Desirability serves as
the key field for inserting this new entry into the “little black book”
priority queue data structure. Dating is the process of extracting the most
desirable person from the data structure (Find-Maximum), spending an evening
to evaluate them better, and then reinserting them in... 阅读全帖 |
|
w********p
发帖数: 948 | 11 第一题，我会想按照图来做，类似BFS, 从root, 把所有的left, right Children放到
queue里。放后mark颜色，每次 add elements 到queue的时候，比较两个queue 加入的
element 和个数 是不是一样。 |
|
r****m
发帖数: 70 | 12 HR先介绍流程
1. 接着和一个engineer吃饭，同胞，吃饭同桌的还有好几个其他同胞，用中文聊了一
会天，吃完饭开始面试，讨论了很多distribute的东西，shard, hash, queue之类,
怎么design pinterest homepage.
2. 接下来另engineer，但没口音，问了两道题
a. 给一个数组和一个位置，从该位置起左右jump，检测能否jump到值为0的位置,
canJump(int a[], int pos)
b. 给一组字符串，找最长的公共前缀，至少两个字符串公共
3. Hire Manager, 让我介绍了一下项目，然后问了我能想到的怎么improve pinterest
每次查询，将查询字符串写入日志文件，查找出现次数前十的查询字符串
我用priority queue实现，然后问我怎么实现priority queue, 我给他介绍了堆的
实现: 插入、删除和调整
然后问在不同机器怎么办
4. 非技术, 问了最自豪的项目和好几个behavior的问题
5. 和HR随便聊聊，结束面试
已经被拒，分享出来希望对大家有... 阅读全帖 |
|
r****m
发帖数: 70 | 13 HR先介绍流程
1. 接着和一个engineer吃饭，同胞，吃饭同桌的还有好几个其他同胞，用中文聊了一
会天，吃完饭开始面试，讨论了很多distribute的东西，shard, hash, queue之类,
怎么design pinterest homepage.
2. 接下来另engineer，但没口音，问了两道题
a. 给一个数组和一个位置，从该位置起左右jump，检测能否jump到值为0的位置,
canJump(int a[], int pos)
b. 给一组字符串，找最长的公共前缀，至少两个字符串公共
3. Hire Manager, 让我介绍了一下项目，然后问了我能想到的怎么improve pinterest
每次查询，将查询字符串写入日志文件，查找出现次数前十的查询字符串
我用priority queue实现，然后问我怎么实现priority queue, 我给他介绍了堆的
实现: 插入、删除和调整
然后问在不同机器怎么办
4. 非技术, 问了最自豪的项目和好几个behavior的问题
5. 和HR随便聊聊，结束面试
已经被拒，分享出来希望对大家有... 阅读全帖 |
|
b*********h
发帖数: 103 | 14 看大家都用优先队列，贴一个 set 的吧 呵呵，用 C++ 的表示声明 priority queue
打字太多。。。继续说 C++ 的 priority queue 又不支持 decrease key，喜欢用 set
当 priority queue 。。。
class Solution {
public:
ListNode *mergeKLists(vector &lists) {
multiset S;
for (int i = 0; i < lists.size(); ++i) {
if (lists[i]) {
S.insert(lists[i]);
}
}
ListNode* head = 0;
ListNode* tail = 0;
while (!S.empty()) {
ListNode* nod... 阅读全帖 |
|
g******z
发帖数: 893 | 15 如果这种情况的话，能不能BFS+queue
把周围的同色棋子和空格用queue保存下来
如果queue空之前到达棋盘边界就没有被围，不然就是被围了？ |
|
x*****0
发帖数: 452 | 16 Given a linked list where in addition to the next pointer, each node has a
child pointer, which may or may not point to a separate list. These child
lists may have one or more children of their own, and so on, to produce a
multilevel data structure, as shown in below figure.You are given the head
of the first level of the list. Flatten the list so that all the nodes
appear in a single-level linked list. You need to flatten the list in way
that all nodes at first level should come first, then nod... 阅读全帖 |
|
l*******b
发帖数: 2586 | 17 想了个这个办法, 不知道好实现不?
建立一个高度的priority queue
把边界一圈push进去
当该queue非空时, 弹出最低的那个, 把该点未搜索过的领域push到queue里. 如果领域
比弹出的这个元素高度低, 那么就把差距加到总的可以积水的量里面
返回总积水量 |
|
l*******b
发帖数: 2586 | 18 想了个这个办法, 不知道好实现不?
建立一个高度的priority queue
把边界一圈push进去
当该queue非空时, 弹出最低的那个, 把该点未搜索过的领域push到queue里. 如果领域
比弹出的这个元素高度低, 那么就把差距加到总的可以积水的量里面
返回总积水量 |
|
o******3
发帖数: 91 | 19 我今天又写了一下
现在这个可以过所有数据集合了
方法还是BFS
区别的 这次我没有模拟stack
直接在Array上操作 这样程序更简单 写的可以快一点
#include
#include
#include
#include
#include |
|
f********d
发帖数: 51 | 20 while(true) {
CountDownLatch o = oq.take(); // take an O
CountDownLatch h1 =hq.take(); // take an H
hq.take().countDown(); // take another H
h1.countDown(); // count down all the rest
o.countDown();
}
any new formula, you only need to make sure the first 3 lines reflects your
formula well. it becomes very extensible. and you can also do
Collection list = Lists.newArrayList();
for (ElementDefinition ed : defs) {
BlockingQueue ... 阅读全帖 |
|
f********d
发帖数: 51 | 21 while(true) {
CountDownLatch o = oq.take(); // take an O
CountDownLatch h1 =hq.take(); // take an H
hq.take().countDown(); // take another H
h1.countDown(); // count down all the rest
o.countDown();
}
any new formula, you only need to make sure the first 3 lines reflects your
formula well. it becomes very extensible. and you can also do
Collection list = Lists.newArrayList();
for (ElementDefinition ed : defs) {
BlockingQueue ... 阅读全帖 |
|
w***y
发帖数: 6251 | 22 我问了几个人，大概是这个思路
不过如果访问量太大， 一个queue里要存的ts太多， 就可以考虑用queue存每second的
#visits, 这样就是一个固定size的queue |
|
d**********x
发帖数: 4083 | 23 queue可以用linkedlist实现。
至于queue删除也是可以做到O(1)的，我想你要说的是，删除一个节点并push到queue的
前端做不到O(1) |
|
L***Q
发帖数: 508 | 24 如果可以改动matrix的值，有一个简单办法。
Idea: 如果所有white的cell相连，那么从任何一个white cell开始，往四个方向扩展
，把遇到的white都改成black，那么最终所有cell都是black。
step 1：find any white cell as start point;
step 2: use a queue or stack to record white cells: get a cell, set it as
black, and then check the four directions. If a neighbor is white, put it in
queue/stack; Finish when queue/stack is empty
step 3: check the board again, return false if finding a white cell.
Complexity O(n^2). 如果两个white cell (i, j)和(i+1, j+1)算是相连，那step 2就
是check 8个方向 |
|
s*****r
发帖数: 43070 | 25 priority queue，先放(1,1),然后开始pop，每pop出一个，把其右边和下面的数放入
queue，如果queue里面已经有了，就不放 |
|
h*****a
发帖数: 1718 | 26 随便抛块砖。
如你所说，没有标准答案，不同面试官心里可能装着不同的答案，你要尽可能顺着对方
思路走。多问问题澄清假设，给出多种选择让对方决定详细说哪一个。
其实因为用户的状态更新一旦提交，在整个生命周期就是只读状态，（如果允许删除状
态更新的话会增加复杂性，这里暂不考虑）所以处理起来相对复杂性并不高。我觉得需
要考虑的有以下几点：
1）确定需要处理的数据规模。假定FB有10亿用户，里面有1亿每天登陆的活跃用户需要
看到update，平均每个人每天看到50条更新。10亿用户中平均每两周有5000万会发布状
态更新，平均每人每周10次，每条更新需要50个字节的存储和传送（内容＋timestamp+
uid+updateId)。这些都是我的假设，需要对方confirm。
如果对方认可，那每天需要传送到活跃用户wall上的数据是50Byte * 100M * 50 =
250G bytes ， 约为 3MB/second。考虑到要能处理spike，可以设计传输的capacity为
10MB/second.
存储系统只需存储过去两周的数据，50M * 10 * 50byte = 25GB，考虑p... 阅读全帖 |
|
h*****a
发帖数: 1718 | 27 随便抛块砖。
如你所说，没有标准答案，不同面试官心里可能装着不同的答案，你要尽可能顺着对方
思路走。多问问题澄清假设，给出多种选择让对方决定详细说哪一个。
其实因为用户的状态更新一旦提交，在整个生命周期就是只读状态，（如果允许删除状
态更新的话会增加复杂性，这里暂不考虑）所以处理起来相对复杂性并不高。我觉得需
要考虑的有以下几点：
1）确定需要处理的数据规模。假定FB有10亿用户，里面有1亿每天登陆的活跃用户需要
看到update，平均每个人每天看到50条更新。10亿用户中平均每两周有5000万会发布状
态更新，平均每人每周10次，每条更新需要50个字节的存储和传送（内容＋timestamp+
uid+updateId)。这些都是我的假设，需要对方confirm。
如果对方认可，那每天需要传送到活跃用户wall上的数据是50Byte * 100M * 50 =
250G bytes ， 约为 3MB/second。考虑到要能处理spike，可以设计传输的capacity为
10MB/second.
存储系统只需存储过去两周的数据，50M * 10 * 50byte = 25GB，考虑p... 阅读全帖 |
|
u*****o
发帖数: 1224 | 28 来自主题: JobHunting版 - f 的面经 可以用DEQUE吗？
先连QUEUE的头，再连QUEUE的尾，一直到QUEUE空为止。。 |
|
g**G
发帖数: 767 | 29 2. 当queue不为空时
把queue里的坐标poll出来，看这个坐标上下左右，如果是O, add到queue最后
你有没有标记访问过的点？ |
|
r****s
发帖数: 1025 | 30 用一个synchronous queue,再加个semaphore size(1)， 一个字符 变量， 不就行了？
每个thread wait on semaphore, 而不是queue。抢到semaphore的就先查前一字符是什
么，如果是回车就release semaphore, exit; 如果不是就等在queue那里，进来一个字
符就print，然后把字符update进变量。release semaphore.
最后送一个回车符，大家一起exit就行了。 |
|
g*****g
发帖数: 34805 | 31 我给个分布式设计，过面试应该够了。
每个share产生一个event，发给一个dispatch cluster，这个cluster干的活就是根据
url算个hash出来，分配给下一个count cluster，所以相同的url会发给同一个结点处
理。count cluster上每个结点需要一个存一个根据时间排列的queue，每个dispatch
event会产生一个当前时间的+1 job和5分钟后的-1 job。queue可以用诸如Cassandra
DB time based UUID实现，scheduled excutor可以用Java的
ScheduledExecutorService实现。这个结点可以用ConcurrentSkipListMap 维护所有
link count并快速获得top 5 link。count cluster是最大的一个cluster，比如说有
1000个结点。
接下来如果count cluster很大，可以有一个aggregation cluster，干的事情是周期性
poll (比如说每5秒) count cluster 的一部分获得所有top 5排... 阅读全帖 |
|
f********a
发帖数: 165 | 32 server连续的接受到yes和no,当我们查询server的时候，返回以前的某一个小时最多的
yes个数。一个一个小时的time slot从server start算起。貌似要考虑多线程。 我想
法是用一个queue,每当接受到一个yes，检查时间，从queue里面pop出超过一个小时的
yes，然后比较这时queue的size和最大个数,如果大就更新最大个数. 我用c++,
multithreading写起来费力，因为查询的时候貌似要stop server？ 那位大侠说说。 |
|
m****i
发帖数: 15 | 33 找工作期间在本版潜水两个月，收益良多，发一下最近面经和经验作为回馈。
本人背景：美国不错学校电子PHD即将毕业，专业是EDA做电路设计算法优化。因为EDA
已经是一个很稳定的工业，没什么太大的前景，随想转到前沿的tech公司。本专业只投
了一家现在最大的公司，拿到offer。别的投了Google, Facebook, Rocket fuel,
Twitter, Linkedin, Yahoo, Amazon, Box, Oracle. 除了box别的都找人refer了， 在
此感谢板上大哥们的热情帮忙. 除了GFR别的都没理我，可能背景差太大了。
因为之前是学算法的，mit算法书以前就看过两遍，基础还可以，前期8月份刷了遍
leetcode。然后9月初投出简历。两个星期刷Career cup 150， 最后面试期间一直查缺
补漏。到现在尘埃落定大概两个月。 最后GFR全挂，总结下惨痛经历：
1. Facebook电面
面试官做distributed cache infrastructure的，先问我最难的project，没怎么好好
准备过behavior，胡乱说了一通。但是因为做的是电... 阅读全帖 |
|
m****i
发帖数: 15 | 34 找工作期间在本版潜水两个月，收益良多，发一下最近面经和经验作为回馈。
本人背景：美国不错学校电子PHD即将毕业，专业是EDA做电路设计算法优化。因为EDA
已经是一个很稳定的工业，没什么太大的前景，随想转到前沿的tech公司。本专业只投
了一家现在最大的公司，拿到offer。别的投了Google, Facebook, Rocket fuel,
Twitter, Linkedin, Yahoo, Amazon, Box, Oracle. 除了box别的都找人refer了， 在
此感谢板上大哥们的热情帮忙. 除了GFR别的都没理我，可能背景差太大了。
因为之前是学算法的，mit算法书以前就看过两遍，基础还可以，前期8月份刷了遍
leetcode。然后9月初投出简历。两个星期刷Career cup 150， 最后面试期间一直查缺
补漏。到现在尘埃落定大概两个月。 最后GFR全挂，总结下惨痛经历：
1. Facebook电面
面试官做distributed cache infrastructure的，先问我最难的project，没怎么好好
准备过behavior，胡乱说了一通。但是因为做的是电... 阅读全帖 |
|
|
m**p
发帖数: 189 | 36 这个怎么样？
#include
#include
#include
#include
template
class Queue
{
public:
T pop()
{
std::unique_lock mlock(mutex_);
while (queue_.empty())
{
cond_.wait(mlock);
}
auto item = queue_.front();
queue_.pop();
return item;
}
void pop(T& item)
{
std::unique_lock mlock(mutex_);
while (queue_.empty())
{
cond_.wait(mlock);
}
item = queue_.front();
que... 阅读全帖 |
|
d***n
发帖数: 832 | 37 再来个更先进的, blocking bounded queue
public class BlockingBoundedQueue
{
private Queue m_queue = new Queue();
private int m_capacity;
private object m_fullEvent = new object();
private int m_fullWaiters = 0;
private object m_emptyEvent = new object();
private int m_emptyWaiters = 0;
public BlockingBoundedQueue(int capacity)
{
m_capacity = capacity;
}
public int Count
{
get
... 阅读全帖 |
|
l*********d
发帖数: 78 | 38 尝试过许多解法，但老是 TLE. 有高人能帮忙看一下这一段代码吗？
基本上就是 double queue + backtracking，跟这里的http://blog.csdn.net/niaokedaoren/article/details/8884938
很相似。但是问题出在哪里呢？
提前谢谢了！
------------------------------------------------------------------------
import java.util.Map;
public class Solution {
public void fillPaths(String start, String cur, Map>
map,
ArrayList> result, LinkedList post
) {
post.addFirst(cur);
if (start.equals(cur)) {
... 阅读全帖 |
|
h**o
发帖数: 548 | 39 我觉得和cc150 8.2 design a call center 类似。
bank/callcenter 收到一个request,分给一个空闲的elevator/employee
如果没闲人，把request入queue. 一旦有人闲下来，就来queue里找任务去处理。bank/
callcenter就好像server, elevator/employee 就好象process/thread/task.
passanger 是 request 中的 subrequest.
贴一个我的码吧。 欢迎指正。网上有些code有铃啊，门的。我不明白。就不加入我的
码了。
test_evelatorSystem(){
mg = Manager::getInstance();
for (i = 0; i < 4; i++){
//sb. press button UP at floor 5
Request* req = new Request(floor=5, direction=UP);
mg.dispatchRequest(req)... 阅读全帖 |
|
l******6
发帖数: 340 | 40 level order traverse.
一个flag ： noMoreNode == false
过程中：
noMoreNode == false 的时候
如果一个节点左右child 都有， 正常继续 traverse, 左右child 先后进queue
如果一个节点只有左child/没有child, 左child 进queue/什么不干， noMoreNode =
true;
如果一个节点只有右child return false
当 noMoreNode == true的时候， 任何node需要进queue: return false
最后什么也没发生 return true |
|
p*****e
发帖数: 537 | 41 我也觉得BST不必要，因为肯定是从最左边的leaf删，然后加到最右边的leaf去。我觉
得一个queue就够了，然后如果assume key永远不会重复，那么add就仅仅是加进queue
和hashtable，getMsg()也只是query，只有getAvg（）的时候做delete，worst case的
time complexity是O(n),因为有可能把所有的msg都删掉。这样做的坏处是memory可能
占用很多，然后synchronization的overhead比较高。
为了减少synchronization overhead，我觉得可以考虑不用shared system，每一个
thread搞一个thread local的queue和hashtable，这样add的时候需要load balancing
，query的时候需要gather，然后getAvg的时候需要gather和scatter，和distributed
system一样了，呵呵。 |
|
t********2
发帖数: 28 | 42 Q1: sort the intervals by starting time， use a priority queue to store
available time for current rooms, then start from the first, check whether
there is a room available, if yes, use that one and reset its available time
, if not, add new room into the queue. At the same time, count the new rooms
which have been added into the queue. complexity ~ O(NlogN) |
|
j*****4
发帖数: 12 | 43 估计挂了，有一题基本不知道怎么解。
设计一个function: bool cancall(), 保证每秒钟内return true的数量小于 N,
想了两个办法，
a)写个queue, 每次 call 把 request time放到queue 里面，dequeue 1秒以前的
request.然后看queue的size..没效率，被否。
b)每秒一个bucket,然后保证当前bucket,的count小于N/2,不精确，被否。
然后就没时间了，这个怎么搞，到底？ 提示是"keep track of available count
instead... "
面试管好像说是一个XXX algorithm,在network里面用的。有人听着耳熟么？ 我是不是
被黑了。 |
|
h*d
发帖数: 19309 | 44 用一个queue，里面保存上次成功的时间，如果已经size N而且第一个时间差<1秒就拒
绝，如果第一个>1秒就出queue，把新的成功cancall加入queue。 |
|
h*d
发帖数: 19309 | 45 FIFO我觉得应该用Queue啊，不过可能每次都查太慢？这个可以考虑降低储存的时间的
精度，设定一个delta来保存，这样Queue变化的频率就降低了，另外可能需要考虑lock
的问题？如果同时上百万的请求访问这个，可以考虑把服务的false结果作一个cache，
指定一个delta时间，比如1/10秒，这样1/10之内的所有访问就不需要对Queue进行任何
操作，直接拿false的结果？ |
|
r*******2
发帖数: 104 | 46
好的，我把我的解题过程也说一下。Leetcode原题就不用说了。
第一组：
第1轮：判断subtree。假设两棵树T1和T2，先用DFS在T1里找到和T2的root一样的结点
，然后从找到的结点开始和T2进行比较，我用了BFS，就是用queue，一边一个queue，
同时push/pop进行比较，如果碰到不一样的就return false。做完了想起来其实就是
Leetcode上的Same Tree，直接还用DFS递归比queue省事。
第2轮：找出maze中的path。开一个matrix标记maze的每一个点是否访问过，然后DFS搜
索，从起点开始，查找它的上下左右邻居，如果没有访问过也没有obstacle，就作为一
个选择进行下一步搜索，一直递归下去直到找到终点为止。
第3轮：设计题。
第4轮：ASCII和Kanji字符的题以前面过，当时没做出来，答案就是回来网上搜的（参
考这个网址http://discuss.joelonsoftware.com/default.asp?interview.11.334807.4）。Spiral Matrix是Leetcode原题就不说了。
第... 阅读全帖 |
|
z*******3
发帖数: 13709 | 47 对比一下queue和heap的效率哈
queue的删除很简单，尤其是删除头尾，对内部结构完全没有影响
heap的删除root之后，要heapify，这个开销很大
插入
两个都是lgn，所以queue可以省掉heapify这一个步骤
看hadoop什么都是用priorityqueue，而不是treemap
所以这题貌似heap并不是最优解，只是一个相对简单的解法
看来swjtuer是对的 |
|
z*******3
发帖数: 13709 | 48 对比一下queue和heap的效率哈
queue的删除很简单，尤其是删除头尾，对内部结构完全没有影响
heap的删除root之后，要heapify，这个开销很大
插入
两个都是lgn，所以queue可以省掉heapify这一个步骤
看hadoop什么都是用priorityqueue，而不是treemap
所以这题貌似heap并不是最优解，只是一个相对简单的解法
看来swjtuer是对的 |
|
b*****i
发帖数: 130 | 49 题目是： process A,B are running, C is sleeping, how wake up cafter A and B
are completed?
我回答把A,B放到"running state"的queue，然后等A,B run完之后把C从ready state
queue transfer 到 running state的queue。
面试官问怎么知道A,B run 完，不知道怎么答。。
ee的，这一周才学的OS课件，底子薄。。请大家帮助。。 |
|
u*****n
发帖数: 126 | 50 在他们家遇到了两个傻B阿三。一个不停的纠正我的逗号和分号，另外一个给的hints都
是废话。最后挂了。他们家的阿三是我面过的所有公司中最极品的。所以面试他们家要
小心傻B阿三。当然他们家的华人美女HR相当的nice，是我遇到的所有HR中最nice的。
总共面了四轮：
第一轮：定义buddy system为一棵complete binary tree。一个node可能为0也可能为1
. 它的
value为1，当且仅当它所有的child的value均为1.
1
|
1 2
| |
1 2 3 4
| | | |
1 2 3 4 5 6 7 8
实现下列的method。
1' clearBit(int offset, int len);
2' setBit(int offset, int len);
第二轮：设计一个task dispatching system，里面有一个task queue和两个function。
1’ trigger。这个func... 阅读全帖 |
|
