x******3
发帖数: 245 | 1 看看这样行不
把所有点按照x或者y坐标排序，比如说按照x坐标排序， 然后找到x坐标的median， 划
条垂直线 |
|
a***g
发帖数: 234 | 2 这个不就直接bisection么
没有其他条件么
(0
the |
|
r****o
发帖数: 1950 | 3 呵呵，如果所有的点都排在你想找的那条Median线上，这方法就不灵了。 |
|
r****o
发帖数: 1950 | 4 一个例子
(-1,0), (1,0), (2,0), (0,-1), (0,1), (0,2) |
|
|
d*******8
发帖数: 785 | 6 那就在这条Median线上找它的Median，然后把这条线以这个Median为中心转一个很微小
的角度..... |
|
|
l********k
发帖数: 613 | 8 这样可以不可以呢？
先随便画一条线，把每个点投影到这条线上面，
如果所有的投影点在线上不重合，那在最中间的两个投影之间划一条垂线，这条垂线肯
定将所有的点分成两个部分；
如果有投影点重合的，就把这条线转一个小角度，直到没有重合的投影点。
(0
the |
|
r****o
发帖数: 1950 | 9 我也不知道怎么搞定，看来这题没这么简单。
呼唤高人。 |
|
x******3
发帖数: 245 | 10 仔细想想，如果所有点都已经给定， 旋转一下是可以的，就是实现起来不那么简洁，
哪位大侠给个elegant的解法 |
|
g*******y
发帖数: 1930 | 11 数学上来讲，旋转任意小一个角度，总能保证两边点数相等的...
， |
|
|
g*******y
发帖数: 1930 | 13 从写程序上来讲，找到那条线后，找到转轴后，可以扫描所有其他不在这条线上的点，
算出夹角，得到一个
最小的夹角，那么该直线只要转动角度小于这个最小夹角不就行了，总共也就是O（N）
的复杂度吧
， |
|
g*******y
发帖数: 1930 | 14 线上的若干点的median位置
比如第一次你是按所有点的y坐标划分出一条水平线 y=y0
那么这次就用x坐标找在y=y0线上的所有点的median x0 |
|
|
g*******y
发帖数: 1930 | 16 补充一点的就是
其实两次分别找y0 x0并不是找median |
|
|
|
g*******y
发帖数: 1930 | 19 说错了，第一次找y0是所有y坐标的median
第二次找x0不一定是median，取决又有多少个点在直线上面，多少在直线下面... |
|
r****o
发帖数: 1950 | 20 是不是先找到y=y0,
然后再判断多少点在y=y0上方，多少点在y=y0下方，多少点刚好落在y=y0上，
然后再决定x0怎么找? |
|
k***e
发帖数: 556 | 21 哈哈 this may not work when all points formed a cross |
|
g*******y
发帖数: 1930 | 22 why？这个方法找出来的是过cross中心的一条斜线啊，不正好吗 |
|
k***e
发帖数: 556 | 23 i am not sure i totally get your method
my only concern is how you make sure exactly half points are on each side of
the line.
we can make sure for this when the slope of the line we will choose is not
equal to all the n(n-1)/2 slopes we can get from the n points |
|
|
|
y**i
发帖数: 1112 | 26 今天刚收到被拒的消息，说说我自己的感受吧，一方面攒点RP，给大家做点贡献，另一
方面希望牛人能给我些建议，好让我认识到自己具体在哪里不足，好让我能有效的准备
以后可能的面试（如果有的话）。
简单说一下背景，我不是CS专业的，PhD，研究方向跟计算机完全无关，但国内大型网
络公司工作过2年，google两个月前通过（应该是）monster找到我，给我面试的机会的
。这两个月我就主要准备这个了，看了CLRS（一个帖子中小尾羊建议的部分章节），还
有就是版面题目，careercup题目看的不多，三四十道左右吧。
第一轮：
应该是个印度人，口语很难听懂，口音重，语速快，开始介绍google，5分钟吧，然后
问我的想法。我就简单说了一两句吧。然后就直接上来问题目，有序链表中删除出现次
数超过一次的元素，简单吧。我很快说了一下思路，时间O(n)，然后就是让写代码，大
概15-20分钟写了一下，其实可以更快，但是太谨慎了，怕出错，写两句翻回来又看一
句，就花了这么久。可能紧张吧，开始都忘了写return，不过自己发现了，补上去了。
然后把代码赶紧从google doc里面拷到VS里编译一下，发现一个 |
|
j**l
发帖数: 2911 | 27 呼唤小尾羊吧，他以前见过那篇传说中的paper。
关键词：Inshuffle in-place linear algorithm
不过这背后有些复杂的数论知识，作为面试要求过高。一般你知道那个n*logn的方法也
就够用了。 |
|
j**l
发帖数: 2911 | 28 http://www.mitbbs.com/article_t1/JobHunting/31563337_0_1.html
三江口内，风浪不息，铁索连舟，如履平地。
这是小尾羊同学Google最终面的一道经典题目
核心思想就是，先合后分。
先平凡复制整个链表，不考虑random指针。
充分利用random指针和next指针，把原始链表和复制的链表这两个链表关联起来。传说
中有两种连接法：一种是串成长度为2倍的新链表(类似一串珍珠)，另一种是两个平行
但在竖直方向对应节点相连的链表（类似横着的梯子)
不管哪种连法，都可以方便的给random指针赋值。
然后不要忘记把两个链表的关联断开，成为两个一样的独立链表。 |
|
j**l
发帖数: 2911 | 29 我以前有帖子讲了几种解法，小尾羊补充了一下
第一种解法是利用前序+中序(或者中序+后序)来重建。我当时提出了这个方法，但是没
有复习，忘记了怎么重建，失败。
第二种解法是利用一个一维数组来存储，也就是存储完全二叉树或者堆的那种方式，但
是对普通二叉树会严重浪费空间。我当时也提到了这种方式，但是描述不清晰，面试官
没有听懂。
第三种解法是对第二种方法的改进，适合存储普通二叉树。实际上是用了三个数组，一
个数组用来存节点信息，此外引入了L和R两个辅助数组来指示每个节点的左右孩子
第四种方法是对第一种方法的改进，只需要一个前序(或者中序，或者后序)就可以了，
但是对NULL,也要用特殊的符号输出标示，作为delimiter
我想只有提到了全部四种，而且会编写第一种和第四种方法重构的代码，才算完美解答
了这道题 |
|
j**l
发帖数: 2911 | 30 方法一DP确实不行，小尾羊说要用suffix tree做。
方法二的那个DP, 暂时没看出有什么问题。
对这道题，二重循环也够用了，DP可能是牛刀 |
|
m******9
发帖数: 968 | 31 如果6月份毕业，没有opt的话，只有2个月的grace period，status只能维持到8月份呢。 有opt了，就没有问题了。 不知道我的理解是不是错的。
小尾羊还是要详细咨询一下。 |
|
l********y
发帖数: 593 | 32 bless，小尾羊来了3年拿了两个master啊？还找到工作了，不错不错
最坏也就是回国玩两个月再回来上班嘛，放松点 |
|
m******9
发帖数: 968 | 33 好希望小尾羊这个事情能尽快的完满解决。
另外，请问满老，我在精华区里面翻出了一个帖子，好像还是你以前整理的，他是这样
说的：
下面分两种情况来谈H-1B的生效方式和OPT的关系。
一、
如果你的I-20的有效日期或者有效日期＋60天grace period能够cover到H-1B生效之日，
也就是说，你可以在美国连续合法居留，
则无论OPT如何处理，
你的H-1B批复都会附有新的I-94，属境内生效；
二、
如果你的I-20的有效日期＋60天grace period不能cover到H-1B生效之日，
你就要借助OPT来cover这个GAP了。
则又可细分出甲、乙两种情况：
情况甲
如果你申请H-1B的时候，OPT已经批准，
则这个GAP肯定能够被cover，
你的H-1B批复会附有新的I-94，属境内生效；
情况乙
如果USCIS批准你的H-1B申请的时候，OPT仍然处于pending状态，
由于这段GAP还没有被cover，
你的H-1B批复就不会附有新的I-94，属境外生效，
你就必须出境，到驻外美领馆拿到H-1B visa stamp来激活你的H-1B status.
帖子地址： |
|
f********i
发帖数: 563 | 34 patpat，安慰一下
小尾羊今年和美国移民局犯冲，去拜拜佛吧：） |
|
g*******y
发帖数: 881 | 35 小尾羊别烦，好事多磨阿～会顺利解决的，加油！！
还请满老给补补课阿，是不是H1B办好后，学生身份就自动取消了阿？那是不是每个学
生都应该在申请H1B之前，把OPT办好呢？ |
|
|
x******e
发帖数: 1428 | 37 刚刚看小尾羊的帖子说到这个问题，看起来好像是H1B生效之后就自动结束F1身份了。
在10月1号H1B生效以前应该OPT就是有效的吧。
一起申技术上是没有问题的，好像很多人这样做。
Good luck~
都可以申H1B了啊，羡慕一下……
我马上就无业游民了…… |
|
c******f
发帖数: 2144 | 38 之前看到小尾羊的帖子。我申请的OPT8月15日生效 是不是等我拿到OPT卡以后再申请
H1B比较保险？那么8月15日再申请H1B还来得及么？ 在什么情况下能保证OPT不会被影
响？ |
|
|
t******e
发帖数: 1293 | 40 OPT还没有拿到，还是initial view
不会cancel的，USCIS出了一个什么备忘录的东西，学校的ISO和CBP都拿到
这份备忘录。可以在网上搜别的学校ISO的说明，我看了好像duke和columnbia有
新的备忘录。小尾羊，你学校的那份是旧的，其实不会cancel。
一般来说，CBP可能会额外查看你的OPT receipt (offer letter，如果他们要的话) |
|
P*******7
发帖数: 55 | 41 已面试facebook, bloomberg, linkedin三家，都拿到offer。在本版收益很多，特来回
馈。
背景：12月-4月找faculty全军覆没，5月份开始准备工业界面试，花了近1个月时
间将本版1万
多帖子过了一遍，发现绝大部分面试题都不出其中，非常有用。这里补充一些自己遇见
的题目：
推荐“A Collection of Dice Problems”,面试facebook时遇到不少概率题，都不超出
这篇文
章的思路和难度。
Lock-free algorithms。推荐
http://www.ibm.com/developerworks/java/library/j-jtp04186/index.html
Bloomberg题目较容易，比如一个数组只有0，1两个数字，如何O(n)time, O(1)space排
序。但
同样思路的题目在facebook就变成一个数组有k个不同数字,假设k是常数，如何O(n)
time,
O(1)space排序，现场写出程序还是很麻烦。
另外小尾羊曾总结O(nlgn)的算法找出最长增长序列，面试中有遇到。
排序和binary sear |
|
|
a*****p
发帖数: 189 | 43 我也赞同小尾羊的看法，版上的潜水大牛还是很厉害的，非我等可比。
不过大家报个平常心吧，毕竟不是人人都是牛人的，战胜自己最重要。
不知道在哪里听到这样一句：男人不挣有数字的钱！
共勉 |
|
|
I**A
发帖数: 2345 | 45 开什么玩笑
当然是cong着再说
小尾羊就是补了第二次就拿到了
你也是一样的。
我19号
那天应该是好日子吧。 :) |
|
|
|
|
d**e
发帖数: 6098 | 49 本版算法牛人小尾羊同学好像也是物理毕业的，横扫各大公司。 |
|
|
