j**l
发帖数: 2911 | 1 嗯，你这个其实就是顺序存储结构，即用三个数组来存储一棵二叉树。也可以把data，
left, right放在同一个struct里头，这样只需要一个数组，每个元素是包含三个域(
data, left, right)的struct。
另外，如果是完全二叉树，连left, right都可以省略掉，因为可以推算出来，比如0号
元素的左孩子是1，右孩子是2, i号元素的左孩子是2*i+1, 右孩子是2*i+2，如果值大
于结点个数，则该孩子不存在。普通二叉树也可以用这种完全二叉树的存储方式，但必
须标志某些结点是空的，这会造成空间的浪费。最坏情况是右单支树，一棵高度为k的
右单支树，只有k个结点，却需要2^k - 1个数组元素的空间。 |
|
T***a
发帖数: 218 | 2 朋友刚做的，面的是Google product manager，这种题怎么回答啊？ 感觉特别空，不
知道面试官想听什么。
How would you design a voice search engine?
What is your favorite Google product and how can you improve it? |
|
h**k
发帖数: 3368 | 3 一个格子被某个棋手的旗子占据为１，被另外棋手的旗子占据或者空着为０。这样我们
在每次需要判断时，对于每个棋手可以生成一个9 bit的整数。
那么可以建立一个有512元素的数组，每个元素的index对应一个pattern，值则为1，表
示棋手赢；为0，则还没赢。每次判断，直接查询两次数组就可以了。 |
|
h**6
发帖数: 4160 | 4 DP
每个格子有三种情况，总共3^9种布局。
任何一种布局可能有先胜，后胜，未分出胜负，无效(双方都三连或先后手棋子数差不
为0或1)
从满局往空局方向开始判断，每种布局最多有9种发展，对对手最有利的结果是该布局
的结果。
因此复杂度为3^9*9 = 177147 |
|
z****n
发帖数: 1379 | 5 竖过来看，周围一圈都是高是3的柱子，中间薄薄一层底子，高度是0，可不就是装
3个单位的水吗。数字代表的是筒壁的高度，是不能装水的东西的高度，中间空的部
分是能装水的 |
|
l*********r
发帖数: 674 | 6 我靠，第一题我用C和java分别run了一下，居然结果不一样。
java的结果（run in eclipse 3.6.1）
x=55, y=36 //第一步
x=56, y=93 //第二步
C的结果（cygwin + gcc）
x=56, y=36 //第一步
x=57, y=94 //第二步
顺便说一下，y=++y+++x;两个都报错，至少要空一格写成：y=++y+ ++x;
觉得java下面，第一步算出来x=20+55 = 55，后面的x++不运行。
但是C下面，x=55之后，x++还要先加再用一次，就变成了56。
跟内存模式有关么？是不是java下面的left side构造了一个新地址for x? |
|
f*****y
发帖数: 444 | 7 Update: onsite 失落归来。不知道当时怎么这么晕菜，写一个strlen 函数忘了检查空
指针。犯个严重低级错误。pass 了。还有两个brain teaser, 一个太简单不说了，另
一个是称8球问题， careercup150上有。 |
|
j**l
发帖数: 2911 | 8 要先向interviewer确认，是求二叉树的直径，也就是节点的最大距离。
最大距离的路径，一定穿过某棵子树(含整棵树的情形)的根节点A, 长度(边的条数)是A
的左子树的高度和右子树的高度之和。假定空树的高度为0，单节点树的高度为1。 |
|
d********i
发帖数: 363 | 9 二面完了，抽点小空写下总结。
网上好像找不到很多这个职位的面试信息，给后来人参考下。
前两面基本是技术面。
问简历+编程。
简历基本就是问做过的projects。所以对自己简历一定要熟悉，interview前最好能自
己先过自己这关，想象面试问题，自己回答。我的第一个interview前，排练了好几遍
，project的问题答得不错。第二个interview，没啥排练，对方问了个easy question(
你最喜欢的project是哪个，介绍下)结果语速慢了。
编程的话，共三个（本人统计背景，编程用R）
1.给几个元素在一个集里，要得到所有的子集。（这个除了用recursion，我实在想不
出其他，但是好像不是他们需要的答案。）
2.查找出一个名单中所有有重复的名字。
3.如果仓库没货，如果估算送货时间。（根据他们给的历史数据，我直接用了75%
quantile）
4.掷骰子的概率计算。（这个手算，不需要编程）
另外，面试官都很nice，过程中有想不出来的一直鼓励我。
希望对大家有帮助。 |
|
h********3
发帖数: 2075 | 10 为啥近处密度大？
科学松鼠会上以前有篇文章专门讨论过这个问题。这个是一个有趣的悖论问题。其实按
极坐标来产生和按照面积体积之比来产生，都是正确答案。关键取决于你对随机变量的
定义。
如果你在X,Y，Z空间看的觉得分布的密度是均匀的，那么在极坐标(r,\theta,\phi)空
间上看会觉得你的点趋向于产生r坐标较大的，那么也有人跳出来说你不是真正均
匀分布的。同理，你在任何一个空间看是均匀密度的点集。那么我都可以找到一种仿射
变换，我都可以让你的分布在那个空间上不是均匀的。
到底谁是正确的？
实际上，任何一块连续的空间，点的集合都是无穷大的。根本就没有点的密度可言或者
点的密度都是无穷大。 |
|
h********3
发帖数: 2075 | 11 并不是科学松鼠发表了那篇文章。别人不过是科普性质的引用，这个问题早100多年前
的数学界都讨论很久了。别人只是转述。极坐标产生的随机点集的概率密度在极坐标空
间内也是even的。 |
|
c*******7
发帖数: 2329 | 12 我当时脑袋一片空白木有想出来......sign
My |
|
h*******s
发帖数: 8454 | 13 发给我一个email
题目是bloomberg phone interview
内容是空的。。。
搞什么。。。 |
|
w****x
发帖数: 2483 | 14 int _inner_ways(const char* pStr)
{
if (*pStr == 0)
return 1;
if (*pStr <= '0' || *pStr > '9')
return 0;
int n = _inner_ways(pStr+1);
if ((*pStr == '1' && *(pStr + 1) >= '0' && *(pStr + 1) <= '9')
|| (*pStr == '2' && *(pStr + 1) >= '0' && *(pStr + 1) <= '6'))
n += _inner_ways(pStr+2);
return n;
}
int GetWays(const char* pStr)
{
if (NULL == pStr || *pStr == 0)
return 0;
return _inner_ways(pStr);
}
int GetWaysDP(const char* pStr)
... 阅读全帖 |
|
c****g
发帖数: 85 | 15 external sorting里merge m个已经内部排序的文件。
在内存里建立m个queue。
分别m个文件的数据，然后取m个数字排序写入final file。如果queue空了，再读入。 |
|
|
|
j********g
发帖数: 80 | 18 1 class A{};
2 void main()
3 {
4 A a;
5 }
一个空类，然后问在第三行会发生什么？ |
|
h****n
发帖数: 1093 | 19 第二行，压入AX,CX,DX寄存器，压入返回地址，压入EBP寄存器，更新EBP寄存器为当前的
ESP
第三行应该是啥都没干
第四行的话空类里面自动初始化了默认构造函数，默认析构函数，默认复制构造函数和
默认赋值运算符，然后把该object压入函数栈 |
|
a********9
发帖数: 129 | 20 一定要interative么，能不能还是用recussion，只是比如说当临时储存的文件空了的
时候再读一下stream？ |
|
g******z
发帖数: 893 | 21 如果这种情况的话，能不能BFS+queue
把周围的同色棋子和空格用queue保存下来
如果queue空之前到达棋盘边界就没有被围，不然就是被围了？ |
|
r********9
发帖数: 1116 | 22 BFS+stack? 不是应该BFS+queue吗？
这道题不难，但如果置换成计算一块棋是否被包围，被包围了判断是死是活的话，好像
很难了。
关键是怎么区分内空和外空？
fail |
|
p*g
发帖数: 141 | 23 这个思路是对的, 但是逻辑不对吧
应该是: 只要有一个地方是空的, 这一块棋就是活的
if ( out of boundary || B || visited ) return false
if ( empty ) return true
for ( 4 neighbours )
if ( dfs(neighbour) ) return true
return false |
|
z*****4
发帖数: 12 | 24 昨天下午的google intern电话面试，写出来给其他准备的人些信息。
两轮店面。
Round 1. 美国人，上来问abstract vs interface的区别。回答的内容忘说abstract只
能单继承，interface可以多implement的区别了，对方通过不通过方式问了几遍，我才
想起这个，感觉自己太二了。然后接着又问为什么java不让多继承，回答avoid dimond
-shaped inheritance。问完这些就是coding题。很简单，就是给一个文件，返回vowel
（就是原因aeiou）数量最多的行。还说不考虑大数据情况，就是一个普通file。于是
中规中矩写完代码。然后问client side怎么区分文件不存在和文件为空的情况，答可
以在文件不存在的情况下抛异常。对方又问为什么一开始写代码时候没抛异常，答写代
码时候考虑的是算法本身，抛异常这些都可以慢慢加。结束。
Round 2：美国人，比较nice。直接说45分钟的面试就做一套题，但是会慢慢深入，看
能写多深入。大概内容是设计一个cache。我写了一个HashTable的框架，用chaining处
... 阅读全帖 |
|
z********8
发帖数: 255 | 25 HR那种啥都不懂的 看上去差不多一般都说好。
人MANAGER说不定有其他人内推的，早就有差不多的人了，或者人不喜欢你，宁愿空着。
。。说人黑你。。犯得着么。。多找找自己的原因。 |
|
|
s********u
发帖数: 1109 | 27 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
样吧。不过他说会给足时间。
题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
所在的interval返回。
分享题目和答案：https://docs.google.com/document/d/
1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit
这个我记得就是用BST做的。
有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。
中间讨论了一下维护min和max变量是否必要，我说主要是在val超出范围的时候直接判
断，他说那其实interval中间也有空当。我就说那就只有两端的时候，会比较有用... 阅读全帖 |
|
n****e
发帖数: 678 | 28 没有看懂这句：
“有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。”
能详细说说吗？ |
|
s********u
发帖数: 1109 | 29 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
样吧。不过他说会给足时间。
题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
所在的interval返回。
分享题目和答案：https://docs.google.com/document/d/
1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit?usp=sharing
这个我记得就是用BST做的。
有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。
中间讨论了一下维护min和max变量是否必要，我说主要是在val超出范围的时候直接判
断，他说那其实interval中间也有空当。我就说那就只... 阅读全帖 |
|
n****e
发帖数: 678 | 30 没有看懂这句：
“有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。”
能详细说说吗？ |
|
f********4
发帖数: 988 | 31 哦，我去看看rolling hash是神马东西。。
push back和 substr时间复杂度应该都是liner的吧，因为只有10个character，但是空
间复杂度就不好说了，buf = buf.substr(1)我也搞不清是不是call 了copy
constructor |
|
m**********g
发帖数: 153 | 32 RateLimit是否可以用token bucket 来实现， 一个timer thread定期添加token, 一个
请求消耗一个token, bucket 为空时reject request. 也可以用类似select()的
function实现timer 与demultiplex. |
|
f*****e
发帖数: 2992 | 33 想出来了，每pop一个，peek一次就行了。对于distinct elements而言。
对于有重复的继续pop，并记载次数，直到peek到不同元素或为空为止。 |
|
f*****e
发帖数: 2992 | 34 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
1变为2。然后stack为空，populate array啦。很简单的。
其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
尾还是放到头。中间有个gap。 |
|
G*********n
发帖数: 53 | 35 我觉得难度中上吧，不过比我面试的难多了。首先，class 实现的话就是 一个random
判断 头还是尾。
第二， 1 如果 数组只剩一位的话，直接拷贝进去
2. 如果是第一次操作的话，先pop 一个出来
3. 如果lastPop < currentPop的话， 那么 lastPop 一定是在array remaining 部分
的head
如果 lastPop > current Pop 的话， 那么 lastPop 一定是在 array Remaining
的 tail
Put lastPop， update head and tail of that array, lastPop = currentPop;
第三，如果用重复的话，就会麻烦点，有点像 leetcode 上面 search in rotated
array II 。 我觉得可以考虑用 buffer hold 住 重复的数知道不重复，这样一次放入
buffer 进数组
主要还是 分类思考，一步步地想。就跟leetcode的oj一样，第一步测试空数组， 第二
步长度=1 的数组 第三步长度 = 2 的数... 阅读全帖 |
|
f*****e
发帖数: 2992 | 36 想出来了，每pop一个，peek一次就行了。对于distinct elements而言。
对于有重复的继续pop，并记载次数，直到peek到不同元素或为空为止。 |
|
f*****e
发帖数: 2992 | 37 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
1变为2。然后stack为空，populate array啦。很简单的。
其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
尾还是放到头。中间有个gap。 |
|
G*********n
发帖数: 53 | 38 我觉得难度中上吧，不过比我面试的难多了。首先，class 实现的话就是 一个random
判断 头还是尾。
第二， 1 如果 数组只剩一位的话，直接拷贝进去
2. 如果是第一次操作的话，先pop 一个出来
3. 如果lastPop < currentPop的话， 那么 lastPop 一定是在array remaining 部分
的head
如果 lastPop > current Pop 的话， 那么 lastPop 一定是在 array Remaining
的 tail
Put lastPop， update head and tail of that array, lastPop = currentPop;
第三，如果用重复的话，就会麻烦点，有点像 leetcode 上面 search in rotated
array II 。 我觉得可以考虑用 buffer hold 住 重复的数知道不重复，这样一次放入
buffer 进数组
主要还是 分类思考，一步步地想。就跟leetcode的oj一样，第一步测试空数组， 第二
步长度=1 的数组 第三步长度 = 2 的数... 阅读全帖 |
|
a*****y
发帖数: 22 | 39 假设Quack的顺序是递增
我的思路是，想办法找到最大的元素（尾），然后push进一个标志（如MIN_INT）;下次
peek的时候，只pop非MIN_INT的元素，直到再次遇到最大的那个元素，此时可以pop标
志，直至空
void PopQuackToArray(Quack& quack, vector& array) {
vector tmp;
int last = quack.pop();
tmp.push_back(last);
int curr;
while (!quack.empty()) {
curr = quack.pop();
if (curr != last) {
break;
}
tmp.push_back(last);
}
if (quack.empty()) {
if (curr < last) {
array.push_back(curr);
... 阅读全帖 |
|
a*****y
发帖数: 22 | 40 假设Quack的顺序是递增
我的思路是，想办法找到最大的元素（尾），然后push进一个标志（如MIN_INT）;下次
peek的时候，只pop非MIN_INT的元素，直到再次遇到最大的那个元素，此时可以pop标
志，直至空
void PopQuackToArray(Quack& quack, vector& array) {
vector tmp;
int last = quack.pop();
tmp.push_back(last);
int curr;
while (!quack.empty()) {
curr = quack.pop();
if (curr != last) {
break;
}
tmp.push_back(last);
}
if (quack.empty()) {
if (curr < last) {
array.push_back(curr);
... 阅读全帖 |
|
j****l
发帖数: 85 | 41 才第一轮，感觉面的不太好。leetcode刷了这么多，发现还是不够呀。
面试官感觉是非老美非烙印非老中的外国人，口语很好，略有口音，但是电话音质太差
，整个过程听起来很累。
先让自我介绍，问了最喜欢的project，希望在技术方面讲细一点，但是我的那个
project可讲的细节太多了要讲好久，讲了一会儿感觉他没什么反应，就问说如果感兴
趣我可以更深入讲，他说不用了，挺好，然后开始code题目。
第一道是经典题给很多（millions以上）个点，以（x，y）坐标表示，找出离原点最近
的k个点。k 远小于 n。
开始还想了一会儿，后来想到用priority queue来做，问了时间复杂度是nlogn。面完
后问了一下别人，发现是可以用selection做的，更快。
第二道比较tricky给是一个string和一个alphabet，找出包含所有alphabet的最短的
substring。我的方法是用hashset保存alphabet，读string，每遇到一个字母，就从
hashset里面移除对应字母，最后如果hashset为空则string包含所有字母。在面试官提
示下发现可以试着缩短这... 阅读全帖 |
|
R******9
发帖数: 267 | 42 1. Given an increasing int array, find the smallest integer that is greater
than a given number.
我用的是C数组，interviewer又问如果输入的数组指针是空的，code会在哪行 core
dump
2. Given a log with entries starting with timestamp
2014－05－19 ...
2014－05－21 .....
# Get the number of occurrences of unique log entry for 2014-05-21.
# Find any log entries that have the letter A or B
3. class A;
class B;
class C {
A* a_;
B* b_;
...
};
implement constructor, copy constructor, = and destructor of C.
写 assignment oper... 阅读全帖 |
|
h*********d
发帖数: 336 | 43 这道题的难点是处理空数组和最后的a[len-1]吧，还有打印格式
if (a.length==0) System.out.println("0-99");
int prev = -1;
for (int i=0; i
if (a[i]-1==prev) {
prev=a[i];
} else {
if (prev+1==a[i]-1)
System.out.println(prev+1);
else
System.out.println((prev+1) + "-" + (a[i]-1));
prev=a[i];
}
if (i==a.length-1 && a[i]!=99)
if (a[i]==98) System.out.println(99);
else System.out.println((a[i]+1)+"-"+99);
}
请大牛指点
} |
|
h***k
发帖数: 161 | 44 方法就是carry进位么，case包括空数组，加一后长度不变/增加一位 |
|
h***k
发帖数: 161 | 45 方法就是carry进位么，case包括空数组，加一后长度不变/增加一位 |
|
g*******0
发帖数: 20 | 46 给一个2d array，要求写一个顺序访问这个2d array的Iterator，包括hasNext()与
next()。注意2d array的每行中元素的个数可能不一样，也可能为空。followup是写一
个remove()，注意是remove当前item，不是下一个item。
要求code能运行。也没有bug free，bug fix得比较快，还是给onsite了。跪求版上面
过airbnb的大牛们的面经，包括culture fit的问题，可站内，多谢了！ |
|
b*******i
发帖数: 20 | 47 好像很麻烦啊，匆匆想到下面三种解法，抛砖引玉。
1. 暴力求解，时间复杂度至少是O(S^3)，我不确定
找到下面各种矩形
R0 = 相交至少0次的矩形 （就是原来的矩形）
R1 = 相交至少1次的矩形，(就是上一步R0的交集，复杂度O(S^2), 如果为空，就不要
往下算了)
R2 = 相交至少2次的矩形 (就是上一步R1的交集)
...
R(S-1) = 相交至少S-1次的矩形
结果是R0-R1+...
2. 分割矩形， 时间复杂度至少是O(S^2)，我不确定
从1个矩形开始，加入第2个矩形后，如果有相交，记录他们分割的小矩形。
再加入第3个矩形，跟前面的小矩形如果有相交，记录他们分割的小矩形。
...
结果是所有分割后小矩形的面积之和。
3. 另外坐标是整数，离散化方法。 |
|
h**p
发帖数: 211 | 48 这题总代码会挺长，因为要建几个额外的array当map用，中间的实际代码量会很小
从后往前，每次只取3个，同时传入参数决定是空/thousand/mil/bil。如果每次最后2
位不是00，那是肯定要加and的
还有ls有位说单复数的同学，肯定是小学英文没学好，只有three hundred，没有three
hundreds |
|
l*****i
发帖数: 13 | 49 能
长度n的数组建堆是O(n), 从空堆一个一个加进去是nlogn |
|
T***1
发帖数: 445 | 50 面试结束，就应该把精力放在其他面试上，而不是空等。 |
|
