b****z
发帖数: 176 | 1 用queue 做树的广度优先遍历，空间复杂度是多少？
感觉好像不是O(n), 应该会比O(n)小？ 因为 空间复杂度应该是 树的底部的节点的数
量，因为每次都会dequeue。
大家觉得呢？ |
|
A*********c
发帖数: 430 | 2 去年末海投了MS软工，校园interview过了，等待onsite。两周内居然收到来信说SDE招
满了，onsite取消。问要不要考虑SDET。本身对SDE更有兴趣，但是考虑到onsite的经
验不多，拖了一阵也就接受了。前几天面的。
之前问过recruiter要面哪个组，一直没准信，面试前15分钟得知Azure组。没申这个组
, 不知为啥安排的。
校面: 论文, reverse words in sentence
1. 亚裔：Unknown Interviewer profile: a) Median of two sorted arrays, b)
1000 number files each contain 1,000,000,000,000 numbers, find the median
2. 小印：SDET 3 years: a) Quora’s design. b) For a quora question, given
getRndAns(), implement function to return “More Answers…” (i.e. next n... 阅读全帖 |
|
f******h
发帖数: 45 | 3 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
j*****4
发帖数: 12 | 4 估计挂了，有一题基本不知道怎么解。
设计一个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里面用的。有人听着耳熟么？ 我是不是
被黑了。 |
|
m**********e
发帖数: 22 | 5 我来贡献一个用queue的方法。C#写的：
// Iterative approach
public List generateParenthesisIter(int n)
{
Queue queue = new Queue(
);
queue.Enqueue(new ParenthesisWrapper("",0,0));
List result = new List();
while (queue.Count > 0)
{
ParenthesisWrapper curr = queue.Dequeue();
if (curr.left == n)
{
if ... 阅读全帖 |
|
r*****3
发帖数: 27 | 6 用一个类似双向Queue的结构?
queue存的是(time, count)
每次hit 都看一下queue里面最后一个元素的时间是否一样, 如果一样就count++, 如果
不一样就把(time, 1)压进去
hit的时候可以顺便把超过30min的头部都dequeue...
不知道这样可不可以 scale不清楚 - - |
|
r*****3
发帖数: 27 | 7 用一个类似双向Queue的结构?
queue存的是(time, count)
每次hit 都看一下queue里面最后一个元素的时间是否一样, 如果一样就count++, 如果
不一样就把(time, 1)压进去
hit的时候可以顺便把超过30min的头部都dequeue...
不知道这样可不可以 scale不清楚 - - |
|
g****v
发帖数: 971 | 8 发现这个还是挺常见的，这是网上的标准解法，希望可以对大家有帮助。
唯一的问题是为什么2个方法里面都用while来判断， 而不是用if？
---------------------------------------------
public synchronized void enqueue(Object item)
throws InterruptedException {
while(this.queue.size() == this.limit) {
wait();
}
if(this.queue.size() == 0) {
notifyAll();
}
this.queue.add(item);
}
public synchronized Object dequeue()
throws InterruptedException{
while(this.queue.size() == 0){
wait();
}
if(this.queue.size() == t... 阅读全帖 |
|
s******x
发帖数: 417 | 9 我也是这么想的。。enqueue 和 dequeue的时候lock下就行。 |
|
p*******8
发帖数: 344 | 10 我明白你的意思，我找到我前面问题的答案了：
1. 调用wait() 会release掉当前的锁, 所以其他线程可以调用take()
2. 关于java linkedBlockingQueue的实现，为什么两个不用的锁也可以, 因为enqueue
/dequeue的操作只分别对head/tail的操作，所以put/take可以同时进行 |
|
|
T*********g
发帖数: 496 | 12 dequeue那个时候还没拿到lock 继续 wait 直到enqueue方法做完 |
|
m*****k
发帖数: 731 | 13 dequeue那个时候可能已被唤醒，但拿不到lock， 因为synchronized enqueue方法还没
退出 |
|
h******e
发帖数: 52 | 14 来自主题: JobHunting版 - g 家面经 简化一下
public class ProducerConsumer
{
private Semaphore fillCount;
private Semaphore emptyCount;
private ConcurrentQueue queue;
public ProducerConsumer()
{
fillCount = new Semaphore(0, 100);
emptyCount = new Semaphore(100, 100);
queue = ConcurrentQueue();
}
public void Producer()
{
while(true)
{
//produce something
int x = 1;
... 阅读全帖 |
|
l******s
发帖数: 3045 | 15 private static void updateBoard(int[,] board, int k){
int m = board.GetLength(0), n = board.GetLength(1);
Queue queue = new Queue();
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(board[i, j] == 1) queue.Enqueue(new int[]{i, j});
while(k-- > 0 && queue.Count != 0){
int count = queue.Count;
while(count-- > 0){
int[] xy = queue.Dequeue();
for(int x = xy[0] - 1; x <= xy[0] + 1; x++)
for(int y = xy[1] - 1; y <= xy[1] + 1; y++){
if... 阅读全帖 |
|
j*h
发帖数: 3 | 16 实现的数据结构，可以是circular array， dequeue， priority queue
class Service{
bool handleRequest(double timestamp){
}
}; |
|
y*********e
发帖数: 518 | 17 当怎么排都有conflict的时候就抛异常呗。代码如下：
struct class {
int class_id;
int start_time;
int end_time;
}
// sort by start_time
struct room {
int available_start_time;
vector class_ids;
}
// sort by available_start_time
vector find_scheduling(
vector rooms,
vector classes) {
priority_queue rq(rooms.begin(), rooms.end());
priority_queue cq(classes.begin(), classes.end());
while (!cq.empty()) {
const class& c = cq.dequeue();
for (room& r : rq) {... 阅读全帖 |
|
b*******y
发帖数: 12791 | 18 虽然queue长，但是processor多，dequeue的速度挺快的 |
|
b*e
发帖数: 3845 | 19 要实现一个类似Round Robin的分配系统。这个系统的背景是这样的，有n个Manager,设为
n1,n2,...,nn. 有m个tele-marketing people. Telemarketing
people打电话骚扰potential customer，如果对方中招，就通过一个Webpage
填入customer的信息，然后选一个manager,把这个customer的信息发给他(用JavaScript)
。
现在要求动态的根据manager的load自动选一个manager。算法很简单，比如说用一个queu
e,每次dequeue后，再insert到最后。我的问题是这样的系统怎么实现比较方便？以下是
我的一些想法，请教各位高手，有没有其他Architecture的可能？多谢。
1. 用Client-Server结构。Server will have a queue and is multi-threaded. It can
output to a queue file and read in the queue file.
Telemarketing的webpage可以 |
|
I*******e
发帖数: 1879 | 20 ☆─────────────────────────────────────☆
bee (只会嗡嗡叫的蜜蜂) 于 (Wed Jan 15 21:39:41 2003) 提到:
要实现一个类似Round Robin的分配系统。这个系统的背景是这样的，有n个Manager,设为
n1,n2,...,nn. 有m个tele-marketing people. Telemarketing
people打电话骚扰potential customer，如果对方中招，就通过一个Webpage
填入customer的信息，然后选一个manager,把这个customer的信息发给他(用JavaScript)
。
现在要求动态的根据manager的load自动选一个manager。算法很简单，比如说用一个queu
e,每次dequeue后，再insert到最后。我的问题是这样的系统怎么实现比较方便？以下是
我的一些想法，请教各位高手，有没有其他Architecture的可能？多谢。
1. 用Client-Server结构。Server will have a queue and is mult |
|
T***B
发帖数: 137 | 21 The problem is the Predictor constructor needs to do some heavy lifting work
thus is slow. I am thinking to pre-create a bunch of Predictor objects and
put them in a BlockingQueue. Once predict() is called, the handler dequeues
a predictor and pass it to ExecutorService. |
|
g*****g
发帖数: 34805 | 22 This is a classic producer/consumer problem then, you should be able to find
many examples online. You could create a fix thread threadpool, and the
same number of Predictor, you then pass predictor and your input to your
jobs before sending them to executor.
work
and
dequeues |
|
l*******m
发帖数: 1096 | 23 是SVM classifier吧。你这个应该可以。主要缺点是多个model的copies。当然如果不
是太大，这样倒是省心。如果太大，把model本身（一堆矩阵）独立出来，设成global
object就好了
work
and
dequeues |
|
a****n
发帖数: 230 | 24 我现在用Dequeue做buffer
有两个thread,一个插入，一个Pop out，要求插入要快
发现主要是两个thread之间等待对Buffer的ownership等比较久
不知道大家有什么好办法，谢谢。。。。 |
|
i******r
发帖数: 323 | 25 如果是这样可以用queue代替dequeue? 不thread safe估计不行 |
|
p*****2
发帖数: 21240 | 26 java 400多毫秒，scala 1000毫秒超时。
object test6 extends App {
def add(x:Int, y:Int):Unit={
if(x<1 || x>n || y<0) return;
val yy=Math.min(y,a(x)+1)
if(v(x)(yy)) return
queue+=Array(x,yy)
v(x)(yy)=true
}
val sc=new Scanner(new File("input.txt"))
val out=new PrintWriter("output.txt")
val n=sc.nextInt
val a=new Array[Int](n+1)
val v=Array.ofDim[Boolean](105, 100005)
val queue=Queue[Array[Int]]()
for(i<-1 to n) a(i)=sc.nextInt
... 阅读全帖 |
|
n*****t
发帖数: 22014 | 27 这个当然 depends，就这个例子，enqueue 之后如果需要别的 function dequeue，还
是应该 malloc |
|
n*****t
发帖数: 22014 | 28 我觉得单线程够呛，单节点多进程收包，查询就直接 read，锁票先 lock 再 write，
确认出票不用锁。enqueue/dequeue 开销太大 |
|
L*****e
发帖数: 8347 | 29 一旦引入多线程，各个线路之间的耦合就出来了，线路多少就极为相关了。。。
enqueue/dequeue和锁写哪个开销更大，需要根据线路多少来平衡了。。。 |
|
L*****e
发帖数: 8347 | 30 因为googbug一直强调说你只需要单线程，所谓我按单线程理解。。。如果用interlock
，所节约的时间也就是enqueue/dequeue吧？ |
|
T********i
发帖数: 2416 | 31 不对，enqueue/dequeue开销基本为0。
写这种系统，本版长出来晃的，我还没见到有第二人都这个经验。
interlock |
|
n*****t
发帖数: 22014 | 32 /* route code */
#define AB 0
#define AC 1
/* ... */
#define YZ 190
queue_to_check[AB] = { AB, AC, AD, AE, /* ... */ AZ, -1 };
queue_to_check[KO] = { KO, KP, JO, KQ, /* ... */ AZ, -1 };
queues = ticket_queue_base + queue_to_check[get_route_code(req->from,req->to
)]
switch (req->op) {
case QUERY:
return ticket_avaliable[req->train][req->class][indexof(req->from,
req->to);
case RESERVE:
queue = get_queue_to_check(ticket_queue, req->from, req->to);
while (queue) {
... 阅读全帖 |
|
n*****t
发帖数: 22014 | 33 还好吧，哪个队列有票，查 20x20 bitmap 就知道了，剩下就是 dequeue 一张票。如
果某个区间不可能出票，写到另一个 bitmap B，下次不用算了。有退票的时候再更新
这 2 个 map。enqueue 也是飞快。我估计平均 100 个指令就能搞定 1 张票，even
less |
|
N********n
发帖数: 8363 | 34
And what's the efficiency of this "specifying start and end" thing?
How to quickly locate the exact UUIDs for random start and end? Sounds
like an O(log N) operation, which is more expensive than a typical
ENQUEUE DEQUEUE or Hash Table access. Those are O(1). |
|
N********n
发帖数: 8363 | 35
QUEUE首先要FIFO，ENQUEUE、DEQUEUE要O(1)复杂度。C* HASHTABLE不是干
这个用的。这不是什么J2EE概念，这属于最基本的算法和数据结构。 |
|
N********n
发帖数: 8363 | 36
怎么都行的数据结构是不存在的。QUEUE要保证FIFO，ENQUEUE、DEQUEUE都
是O(1)，看不出C*怎么能做到。FIFO本身就是一种紧耦合，觉得拿啥NOSQL
来都没戏，只能这里妥协一下、那里妥协一下。 |
|
N********n
发帖数: 8363 | 37
"用timestamp 做rowkey"本身就是问题。假设时间区间[A, B]，A的TIMESTAMP
如果不在TABLE里面怎么办。你怎样快速找到下一个离A最近的MSG? 这里没有
取巧，一旦要搜索你的DEQUEUE效率就不是O(1)。
先说TIMESTAMP，其他问题肯定也不少。总之这个数据结构不能当QUEUE用。 |
|
N********n
发帖数: 8363 | 38
扯淡，普通queue做enqueue/dequeue都是O(1)效率。啥分布式系统也无法
跟这叫板效率。也就不懂装懂的拿个HashTable出来瞎叫唤。 |
|
l****r
发帖数: 105 | 39 最近没事刷刷leetcode，碰到几个二叉树问题，测试时创建二叉树手写起来太麻烦（C#
），所以想自己搞个工具，作用是根据给定数组创建二叉树。
初步写出来是这样的：
public static TreeNode CreateBinaryTree(int[] values)
{
TreeNode root = new TreeNode(values[0]);
Queue nodeQueue = new Queue();
nodeQueue.Enqueue(root);
TreeNode current = null;
foreach (var value in values.Skip(1))
{
if (current == null || (current.left != null && current.
right != null))
... 阅读全帖 |
|
h**********c
发帖数: 4120 | 40 估计汉语是您第二语言吧，四个连续字符的子窜。
用一个hashset,
随机生成四窜，set里有就加，没有就过，
用dequeue来做sliding window.
Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab0Ab1Ab2Ab3Ab4Ab5Ab6Ab7Ab8Ab9Ac0Ac1Ac2Ac3
,. |
|
