f*****e
发帖数: 2992 | 1 Q3用凸包比较好做，记录polar angle和distance。也只要O(N^2) |
|
|
A***o
发帖数: 358 | 3 luckynoob gave an answer to Q2, not repeating ,,, |
|
s*******r
发帖数: 2697 | 4 差距啊 极坐标我现在也只记得一个名词了 回去复习去! |
|
s*******r
发帖数: 2697 | 5 嗯 我的思路也是这样 不过没有你想的这么细
可能口语不行吧 烙印都没耐心听我把坐标系建立完
these
to
of |
|
l*******b
发帖数: 2586 | 6 电面时间不多呀, 这个坐下来自己想肯定能搞清楚的, 面起来就不好说了, 感觉. |
|
|
r*********n
发帖数: 4553 | 8 Q2 idea
显然坐标系不是唯一的，
让第一个点是原点（0,0,0）
让第二个点在x axis上面，这样第二个点的坐标是(d12,0,0)，同时确立了x axis的方向
让第三个点在x-y平面上面，这样第三个点的坐标可以表示为(x3,y3,0)，通过d13,d23
解一个2元2次方程，并让y3取正值，这样相当于确立了y-axis方向（如果y3取负值，y-
axis就反向而已）（这里有个细节，如果1，2，3三个点在同一线上，那么是无法确立y
axis，这个时候就要找下面一个点了）
有了x axis和y axis，z axis就自动确立了。
剩下来的点的坐标假设为(a,b,c)，通过列方程求解。 |
|
p****e
发帖数: 3548 | 9 Q2估计老印也觉得不适合作为面试题，就move on了 |
|
r*********n
发帖数: 4553 | 10 Q3 idea
通过Q2，我们可以从M1，M2算出每个点在两个坐标系的坐标。通过M1算出来的坐标是ui
，i = 1, ..., n，同理通过M2算出来的坐标是vi。Q3实际上等同于问有没有线性变换
把一个坐标系换成另外一个坐标系，or equivalently does there exist a matrix A
such that
A*ui = vj for some i,j = 1,...,n
A represents rotation and the translation (means swap of indices?) is
captured by the the fact i,j could be different.
但是这个怎么解，还没想出来。
LZ面的职位不是纯码工吧 |
|
|
s*********l
发帖数: 103 | 12 Q3:
求和，平方求和，三次方求和，...
或者 每项d_(ij)换成exp(-d_(ij)*d_(ij)/sigma), 任取sigma, 再求和，
如果对两个矩阵用以上的运算得到的和都一样的话，可以肯定两个点集是isometry(旋
转平移)
Keywords: euclidean distance matrix, isometry-invariant |
|
s*********l
发帖数: 103 | 13
或者检查两组特征值是否一致，不过复杂度(N^3)应该比上面的求和复杂度(N^2)高。 |
|
a******g
发帖数: 19 | 14 请问面的是什么职位，是SE吗？还是他家data scientist也是这么面？谢谢了 |
|
c********t
发帖数: 5706 | 15 弱问一下Q3，就算所有distance都一样，也不一定是相同点集合啊
极端一点
矩阵M 0 1
矩阵N 0 1
M和N能代表相同两个点吗？ |
|
|
|
g*******s
发帖数: 2963 | 18 Q3我也有同样的疑问。
distance矩阵只包含local信息。就算M1 M2完全一样，也只是说明可能两个set组成的
多边形形状一样。 你对这个多边形做任意旋转或平移M都不会变把？ |
|
w*********m
发帖数: 4740 | 19 Q2, multiscaling problems in data mining
Q3, first do Q2, then compute its eigen values, eigen vectors, and new
coordinates projected to the new eigen vectors by SVD.
if sorted eigen values different, different
else if sorted eigen vectors different, different
else if sorted new coordinates different, different
else same |
|
|
H****r
发帖数: 2801 | 21 Q1 输入是valid sentence么？ Reverse 后是不是需要改大小写？ “Good is it"?
有标点符号的情况呢？ "Good, is it?" reverse => "It is, good?" or "?It is ,
Good" or "It is good" or "it is Good"? |
|
p***l
发帖数: 586 | 22 原计划后天onsite。今天告诉我取消了。。。。。。：（
明天F家onsite，求bless～ |
|
|
|
|
|
|
P*******y
发帖数: 168 | 28 一共两轮，通过LinkedIn找人内推拿到的面试。
第一轮：美国人
1. three sum，很快给了n^2的解，然后问nlogn的解，提示说用hash_map，想了一会儿
想不出来，然后就move on下一题。后来到版上问发现被忽悠了，应该不存在nlogn的解
2. 2G 大文件，RAM只有1G，怎么sort。
3. 一个image，每个pixel一个颜色。给你其中一个pixel的位置，以及一个颜色，如果
那个pixel颜色和给的一样，什么都不用做，如果不一样，就把这个pixel变成给定的颜
色，同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再
neighbor的neighbor这样下去。给了思路，没让写code，说我肯定写得出，然后就结束
了。
他家recruiter效率很高，结束后一个多小时就通知过了，安排第二轮。
第二轮昨天，一个三姐，迟到了十分钟。recruiter原来邮件里有说如果面试官十分钟
内没来，给她说一下。十分钟刚到，给recruiter发了邮件，三姐就打过来了。就开始
面了。
1. 给个时间，string格式，比如10:35，让你求时... 阅读全帖 |
|
|
|
|
|
p*****2
发帖数: 21240 | 33 中间大两头小但是并不是sorted呀。能用bs吗？ |
|
|
|
r*******6
发帖数: 99 | 36 谢谢分享。"同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再 |
|
P*******y
发帖数: 168 | 37 是sorted,从左边到高点递增，然后再递减这样。这一题安静了想了一两分钟，给了她
方法
跟传统的rotated sorted array有点像，但是判断哪边混合的哪边单调的方法不太一样 |
|
P*******y
发帖数: 168 | 38 不用这样的，直接找中间，然后判断中间的右边那个是大是小就知道两边的情况了
然后就可以找其中一边BS |
|
P*******y
发帖数: 168 | 39 嗯，就是做BFS，不过要mark visit过的点 |
|
l****i
发帖数: 2772 | 40 我怎么觉得不需要mark visit过的点。因为在BFS的同时，修改了点的颜色。 |
|
j*****y
发帖数: 1071 | 41 比如是 1 2 4 0, 要搜索 0
第一次 中间的数字是 2， 这个时候怎么确定哪边搜索呢 ? |
|
|
s*****1
发帖数: 134 | 43 bless~
先Binary Search找最大数，再两个单调递增或递减的binary search找那个值 |
|
P*******y
发帖数: 168 | 44 找到2，然后看右边是4，右边比中间大，说明右边是混合的，左边是单调递增的
然后就把你的target和左边范围比较，如果在左边里，就找左边，反之，找右边
这是当时写的代码：
if(A[mid] > A[mid+1]){
if(target < A[mid] && target >= A[end])
return search(A, mid+1, end);
else
return search(A, begin, mid-1);
}else{
if(target >= A[begin] && target < A[mid])
return search(A, begin, mid-1);
else
return search(A, mid+1, end);
} |
|
P*******y
发帖数: 168 | 45 需要的，而且mark要在入队的时候，不然会有重复入队的情况发生
因为一个点可能是好几个点的neighbor |
|
j*****y
发帖数: 1071 | 46 用你的代码跑
-1 2 4 0, target = 0 就有问题 |
|
l****i
发帖数: 2772 | 47 入队之前，把点的颜色就改了，应该就不会出现重复入队了。 |
|
n**m
发帖数: 122 | 48 这样有问题吧
如果target比中值小 两边都有可能。 |
|
w********p
发帖数: 948 | 49 这道题cc150上有高度类似的体。
总的来说比较合理的题。
不过电面里的任何一题， bug free 的写出来都是要功夫的。 |
|
P*******y
发帖数: 168 | 50 有道理，我上面举的例子有问题，原来题目的例子是这样子：
rotate之后： 1,2,3,10,9,8,7,6,5,4
rotate之前： 1,2,3,4,5,6,7,8,9,10
就是原来增序的后面一半反转后形成的的。这样子就可以用那个方法 |
|
