i*******l
发帖数: 6 | 1 最近在看PM quadtree,可是看了半天还是不懂书上的意思,想想还是直接看code比较好,所
以哪位大侠如果有,方便的话能不能给我一份copy或者介绍一下coding应该注意的地方,象
insert,delete或者search.
谢谢! |
|
j*****y
发帖数: 1071 | 2 来自主题: JobHunting版 - G 家面经 求 bless :)
面了四个人.
第一个人: 关于 quadtree 的
比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
那么这个 image就是黑(B)的，如果所有的pixel 是白(W)的，那么这个 image就是白的。
否则的话，需要把这个 image等分成四份，如下图
__________ __________
| | 等分成四份就变成 | | |
| | |____|___|
| | | | |
|________| |____|___|
分成四份以后每个小份就是一个 sub-quadtree
问题1 : 为这个 quadtree里面的 node 设计 data structure
然后的问题是关于两个 quadtree 的 intersection, 有两个 quadtree, 它们描述的
... 阅读全帖 |
|
j*****y
发帖数: 1071 | 3 来自主题: JobHunting版 - G 家面经 求 bless :)
面了四个人.
第一个人: 关于 quadtree 的
比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
那么这个 image就是黑(B)的，如果所有的pixel 是白(W)的，那么这个 image就是白的。
否则的话，需要把这个 image等分成四份，如下图
__________ __________
| | 等分成四份就变成 | | |
| | |____|___|
| | | | |
|________| |____|___|
分成四份以后每个小份就是一个 sub-quadtree
问题1 : 为这个 quadtree里面的 node 设计 data structure
然后的问题是关于两个 quadtree 的 intersection, 有两个 quadtree, 它们描述的
... 阅读全帖 |
|
y***k
发帖数: 162 | 4 ［Update］没想到借了个朋友的ID发个面经也会引发性别问题的争议。面试的主人翁是
个30好几的老大爷。运气真的很好，所有题目都不难。
概略：从本科到PhD一直念的EE。PhD毕业后没怎么找工作就直接到一个小型research
lab做networking research待了2年多。2014年初第一次Google试水，挂在onsite上了
。到了下半年这几家的recruiter开始陆续contact我，想想也差不多是时候换一下环境
了，就安排了感恩节前一周三个电面。电面除了G都非常顺利。G的电面我自己作死，面
完觉得必须挂的。谁知道过完感恩节那周竟然三家都收到onsite通知了。当时的想法是
避免战线拖太长，所以把三个onsite都安排在元旦后第一周。计划利用圣诞／新年长假
养精蓄锐好好复习，然后一鼓作气搞定。现在回头看，这个策略这次发挥的非常出色。
三家onsite都发挥的非常好，据说feedback都不错，最后都拿到了offer，包裹也都挺
不错的（G > L > F）。
准备：我一直不认为临急抱佛脚似的突击能有多大用处。所以准备时间比较长，可以算
从2013下半年就开始了。因... 阅读全帖 |
|
|
|
q***s
发帖数: 2243 | 7 汇报一下，最后我用的QuadTree来实现的。
我的要求很简单，一个平面上，分布了很多点，用QuadTree来把不要的空间去掉，然后
就是聚类了。
谢谢各位！ |
|
q***s
发帖数: 2243 | 8 汇报一下，最后我用的QuadTree来实现的。
我的要求很简单，一个平面上，分布了很多点，用QuadTree来把不要的空间去掉，然后
就是聚类了。
谢谢各位！ |
|
g*******y
发帖数: 1930 | 9 我觉得应该也能用closest pair的思路来做吧
我感觉quadtree的思路就是closest pair的思路的二维版 |
|
f*******r
发帖数: 1086 | 10 第一轮电面通过了，之前recruiter说安排onsite
但因为我在欧洲，recruiter希望我能飞到US来onsite，
也许为了保险起见，要求进行第二轮电面，今天晚上
刚刚电面结束了。准备面试过程中一直得到板上朋友
的帮助，非常感谢！把问的问题和大家分享一下:
上来第一个问题是问我为什么对于google有兴趣?
我自己是computer graphics的PHD背景，我按照
我自己的情况和他说了一下发现google最近推出了
webGL标准的O3D SDK， 还有就是最新的3D google
map，其中我发现3D map在terrain方面感觉绘制还
需要提高，balabala。。。 这个过程大约10分钟
左右。
第二个问题是关于描述一个自己coding以来最难的
debug case。 我结合自己的背景，讲了一个自己
当时在GPU shader里面debug linear quadtree
traversal的问题。其实不是很难，不过我自己觉得是一个
有意思的问题。大约10分钟。
第三个问题是给一个simple code:
char* F()
{
char S[100 |
|
b********h
发帖数: 119 | 11 NASA有个项目叫WorldWind，但做的是3D的地图，与Google Earth相对应。如果你只要
2D的话，其实自己写一个也不是很复杂。Google Map和Bing Map都是基于quadtree的
index的，就是把整个地图在每一层分成四块，然后每块再递归的往下分，直到最基本
的解析度。 |
|
h**6
发帖数: 4160 | 12 四流学校Fresh EE PhD年底毕业，找了半年的工作终于有着落了。
微软Windows Live 59级SDE，给的是master的价：
8.1w + 0-20%bonus + $5w stock/4 years + 0.5w搬家费
网上投的简历，三周后网上测试，四周后hr电面，六周后onsite面试，七周后offer。
onsite面了五个人，第三人包括吃午饭共90分钟，其余每人60分钟。
1.C语言字符串相关问题。
1)写出strstr函数，准备好的BM算法没有用上，用的最土的O(nm)算法。
注意两点：a.不要用strlen(防止某个字符串很长)，b.只检查长度许可的部分(起始位
置为0到n-m+1)
2)在长度未知的文件中查找字符串。
2.定义无符号可变长度长整数类并实现加减乘除。
1)加法因为内存分配研究了半天，定义了分配和使用两个size而搞定；
3)乘法提到可以使用FFT，但仍然用普通方法实现。
4)除法的试商函数没有时间写了，但我说用二分法实现，面试官表示满意。
3.吃饭时未必需要参考版上的建议什么可以吃，什么不能吃。我的饮食一向比较独特，
选自己熟悉的吃就行了。吃... 阅读全帖 |
|
l******e
发帖数: 12192 | 13 答曰QuadTree。继续问如何建立平衡和自平衡四叉树，答曰如果所有点都给定，可以找
出 x 和 y 的中位数建立平衡四叉树；自平衡的就非常复杂了，建议上网看paper。
~~~~~~~~~~~~~~~~当时你是这么回答的？ |
|
h**6
发帖数: 4160 | 14 集中回复一下各位朋友：
1.微软的绿卡政策还不清楚，不过听说最近perm拒了一大批。59级SDE是很低的等级，
一般master都有这个级别，我只能指望进去慢慢升级了。
2.关于QuadTree，我确实了解不多，以前我自己实现的时候，用的是洗牌后随机顺序插
入结点的方法，以达到平衡，面试时只提到中位数法。至于自平衡，更是一无所知了，
不知larrabee是否有更好的方法。
3.股票的问题，可能我写的不够清楚。是价值5w的股票，分4年给，如果是5w股，我做
梦都笑醒了。
4.在长度未知的文件中查找字符串。每次我从文件中读取一定长度(大于等于所查找字符串长度)，然后把相邻两段合在一起查找字符串，如果没有就继续读下一段，直到文件末尾。
5.长整数四则运算问题，我是在白板上写的，并没有电子版代码，没法贴在这里了。 |
|
g**u
发帖数: 583 | 15 马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F ... 阅读全帖 |
|
S**I
发帖数: 15689 | 16 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 17 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
r*****i
发帖数: 26 | 18 和二爷说的差不多，就是搞个heap。这题我去twitter onsite时问了，当时面试官说他
prefer用quadtree做。 |
|
p*****2
发帖数: 21240 | 19
quadtree这东西第一次听说。这东西好搞吗？ |
|
p*****2
发帖数: 21240 | 20
k-d tree跟quadtree是一个东西吗？CLRS上有讲吗？ |
|
d**********x
发帖数: 4083 | 21 CLRS上至少正文没有。我只记得CLRS在讲解分治法的时候举的那个找最近点的例子里，
用了kd-tree找最近点时回溯的思想。。。当时惊为天人，后来知道了kd-tree之后发现
天下文章一大抄。
CLRS上的面并不是铺得特别开，比如说Trie都是在习题里面才出现的。所以才有人说看
CLRS不做习题不好。
至于quadtree是啥。。？如果是类似Octree的话，那和kd-tree不是一回事。简单点说
八叉树是把空间等分，而kd-tree是在每一个点处将空间一分为2，然后在该超平面两侧
找另一个维度，用median将空间再次一分为二。
说起来太抽象，有个图你一看就懂。
http://upload.wikimedia.org/wikipedia/commons/b/bf/Kdtree_2d.sv |
|
o***d
发帖数: 313 | 22 大牛高山仰止阿,这个都懂!
quadtree这种东西在2/3维几何模型上有应用,所以我总觉得太specific了 |
|
w****x
发帖数: 2483 | 23 做了一个QuadTree
struct PT
{
int x;
int y;
};
struct REC
{
POINT topLft;
POINT bottomRgt;
REC(int a, int b, int c, int d)
{
topLft.x = a;
topLft.y = b;
bottomRgt.x = c;
bottomRgt.y = d;
}
bool inRect(PT pt)
{
return pt.x >= topLft.x && pt.x <= bottomRgt.x
&& pt.y >= topLft.y && pt.y <= bottomRgt.y;
}
bool intersect(REC rect)
{
return min(bottomRgt.x, rect.bottomRgt.x) >= max(topLft.x, rect.
to... 阅读全帖 |
|
l***b
发帖数: 125 | 24 来自主题: JobHunting版 - G 家面经 quadtree...这个似乎很少考，两年前我去也被问到这个，不会还是同一个面试官吧：）
的。 |
|
p*****2
发帖数: 21240 | 25 来自主题: JobHunting版 - G 家面经
：）
你上次考的是什么题？前两天有个T的面试官说quadtree解。还不清楚应该怎么解。 |
|
m******s
发帖数: 165 | 26 来自主题: JobHunting版 - G 家面经 4个pixel全白，根据quadtree定义，应该merge成一个大的
后序遍历一次完事。。。 |
|
s*****n
发帖数: 5488 | 27 来自主题: JobHunting版 - G 家面经 楼主什么背景，这题都很难啊。
1. quadtree其实就是geohash.可以用zorder排序的。所以第一题应该是map reduce.
所有的的点来一遍就可以得到intersection
2. 双向搜是biidrectional dijistra吧。
4.最后那个其实是n-gram markov chain.里面水挺深的。简单prefix tree是不行的。
否则那么多怎么选。然后算概率还要调整。尼玛，不看书老夫早基本忘了叫什么了。没
有NLP背景这题太坑爹了。
的。 |
|
|
l***b
发帖数: 125 | 29 来自主题: JobHunting版 - G 家面经 quadtree...这个似乎很少考，两年前我去也被问到这个，不会还是同一个面试官吧：）
的。 |
|
p*****2
发帖数: 21240 | 30 来自主题: JobHunting版 - G 家面经
：）
你上次考的是什么题？前两天有个T的面试官说quadtree解。还不清楚应该怎么解。 |
|
s*****n
发帖数: 5488 | 31 来自主题: JobHunting版 - G 家面经 楼主什么背景，这题都很难啊。
1. quadtree其实就是geohash.可以用zorder排序的。所以第一题应该是map reduce.
所有的的点来一遍就可以得到intersection
2. 双向搜是biidrectional dijistra吧。
4.最后那个其实是n-gram markov chain.里面水挺深的。简单prefix tree是不行的。
否则那么多怎么选。然后算概率还要调整。尼玛，不看书老夫早基本忘了叫什么了。没
有NLP背景这题太坑爹了。
的。 |
|
|
s********i
发帖数: 145 | 33 背景：C++，本科数学，研究生改CS，偏Graphics方向
电面一轮，上来随便聊几句项目，然后问了一个C++基础，什么是pure virtual
function。之后做题，2维平面的一堆点，假设有一个在坐标原点的viewport,任给
range(eg: 30度), 问什么角度viewport可包含最多的点。我说先把点转成极坐标，然
后sort by angle, 然后再按点search。他问我search什么复杂度？我说binary search
, nlogn。他说可以做到linear，我想了一会没想到怎么做，他说那你写吧。然后就开
是写代码，发现边界的时候不太好处理，基本写废了，就差没拍桌子了...折腾时间差
不多了，人说就这样吧，有啥问题不？我问他linear的算法是啥,他说window sweep.
感觉不是很好，以为绝对挂了，结果recruiter打电话说表现很好，来onsite吧...于是
约了几周后onsite。
onsite一共5轮，3轮考基础+算法，1轮考test, 1轮考design。中午有个日本人带着吃
了个汉堡，随便聊了几句。每轮过后会留出几分钟让你问问题... 阅读全帖 |
|
f*******t
发帖数: 7549 | 34 自己找题写不行吗，来，写个quadtree merge |
|
|
|
s********u
发帖数: 1109 | 37 EPI： Elements of Programming Interviews
leetcode上面的题还是比较专注数据结构和传统算法，偏应用的少了些。
最近碰到的面经感觉epi出现率很高，
比如那道log记录每个时间段用户数的（fb），epi的14.22指出了bst的最优做法；
我自己碰到的问题，epi的14.14也有，两个BST的思路（还有quadtree和r-dtree）；
还有14.19就是view from above；
15.1是skyline。都是活生生的面试题，我感觉比起解决BST问题，很多时候带应用背景
的面试题难点更在于想到用BST，这里是打个比方，适用于各个数据结构或者算法。
还有种种，search engine啊，spell correction啊，都有。
行动吧，少年们！ |
|
l***h
发帖数: 96 | 38 上上周五去MTV onsite的，这周一HR说HC已经过了，等这周EC省材料，下周给我消息。
希望不要在最后一步出啥问题吧。
电面题目：
一位国人大哥，先在这里谢过啦，时间刚好45分钟，吐槽下Google docs上写程序好蛋
疼，什么时候可以搞个可以支持Vim的编辑器吧。。。。
Assume some binary (each pixel is either black or white ) images, have same
width and height, and the length is power of 2. Present it by quadtree:
divide the image into quarters, each quarter can be all back, all white or
mixed, subdivide the mixed ones… recurse.
+-------+---+---+
| | F | F |
| T +---+---+
| | T | T |
+---+---+---+---+
| F ... 阅读全帖 |
|
f******h
发帖数: 45 | 39 也找工作了一段时间了，从版上学了很多，上周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)... 阅读全帖 |
|
l**********2
发帖数: 5 | 40 今年在板上潜水良久，受益匪浅，特来报offer报题求指导.
先post一下现在还记得的面试题
word ladder
Minimum Window Sub-string
quadtree merge
coins permutation/combination
multiply two big number
swap bits in an integer
read4k
regular expression match
median in two sorted array
egg drop problem
remove all duplicates in place for a give array
cycle detection in linked-list
max contiguous sub-array
3sum
c++ virtual function, virtual inheritance, template partial
specialization. (I said I am 'proficient' in C++ so he said a lot in
depth)
c... 阅读全帖 |
|
z*********8
发帖数: 2070 | 41 kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google s2
library把地图分成若干cell |
|
s**x
发帖数: 7506 | 42 那个cell不是简单的分块，是用Hilbert curve 弄的。俺也不憧。
: kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google
s2
: library把地图分成若干cell
|
|
发帖数: 1 | 43 不仅要会线段树
还有会红黑树 b树 AVL树 QuadTree 带花树
加油吧 骚年们 |
|
|
r*****s
发帖数: 1815 | 45 Geohash.
quadtree一般用于碰撞检测 不是一定不可以 但是要看具体应用。 |
|
|
r*****s
发帖数: 1815 | 47 Geohash.
quadtree一般用于碰撞检测 不是一定不可以 但是要看具体应用。 |
|
F****n
发帖数: 3271 | 48 第一点，bitmap只是一种join的方式，没有说一定要用bitmap, 我只是根据你提到
bitmap引申而已。但query planner应该根据具体索引结构建立最佳方案，而不是省事
略过
第二点，如果一个Composite Index只对两个字段起作用，那么我一共要建立三个INDEX
，当然是一种浪费。我说“一般情况", 是因为存在可以单个字段上起作用的
multidimensional index, 比如一些变种的KD tree, Quadtree, R-tree都可以。 |
|
F****n
发帖数: 3271 | 49 弱问个简单都问题。。。却让我想了一阵子
之前我存地址，都是在model里分几个field，city, street, number什么的，然后做地
址搜索。可是发现这个不现实：
1. 街道会有缩写吧, 有人写street, 有写 str, 或者st的，什么ave, dr, circle就更
多了。不可能都存吧？也不可能每次搜，都parse string，把st换成street啥的。。。
- 索引和搜索之前要分析，比如不管"St."还是"Street"，Analyzer都先转换为"Street
"。搜索和索引使用统一Analyzer
2. 有可能地址输入错了，或者是个模糊地址，这样一搜搜不到了。。。
- 可以用字典（hunspell）和模糊搜索
然后，我发现google提供了个api，可是输入地址用google map搜。。。可是，又有了
新问题：
1. 这些地址，怎么存入数据库？存String呢，还是用这个string 在google maps上搜
完了之后，存 lat, lng?
- 一般是Prefix Tree for String + Quadtree/Rtree for Coo... 阅读全帖 |
|
G*****7
发帖数: 1759 | 50 no need to bother with quadtree
float / mesh_grid_size = index of containing cell |
|
