z*******y
发帖数: 578 | 1 昨天facebook phone screen的时候就让我写的这道coding
你可以把每层放进queue以后，再 queue.push 一个NULL来表示一层结束了
每次从queue里出来的元素，如果是NULL就换行，不是就接着打印
这里关键的一点是每次NULL从queue里边pop出来后，要push一个新的NULL到队列结尾
你先看看，还不明白的话我就把代码贴上来 |
|
q*********u
发帖数: 280 | 2 那应该就是写一个while在里边吧。
while((mission = queue.pop())!=null){
for(){
data sampling
data collection
...
}
}
外面的listener反正一直往queue.push(your mission);
如果有特殊要求，比如取到在queue里的某个特定的mission，不能queue.pop(),那就按
照interviewer的要求来吧。
抱歉， 才发现原帖中work thread的图乱了， 现在改过来了
start workthread
|
V
StartStage(get list of objects)
|
|
|
I**********s
发帖数: 441 | 3 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
a****n
发帖数: 1887 | 4 High performance考虑的话，一般专门起一个logging thread,其他线程用message
queue/blocking queue（或者直接用shared memory），把要写的log发到logging线程，同步文件写第一次大概300微秒（包括寻道）， 以后每次大概20微秒（2.4GHZ CPU， 5400转硬盘）
使用linux的message queue 大概 4微秒可以push到queue
其实你也可以直接用log4cxx的异步logging， 不过那个很慢，我是自己实现的logger class， 大概就是4微秒每次logging
其他的feature应该不难 |
|
c******a
发帖数: 789 | 5 Distributed queue use case:
10 million tasks in task queue, overseeing 10 VMs on a cluster. FIFO order
needs to apply to all queue operations cluster-wide.
有人说他实现了。。。。
http://code.google.com/p/hazelcast/wiki/Queue |
|
e**********6
发帖数: 78 | 6 集中回答一下大家的问题。
第一题有一个隐含的限定条件：购买不可以在抛售之后。
第二题，就用简单的递归。pseudo-code如下：
recursive(array, queue, mark){
if queue is full
then print and return
for each char in array not marked
do mark it
push it into queue
recursive(array, queue, mark)
unmark and pop it
}
注意unmark和pop。因为要保持递归每一阶段的唯一性。 |
|
f*******4
发帖数: 1401 | 7 用一个queue 每次新来一个数就pop掉queue尾部比它小的数，然后插入queue
尾部，每次出去一个数看一下是不是queue的头部 |
|
f*****y
发帖数: 444 | 8 I am preparing algorithm, wrote the following algorithm. Share with you. Not
sure whether it is a duplicate post or not.
//---- Breadth Fast Search algorithm ---
// circular queue
int head = 0;
int tail = 0;
#define Q_EMPTY (head==tail)
#define Q_FULL ((tail-head+1)%SIZE==0)
#define SIZE 10
struct Node* q[SIZE];
void put(struct Node* x)
{
if (x==NULL) return;
if (Q_FULL) return; //queue full
q[tail] = x;
tail = (tail+1) % SIZE;
return;
}
struct Node* get()
{
if (Q_EMPT... 阅读全帖 |
|
i**********e
发帖数: 1145 | 9 不必。
有两种解法：
1）用两个 queue -- q1 & q2，把下层的元素 push 进 q2，当 q1 为空时你就知道这
行打印完毕。这时候替换 q1 & q2。替换 q1 & q2 的时候会把 q2 的元素一个一个
copy 进 q1，如果 queue 很大的话 效率可能不是很好。解决方法：可以只交换 q1 &
q2 的指针。
2）一个 queue，但用两个 extra variable: nodesInCurrentLevel &
nodesInNextLevel.初始化 nodesInCurrentLevel 为 1（因为你一开始是 push root
节点进 queue 里了）。当 push 下层的时候就增加 nodesInNextLevel，然后
decrement nodesInCurrentLevel by 1。当 nodesInCurrentLevel 为 0 时 也就是该
换行的时候了。 |
|
j********x
发帖数: 2330 | 10 Effect of different data structures
The designer of the priority queue should take into account what sort of
access pattern the priority queue will be subject to, and what computational
resources are most important to the designer. The designer can then use
various specialized types of heaps:
There are a number of specialized heap data structures that either supply
additional operations or outperform the above approaches. The binary heap
uses O(log n) time for both operations, but allows peeking... 阅读全帖 |
|
P***P
发帖数: 1387 | 11 这题o(n)
就是implement a queue with getMax().
有点像crack150里面的stack with getMax()
public void addLast(T data) {
// insert data to the data queue.
dataQ.add(data);
// adjust the auxiliary queue.
while (!auxiQ.isEmpty() && auxiQ.getLast().compareTo(data) < 0) {
auxiQ.removeLast();
}
auxiQ.add(data); //append to the end.
}
public T getMax() {
return auxiQ.getFirst();
}
public T removeFirst() {
T data = dataQ.removeFirst();
// adjust the auxiliary queue. Because... 阅读全帖 |
|
P***P
发帖数: 1387 | 12 这题o(n)
就是implement a queue with getMax().
有点像crack150里面的stack with getMax()
public void addLast(T data) {
// insert data to the data queue.
dataQ.add(data);
// adjust the auxiliary queue.
while (!auxiQ.isEmpty() && auxiQ.getLast().compareTo(data) < 0) {
auxiQ.removeLast();
}
auxiQ.add(data); //append to the end.
}
public T getMax() {
return auxiQ.getFirst();
}
public T removeFirst() {
T data = dataQ.removeFirst();
// adjust the auxiliary queue. Because... 阅读全帖 |
|
l******e
发帖数: 149 | 13 你程序里这段是什么意思？
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N); |
|
s******n
发帖数: 3946 | 14 keep another queue V.
when append a new element to queue, pops elements from V's end until find
element is less or equal than the new one, then append new element to the
end of V.
when remove first element from the queue, if front item of V is equal to the
first element of the queue, then remove first element of V.
the smallest element is the first element of V. |
|
f****0
发帖数: 151 | 15 用个queue？把数一个一个放进queue里，同时记录queue里面最长的递增序列的长度，
一旦发现有新的数列比之前的更长，就把之前的全部dequeue。这样最后一个数到了以
后，在queue头里刚开始存的递增数列就是最长数列 |
|
p*****o
发帖数: 1285 | 16 T里的元素都放在hashtable的queue里，后面每多加一个前面就拿走一个。这是我最初O
(kn)的code，后来的都没有存。为了方便用的是STL里的map，比hashtable慢一点。
class Solution {
public:
string minWindow(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map > tbl;
int ct = 0; // counter to find the first full set
int lowest; // lowest index of current set
for (int i=0; i
if (tbl.find(T[i]) == tbl.end()) tbl[T[i]] ... 阅读全帖 |
|
G******i
发帖数: 5226 | 17 ☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Sat Oct 29 00:10:37 2011, 美东) 提到:
**********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You ... 阅读全帖 |
|
l****c
发帖数: 782 | 18 So, I think that another BULL GUY is using recursive to push_back the lower
layer's values into container. And when it reaches the lowest level begin
to print, then the 2nd lowest layer's values printed.
I am trying to use non-recursive means. From the highest level, push the
node into a queue (for next level) and a stack for final printing. When the
level popped out from the queue increases to the lower level, check whether
it is the objective. If yes, stop and print everything in the stack. B... 阅读全帖 |
|
g*****e
发帖数: 282 | 19 我很好奇用什么数据结构来存储和更新当前的有效entry。很久之前做过类似的，fb的
题。返回过去n小时内（n<48）内访问最多的ip。只需要描述，不coding。
我给出的解法是同时维护一个queue（按时间顺序存储当前所有有效entry），max
priority queue（快速求top n）和一个hash function（把queue里的值map到priority
queue的node）。因为ip addr其实就是int32，开个hashtable内存勉强吃得消。如果
是url之类的entry似乎更expensive（转成短url？）。欢迎探讨。 |
|
v***n
发帖数: 5085 | 20 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... 阅读全帖 |
|
O*******d
发帖数: 20343 | 21 来自主题: JobHunting版 - 一道电话题 不需要写code。
一个producer， 一个consumer。 中间用一个queue连接。
producer每秒钟往queue里放一个token。 持续8秒，休息两秒，再持续8秒，休息两秒,
一直这样重复。
consumer每秒钟从queue里取出一个token，持续80秒，休息20秒，再持续80秒，休息20
秒，一直这样重复。
求：
最小的queue size，可以满足consumer每次提取时有token取用。 |
|
p*****2
发帖数: 21240 | 22 终于写完了，大牛们见笑了。
require 'set'
$dict=Set.new ['fox','fog','dog']
def indict?(word)
$dict.include? word
end
def transfer(first,last)
queue=[first]
hash={first=>0}
until queue.empty?
word=queue.shift
step=hash[word]
(0...word.length).each do |i|
curr=word[i]
('a'..'z').each do |c|
word[i]=c
if(word==last)
return step+1
elsif indict?(word) && !hash[word]
hash[word]=step+1
queue<<(String::new word)
end
... 阅读全帖 |
|
h****n
发帖数: 1093 | 23 其实两个binary semaphore就足够了，一个sem_full另外一个是sem_empty 初值都为0
pop操作只有在检测到queue为空的时候才去wait(sem_full)，当push一个新元素的时候
都会去notify一个等待的线程
push操作检测queue为满的时候做类似操作
如果光用mutex的话，当queue为空的话，做pop操作的线程即使拿到mutex每次都检测到
queue为空，这样子就做了很多无谓的工作，还占用了时间片
而用同步机制的话，这种情况下会被scheduler直接放进pending list里面直到被
notify避免了cpu的浪费 |
|
j*****y
发帖数: 1071 | 24 开始寒暄了一下差不多10分钟的简历
写一个 queue的类
template
class queue
{
};
构造函数里面传递 queue的大小(capacity)
后来还问了 mutlthreading 下如何考虑, 感觉这个没答好，
应该直接说mutex整个queue就完事了，我当时说用 producer/consumer
，这个其实不太好弄
还就是没做 一个check, 比如如果 queque myqueque(-5), 这个时候
用户输入一个 负数 size怎么办. 不过整个过程也没有给我指出这个.
求bless |
|
h***i
发帖数: 1970 | 25 贴个scala的。
case class Node(value: Int, to_list: List[Int])
def topologic_sort(graph: List[Node]): List[Int] = {
if (graph.isEmpty) return List()
val queue = graph.filter(_.to_list.isEmpty).map(_.value)
if (queue.isEmpty) return List()
queue ++ topologic_sort(graph.filter(!_.to_list.isEmpty)
.map(x => Node(x.value,
x.to_list.filter(
!queue.contains(_)))))
}
val graph = List(Node(0, List(1, 2)),
No... 阅读全帖 |
|
d****o
发帖数: 2 | 26 抛砖引玉
#include
#include
#include
const int kMaxK = 5;
const int kMaxN = 8;
const int kMaxS = 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5;
#define DEBUG(v) std::cerr << #v << " = " << (v) << "\n"
int N, K, max_state;
short top[kMaxS][kMaxK];
int G[kMaxS][kMaxK * (kMaxK - 1) + 1];
int src = 0, dst = 0;
int f[kMaxS];
int pow(int base, int power) {
int r = 1;
for (int i = 0; i < power; r *= base, ++i);
return r;
}
int get(int num, int d) {
for (int i = 0; i < d; num /= K, ++i)... 阅读全帖 |
|
d****o
发帖数: 2 | 27 抛砖引玉
#include
#include
#include
const int kMaxK = 5;
const int kMaxN = 8;
const int kMaxS = 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5;
#define DEBUG(v) std::cerr << #v << " = " << (v) << "\n"
int N, K, max_state;
short top[kMaxS][kMaxK];
int G[kMaxS][kMaxK * (kMaxK - 1) + 1];
int src = 0, dst = 0;
int f[kMaxS];
int pow(int base, int power) {
int r = 1;
for (int i = 0; i < power; r *= base, ++i);
return r;
}
int get(int num, int d) {
for (int i = 0; i < d; num /= K, ++i)... 阅读全帖 |
|
M******7
发帖数: 30 | 28 维护一个queue存每次访问的时间戳，每一次有新的访问at time t，do:
step 1：remove elements in queue which t'
step 2: add t to queue
total_visit(): return size of queue
是这个意思吗？ |
|
c**y
发帖数: 172 | 29 问题1
reverse a single list
问题2
实现两个函数producer和consumer。这两个函数操作一个共同的queue,这个queue的
size有限。要求这两个函数是multithread-safe。
producer() {
// add elements into the queue
}
consumer() {
// remove elements out of the queue
}
问题3
一台电脑，内存有限（4GB），硬盘无限大。如何sort一个200GB的文件。
bottle neck可能出现在哪里？
如果硬盘IO带宽是100MB/s，那么需要多长时间才能完成整个sorting过程。 |
|
b******7
发帖数: 92 | 30 就是一个topological sort 的变种
1.初始化每个node的入度degree
2.将u放queue中
3. while queue is not empty, do
4. 从queue中取u
5. 删除与u相关的parent的节点中的边
5. 删除与u相关的child的节点的parent边，将degree[child]--，若减为0，将
child入queue |
|
c********p
发帖数: 1969 | 31 这个题，我是这样做的：
1. 从4周(最上一行，和最下一行，然后第一列除去首尾，最后一列除去首尾)找到 O,
把坐标x,y 放到2个queue里。找到的时候，把O标记成了Y.
2. 当queue不为空时
把queue里的坐标poll出来，看这个坐标上下左右，如果是O, add到queue最后。
3. 把矩阵中的O变成X, 把Y变成O.
过的了小oj，过不了大oj
我参考的是这个blog，然后把人家c++代码放进去跑了，就过的了大oj。。。
http://fisherlei.blogspot.com/2013/03/leetcode-surrounded-regio
我哪里耗时耗空间了？？ |
|
z****e
发帖数: 54598 | 32 java的，二爷博客上的java的bfs有个bug
不过在leetcode上测不出来就是了，当m!=n的时候，二爷代码就出错了
这题真心坑爹，尤其用java做
递归的调用很容易就超时了
所以我在二爷代码的基础之上做了点优化
大概能优化50ms左右，对于小oj来说
大oj还是需要连点两次，激活jvm的jit才能过
public class Solution {
char[][] board;
int m,n;
Stack queue = new Stack();
private void fill(int i, int j){
if(i<0||j<0||i>=m||j>=n||board[i][j]!='O') return;
board[i][j] = 'D';
queue.push(i*n+j);
}
private void bfs(int i, int j){
fill(i,j)... 阅读全帖 |
|
r*c
发帖数: 167 | 33 之前写了个C#的。思路都一样， use tree matching algorithm to determine the
candidate window.
//using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
class MinWindowSolution
{
class TreeNode
{
public TreeNode parent;
public int val;
public List children;
public TreeNode(int i, TreeNode p) { val = i; parent = p; children =
new List(); }
};
public void FindMinWindow_Tree(int[] input, int[] query, out int nS... 阅读全帖 |
|
h****y
发帖数: 137 | 34 用一个queue装实时数据, 有新的插入, 过时的删除.
所有queue插入QUEUE的数据同时插入一个BST, 用hash存在BST中的位置, 从QUEUE中删
除时也从BST中删除,
BST中的节点加一个信息, 记录以此为根的子树所有的string的总长和string的个数,
log(n)时间算出95%的平均
5% |
|
w********s
发帖数: 1570 | 35 你被黑了吧
schedule实现很复杂的，要你写code，明显还要考你mutex/lock
具体实现，用一个queue来存timestamp+function
然后开一个线程，其中一个loop
每次检查queue的开头时间是不是过了，过了的话，取出来执行func。
schedule就要往那个queue里插入pair
注意你需要一个mutex和一个lock来保护对queue的访问。 |
|
f******h
发帖数: 45 | 36 也找工作了一段时间了，从版上学了很多，上周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)... 阅读全帖 |
|
h****j
发帖数: 15 | 37 感谢楼主，对于第二题，有些疑问，楼主的描述不太像一个通常的task dispatch
system，一般addtask里不直接运行task的。
请问一下addTask()和trigger()是运行在两个线程里的么？
两个线程共享一个task queue，这个queue需要用锁来保护。
trigger线程里面有一个for loop，不断的从queue里面拿出task执行。如果队列空，停
等。
addtask线程里面不断的将新的task写入queue里面
这个理解对么？多谢！ |
|
h****j
发帖数: 15 | 38 感谢楼主，对于第二题，有些疑问，楼主的描述不太像一个通常的task dispatch
system，一般addtask里不直接运行task的。
请问一下addTask()和trigger()是运行在两个线程里的么？
两个线程共享一个task queue，这个queue需要用锁来保护。
trigger线程里面有一个for loop，不断的从queue里面拿出task执行。如果队列空，停
等。
addtask线程里面不断的将新的task写入queue里面
这个理解对么？多谢！ |
|
m*****n
发帖数: 204 | 39
The following is an O(nlgn) solution for string of size n.
It maintains a heap for eligible chars, preferring longer streams.
Ineligible chars are maintained in a candidate queue, and added back
to the working queue when their position constraint is removed.
public class MinDistance {
public String rearrange(String source, int distance) {
// TODO Check params.
// WorkingQueue of eligible streams. Longest stream at head,
// but BackupStream at tail.
PriorityQueue阅读全帖 |
|
c***z
发帖数: 6348 | 40 【 以下文字转载自 DataSciences 讨论区 】
发信人: chaoz (面朝大海，吃碗凉皮), 信区: DataSciences
标 题: OCR job from recruiter - it is interesting but I can't do it, yet
发信站: BBS 未名空间站 (Fri Jun 20 12:25:07 2014, 美东)
If you would be interested please let me know at h******[email protected] as
early as possible.
Job Title: position for Data Scientist for Machine Learning and Natural
Language Processing Experience
Company: BITS
Task 1: Extend NIST Scientific Text Extraction System
Description of Tasks
I. Implement distributed... 阅读全帖 |
|
p**f
发帖数: 59 | 41 骑驴找马，某相对热门startup，最后一轮，估计已挂。。。
面试官：director白男，老中，一个烙印，另外一个白男。
题一：
web service相关，后台需要收集用户上传的日志并分析后反馈结果，日志文件压缩，
size在300MB以上，需要可以scalable。
没有太多时间考虑细节，直接给了个方案：
前台日志文件分片上传并通知后台chunk数目，后台接收到每个chunk成功写入临时文件
通知前台继续下一个chunk，结束后比较文件size。使用rabbitmq + celery的架构，成
功接收文件后web server把解压分析的task发布到相应的queue，worker server
monitor这个queue做相应的解压分析工作。
感觉面试官还算满意，中间问了很久如何保证data integrity， 如何monitor queue并
在合适时候进行worker扩容等问题。
接下来这题估计挂了（题一扩展）：
题二需求：后台实现一个可以接收前台任意payload的service，payload的大小在1MB以
下，多种类型客户端同时上传，百万量级。某些类型的payl... 阅读全帖 |
|
t**r
发帖数: 3428 | 42 每个访问者维护一個queue. 每次访问往queue里加add。 每5秒pop所有的queue一次.
queue最长的就是了 |
|
o********r
发帖数: 79 | 43 不要吵了。
我按beanbun的思路写了一遍，指教一下
typedef pair COORD;
void extend(COORD cur,
vector >& visited,
vector > matrix,
queue& current,
queue& next )
{
vector shift;
shift.push_back(make_pair(0,-1));
shift.push_back(make_pair(0,1));
shift.push_back(make_pair(1,0));
const int m = matrix.size();
const int n = matrix[0].size();
for(const auto s:shift)
... 阅读全帖 |
|
h******e
发帖数: 52 | 44 来自主题: 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;
... 阅读全帖 |
|
I*******x
发帖数: 69 | 45 来两个Queue和一个List
一个queue里面装了当前Level的node，从左往右放好的，再一个一个取出来，将他们的
值放进List，
另外一个queue放下一level的node，将当前level取出来的node的left和right放进去，
直到当前level的queue为空，然后将currentQueue ＝ nextQueue;nextQueue ＝ new
LinkedLIst(); list放进最终的List> 里面的第一个。
直接上code：
public List> levelOrderBottom(TreeNode root) {
List> result = new ArrayList>();
if(root == null) return result;
LinkedList cq = new LinkedList();
LinkedList阅读全帖 |
|
f**********e
发帖数: 288 | 46 给你两个independent queue，每个queue都存着timestamp，只能有getNext()来取
queue里面的timestamp，每个timestamp只能被取一次，比较这两个queue里的
timestamp，如果差值<1，print这两个timestamp.
Q1 0.2, 1.4, 3.0
Q2 1.0 1.1, 3.5
output: (0.2, 1.0), (1.4, 1.0), (0.2, 1.1), (1.4, 1.1), (3.0, 3.5)
two sigma onsite 题。 我只想到用brute force。 有木有人给个更好的解法？ |
|
c*******t
发帖数: 123 | 47 来自主题: JobHunting版 - U电面经历 我觉得你这个似乎有问题？
首先你返回true or false是O(1)吗？这种题目一般要求查询O(1) 复杂度，而你里面还
有for loop.我没细看。
其次，你时间判断 “counter[i].first >= current - 10” 我怎么觉得有点问题？
你下面调用
if (counter.quotaExceeded()) return;
std::cout << "g() " << count << std::endl;
如果在0.000000000秒有100次调用。第10.00000秒你执行if 判断，答案是不能再调用
了。
但实际上是可以调用的，因为假设你if判断执行了0.01毫秒，到第二行std::cout....
真正执行的时候，
第0.0000000000秒的已经过期了。
所以 “counter[i].first >= current - 10” 中的等号是不是应该去掉？
为什么不用queue 呢？
每次只要检查queue前端是否已经过时，过时弹出，这个是不变量，
然后只要 return queue.size<100;
queue si... 阅读全帖 |
|
b*****n
发帖数: 618 | 48 我只是说了merge的那部分，produce那部分也比较好办把。
idea是一样的，可以用两个queue，
第一个queue里开始存的都是input，
produce完的output放到第二个queue里面。
每个thread worker的逻辑是一个while(true) loop
先看一下第一个queue里面还有没有input没处理，如果还有就先处理produce，
否则就是上面的处理merge的逻辑。
其实就是个size为k的threadpool。
我可能还是没明白你说的 “use a PriorityQueue to create two functions:
producer and consumer” 是什么意思？ |
|
h******6
发帖数: 2697 | 49 我来抛砖引个玉吧。是不是首先还得计算出个dp[][]数组表示i到j是不是chunked
palindrome，后面就跟palindrome partition一样了。所以关键是如何构造那个dp[][]
也就转化为给定一个String，如何判断它是不是chunked palindrome。
boolean isChunkedPalindrome(String s) {
int left = 0, right = s.length() - 1;
LinkedList queue = new LinkedList();
int[] cnt = new int[256];
while (left < right) {
char leftChar = s.charAt(left);
char rightChar = s.charAt(right);
queue.add(rightChar);
cnt[leftChar]++;
cnt[righ... 阅读全帖 |
|
f*******b
发帖数: 520 | 50 之前也onsite了dropbox, pintreset, 和whatsapp都挂了，后来才慢慢找到点感觉。我
把面的题基本都写下了，但我不在这里和大家讨论这些题了。
A (Airbnb)
1. 2D array, 访问顺序必须是‘回’字的方式，就是从外圈转到里圈，写出class,
Iterator, hasNext(), next().
2. 电话号码和计费的一个log, 去parse 看规定时间内哪个号码产生费用最高。
3. leetcode anagram 的一题变种
4. 有很多个sorted queue存在不同服务器上，如何有效的读取到一个 sorted 大queue
里 (google也面到了这题）
5. 设计db, 如何存取房东和房客的reviews, 如何maintain他们之间的关系。
Airbnb确实和大家说得一样面试官很nice, 内部装潢笔格明显很高，非常酷炫.
offer: 160k + 5000股／2年 ＝ 260k
A (Amazon)
1. leetcode tree的一题，就是每层的nodes横着也是连着的
2. 设计搜索，在amazon搜索如何设计。... 阅读全帖 |
|
