|
h****r
发帖数: 2056 | 2 你这两点都错了吧。
1.以任何一个点为起点，计算和其他任何一个点之间的角度的话无非是计算一次（Xi -
Xj）/（Yi - Yj)，第一个起点需要计算N-1次，然后逐个起点的计算量递减一次。这个怎么会需要O(NlogN)？ O（N）足以。总共N个点。O(N^2)足够完成全部计算。
2.无需排序，只要已经做过起点的点不再继续参加角度计算即可，这个第一层for loop
就会帮你解决问题。你想一下我前面提到的n阶对称矩阵就明白了。只需要计算出一个
上半或者下半矩阵的角度就结了。任何两点间的角度只会计算一次，没有重复。
), |
|
l******o
发帖数: 144 | 3 这么问你吧, N个数, 你怎么在O(N)的时间里找到重复的?
用hashset的那个方法忽略, 理由已经说过了.
你这两点都错了吧。
1.以任何一个点为起点，计算和其他任何一个点之间的角度的话无非是计算一次（Xi -
Xj）/（Yi - Yj)，第一个起点需要计算N-1次，然后逐个起点的计算量递减一次。这
个怎么会需要O(NlogN)？ O（N）足以。总共N个点。O(N^2)足够完成全部计算。
2.无需排序，只要已经做过起点的点不再继续参加角度计算即可，这个第一层for loop
就会帮你解决问题。你想一下我前面提到的n阶对称矩阵就明白了。只需要计算出一个
上半或者下半矩阵的角度就结了。任何两点间的角度只会计算一次，没有重复。
), |
|
|
l******o
发帖数: 144 | 5 此外你那个对称矩阵, 只不过是把复杂度降低一半而已, 没有从阶上得到降低.
这么问你吧, N个数, 你怎么在O(N)的时间里找到重复的?
用hashset的那个方法忽略, 理由已经说过了.
你这两点都错了吧。
1.以任何一个点为起点，计算和其他任何一个点之间的角度的话无非是计算一次（Xi -
Xj）/（Yi - Yj)，第一个起点需要计算N-1次，然后逐个起点的计算量递减一次。这
个怎么会需要O(NlogN)？ O（N）足以。总共N个点。O(N^2)足够完成全部计算。
2.无需排序，只要已经做过起点的点不再继续参加角度计算即可，这个第一层for loop
就会帮你解决问题。你想一下我前面提到的n阶对称矩阵就明白了。只需要计算出一个
上半或者下半矩阵的角度就结了。任何两点间的角度只会计算一次，没有重复。
), |
|
h****r
发帖数: 2056 | 6 呵呵，这个问题是越辩越明了。
计算出上半矩阵来，需要O(N^2)。
列出矩阵里每行里出现的重复角度需要排序，这个是O(NlogN)，N行即为O(N^2logN)。
所以复杂度是O(N^2) + O(N^2logN)，也就是O(N^2logN)。
-
loop |
|
|
S******a
发帖数: 862 | 8 不是有传说中的perfect hasing吗？
前面的面试我一直用O（1）来算hase的复杂度的。。。
求赐教
),
了。 |
|
f****e
发帖数: 30 | 9 如果1245在一条线上，245也会在一条线上，怎么才能remove redundancy? |
|
|
b******v
发帖数: 1493 | 11 这个容易，第i个点考虑过后，就把它从点集中移除 |
|
K******g
发帖数: 1870 | 12 为什么这么复杂啊，我觉得很简单啊。
随便挑一个点为原点，然后求剩下的N-1个点与x轴的夹角，把所有的夹角排序，然后不
久找出在同一条直线上的点了吗？
N-1+NlgN |
|
x****r
发帖数: 99 | 13 如果斜率无穷大也不好存。 要不不存斜率存一个pair的话，还要求最简才能
比较，如果两个都是浮点就更没发弄了。 |
|
x****r
发帖数: 99 | 14 ，，，，
经过很多点那条线很可能不经过你这个点。。。 |
|
|
f****4
发帖数: 1359 | 16 为啥都只用斜率来表示直线啊？就算斜率相同也可能是平行线啊
从N中取所有任意2天求直线，(k,y0)代表那个直线做hashtable key，value (
lineCounter,*linklist)
这里linklist 节点存储的是点对(xi,yi,xj,yj)
只要是相同直线，lineCounter++,点对放到linklist里面
然后遍历hashtable,对所有的lineCounter>3的，输出不重复的点（用个set）
就是比较费空间 |
|
w******1
发帖数: 520 | 17 不知道从哪里看到 过
存成很多个集合，集合中包含任意两个点和他们连线后的夹角。
再在这个集合中找同角度的， 有重复点的最大集合。 |
|
s********a
发帖数: 1447 | 18 Thanks for sharing!
问一下 在你的店面面经里面
google的第一题
“1.1. 输入: 一个数独的解
输出: 判断是否是成功的
”
这个输入的是什么啊？没看明白:( |
|
y**i
发帖数: 1112 | 19 今天刚收到被拒的消息，说说我自己的感受吧，一方面攒点RP，给大家做点贡献，另一
方面希望牛人能给我些建议，好让我认识到自己具体在哪里不足，好让我能有效的准备
以后可能的面试（如果有的话）。
简单说一下背景，我不是CS专业的，PhD，研究方向跟计算机完全无关，但国内大型网
络公司工作过2年，google两个月前通过（应该是）monster找到我，给我面试的机会的
。这两个月我就主要准备这个了，看了CLRS（一个帖子中小尾羊建议的部分章节），还
有就是版面题目，careercup题目看的不多，三四十道左右吧。
第一轮：
应该是个印度人，口语很难听懂，口音重，语速快，开始介绍google，5分钟吧，然后
问我的想法。我就简单说了一两句吧。然后就直接上来问题目，有序链表中删除出现次
数超过一次的元素，简单吧。我很快说了一下思路，时间O(n)，然后就是让写代码，大
概15-20分钟写了一下，其实可以更快，但是太谨慎了，怕出错，写两句翻回来又看一
句，就花了这么久。可能紧张吧，开始都忘了写return，不过自己发现了，补上去了。
然后把代码赶紧从google doc里面拷到VS里编译一下，发现一个 |
|
k*n
发帖数: 150 | 20 看前面有大牛发phd的面经，感慨万千，不一样就是不一样，同样是phd。top学校牛导
和我这样的土博差距太大了。。。
面试：
1. 老中，人很nice，英语很清楚。最后面试时间竟然超了15分钟。
－ 自己讲一个最体现problem solving technique的项目
－ merge sort，时空细节，我竟然忘了这个东西需要recursive了，一直按bottom-up
的办法讲，后来才反应过来
－ open problem，序列的异常点检测，我到最后才真正明白什么意思，答了两种办法
，我估计他更喜欢第二种，但没时间讲清楚了
2. 老美，人也很nice，英语也不快。交流没问题是我这次面试唯一的欣慰点了。
－ 他选了一个简历里的项目，讲了讲
－ java exception handling，要实现细节，我完全没有印象，只好说，如果是我设计
，会怎样怎样怎样，他再指出来哪里有问题，我再改进，讨论了半天，时间就到了
两次都没有coding，DP是白看了，苦阿。
不过老美跟我说，我的背景和他们组不match，我应该去其他组云云，会不会recruiter
再给安排重新电面呢？ |
|
m*******n
发帖数: 154 | 21 Thanks for sharing. Bless! |
|
|
|
|
x*******7
发帖数: 223 | 25 con!楼主背景？我投了三次，只有一次面试，而且问题太偏了，都是没准备到的。 |
|
t**g
发帖数: 1164 | 26 phd in applied math
可能人家看我不是CS科班出身
问的问题就比较简单吧
//幸运 :) |
|
|
|
h****b
发帖数: 157 | 29 为什么是destructor? 应该是constructor吧？ |
|
B*******g
发帖数: 1593 | 30 如果是protected/private ctor你得用Named Constructor Idiom 才能instantiate（也
许还有其他办法），那个问题的意思应该是
CLASS * a = new CLASS(); 是允许的
但是不允许
CLASS b;
b 在out of scope的时候会自动被销毁，但是dtor不是public 所以compiler会报错 |
|
s******u
发帖数: 501 | 31 但是你同样也不能用delete a来销毁这个object，容易导致memory leak
还是用factory好说话一点吧
private ctor, make it friend to factory class, use factory to instantiate/
destroy object
不过关于private dtor的这点倒是学习了，呵呵
（也 |
|
c******f
发帖数: 2144 | 32 公司和组就不说了，你们知道的。觉得最近题目都貌似很简单
第一个coding 1)给三点判断三角形的类型2)判断是不是回文 要测试，给case；
说各种sort方法，我说了包括merge sort 和 quick sort
第二个coding 1)字符数组压缩，把有序数组里重复的字符去掉
找最重的一个球的经典老问题，我说了这很经典以后，她又问了一个，忘记是什
么了，但是好像也不难，立刻能答出来
第三个coding 1)红蓝球分开的问题 2）一个数组有多少a多少b多少组连续的a多少组连
续的b
测试一个茶杯（个人认为比较诡异，当时真想说茶杯不就喝水么，能测试什么..
....但还是老实分析了）
第四个coding 1)找最近的公共祖先，不能用额外的数据结构
聊天说说自己的长处和短处实习什么的
就四轮，很奇怪，但是最后一个是经理，告诉我她就是最后一个面我的时候，我小楞了
一下。鉴于只面了4个人，不同于别人的5-6轮，还有其中两个人和我说了good luck，
内心小惴惴中~~
整体答得觉得还可以，感觉面试官也都挺好，没有出偏题怪题，比想象的简单 |
|
J*****n
发帖数: 4859 | 33 1)找最近的公共祖先，不能用额外的数据结构？？
这个什么意思？连数组都不能用？ |
|
|
s********l
发帖数: 998 | 35 bless & cong~
“红蓝球分开的问题” 这个具体问的什么啊？没google到~
.. |
|
|
c******f
发帖数: 2144 | 37 就是一堆红球蓝球的无序序列，让你红球一边 蓝球一边 板上出现很多次了呢 |
|
|
|
|
|
|
|
|
|
|
l*******m
发帖数: 18 | 47 总结的经验，写给一些朋友的。因为有朋友不认识中文，所以写的英文。
所以可能写的比较臭。。。
顺便帮小羊攒点人品，哈哈。
Some experiences in job hunting for software engineer
I will present my understanding of job hunting in this short article. I
think
there are two parts that are both important in job hunting: technique part
and non technique part. In the technique part, I mean questions answering
, white board coding. In the non technique part, I mean your preparation
of resume, communication with friends to get interview opportunities, an |
|
l****a
发帖数: 352 | 48 公司很好，position也很喜欢
希望一切顺利，拿到这个offer！
前16个回帖bless我拿到offer的都给包子，on-site完贡献面经:) |
|
|
s*********t
发帖数: 1663 | 50 攒人品， 老中面的，很友好，题目也不难
1. 描述自己做的项目
2. 实现putlong(long a)
3. C++概念
constructor, copy constructor, destructor, assignment operator
4. 说说知道的数据结构
vector, list, queue, stack, map, set...
5. 实现set
binary tree
6. 如何group anagram: stop, post, spot....
hashtable, 映射到字典序, stop-> opst, post -> opst .....
7. 自由提问
感觉答的还行，因为问的都不深，可能我背景比较差，人家也没指望太多。祝大家好运。 |
|
