m**q
发帖数: 189 | 1 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
想想主要是自己编程水平不行，不能快速的写出bug free code，另外
design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
还是无补 :(
一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
如果这个序列不是静态的，而是一个数据流，如何 处理？
2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
3) 对于google查询的词组成的动态的数据流，在任意时刻取出10个完全随机的查询。
4) 把一个字符串转换成32bit的整数
5) 在一个数组中寻找三个数，使得它们的和为0
6) 大概是用一位数组来表示二维数组，但是每一行的元素个数可以不同，实现get，
set函数
7) 已知每个待查找的字符串长度为10，如何在一个很长的字符串的序列里快速查找这
样的字符串
8) 写程序生成边长为n的如下的方阵
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
9) 应用程序的re-order的buffer的设计,如果满了可以丢弃
10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，要
么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求出
最小的包含它的多边形。
如何加速？如果在多机的情况下呢？ | g***y
发帖数: 764 | 2 6个人考了这么多题目呀
【在 m**q 的大作中提到】
: 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
: 本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
: 想想主要是自己编程水平不行，不能快速的写出bug free code，另外
: design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
: 还是无补 :(
: 一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
: 1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: 2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
| s*i
发帖数: 388 | | H**d
发帖数: 152 | 4 thanks for sharing.
pat ~ pat ~
wish u have a big offer in the future. | l****7
发帖数: 41 | | d**e
发帖数: 6098 | 6 顶风作案得好。。。
【在 m**q 的大作中提到】
: 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
: 本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
: 想想主要是自己编程水平不行，不能快速的写出bug free code，另外
: design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
: 还是无补 :(
: 一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
: 1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: 2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
| f*****w
发帖数: 2602 | | g*********s
发帖数: 1782 | 8 super zan!
【在 m**q 的大作中提到】
: 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
: 本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
: 想想主要是自己编程水平不行，不能快速的写出bug free code，另外
: design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
: 还是无补 :(
: 一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
: 1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: 2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
| S*********r
发帖数: 5693 | 9 再次验证了我说的话，人家根本不在乎你牛不牛，题海战术出来的就行。
【在 f*****w 的大作中提到】
: 靠 好难得题目阿... 吐血了
| t****o
发帖数: 31 | | | | b***e
发帖数: 1419 | 11 强顶！
建议一下，为了保护自己，远离傻逼：
1. 尽量少提供无关信息，如几个人面试。
2. 尽量避免公司全称。G即可。
3. 题目可以打乱顺序。 | g*********s
发帖数: 1782 | 12 先安慰一下楼主。你遇到的题挺难的。
发信人: maxq (zf), 信区: JobHunting
标 题: google全程面试题目，顺求安慰。。。
发信站: BBS 未名空间站 (Tue Mar 22 00:34:25 2011, 美东)
1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18] | A**y
发帖数: 62 | 13
把所有数穿起来排序，保留左右信息，一旦碰到重复的就合并range,O(NlogN)
用一个buffer先排序合并再和前面的合并 ?
reservior sampling
如果两正一负，对每一个负数取绝对值，然后在所有正数里找和等于此数的两个
同理对两负一正的情况
分正负 O(N), 找数 O(N)*O(NlogN+N), 总共O(N^2 logN)
有没有更多信息？多边形怎么表示？
【在 m**q 的大作中提到】
: 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
: 本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
: 想想主要是自己编程水平不行，不能快速的写出bug free code，另外
: design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
: 还是无补 :(
: 一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
: 1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: 2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
| t****o
发帖数: 31 | 14 我觉得多边形覆盖的问题可以抽象为一个树的结构，地球作为根节点，仅被地球包含的
多边形作为根节点的子节点，依次递归建立树。找一个包含给定多边形的最小多边形就
变成找一个给定节点的父节点了 | g*********s
发帖数: 1782 | 15 其实公司名称也可跳过。有些题我看公司之间也抄来抄去。
基本上看难度特征就知道了。最难的肯定是G，F，A。A一般有设计题。
【在 b***e 的大作中提到】
: 强顶！
: 建议一下，为了保护自己，远离傻逼：
: 1. 尽量少提供无关信息，如几个人面试。
: 2. 尽量避免公司全称。G即可。
: 3. 题目可以打乱顺序。
| g*********s
发帖数: 1782 | 16 这个方法好。
【在 t****o 的大作中提到】
: 我觉得多边形覆盖的问题可以抽象为一个树的结构，地球作为根节点，仅被地球包含的
: 多边形作为根节点的子节点，依次递归建立树。找一个包含给定多边形的最小多边形就
: 变成找一个给定节点的父节点了
| g***s
发帖数: 3811 | 17 用一个buffer先排序合并再和前面的合并 ?
using BST. | g*l
发帖数: 385 | 18 安慰一下． 你的题不容易． 哪里面的，总部？
【在 m**q 的大作中提到】
: 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
: 本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
: 想想主要是自己编程水平不行，不能快速的写出bug free code，另外
: design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
: 还是无补 :(
: 一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
: 1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: 2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
| g***s
发帖数: 3811 | 19 10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，要
么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求出
最小的包含它的多边形。 | b******n
发帖数: 4509 | 20
对新加入的 interval 范围再合并
用一个marker来分隔每行即可
rabin karp
先把多边形画出二维地图，之后就容易了
【在 g*********s 的大作中提到】
: 先安慰一下楼主。你遇到的题挺难的。
: 发信人: maxq (zf), 信区: JobHunting
: 标 题: google全程面试题目，顺求安慰。。。
: 发信站: BBS 未名空间站 (Tue Mar 22 00:34:25 2011, 美东)
: 1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
| | | s*******d
发帖数: 4135 | 21 在一个数组中寻找三个数，使得它们的和为0
这题是不是可以这么做：
step1: sort them all O(nlogn)
step2: pick the first element, then in the remaining elements, find two of
them that sum is equals to 0- first element O(n), apply this to all the
other elements O(n2)
total is O(n2) + O(nlogn) = O(n2) | W**********r
发帖数: 8927 | 22 Google的考官自己也没有做出来，正等着哪个面试的提供解题思路呢，呵呵
【在 f*****w 的大作中提到】
: 靠 好难得题目阿... 吐血了
| g**e
发帖数: 6127 | 23 差不多就是这个意思 O(n^2)
【在 s*******d 的大作中提到】
: 在一个数组中寻找三个数，使得它们的和为0
: 这题是不是可以这么做：
: step1: sort them all O(nlogn)
: step2: pick the first element, then in the remaining elements, find two of
: them that sum is equals to 0- first element O(n), apply this to all the
: other elements O(n2)
: total is O(n2) + O(nlogn) = O(n2)
| W**********r
发帖数: 8927 | 24 从题意可以看出来，没有这么一个现成的树，那你有必要和怎么建这个树？每个可能有很多Children，还必须是双向链接，否则要遍历寻找，要费多少空间呢？
【在 t****o 的大作中提到】
: 我觉得多边形覆盖的问题可以抽象为一个树的结构，地球作为根节点，仅被地球包含的
: 多边形作为根节点的子节点，依次递归建立树。找一个包含给定多边形的最小多边形就
: 变成找一个给定节点的父节点了
| c**j
发帖数: 103 | | h**********d
发帖数: 4313 | 26 难死了，楼主也别放弃，google的面试真的是最难的，下次不会有这么难的了 | g***s
发帖数: 3811 | 27 有很多
Children，还必须是双向链接，否则要遍历寻找，要费多少空间呢？ | g***s
发帖数: 3811 | 28 很经典的一道题
http://en.wikipedia.org/wiki/3SUM
of
【在 s*******d 的大作中提到】
: 在一个数组中寻找三个数，使得它们的和为0
: 这题是不是可以这么做：
: step1: sort them all O(nlogn)
: step2: pick the first element, then in the remaining elements, find two of
: them that sum is equals to 0- first element O(n), apply this to all the
: other elements O(n2)
: total is O(n2) + O(nlogn) = O(n2)
| f*****w
发帖数: 2602 | | s*******d
发帖数: 4135 | 30 3) 对于google查询的词组成的动态的数据流，在任意时刻取出10个完全随机的查询。
这个题是用reservior sampling么？ | | | g***s
发帖数: 3811 | 31 yes.
【在 s*******d 的大作中提到】
: 3) 对于google查询的词组成的动态的数据流，在任意时刻取出10个完全随机的查询。
: 这个题是用reservior sampling么？
| m**q
发帖数: 189 | 32 谢谢大家的安慰...板上的面经还是很有用的，可惜我面了
一多半才开始看，早点看就好了，呵呵
9，10两个题目原来写的不清楚，我刚刚改了原帖。
第一题我主要的问题是如果发现新的range包含多个已有的range
的时候怎么对树结构进行操作，一直没有什么好的思路。
大牛们指点下？
【在 m**q 的大作中提到】
: 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
: 本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
: 想想主要是自己编程水平不行，不能快速的写出bug free code，另外
: design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
: 还是无补 :(
: 一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
: 1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: 2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
| m**q
发帖数: 189 | 33 恩，可以用二维数组，直接顺时针填充就行了
【在 f*****w 的大作中提到】
: 生成方阵那个允许用个大数组存结果么？
| s******c
发帖数: 1920 | 34 大牛能不能详细说一下这一题呀？
【在 g***s 的大作中提到】
: 很经典的一道题
: http://en.wikipedia.org/wiki/3SUM
:
: of
| g***s
发帖数: 3811 | 35 1. Avl tree
2. Search by the min num of the range
3. If it is in another range, merge them ; otherwise add a new node for the
range.
4. Check and merge the node(in 3) and the next larger node. Merge: remove
the large node and merge the range to current node. Util no overlap.
谢谢大家的bless...板上的面经还是很有用的，可惜我面了一多半才开始看，早点看就
好了，呵呵9，10两个题目原来写的不清楚，我刚刚改了原帖。第一题我主要的问题是
如果发现新的r........
★ Sent from iPhone App: iReader Mitbbs 6.0 - iPhone Lite
【在 m**q 的大作中提到】
: 恩，可以用二维数组，直接顺时针填充就行了
| g***s
发帖数: 3811 | 36 你要研究小于n^2的解？
前人研究的结果：
http://citeseerx.ist.psu.edu/viewdoc/download?
doi=10.1.1.128.7817&rep=rep1&type=pdf
【在 s******c 的大作中提到】
: 大牛能不能详细说一下这一题呀？
| Y**N
发帖数: 2628 | 37 lz你发帖要小心了，应该是不可以把面试题这样透露出来的。最好删掉以免招来大麻烦。
【在 m**q 的大作中提到】
: 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
: 本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
: 想想主要是自己编程水平不行，不能快速的写出bug free code，另外
: design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
: 还是无补 :(
: 一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
: 1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: 2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
| b***1
发帖数: 668 | 38 I warn you: If you do not delete this post, I will report your name to
Google HR Department. You violated Google's NDA policy which you have signed when you were interviewed by Google. I give you a chance... | b***1
发帖数: 668 | 39 I warn you: If you do not delete this post, I will report your name to
Google HR Department. You violated Google's NDA policy which you have signed
when you were interviewed by Google. I give you a chance... | s**********t
发帖数: 291 | 40 不懂
【在 m**q 的大作中提到】
: 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
: 本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
: 想想主要是自己编程水平不行，不能快速的写出bug free code，另外
: design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
: 还是无补 :(
: 一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
: 1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: 2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
| | | g********x
发帖数: 4671 | 41 I warn you: If you do not delete this post, I will report your name to
Google HR Department. You violated Google's NDA policy which you have signed
when you were interviewed by Google. I give you a chance... | M********G
发帖数: 1207 | 42 You forgot to translate it to Chinese.....
signed
【在 g********x 的大作中提到】
: I warn you: If you do not delete this post, I will report your name to
: Google HR Department. You violated Google's NDA policy which you have signed
: when you were interviewed by Google. I give you a chance...
| z***m
发帖数: 1602 | | m***e
发帖数: 991 | 44 这个鱼虫是谁啊，这么多人跟他有仇? 哪个路过的好心人给解释一下？
几天不来MIT，就out啦。
signed
【在 g********x 的大作中提到】
: I warn you: If you do not delete this post, I will report your name to
: Google HR Department. You violated Google's NDA policy which you have signed
: when you were interviewed by Google. I give you a chance...
| k********e
发帖数: 702 | | L******r
发帖数: 33 | 46 老兄，
你知道外国人在他们的网站上也分享这些信息吗？看名字，老印，老白都有，他们的道
德比我们高吗？你再看一些一些此类面试书籍的开头里都说，“他认识一个人，all
the way best，面试没有被录因为没有买他的书，巴拉巴拉，。。。”你知道ICC是怎
么生存的吗？你知道Oracle里面都是印度大妈拿着高薪，你知道白人什么都不懂，过几
年却当了你的Manager？你知道Suncor（加拿大一石油公司）里面一个普通白人，拿26
万每年。他可能才是技校毕业（SAIT)。中国人可能吗？现在招人考这些和工作不相关
的东西，和写茴香豆豆没多大区别，这种体制早就出问题了，他们忽悠我们，我们不要
被他们忽悠了。你这样做不是自废武功吗？中国人很多人不爱看英文网站，我也是，很
吃亏，消息渠道本来就少，你这样做，不是让大家添堵吗？
signed
【在 g********x 的大作中提到】
: I warn you: If you do not delete this post, I will report your name to
: Google HR Department. You violated Google's NDA policy which you have signed
: when you were interviewed by Google. I give you a chance...
| u*******o
发帖数: 405 | 47 我觉得这道题是在迷惑人（如果我理解对了的话）。实际上跟多边形没多大关系，也不
用建树（建树就要sort, sort就是nlog(n))。这就是一个找max值问题的变形。根据题
，所有poly或者包含，或者不重叠，那么其实你关心的所有poly都是包含given poly的
，所以他们肯定互相包含，不会互不重叠。这样所有的candidate（也就是包含given
poly的所有poly)是单调包含的。
设A>B表示A包含B，那么算法如下
min=null
foreach poly
if poly > given_poly and (min = null or min > poly)
then min = poly
return min
这个算法是O(n)的
多机就把整个集合分成n块，然后每块上面运行上面的算法，最后reduce就可以了。不
过多机永远没法降低时间复杂度的级别。
the
remove
【在 g***s 的大作中提到】
: 1. Avl tree
: 2. Search by the min num of the range
: 3. If it is in another range, merge them ; otherwise add a new node for the
: range.
: 4. Check and merge the node(in 3) and the next larger node. Merge: remove
: the large node and merge the range to current node. Util no overlap.
:
: 谢谢大家的bless...板上的面经还是很有用的，可惜我面了一多半才开始看，早点看就
: 好了，呵呵9，10两个题目原来写的不清楚，我刚刚改了原帖。第一题我主要的问题是
: 如果发现新的r........
| g***s
发帖数: 3811 | 48 你跟我说的不是同一题
【在 u*******o 的大作中提到】
: 我觉得这道题是在迷惑人（如果我理解对了的话）。实际上跟多边形没多大关系，也不
: 用建树（建树就要sort, sort就是nlog(n))。这就是一个找max值问题的变形。根据题
: ，所有poly或者包含，或者不重叠，那么其实你关心的所有poly都是包含given poly的
: ，所以他们肯定互相包含，不会互不重叠。这样所有的candidate（也就是包含given
: poly的所有poly)是单调包含的。
: 设A>B表示A包含B，那么算法如下
: min=null
: foreach poly
: if poly > given_poly and (min = null or min > poly)
: then min = poly
| u*******o
发帖数: 405 | 49 好吧我说的是第10题
【在 g***s 的大作中提到】
: 你跟我说的不是同一题
| C*********5
发帖数: 420 | | | | T******T
发帖数: 3066 | 51 这哪儿蹦出来个自以为是的？ 还自爆家们。。晕了，google都这些
EQ 欠缺的家伙，谁TMD去啊，去了也是被国人背后捅刀子。
signed when you were interviewed by Google. I give you a chance...
【在 b***1 的大作中提到】
: I warn you: If you do not delete this post, I will report your name to
: Google HR Department. You violated Google's NDA policy which you have signed
: when you were interviewed by Google. I give you a chance...
| T******T
发帖数: 3066 | 52 靠！被骗了，错过了那个google 男的大坑，否则一定上去臭骂一顿。
【在 T******T 的大作中提到】
: 这哪儿蹦出来个自以为是的？ 还自爆家们。。晕了，google都这些
: EQ 欠缺的家伙，谁TMD去啊，去了也是被国人背后捅刀子。
:
: signed when you were interviewed by Google. I give you a chance...
| s********8
发帖数: 264 | | n*****t
发帖数: 22014 | | r*******n
发帖数: 3020 | 55 10
input: all_poly = set(p1, p2, p3, ..., pn)
p is a given poly.
output: minimum poly that contain p.
step1:
result = set()
for each in all_poly:
if each contain p:
then put it in result.
step2:
Since any p1, p2 in result, either p1 contain p2 or p2 contain p1
take any two polys, assume p1 and p2,
if p1 contain p2, then remove p1 out of result,
otherwise remove p2 out of result.
until there is only one poly in result,
return that.
two steps all can be done with divide and conque.
【在 m**q 的大作中提到】
: 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
: 本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
: 想想主要是自己编程水平不行，不能快速的写出bug free code，另外
: design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
: 还是无补 :(
: 一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
: 1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: 2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
| p*****a
发帖数: 147 | 56 这题正解是什么？
- 树结构，O(lgn), how to build tree? 怎么用二分加速？
- 矢量乘法？
- scan all polys, find the min poly that contains the given poly. O(n), easy
to understand and divide to multiple machines.
10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，
要么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求
出最小的包含它的多边形。已知有现成的函数可以判断两个多边形是否相互包含，
iscontained(poly p1, poly p2)。
如何加速？如果在多机的情况下呢？
=> 可以用树结构表示包含的关系。
可以用二分搜索做加速。
多机的话可以range一个机器处理一个区域，另外要考虑前端处理机的负载不要成为瓶
颈，所以让每个机器自己判断此多边形是否包含。
【在 m**q 的大作中提到】
: 恩，可以用二维数组，直接顺时针填充就行了
| L********n
发帖数: 930 | 57 Sick? ! Ghost!
signed when you were interviewed by Google. I give you a chance...
【在 b***1 的大作中提到】
: I warn you: If you do not delete this post, I will report your name to
: Google HR Department. You violated Google's NDA policy which you have signed
: when you were interviewed by Google. I give you a chance...
| h**********8
发帖数: 267 | | P**********c
发帖数: 3417 | 59 题目总体上太难了吧，很难复习到，也很难现场想到最佳解法。
【在 m**q 的大作中提到】
: 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
: 本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
: 想想主要是自己编程水平不行，不能快速的写出bug free code，另外
: design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
: 还是无补 :(
: 一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
: 1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: 2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
| a********m
发帖数: 15480 | 60 赞。也注意保护自己。
g号称录取/申请比例是0.1-0.4%,能过电面也很不错了。还有除了算法外，bug free
code确实很重要。 | | | b*******y
发帖数: 2048 | | t********3
发帖数: 567 | 62 都是难题啊，楼主很不容易了，为啥有人这么反感讨论题目呢，大多数题目远远难于真
正的工作需要，何必为难别人呢 | k*j
发帖数: 153 | 63 哪位同学说一下第六题怎么做？多谢
6) 大概是用一位数组来表示二维数组，但是每一行的元素个数可以不同，实现get，
set函数 | P**********c
发帖数: 3417 | 64 我觉得可以定义一个array n
n[0]=0;
n[i]=n[i-1]+length(row[i-1]) for 1<=i
那样a[x][y]就是a[n[x]+y]
【在 k*j 的大作中提到】
: 哪位同学说一下第六题怎么做？多谢
: 6) 大概是用一位数组来表示二维数组，但是每一行的元素个数可以不同，实现get，
: set函数
|
|
