l******s
发帖数: 3045 | 1 两个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... 阅读全帖 |
|
c****t
发帖数: 19049 | 2 THE GHASTLY ORDEAL OF TIMOTHY CAVENDISH
One bright dusk, four, five, no, my God, six summers ago, I strolled along a
Greenwich
avenue of mature chestnuts and mock oranges in a state of grace. Those
Regency residences
number among London’s costliest properties, but should you ever inherit one
, dear Reader, sell
it, don’t live in it. Houses like these secrete some dark sorcery that
transforms their owners into
fruitcakes. One such victim, an ex-chief of Rhodesian police, had, on the
evening in qu... 阅读全帖 |
|
j*****u
发帖数: 1133 | 3 写了个非递归的
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
... 阅读全帖 |
|
s*x
发帖数: 3328 | 4 保存一个标记在queue里边，初始的时候是root，标记。以后每次读出标记，都把标记
再扔回去，同时换行。比如你前面的那个例子
1
2 3
4 5
queue 的变化就是：
| 1 queue |
1 | queue 2 3 |
1 nl | 2 3 queue |
1 nl 2 | 3 queue 4 5 |
1 nl 2 3 | queue 4 5 |
1 nl 2 3 nl | 4 5 queue |
1 nl 2 3 nl 4 | 5 queue |
1 nl 2 3 nl 4 5 | queue |
1 nl 2 3 nl 4 5 nl | queue |
fin |
|
z********i
发帖数: 568 | 5 queue and stack are different for min: (1) min of queue is dynamic,
depending on futher insertion of numbers, while (2) min of stack is "static"
--is determined by current numbers in stack.
For example：both queue and stack have numbers 10 20 30 40. Then the min of
both queue and stack are 10. However，after 5 is inserted, the min of the
queue is 5(min of 10 20 30 40 5), while the min of the stack is still 10(min
of 10, 20, 30, 40)
Now let look at one example for min using auxiliary stack to imple... 阅读全帖 |
|
b****z
发帖数: 176 | 6 代码如下：
基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
recover path。感觉没有任何冗余计算啊！！！为什么过不了？
谢谢各位！！
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> res = new ArrayList>();
Set visited = new HashSet();
... 阅读全帖 |
|
b****z
发帖数: 176 | 7 代码如下：
基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
recover path。感觉没有任何冗余计算啊！！！为什么过不了？
谢谢各位！！
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> res = new ArrayList>();
Set visited = new HashSet();
... 阅读全帖 |
|
a**********0
发帖数: 422 | 8 题目很简单 思路就是 level order traverse 其间每一层除了最后一个node 其他的
node的next都指向本层的下一个 最后一个node的next指向null
不过老过不了OJ 报错 而且我自己在eclipse上跑了一下 发现自己跑的结果和报错的情
况不一样 难道是oj错了
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if(root == null)
return;
LinkedList que... 阅读全帖 |
|
h**********d
发帖数: 4313 | 9 1.如果是full tree，可以用递归
2.如果不是full tree，笨办法用level-order traversal遍历，同时把当前节点next指
向queue.peek(),复杂度O(N)
写个java版本
void populate(TreeNode root){
if(root == null)return;
Queue queue = new Queue();
queue.put(root);
Node node;
int thisLevel = 1; int nextLevel = 0;
while(!queue.isEmpty()){
node = queue.pop();
thisLevel--;
if(thisLevel != 0){
node.setNextRight(queue.peek());
}
if(node.getLeft() != null){
queue.put(node.getLeft());
nextLe... 阅读全帖 |
|
g**********y
发帖数: 14569 | 10 就是简单的BFS, 运行很快，对N=25, 16ms。f(19)=299, f(25)=899
public class MonkeyWalk {
public final static void main(String[] args) {
new MonkeyWalk().run(25);
}
private void run(int N) {
ArrayDeque queue = new ArrayDeque();
queue.add(new Point(0, 0));
HashSet visited = new HashSet();
visited.add("0 0");
while (!queue.isEmpty()) {
Point p = queue.pop();
visit(p.x+1, p.y, queue, visite... 阅读全帖 |
|
c*****a
发帖数: 808 | 11 怎么优化space,有报错 Run Status: Memory Limit Exceeded
本地IDE倒能跑
public class Solution {
public ArrayList> zigzagLevelOrder(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> res = new ArrayList
>();
Queue queue = new LinkedList();
queue.offer(root);
queue.offer(null);
ArrayList row = new ArrayList();... 阅读全帖 |
|
y**x
发帖数: 67 | 12 official offer 出来了，实在一般。可能我的级别很低吧,entry level，“associate
” SE。有牛人指点一下怎么negotiate啊，是不是太少了？78k + 6280/year bonus +
1000share/4years。不知道这种转正式的software engineer要多久呢？好了，以下面
经，反正也没签什么NDA，我一股脑全贡献出来啦：
第一次onsite screen。不知为何没有phone screen，可能因为我住的近，他们直接叫
我过去了。一个小时一个白哥。问了how to delete a node from binary search tree
。CLRS上直接有解法。白哥答案要求的很笼统，写个psuedo code就pass了。连找
successor node的具体实现都不用写出来。后来又问不用mutex怎么实现share data
between threads。我说GPU里面有一个东西叫thread synchronizer （我master学位做
了些CUDA编程），白哥没理解，说他会用个queue把thread都qu... 阅读全帖 |
|
p*****2
发帖数: 21240 | 13 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
p*****2
发帖数: 21240 | 14 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
l******s
发帖数: 3045 | 15 好像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[... 阅读全帖 |
|
c********t
发帖数: 5706 | 16 这个是完整测试代码，有兴趣的可以跑跑试试
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);
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 17 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
... 阅读全帖 |
|
|
e***s
发帖数: 799 | 19 问个很弱的问题,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 | 20 问个很弱的问题,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... 阅读全帖 |
|
z*******3
发帖数: 13709 | 21 这是新的代码
建 route 的时候，不从字典里面找，而是挨个替换字符串的char，换成其他char，组
建成新字符串，然后再去看字典里有没有，有的话，放到set里去，再把set放到map里
，每个pair表示从key string出发，能够转换的点的集合
然后从start开始找，用linkedlist，不用queue，queue是二叉树，效率低，用
linkedlist快，bfs都用linkedlist，先进先出，linkedlist的pollfirst效率高
然后建立一个类，node，这个node记录当前的string，以及上一个string，还有当前
路径长度
然后方法主体，每次把当前string对应的点取出来，然后看能走到那些点，挨个对比这
些点，看是不是end string，如果是，则表示找到，那就记录当前长度，因为还有可能
有相同长度的解，然后继续，如果不是end string，则查找visitedmap，看是否访问过
，如果访问过，比较当前路径长度跟上次访问的长度，如果上次访问的长度更短，则把
set里面这个node给移除，要不然会产生死循环，这里还要避开并发修改的问题，... 阅读全帖 |
|
w********s
发帖数: 1570 | 22 第三题：
struct Pair
{
Pair(int idx, int v)
{
index = idx;
value = v;
}
int index;
int value;
};
std::deque queue;
void enque(int idx, int x, int w)
{
if (!queue.empty() && queue.front().index <= idx - w)
{
queue.pop_front();
}
while(!queue.empty() && queue.back().value > x)
{
queue.pop_back();
}
queue.push_back(Pair(idx, x));
}
int get_min()
{
return queue.front().value;
}
std::vector min_window(int* arra... 阅读全帖 |
|
a**********0
发帖数: 422 | 23 为什么一定要用DFS 不是类似surrounded reigions 吗 可以用 BFS
只不过要设一个variable用于记录cluster的数目
而且BFS过后的要label一下表示不能继续使用 我试着贴一下代码
private void bfs(char[][] board, int i, int j) {
int row = board.length;
int col = board[0].length;
ArrayList queue = new ArrayList();
queue.add(i * col + j);
board[i][j] = 'P';
while (!queue.isEmpty()) {
int cur = queue.get(0);
queue.remove(0);
int x = cur / col;... 阅读全帖 |
|
a**********0
发帖数: 422 | 24 为什么一定要用DFS 不是类似surrounded reigions 吗 可以用 BFS
只不过要设一个variable用于记录cluster的数目
而且BFS过后的要label一下表示不能继续使用 我试着贴一下代码
private void bfs(char[][] board, int i, int j) {
int row = board.length;
int col = board[0].length;
ArrayList queue = new ArrayList();
queue.add(i * col + j);
board[i][j] = 'P';
while (!queue.isEmpty()) {
int cur = queue.get(0);
queue.remove(0);
int x = cur / col;... 阅读全帖 |
|
m**********e
发帖数: 22 | 25 我来贡献一个用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 ... 阅读全帖 |
|
发帖数: 1 | 26 没必要那么复杂。用一个priority queue, element class implements comparable.
consumer:
每个consumer进来，如果blocking queue里面没有东西，创建一个priority queue的
element,然后加进priority queue, 这个consumer thread就wait on这个element。
producer:
每个producer进来，dequque priority queue，wakeup thread，直到priority queue
empty或者blocking queue empty。
以上步骤synchronize on priority queue或者blocking queue都行。 |
|
k***s
发帖数: 277 | 27 是转载，这个链接中海油很多评论
http://www.ccthere.net/thread/3798488
是西西河中的大鱼 布老虎 写的
（这是另一篇相关的介绍，属于业内人士写的 http://www.ccthere.net/thread/3793728)
请各位大牛点评一下。
（不知道如何排版，大家将就一下）
为了避免铁道部把这个系统再次搞成世界级的笑话，那我就免费给他们大概地，简单地
设计一个每秒千万级响应的系统吧。
首先，实际的做法是eventual consistency,而不是immediate consistency。全世界最
大的电商Amazon,就是eventual consistency的老祖宗。有的同学提出async
processing,算是摸着点儿边了。IBM之流肯定会忽悠你去搞一个实时交易系统，然后通
过系统硬件升级狠宰你一刀。注意，这就一个人民群众买车票的系统，我草，别把自己
当NYSE了。
其次，绝对不能和其他系统互联。高峰时间的流量未必能crash铁道部的这套系统，但
是一定会搞死工农中建的交易支付系统。简单的解决方法就是全国人民用身份证号登陆
，事先... 阅读全帖 |
|
S*********t
发帖数: 271 | 28 http://www.smh.com.au/digital-life/mobiles/student-in-tears-aft
Student in tears after being kicked out of iPhone 6 queue
A young woman was in tears after police kicked her out of the queue to Apple
's flagship Sydney store before she was able to buy the new iPhone 6.
Anna, a 24-year-old international student from China, was ordered by police
around 10am to leave the George St area for six hours or risk being arrested
, after they asked her multiple times to stay put in the queue.
Two models of ... 阅读全帖 |
|
m*****g
发帖数: 226 | 29 前面贴过好象
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. |
|
s*****n
发帖数: 162 | 30 1.from top
Use two queues q1 and q2. Get a node from the first queue, print it, and
then push its children into the second queue.When the first queue is empty,
get nodes from the second queue and push their children into the first queue
, and so on...
2. from bottom
Use two queue q1 and q2, and one stack s1. The stack is used to store nodes.
When all nodes are visited, get nodes from the stack and print. Similarly
to the above, except that when you get a node from one queue, first push its
right |
|
d*****t
发帖数: 41 | 31 这个可以把给定的n个单词先放到hash table里。
然后从文章开始，每扫一个单词到hash table里找，如果在就把单词和位置放到queue
里，一直到这n个单词都在queue里（有的单词可能出现多次），记下此时cover
distance。这之后每次往queue里加单词的时候，如果检查queue的前端，如果是同一个
单词，就pop。每次pop之后从queue前往后扫描一直扫到queue里只出现一次的元素，把
前面的删除，确保queue里不会所有的单词都出现2遍，同时更新cover distance,一直
到扫完text
貌似用这种方法是，amortized O（n）,但是更新queue导致不能保证O（n）
呼唤更好的办法~ |
|
p*****2
发帖数: 21240 | 32 写了一个BFS的。
class Node
{
int value;
Node left;
Node right;
public Node(int v)
{
value = v;
}
}
class Ele
{
int min;
int max;
Node ref;
public Ele(int _min, int _max, Node _ref)
{
min = _min;
max = _max;
ref = _ref;
}
}
Node convert(ArrayList> tree)
{
Queue queue = new LinkedList();
... 阅读全帖 |
|
e***s
发帖数: 799 | 33 来自主题: 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)
... 阅读全帖 |
|
w*******s
发帖数: 138 | 34 贴一个相对简洁点的：
void push(vector& q, TreeNode* node) {
if (node)
q.push_back(node);
}
vector > zigzagLevelOrder(TreeNode *root) {
vector > results;
vector queue[2];
int q = 0;
push(queue[0], root);
while (!queue[q].empty()) {
results.push_back(vector());
for (int i = queue[q].size() - 1; i >= 0; --i) {
TreeNode*& node = queue[q][i];
... 阅读全帖 |
|
m********o
发帖数: 26 | 35 帮朋友转一下面经：
不是牛人，也没有遇到牛人那么难的面试。
4个多月前面的，整理过几个国人论坛半年内的G面经，周围也有不少人面，感觉还是比
百分之七八十的面经难，擦。
之前准备了一些最近常考的G家独有题，结果一个都没碰到。。。也没碰到过leetcode
，CC150原题。之前也看了不少杂书和advanced topic， 花了不少功夫准备，不过因为
其他事情中断了复习，最后突击了一下，这点还是希望大家引以为戒。
也许是大家都刷题bar高了，基本上全是算法而且要求写code且量不小，所有题都要推
到optimal解法， 至少有三个面试官没有循循善诱，而是赤裸裸的不到最优解不让写
code外加鄙视。后来自己从最优解回头看所有题目，各种呵呵。
面经只包括主要的题目，面试前后扯淡神聊的都没记录在内。我的表现也自然有好有坏
, 面试官看上去都很nice，可惜题目摆在那里，我水平不够，想放水都难。我简历是越
来越挫，G家还这样招待我教我做人，水平确实有限就不高攀了，自己回去闭关反省了
，希望能帮到大家。
电面1：
expr ::= int | ‘(‘ op expr… ‘)’;
op ::= ‘+... 阅读全帖 |
|
x*****0
发帖数: 452 | 36 Assume in a system, users will register a callback function with system and
that callback function will be called when an event is triggered
but if the event is already triggered, the user will synchronously call
the callback function
For example
suppose user i registers cb i at time Ti,
and the event happens at time Te
and assume that T1 < T2 < T3 <...< Tm < Te < Tm+1 < ... < Tn
at time Te, cb1..cbm will be called
cbm+1 .. cbn will be called synchronously
impleme... 阅读全帖 |
|
m******n
发帖数: 51 | 37 Total 4 questions.
--------------------------------------------------------------
Question 1:
1. What is the runtime complexity for the code below?
2. What is the space complexity for the code below?
Queue queue = new LinkedList() ;
public void myMethod(TreeNode root) {
if (root == null)
return;
queue.clear();
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.remove();
if(node.left != null) queue.add(node.left);... 阅读全帖 |
|
l******s
发帖数: 3045 | 38 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... 阅读全帖 |
|
k****r
发帖数: 807 | 39 good idea!!!
You mean the consumer could decide to process the first Queue or the second
Queue, right?
What I was saying is to define producer and consumer with this priorityQueue
. Like:
class Producer implements Runnable {
private BlockingQueue bq = null;
public Producer(BlockingQueue queue) {
this.setBlockingQueue(queue);
}
public void run() {
....
}
}
class Consumer implements Runnable {
protected BlockingQueue queue = null;
public Consumer(Blockin... 阅读全帖 |
|
发帖数: 1 | 40 谢谢鼓励！ 真不是什么大牛，只是刷题还算认真，又运气好碰到面经题而已
我准备的时候看到的面经题是，给一个string，重排，使每个字母之间间隔至少一个其
他字母，例如"aabbcc"，可以返回"abacbc"。我面到的题是一个string改成了一堆
string，间隔1个改成了间隔n个
对于原面经题，网上有不少讨论，在一亩三分地里，我觉得对的做法大概就是先统计次
数，如果一个字符出现超过1半，则无法重排
然后，也是用一个maxheap，但是现在不用queue，改成用一个temp变量，temp变量每隔
一轮才再放回heap中，其实也差不多就是size为1的queue
回到我面的那个题，如果要说证明的话，我也不会严格的证明。我的理解是这样： 用
堆是可选的，其实你每一趟都是随便选一个当前还可用的string就可以，用堆是保证了
最少的循环次数。但是queue是必须的。这题唯一的要求，就是每个string中间间隔n个
其他string，用queue可以保证这一点，因为只有queue的size >= n，才开始向外Pop。
当然是有可能heap已经为空，但是queue还不为空的情况存在的，但是... 阅读全帖 |
|
o******h
发帖数: 1142 | 41 public class Solution {
List> results;
List list;
Map> map;
public List> findLadders(String start, String end, Set<
String> dict) {
results= new ArrayList>();
if (dict.size() == 0)
return results;
int curr=1,next=0;
boolean found=false;
list = new LinkedList();
map = new HashMap阅读全帖 |
|
S*******C
发帖数: 822 | 42 import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
public class LRUCache {
private final int capacity;
private ConcurrentLinkedQueue queue;
private ConcurrentHashMap map;
public LRUCache(final int capacity) {
this.capacity = capacity;
this.queue = new ConcurrentLinkedQueue();
this.map = new ConcurrentHashMap(capacity);
}
//Check whether the items exists in the cache. Returns n... 阅读全帖 |
|
发帖数: 1 | 43 同是java小白，简单写了一下，供参考。希望楼主是萌妹纸。。嘿嘿。
预祝面试成功。
public List getOldestSisters() {
List ret = new LinkedList<>();
PriorityQueue pq = new PriorityQueue(1, (a, b) -> a.
age - b.age);
Set visitedParents = new HashSet<>();
Queue queue = new LinkedList<>();
if (father != null) queue.offer(father);
if (mother != null) queue.offer(mother);
while (!queue.isEmpty()) {
Person p = queue.poll();
... 阅读全帖 |
|
z**r
发帖数: 17771 | 44 这个QoS要说具体点比较复杂，现在这些家用router，顶多也就是做些非常基本的，不
同型号估计能支持的相差挺多。
不过上面跑的应用都差不多。一般家里的high speed internet是非对称带宽，上行一
般都很小，看你用的什么service，如果最普通的dsl，可能上行只有几百kbps，这种情
况下对这种p2p的应用就要小心，尤其家里有其他应用比如voip等其他对实时性要求较
高的应用，很容易受到影响。
QoS分很多种，基本有4个主要components，classification, marking, policing, and
queueing, 一般家用的都能支持一些很基本的classification和queueing，但是对于
queueing里面也就支持个class based queue。queueing的特点之一有点像你说的如果
没有congestion，就不会起作用，但也不是完全没有作用，要看具体的traffic和设备
能支持的feature，以及设备本身能提供的queue depth等。
再加上video packet的特性就是基本上都是接近MTU的大包，而... 阅读全帖 |
|
w**z
发帖数: 8232 | 45 https://aws.amazon.com/message/5467D2/?utm_content=buffere5a1e&utm_medium=
social&utm_source=linkedin.com&utm_campaign=bufferSummary of the Amazon
DynamoDB Service Disruption and Related Impacts in the US-East Region
Early Sunday morning, September 20, we had a DynamoDB service event in the
US-East Region that impacted DynamoDB customers in US-East, as well as some
other services in the region. The following are some additional details on
the root cause, subsequent impact to other AWS services t... 阅读全帖 |
|
i**********e
发帖数: 1145 | 46 这题用两个 queue 就行了。
一个 queue 来 maintain minimums，另一个 queue 来 push_rear 和 pop_front.
每次 push 一个新元素的时候，检查 min queue 的后面的值是否大于新值。如果是的
话，就一直 pop，直到后边值小于或者等于新值（或者 min queue 为空）。
每次 pop_front 的时候，就检查现在 pop 的元素是否与 current min 相等。如果是
的话，就从 queue 和 min queue 同时 pop.
其实这是 google 经典题 finding sliding window minimum/maximum 的变种。
因为同样一个 data structure 就直接能应用于 finding sliding window minimum，
并且得到 O(N) 的复杂度。
Reference:
http://www.ihas1337code.com/2010/11/stack-that-supports-push-po
http://www.ihas1337code.com/201... 阅读全帖 |
|
z********i
发帖数: 568 | 47 The following algorithm for queue with max is correct to me:
http://www.sureinterview.com/wiki/Shwqst/903001
idea:
1 用数据队列保存所有数据X[0]，X[1]，...
2 用辅助队列保存数据中的X[i1],X[i2],etc. such that
2.1 X[i1]>=X[i2]>=...。
2.2 X[i1]是从X[i1]开始最大的数。
3 enque的时候,删除辅助队列中比要插入的数据小（<）的数据。
4 deque的时候，删除数据队列的第一个数据。同时，如果辅助队列的第一个数据等于数据队列的第一个数据，删除辅助队列的第一个数据。
5 max就是辅助队列的第一个数据
例子一。
数据队列：6 5 4。
辅助队列：6 5 4。
1) max: 辅助队列的第一个数据6.
2) deque：
数据队列：5 4。
辅助队列：5 4
max: 5
3) deque:
数据队列：4。
辅助队列：4
max: 4
例子二。
数据队列：4 5 6。
辅助队列：6。
1) max: 辅助... 阅读全帖 |
|
j********e
发帖数: 1192 | 48 写了个使用O(1)memory, O(logN * logN) (N是tree的size)的程序。
类似于binary search的算法，测试代码也在下面，应该没有大bug。
先获得树的高度h，然后比较h和root->right子树的高度+1,如果相同，
说明树最后一个节点在root->right，否则最后一个节点在root->left的子树。
#include
#include
#include
#include
using namespace std;
class Node {
private:
Node *left;
Node *right;
int value;
public:
Node() {
left = right = NULL;
value = 0;
}
Node(int v) {
left = right = NULL;
value = v;
}
int Height(Node *node) {
int h... 阅读全帖
|
|
j********e
发帖数: 1192 | 49 正好做了这道题。
其实就是recursive，不过先把candidate排序，然后确保输出唯一结果
（例如一旦使用了3，以后就不能再使用比3小的数）
class Solution {
public:
vector > results;
void combinationSum(int sum, int target, const vector &cand,
int index, vector &queue) {
if(sum == target) {
results.push_back(queue);
return;
}
for(int i = index; i
if(sum + cand[... 阅读全帖 |
|
l****c
发帖数: 782 | 50 新手我试一下哈
typedef struct Node{
int value;
int level;
struct Node *left;
struct Node *right;
} node;
void_print(int LEVEL)
{
node *root;
if (LEVEL==0) return;
node *tmp = root;
queue.push(tmp);
stack.push(tmp);
while (queue.front()->level < LEVEL) {
int tmp_level = queue.front()->level;
while(queue.front()->level==tmp_level) {
node *tmp = queue.pop_front();
queue.push_back(tmp->left);
queue.push_back(tmp->right);
stack.push_back(tmp->left);
stack.push_back(tmp->right);
}
}
while(!stack.is... 阅读全帖 |
|
