S**Y
发帖数: 136 | 1 Given a constant number of priorities implement a priority queue with O(1) e
nqueue and dequeue implementations.
I can not think of a way doing this...O(1) enque and deque..
even with a constant number of prioritties..
Any ideas? |
|
s******n
发帖数: 3946 | 2 第二题,搞个升序的dequeue, dequeue[0]表示当前k个连续元素最小difference。
每来一个元素diff[i]，把dequeue上所有比diff[i]大的扔掉，如果dequeue[0]=diff[i
-k]则把dequeue[0]也扔掉。 |
|
e****e
发帖数: 418 | 3 For array, you might have to left shift all the elements by 1, each time
after you dequeue. i.e.
before dequeue: 1 | 2 | 3 |
after dequeue: 2 | 3
Fop linked list, you don't need to do so. i.e.
before dequeue: 1 -> 2 -> 3 header points to 1.
after dequeue: 2 -> 3 header points to 2.
but you have to maintain a pointer which points to the last element and add
new element at the tail when enqueue.
To me it's more efficient to use linked list to implement queue than array.
Show ugly code for deep co... 阅读全帖 |
|
y*********e
发帖数: 518 | 4 想了下，这个题用greedy算法解。有点类似dijkstra算法求最短路径。
首先用一个priority queue来装已经发现的字符串，按照字典序排序。
比如输入是cbacdcbc，
scan到了第三个字符的时候，p_queue里面只有一个值 cba。
当scan到第四个字符c的时候，有了重复。这个时候有两个选择：
a. 把 c 从 cba 里面删除，变成 bac。
b. 不理会新遇到的 c，还是 cba。
把a选项和b选项再重新丢回p_queue。
如此重复一直到字符串结尾。返回p_queue的第一个值。因为p_queue是一个按照字典序
排好的priority queue，所以返回的结果一定就是答案。
伪代码如下：
let q = p_queue
for each c in string:
let s = q.empty() ? "" : q.dequeue()
if not c in s
s += c
q.push(s)
else:
s1 = del c in s
s1 += c
q.push(s)
q.push(s1... 阅读全帖 |
|
E*******0
发帖数: 465 | 5 void ACControl::Enqueue(AC ac)
{
if (ac.type==1) //passenger
PassengerQueue.Enqueue(ac);
else
PassengerQueue.Enqueue(ac);
}
AC ACControl::Dequeue()
{
if (!PassengerQueue.IsEmpty())
return PassengerQueue.Dequeue();
else
return PassengerQueue.Dequeue();
} |
|
K*********n
发帖数: 2852 | 6 看来得用两个指针，指向每层最后一个节点，在enqueue的时候更新。比如：
1
2 3
4 5 6
假如这个指针叫levelEnd1，一开始指向1，然后在enqueue 1的孩子的时候，它先指向2
，再指向3。
然后在dequeue的时候，先dequeue 2，然后enqueue 2的孩子，另一个指针levelEnd2指
向4，然后5，然后dequeue 3，然后levelEnd2指向6，然后没了，因为3没有右子树。怎
么知道levelEnd2指向第三层的最后一个节点呢？用levelEnd1判断。因为levelEnd1指向
第二层最后一个，也就是3，所以他的孩子levelEnd2就是第三层最后一个。
然后，levelEnd1 = levelEnd2，第三层搞定。levelEnd2重置为null，然后去用做第四
层……
我觉得这个方法好，因为给Node加field有点赖皮，而且有可能不被允许。 |
|
K*********n
发帖数: 2852 | 7 看来得用两个指针，指向每层最后一个节点，在enqueue的时候更新。比如：
1
2 3
4 5 6
假如这个指针叫levelEnd1，一开始指向1，然后在enqueue 1的孩子的时候，它先指向2
，再指向3。
然后在dequeue的时候，先dequeue 2，然后enqueue 2的孩子，另一个指针levelEnd2指
向4，然后5，然后dequeue 3，然后levelEnd2指向6，然后没了，因为3没有右子树。怎
么知道levelEnd2指向第三层的最后一个节点呢？用levelEnd1判断。因为levelEnd1指向
第二层最后一个，也就是3，所以他的孩子levelEnd2就是第三层最后一个。
然后，levelEnd1 = levelEnd2，第三层搞定。levelEnd2重置为null，然后去用做第四
层……
我觉得这个方法好，因为给Node加field有点赖皮，而且有可能不被允许。 |
|
s********u
发帖数: 1109 | 8 老印面试，人挺nice的，就是说话还是听不太清楚。特别是带了耳塞接电话，声音很“
刺”，免提又怕更听不清楚。
0.以为电面不问behavior的，没想到问我平时用不用ebay，如何提高用户体验等。。幸
好我用的比较多，随便扯了些。但是很担心突然说让我根据我说的design一下，所以战
战兢兢。
1.用stack实现一个queue，careercup书原题。我在dequeue里面用了shiftstack，他问
我能不能将enqueue的time cost降低到O(1),我说可以，只要每次enqueue时候都
shiftstack就可以了。他问我哪种更好（enqueue和dequeue几率相同），我说前者更好
，因为dequeue的时候，只要leftstack不空，是不需要shiftstack的。
2.// Input -> "I have 36 books, 40 pens2, and 1 notebook."
// Output -> "I evah 36 skoob, 40 2snep, dna 1 koobeton."
如果是数字，原样输出，如果不是，那么倒序。
挺简单的题目... 阅读全帖 |
|
A*******e
发帖数: 2419 | 9 假设空队列时，先有dequeue执行，发现队列为空，等待。
这时来一个enqueue，调用notifyAll()之后，插入新对象之前，dequeue已经唤醒，试
图去删除，这时队列仍然可能是空啊。
public class BlockingQueue {
private List queue = new LinkedList();
private int limit = 10;
public BlockingQueue(int limit){
this.limit = limit;
}
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);
}
publi... 阅读全帖 |
|
c********t
发帖数: 5706 | 10 这个是完整测试代码，有兴趣的可以跑跑试试
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
public class BlockingQueue {
private List queue;
private int limit;
public BlockingQueue(int pLimit) {
this.limit = pLimit;
queue = new LinkedList();
}
public synchronized void enqueue(T item) throws InterruptedException {
try {
if (this.queue.size() == this.limit)
System.out.println("wait, enque " + item);
... 阅读全帖 |
|
L*********3
发帖数: 216 | 11 都是现金交易有什么旁证？一个说往pipe里enqueue了，一个说从pipe里dequeue了，
dequeue出来的和enqueue进去的完全一样，没有data corruption，很简单的protocol
，于是乎书记就有口难辩了。 |
|
s*****n
发帖数: 5488 | 12 我的方法：
数据结构：滑动window array, size_t k as circular buffer.
int max, int maxindex,
int secondaftermax, int second index,
// prepossing:
compute max, maxindex
for all data after max in windows
compute secondafteramx, get the index.
if maxindex is the last one,
secondaftermax is -1, secondinex is -1;
void EnWindow(int x)
{
enqueue(x);
if (x >= max)
update max, maxindex;
if ( x < max && x >= secondaftermax)
update secondaftermax, secondindex;
}
void Dewindow()
{
if... 阅读全帖 |
|
j*****u
发帖数: 1133 | 13 写了个非递归的
void SetSibling(TreeNode root)
{
if (root == null) throw ArgumentNullException("root");
Queue queue = new Queue();
TreeNode splitter = null; // indicates layer ends
queue.Enqueue(root); queue.Enqueue(splitter);
while (queue.Count > 1)
{
TreeNode node = queue.Dequeue();
foreach (TreeNode child in node.Children)
queue.Enqueue(child);
if (queue.Peek() != splitter)
node.Next = queue.Peek(); // set sibling
... 阅读全帖 |
|
f*********i
发帖数: 197 | 14 sorry,头昏了，是DP。
queue的那道题目就是implement enqueue 和 dequeue，不是priority queue。
tricky在判断异常，比如size＝0的时候dequeue抛异常和size full的时候抛提示，还
有头尾结点的指针位置变换，要考虑蛮多细节的 |
|
b***e
发帖数: 15201 | 15 1：
给两个stack，怎样建个queue,写出dequeue,enqueue.
这个简单，写完了，问是否thread safe，如果不safe怎样处理。
public interface IStack {
public void push(E e);
public E pop();
public Boolean isEmpty();
}
public interface IQueue {
public void enqueue(E e);
public E dequeue();
}
public class Queue implements IQueue {}
2：
给一个2维数组，里面是0,1值表示不相邻或者相邻
问题：
查找这个数组里面所有的connected components |
|
a****a
发帖数: 186 | 16 随便画了个简单的DAG， 如下图，
如果用DFS的话，假如我用一个queue,
enqueue root, 然check队列是否为空，不为空就enqueue children(neighbors),
在dequeue node 2的时候，enqueue node 4&5,
在dequeue node 3的时候，不应该enqueue node 5，对吧？因为5已经被访问了，如何
记录这个Node是不是已经被访问过呢（不改动原本的DS）。
想到一个方法是可以用一个数组保存所有被访问过的Node地址，每次进队看是不是在这
个数组里。
如果用递归来做应该也是可行的吧。
class Node{
public:
int value;
vector neighbors;
};
vector visited;
bool isNodeVisited(Node *n)
{
vector::iterator it;
it = find(visited.begin(), visited.end(), n);
return it !=... 阅读全帖 |
|
v*******a
发帖数: 14 | 17 【 以下文字转载自 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... 阅读全帖 |
|
E*******0
发帖数: 465 | 18 class AC
{
int typeName;
int ID;
int size;
}
class ACControl
{
private:
MyQueue PassengerQueue;
MyQueue CargoQueue;
Public:
ACControl;//constructor
void Enqueue(AC ac);
AC Dequeue();
}
class MyQueue
{
private:
AC* smallPointer;
AC* top;
AC* last;
public:
void Enqueue(AC ac);
AC Dequeue();
bool IsEmpty();
} |
|
t********y
发帖数: 14 | 19 adding a null to the end of each level can be helpful. following is printing
out each level. making link list is just same, creating a new list each
time a null is Dequeued. Tail null is taken care automatically.
public void PrintOutLevel(TreeNode node)
{
// null,check.....
Queue q = new Queue();
q.Enqueue(node);
q.Enqueue(null); // This is the tail of the first levle.
while (!(q.Count == 0))
... 阅读全帖 |
|
b****p
发帖数: 216 | 20 c# 写了一个。。
public List mergeintervals(List> a)
{
List r = new List();
int k = a.Count;
if (k == 0)
return r;
PriorityQueue h = new PriorityQueue();
for (int i = 0; i < k; i++)
{
if (a[i].Count>0)
{
h.Enqueue(a[i][0]);
}
}
Interval currentintval=nul... 阅读全帖 |
|
s********u
发帖数: 1109 | 21 1.关于shiftstack，enqueue是push，O(1)操作；但是dequeue的时候，如果leftstack
不为空，那么需要把rightstack的东西全部shift到leftstack去，而不能只shift一个。
2.让我选的是，是否能够把dequeue用O（1）实现，那么也就是说，shiftstack放到
enqueue的时候操作，这样就行了。但这样的话总体来说其实并不划算，因为每次
enqueue都要shiftstack来清空rightstack；而原来那种操作方式，只有在leftstack空
的时候才需要这么做。
他问我的基本就是这些意思 |
|
d***n
发帖数: 832 | 22 贴个C#版本
public class BlockingQueue
{
private Queue m_queue = new Queue();
private int m_waitingConsumers = 0;
public int Count
{
get
{
lock (m_queue)
return m_queue.Count;
}
}
public void Enqueue(T item)
{
lock (m_queue)
{
m_queue.Enqueue(item);
if (m_waitingConsumers > 0)
Monitor.Pu... 阅读全帖 |
|
d***n
发帖数: 832 | 23 再来个更先进的, 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
... 阅读全帖 |
|
c******n
发帖数: 100 | 24 不能用dequeue,因为dequeue.get(i) 的复杂度是n, 用array就可以了。删除的时候就
像好虫说的作Swap
linked |
|
l******s
发帖数: 3045 | 25 好像BFS + Queue
共1680个解。
private static IEnumerable ThreeBuckets(){
Queue queue = new Queue();
for (int[,] tmp = new int[3, 3] { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 } };
tmp[2, 0] == 0; tmp = queue.Peek()[2, 0] != 0 ? queue.Peek() : queue.Dequeue
())
for (int i = 1; i < 10; i++)
if (!(i == tmp[0, 0] || i == tmp[0, 1] || i == tmp[0, 2] || i == tmp[1, 0] |
| i == tmp[1, 1] || i == tmp[1, 2]))
for (int j = i + 1; j < 10; j++)
if (!(j == tmp[0, 0] || j == tmp[0, 1] || j == tmp[... 阅读全帖 |
|
N*****a
发帖数: 17 | 26 来自主题: JobHunting版 - g 家面经 对啊，没怎么复习concurrency的题，感觉挺难的。
请问楼主，consumer为什么用reader lock，consumer里面有dequeue这个操作，更改了
queue的内容，这样岂不是可以好几个reader thread一起dequeue？就不thread safe了
吧。是不是应该直接在method上加synchronized？ |
|
l******s
发帖数: 3045 | 27 两个Queue也可以吧，Queue 和 Queue，保持两个Queue同步就行了
。
It's accepted by leetcode.
private IList allPath(TreeNode root){
Queue queue = new Queue();
Queue qStr = new Queue();
IList result = new List();
if(root == null) return result;
queue.Enqueue(root); qStr.Enqueue(root.val.ToString());
while(queue.Count != 0){
TreeNode cur = queue.Dequeue();
string curStr = qStr.Dequeue();
if(cur.le... 阅读全帖 |
|
k****r
发帖数: 807 | 28 lz 你最后的code有两个问题：
1. dequeue 中idx没有用。
2. enqueue dequeue在对queue操作前notify不对：
notify();
// }
this.queue.add(item); |
|
c********t
发帖数: 5706 | 29 1. dequeue 中idx没有用。
index是打印输出thread id用的。
2. enqueue dequeue在对queue操作前notify不对.
我理解顺序应该无所谓，因为唤醒的thread并不会马上执行，而是等这个thread结束后
才开始执行（ synchronized）.不知道对不对。 |
|
o****g
发帖数: 174 | 30 用的是这个wheel, 要先加载一个package scrapy.
https://github.com/LKI/wescraper
有如下错误：好像是没有得到cookie? 为什么?
[scrapy.utils.log] INFO: Scrapy 1.5.0 started (bot: scrapybot)
2018-01-23 17:51:22 [scrapy.utils.log] INFO: Versions: lxml 4.1.1.0, libxml2
2.9.7, cssselect 1.0.3, parsel 1.3.1, w3lib 1.18.0, Twisted 17.9.0, Python
2.7.13 |Anaconda 4.4.0 (64-bit)| (default, Dec 20 2016, 23:09:15) - [GCC 4.4
.7 20120313 (Red Hat 4.4.7-1)], pyOpenSSL 17.0.0 (OpenSSL 1.0.2l 25 May
2017), cryptography 1.8.1, Platform Linux-... 阅读全帖 |
|
a****a
发帖数: 5763 | 31 http://bbs.weiphone.com/read.php?tid=517864
Mac OS X 10.6即所谓的Snow Leopard操作系统已正式发售。一如既往，Apple产品
光鲜的外表下凝聚了太多艰辛的劳作。ArsTechnic的John Siracusa以其独特的、专业
的、全面的视角深入翔实地体验这款最新的操作系统。
Weiphone.com将对该综述进行翻译整理并独家连载。欢迎关注
Grand Central Dispatch
上一篇连载《并行难题：一封19年前的挑战书(连载11/23)》中，我们讨论了
并行编程(parallel programming)的问题，以及该问题所导致的另一个更为深远问题，
那就是：近一二十年以来，尽管计算机硬件的发展已经迈上了一个新的台阶，然而“软
件”层面的发展却裹足不前，最终成为了限制计算机性能的主要因素之一。
针对这一问题，Snow Leopard的应对方案是Grand Central Dispatch(GCD)。
GCD是刚刚发布的Snow Leopard的一项新特性... 阅读全帖 |
|
p****i
发帖数: 6135 | 32 背景其实是传统的producer， consumer case：
producers 会产生三种不同priority 的events，
consumers 必须1. 总是优先处理高priority的event， 2.同priority的events按先来
后到处理。
刚开始的设想是用priorityblockingqueue， 方便快捷
第一个concern是： priorityblockingqueue无法保证同priority的events能按先来后
到处理。
这个可以通过rewrite comparator解决
第二个concern比较大： priorityblockingqueue是用heap实现的， enqueue and
dequeue都是 log(n) 的操作,
对于我们的大数据量大约是不妥的
现在的想法是只好化简为繁作三个seperate FIFO queues， 分别对应high， medium，
low priority。
好处是dequeue， enqueue都是 O（1）了
坏处是似乎producers， comsumer之间的signalling只好我自己来做... 阅读全帖 |
|
v*******a
发帖数: 14 | 33 来自主题: Programming版 - 问个OO题 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 are not limited to having) the following properties:
AC type: Passenger or Cargo
AC size: Small or Large
The process which m... 阅读全帖 |
|
n*****t
发帖数: 22014 | 34 来自主题: Programming版 - 座席优化 再更正，出票的时候只做 enqueue，不做 dequeue。enqueue 简单，dequeue 还得先找
到对应的 queue 再搜索到这张票，开销大，宁可下次排到这张的时候再扔出去。 |
|
D****g
发帖数: 2860 | 35 * Imagine a binary tree (not necessarily full). Suppose we add two extra
fields (pointers) to every node. Traverse the tree and connect all nodes on
the same level with these two fields.
* Partition an array using a pivot value (this value does not necessarily
appear in the array). Prove the correctness of your code.
* Binary search an array. Make sure every detail and boundary conditions are
taken care of.
* Implement a queue with an array (enqueue and dequeue).
1. Upper limit on the queue si |
|
z****e
发帖数: 2024 | 36 来自主题: JobHunting版 - 一道面试题 Actually, this reminds me that there is another problem saying:
use two stacks to maintain a queue, for Dequeue() and Enqueue(a) operation
with amortize O(1). |
|
c*****y
发帖数: 90 | 37 来自主题: JobHunting版 - 一道面试题 对，就是每个node从queue里面dequeue出来后它的nextRight指向queue的peek。
我现在在想，能否有recursion的方法？想了下想不出来。 |
|
|
|
k***e
发帖数: 556 | 40 as the problems says, you only have const numbers that need to take care of
then just use idea similar to counting sort
by the way, i guess you are talking about priority queue.
please make problems clear.
e |
|
S**Y
发帖数: 136 | 41 yes. it is priority_queue(sated in the text)
can u elabrate it? thx.
of |
|
g*******y
发帖数: 1930 | 42 就是个脑筋急转弯或者文字游戏吧。。。
题目说constant number of priorities
你就假设这个constant number = 2，i.e.，只有两种priorities。。。 |
|
s********a
发帖数: 1447 | 43 用queue
要visit的从dequeue
fringe node enqueue
直到所有的都遍历完 |
|
|
l*******g
发帖数: 8 | 45 一个queue应该就可以了，我把code贴出来了。如果有错误的话，请指正。
printByLevel(Node *root)
{
Queue queue;
int currLevel = 1; /* total number of nodes on the current level */
int currPos = 0; /* current position on the current level */
int nextLevel = 0; /* total number of nodes on the next level */
queue.enqueue(root);
while(currLevel>0)
{
Node *curr = queue.dequeue();
printNode(curr);
if(curr->left){
queue.enqueue(curr->left);
nextL |
|
s*********t
发帖数: 1663 | 46 from OPNET, CODING，比较简单，一小时时间
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 pr
ocess 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 are not limited to having) the following properties
AC type: Passenger or Cargo
AC size: |
|
m*****g
发帖数: 226 | 47 前面贴过好象
for each work, maintain a queue
scan
if(doc[i]==word[j])
queue[j].push[doc[i]];
if( queue[0]...queue[i] all have 1 elem && queue[j] has 2 elem)
update smallestWindowSize;
dequeue queue[0]...queue[i] until every queue has only 1 elem.
endif
end scan. |
|
I**A
发帖数: 2345 | 48 pushstack: s1
popstack: s2
enqueue(0)
enqueue(1)
enqueue(2)
now s1 has 0,1,2
now. dequeue
我需要0对吧？
if s2 empty..
{
s2.push(s1.pop()); //2 in
s2.push(s1.pop()); //1 in
}
最后pop出我要的0
咦，好像是不用。。。 |
|
p******r
发帖数: 2999 | 49 应该是记录个数，dequeue了之后立马enqueue，n-1次之后得到第n个
好残忍啊，吐出来的东西得立马吃回去。。。 |
|
I**A
发帖数: 2345 | 50 你dequeue出来的object被enqueue之前存在哪儿？ |
|
