p******r
发帖数: 2999 | 1 。。。
q.enqueue(q.dequeue()); |
|
j**l
发帖数: 2911 | 2 这样就可以了：
enqueue root
enqueue '\n'
while queue is not empty
{
dequeue and set current node with the returned value
print current node
if current node is '\n' and queue is not empty
enqueue '\n'
else
enqueue all children of current node
} |
|
j**l
发帖数: 2911 | 3 这是下面这道题的特例吧？
请实现一个队列，要求enqueue, dequeue和GetMax都是O(1)时间。
只是随着窗口的滑动，队列每次删除一个元素，插入一个元素，始终维持长度k不变
由于队列可以用两个栈实现，又可归约为下面一道名题
请实现一个栈，要求push, pop和GetMin都是O(1)时间。
到O |
|
d******a
发帖数: 238 | 4 some of them might be easy to give out idea, but a little hard to write bug-
free code.
1 merge-sort without recursion
we should use loop to sovle it. we could use loop to get n/2 sorted
subarrays, then n/4 sorted arrays...I think we should be careful to consider
the boundary conditions.
2 Find whether one string is a subset of another string (not need to be
contiguous, but order should match).
use the idea of hash, > is a pair. e.g. "abcaeaf", "aaf"
a 0, 3, 5
b 1,
c 2,
e 4... 阅读全帖 |
|
P********l
发帖数: 452 | 5 O(n) algorithm:
public Integer[] getMaxInSlideWindow(Integer[] A, Integer w) {
// invalid input
if (A == null || w <= 0 || A.length - w + 1 <= 0)
return null;
Integer[] B = new Integer[A.length - w + 1];
// auxiliary queue that is sorted in descending order
List q = new LinkedList();
for (int i = 0; i < A.length; i++) {
// enqueue. Remove those smaller values
int data = A[i];
whi... 阅读全帖 |
|
P****a
发帖数: 864 | 6 60就够了，不我想的是队列
每秒收到的计数到temp, 下一秒开始前清空并push到queue并dequeue |
|
P****a
发帖数: 864 | 7 60就够了，不我想的是队列
每秒收到的计数到temp, 下一秒开始前清空并push到queue并dequeue |
|
w********r
发帖数: 6 | 8 可能我的问题没有问清楚,这个问题是要求用数据结构queue,用circular array来实现,
我想是用enqueue,dequeue吧.我就是想不出如何用circular array来实现.
这个问题不是用linked list来实现.
如何做? 谢谢各位. |
|
i***1
发帖数: 147 | 9 因为没有什么保密协议就直接粘贴了...
如果有人认为不妥 麻烦联系
1. Implement a thread-safe circular queue of integers of user-specified size using a simple array. Provide
routines to initialize(), enqueue() and dequeue() the queue.
The solution should include a set of test functions that verify the queue is thread-safe.
2. Implement an RAII wrapper class for Win32 handles. The class should be
able to accept a handle from any Win32 function that returns a handle (CreateFile,
CreateThread, etc.). The class should allow copyin... 阅读全帖 |
|
b*****n
发帖数: 482 | 10 Q1: it is similar to the one in CareerCup 150
Use two queues, q1 for incrementing factor of 2, q2 for incrementing
factor of 5. Below are the steps
1. init the queues.
q1: (1,0) which means 2^1*5^0.
q2: (0,1) which means 2^0*5^1.
2. Compare front elements from the two queues, and dequeue the smaller
one: (i,j). Put (i,j) in you output sequence. If num of elements in the
output sequence reaches N, break.
3. Enqueue (i, j+1) into q2, and if (i,j) is from q1, also enqueue (i+1,
j) into q1.
4. Go ba... 阅读全帖 |
|
z**z
发帖数: 222 | 11 queue for 1 question
YANGHUI(int n) {
1. Queue q; q.makeempty();
2. q.enqueue(1);q.enqueue(1);
3. int s = 0;
4. for(i=1;i<=n; i++) {
5. cout << endl;
6. q.enqueue(0);
7. for(int j = 1; j<=i+2; j++) {
8. int t = q.dequeue();
9. q.enqueue(s+t);
10. s = t;
11. if(j!=i+2) cout << s << " ";
}
}
} |
|
a********d
发帖数: 195 | 12 恩，确实是min stack一样，
void enqueue(Node myNode)
{
if(isGreaterThanPrevious(myqueue.peek(),myNode))
{
myNode.CurrnetMax=myNode.Data;
}
else
{
myNode.CurrnetMax=myqueue.peek().Data;
}
myqueue.enqueue(myNode);
}
//dequeue一个意思。 |
|
b******g
发帖数: 1721 | 13 相同是说不光结构相同，而且每个对应的value也相同。根据peking2 和 wwzz建议，我
给个全的，也是个大概，可能边角没有考虑。
int matchRoot(Tree t1, Tree t2)
{
Queue q1=new Queue();
q1.enqueue(t2);
int size=0;
while(q1.size()){
Tree tmp=q1.dequeue();
if(!match(t1,tmpTree)){
if(!tmp.left)
q1.enqueue(tmp.left);
if(!tmp.right)
q1.enqueue(tmp.right);
}else{
size=tmp.size();
}
}
return size;
}
match(Tree t1, Tree t2){
if(t1.value=t2.value)
... 阅读全帖 |
|
h****e
发帖数: 928 | 14 谢谢longway2008的支持。
flyinocean12，下面是书中的BFS算法，s是开始结点。
BFS(G, s)
1 for each vertex u in G.V - {s}
2 u.color = WHITE
3 u.d = INFINITY
4 u.parent = NIL
5 s.color = GRAY
6 s.d = 0
7 s.parent = NIL
8 Q = {};
9 ENQUEUE(Q, s)
10 while Q<>{}
11 u = DEQUEUE(Q)
12 for each v in G.Adj[u]
13 if v.color==WHITE
14 v.color = GRAY
15 v.d = u.d + 1
16 v.parent = u
17 ENQUEUE(Q,v)
18 u.color = BLACK
然后练习题是这么说的：
Ex 22.... 阅读全帖 |
|
f****0
发帖数: 151 | 15 用个queue？把数一个一个放进queue里，同时记录queue里面最长的递增序列的长度，
一旦发现有新的数列比之前的更长，就把之前的全部dequeue。这样最后一个数到了以
后，在queue头里刚开始存的递增数列就是最长数列 |
|
a********r
发帖数: 218 | 16 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... 阅读全帖 |
|
c***p
发帖数: 221 | 17 最近面了几个公司，经验说不上，教训有几条：
1. 一个on-site面试通常4-5个小时，越到后来越要坚持住。回顾最近的这几次on-site
，都是面到最后一个人的时候出的问题最多。一个建议，在面最后一个人之前，要求去
趟卫生间，趁机休息一下，喘口气。
2. coding的要求越来越高了。几乎就是要可以编译执行的那种。一定要注意细节。比
如函数的signature,变量的declaration。所以在做coding题的时候，就当做是在电脑
上输入，然后编译运行。对于C++程序，参数是传值还是传引用，需不需要const声明等。
3. 对于用C++语言，基本的stl container要熟悉。比如，vector, queue, stack,
dequeue, map。这样，在写算法的时候，可以集中精力整理思路，而不必为细节分心。
最近遇到的几个常考coding题：
1. LRU Cache
2. Hash Table的实现（定义hash function, 处理collision, 实现get, put）
3. 合并两个BST 为一个平衡的BST。 |
|
L*****n
发帖数: 15 | 18 "Implement a circular queue of integers of user-specified size using a
simple array. Provide routines to initialize(), enqueue() and dequeue() the
queue. Make it thread safe."
Using c++
怎么写比较好？多谢！ |
|
j*****o
发帖数: 394 | 19 用一个数组的话
用指针记录头和尾的位置
enqueue这么加： arr[ (tail++)%size ] = val
如果是dequeue 就是HEAD指针“右移” （也要用 %size).
弱问thread safe是啥概念。。不越界就行啦？
the |
|
E*******0
发帖数: 465 | 20 void MyQueue::Enqueue(AC* ac)
{
if (ac.size==1)//small
last->next=ac;
ac->previous=last;
last=∾
else
ac->previous=smallPointer;
ac->next=smallPointer->next;
smallPointer->next->previous=∾
smallPointer->next=∾
smallPointer=ac;
}
AC* MyQueue::Dequeue()
{
Ac* rst=top;
top=top->next;
return rst;
} |
|
|
s********o
发帖数: 861 | 22 用 BFS
static {
Queue queue;
queue.enqueue(root);
}
Node next() {
Node x = queue.dequeue();
if (x != null) {
for (Node c: x.children()) {
queue.enqueue(c);
}
}
return x;
} |
|
y**u
发帖数: 28 | 23 公司名就不说了，面试官要求实现一个queue,要求：
enqueue, dequeue, min, max, median 全部在o(1)。。。彻底败了。。。板上的各位
有没有什么想法啊？ |
|
l*****a
发帖数: 559 | 24 enqueue, dequeue, min, max都可以实现。
median要求O（1）有点强人所难了。 |
|
c********t
发帖数: 5706 | 25 if you need maintain heaps, how can dequeue and enqueue be O(1) time? |
|
C***y
发帖数: 2546 | 26 dequeue的时候你怎么从heap里做到O（1）删除？ |
|
e***s
发帖数: 799 | 27 你用array 的方法不太对，所以才要left shift all the elements. 如果你用两个变
量，一个是enqueue的位置，一个是dequeue的位置。就不用了。
add |
|
K*********n
发帖数: 2852 | 28 不要用recursion，用queue
Node cur = root;
q.enqueue(cur);
while(!q.isEmpty()){
cur = q.dequeue();
System.out.println(cur.data);
if (cur.left != null)
q.enqueue(cur.left);
if (crur.right != null)
q.enqueue(cur.right);
} |
|
K*********n
发帖数: 2852 | 29 对，这个问题如果需要in place的话，跟BFS主要的区别就是不能光dequeue，得知道de
queue出来的这个结点在哪层，是否需要新建linkedlist。怎么能知道？ |
|
K*********n
发帖数: 2852 | 30 不要用recursion，用queue
Node cur = root;
q.enqueue(cur);
while(!q.isEmpty()){
cur = q.dequeue();
System.out.println(cur.data);
if (cur.left != null)
q.enqueue(cur.left);
if (crur.right != null)
q.enqueue(cur.right);
} |
|
K*********n
发帖数: 2852 | 31 对，这个问题如果需要in place的话，跟BFS主要的区别就是不能光dequeue，得知道de
queue出来的这个结点在哪层，是否需要新建linkedlist。怎么能知道？ |
|
e***s
发帖数: 799 | 32 来自主题: JobHunting版 - G电面面经 我就不懂了，不就是BFS最后一个节点吗？
public static BTNode DeepestRightMostNode(BTNode root)
{
if (root == null)
return null;
Queue queue = new Queue();
queue.Enqueue(root);
BTNode temp = root;
while(queue.Count > 0)
{
temp = queue.Dequeue();
if(temp.Left != null)
queue.Enqueue(temp.Left);
if(temp.Right != null)
... 阅读全帖 |
|
v***n
发帖数: 5085 | 33 Food for thought...
Write me a function that receives three integer inputs for the lengths of
the sides of a triangle and returns one of four values to determine the
triangle type (scalene, isosceles, equilateral, error). Write test code for
the function assuming another developer coded the function.
Implement a circular queue of integers of user-specified size using a simple
array. Provide routines to initialize(), enqueue(), dequeue() and print()
the elements of the queue. If an item is added... 阅读全帖 |
|
Q*******e
发帖数: 939 | 34 int
queue_is_empty(struct queue_head *q) {
return (stack_is_empty(q->stackA) &&
stack_is_empty(q->stackB));
}
void
enqueue(struct queue_head *q, int value)
{
stack_push(&q->stackB, value);
}
int
dequeue(struct queue_head *q) {
if(queue_is_empty(q)) {
printf("Error: Empty queue\n");
abort();
}
if (stack_is_empty(q->stackA)) {
while(!stack_is_empty(q->stackB)) {
int tmp = stack_pop(&q->stackB);
stack_push(&q->stackA, tmp);
... 阅读全帖 |
|
j*****y
发帖数: 1071 | 35 来自主题: JobHunting版 - BB 电面 cong!
1. 没太弄明白，只知道前几个字母，那么整个 key是不知道的还是知道的？ 感觉
用 prefix tree ?
4, 用 queque 就可以了吧，最近访问了一个就 enqueue, 然后把第一个 dequeue
in |
|
j*****y
发帖数: 1071 | 36 还有一个问题， 对于 queue 里面的操作， 能做到对于 slot 来锁定吗？ 感觉
要复杂些， 因为 dequeue 和 enqueue 有依赖关系. |
|
c********r
发帖数: 286 | 37 Pthread 没有，有一个thread的
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.isEmpty()){
notifyAll();
}
this.queue.add(item);
}
public synchronized Object dequeue() throws InterruptedException {
while(this.queue.isEmpty... 阅读全帖 |
|
y***u
发帖数: 205 | 38 这样head和tail的节点如果相同是不是有问题？新head指向旧tail，但是旧tail已经
dequeue了。
感觉还是用emptyslot和fullslot两个semaphore，和整个Q的mutex。返回size操作不涉
及Q里面数据更新，所以就是一个snapshot吧，不用加mutex吧？ |
|
p*****2
发帖数: 21240 | 39 def solve(n:Int):Int={
val isPow=(n:Int)=>{var m=n;while(m%2==0) m/=2;m==1}
val visited=new Array[Boolean](n+1)
val queue=new Queue[Int]
queue+=n
visited(n)=true
var count=1
var distance=0
while(!queue.isEmpty){
while(count>0){
val curr=queue.dequeue
if(curr==0) return distance
for(i<-0 until n if !visited(i) && isPow((curr-i).abs)){
queue+=i... 阅读全帖 |
|
L*********r
发帖数: 9 | 40 public class CircularQueue {
private int size = 0;
private int count = 0;
private int head = 0;
private int tail = 0;
private int[] arr;
public CircularQueue(int size) {
this.size = size;
arr = new int[size];
}
public void enqueue(int n) {
arr[tail] = n;
tail = (tail + 1) % size;
if ( count == size )
head = ( head + 1 ) % size;
else
count++;
}
public i... 阅读全帖 |
|
p*****2
发帖数: 21240 | 41 第一题
def solve(mat:Array[Array[Int]]):Unit={
val n=mat.length
val m=mat(0).length
val v=Array.ofDim[Boolean](n,m)
def check(i:Int, j:Int):Unit={
val isOK=(x:Int,y:Int)=>{
x>=0 && x=0 && y
}
var fill=true
if(isOK(i,j)){
val set=collection.mutable.Set[Int]()
val queue=collection.mutable.Queue[Int]()
queue+=i... 阅读全帖 |
|
e***s
发帖数: 799 | 42 问个很弱的问题,blocking queue不是就已经thread-safe吗? 怎么实现thread-safe
blocking queue?
找到下面JAVA代码,好像很标准的样子.
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);
}
public syn... 阅读全帖 |
|
e***s
发帖数: 799 | 43 问个很弱的问题,blocking queue不是就已经thread-safe吗? 怎么实现thread-safe
blocking queue?
找到下面JAVA代码,好像很标准的样子.
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);
}
public syn... 阅读全帖 |
|
p*****2
发帖数: 21240 | 44 我写了一个。看看有没有问题？
import collection.mutable.{Map, Queue}
object test2 extends App {
val Array(n,k)=readLine.split(" ").map(_.toInt)
val start=readLine.split(" ").map(_.toInt-1).mkString(" ") //pegs and
discs start from 0
val end=readLine.split(" ").map(_.toInt-1).mkString(" ")
val queue=new Queue[String]()
val map=Map[String,String]()
var distance=0
var count=1
queue+=end
map(end)=null
while(count>0){
distance+=1
while(count>0){
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 45 我写了一个。看看有没有问题？
import collection.mutable.{Map, Queue}
object test2 extends App {
val Array(n,k)=readLine.split(" ").map(_.toInt)
val start=readLine.split(" ").map(_.toInt-1).mkString(" ") //pegs and
discs start from 0
val end=readLine.split(" ").map(_.toInt-1).mkString(" ")
val queue=new Queue[String]()
val map=Map[String,String]()
var distance=0
var count=1
queue+=end
map(end)=null
while(count>0){
distance+=1
while(count>0){
... 阅读全帖 |
|
m*****n
发帖数: 204 | 46 原题见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 | 47 原题见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下面再... 阅读全帖 |
|
d****n
发帖数: 233 | 48 void MinimumWindowCoverInOrder(int[] A, int[] B, out int start, out int min)
{
Dictionary> bPosInAMap = new Dictionary>(
);
Queue[] bPosInA = new Queue[B.Length];
start = -1;
min = Int32.MaxValue;
for (int i = 0; i < B.Length; ++i) {
if (!bPosInAMap.ContainsKey(B[i]))
bPosInAMap.Add(B[i], new Queue());
}
for (int i = 0; i < A.Length; ++i) {
if (bPosInAMap.ContainsKey(A[i]))
bPosInAMa... 阅读全帖 |
|
l***n
发帖数: 89 | 49 基本idea我觉得lz肯定对的。但是每次enqueue就shiftstack好像会有错啊。
比如
enqueue(1), enqueue(2), enqueue(3), 每次都shift的话，那么leftstack里面是1，2
，3. 没问题
然后dequeue（）， 那么1出来。剩下2，3.没问题
然后再enqueue（4）。shiftstack之后，leftstack就是4, 2, 3。这样顺序就不对了。
leftstack
个。 |
|
l******6
发帖数: 340 | 50 1. 2 max stack
2. use dequeue to store idx , pop element from front if out of window and
pop element from back if it is smaller than the most recent one. The front
element will always be the max |
|
