l******x
发帖数: 225 | 1 fresh cs master, G家onsite不包括lunch person总共见了4个人，按顺序分别是三男
、白男、国女、三女，经历如下：
三男：
1. 两个圆在什么条件下相交？
2. m*n的矩阵in place rotation?
看见阿三我心就凉了半截。年纪大了，反应慢，算算术吭哧吭哧，第一题就捣持了
半天。第二题就别提了，吭哧到最后，也就是讲了讲这题有什么corner case,难点在哪，
说如果换做n*n的就简单多了。三男非常满足的在一边幸灾乐祸的从头笑到尾，把我写
的任何一个字，画的图，说得任何一句话都恨不得要记下来。后来他让我写个不是
in place的了事。回来我google半天，也没有找到这道题在任何地方被提起和讨论过。
我后来discussion的时候问他答案是什么，他也不说，就说这不是个straightforward
的问题，说我们主要是看你解决问题的思路，我觉得you are doing quite well, don't
worry about this. 也许是看自己第一个面我，折磨成那样，良心发现了安慰一下。
白男：
1. n个城市之间的距离要把都存下来，怎么存最省空间？
2. 前序中序重建树。
其实这个白男非常拽，也有点岁数了，估计35超上。但这个说的和写得都让他很满意，
应该是最没问题的一个。最后还剩10多分钟，随便聊了聊。
国女：
0. 也许也有个什么warmup, 我忘了。
1. 64 bit的integer,怎么数里面1的个数？
followup: 要是多次使用你怎么办？你不觉得要用空间的太多了吗，怎么办？
2. p*q的matrix,从左下到右上路径数？
followup: 你这个算的会有什么问题？你怎么解决？
followup: matrix中有障碍呢？ （其实我没有感觉到时间过的很快，这个没有code
完，她让我说了说算法了事）
看到国女我喜极生悲，简单的coding被她揪出来bug，不过我不知道她是不是非常nice
的没有记下。要是她能看到这个帖子，我很想说声大姐你很漂亮！
三女：
1. m长的array，长度为k的sliding window,求每次slide一下window里的最大值。然后
问test cases.
2. 你对网络了解吗？（不了解。）好吧那多线程呢？（还行吧）于是问mutex,
semaphore概念，出了个多线程的题，一点一点的深究设计。
三女很认真，虽然跟三男风格大不一样，几乎不记笔记，估计全记脑子里了，但是
她非常认真的在纸上画，试图抓我bug，我面对三女当然谨慎了，没有给她抓到bug。
多线程的设计具体确实不记得了，最后问到一个地方，我愣了20秒没答上来，她心满
意足的发表结束陈词：我们就是想让你能有点东西可以想的，要是你所有问题都答
上来了，说明我们interviewer没有do a good job. 我觉得她很有诚意，应该也没有写
太多坏话。
G家电面在大半年前准备找intern的时候面过了，题目也的确不太记得了，感觉是比
full time的容易。12月初决定quit找工，他家recruiter正好发信问我还有没有兴趣，
我就走上了安排onsite的道路，最后决定安排在2月。 圣诞节左右出去玩了20多天，
回来以后第三天面facebook第一轮电面，然后就挂了。之后onsite了包括G家总共
4家，除了G家别的我都挂了。还是写一下经历吧：
Oracle:
没有电面直接飞过去，吃的好住的好，总共见了5个manager聊天，技术面约等于0，
零星的问一问什么叫BFS， DFS， unix中的ls, cat命令等。汗。最后没有人给我offer，
我厚着脸皮写信问有什么需要改进的。后来还真有人让recruiter回了我的信。他家是唯一
回我这种feedback request的，从头至尾，我感觉O家非常会做人，让我感觉到了丝丝
暖意。只不过有缘无份，非常遗憾。
Epic:
他家非常事儿多，onsite之前要做一些像心理测试类似的东西，onsite的时候要做反
应测试，智力测试，还有写程序。写程序是给5个问题，把你扔到一个办公室自己在
发的sheet本上写。还有见几个人聊天，应该不是manager之类，就是engineer吧，
问了很多behavioral问题，不过都是网上能找到的，我都没有怎么准备，答的肯定不好。
××：
纽约一家比较不算太大的咨询公司，见我的manager是中国人，所以名字我就不说了。
这家公司其实我很有好感，我感觉他们准备面人非常有诚意，虽然公司不大，但是我不
觉得题目比大公司的面试题简单多
少，而且考察的东西很广。而且又是白板、又是笔记本、又是纸上写，什么兵器都用上
了。总共见了5个人，亚裔面孔多，
穿插白人，没有阿三。记得的题目有：
1. 给一段C程序（汗，C我真没仔细学过）看有什么问题，具体的忘了，好像是关于函
数里的char*出了函数就有问题的
事。
2. 从m长的array中随机取里面的n个，怎么做？数学推导？好像还有另外一个也是
sampling啥的，忘了。
3. n-bit的integer，打出所有有k个bit被set的数，你这个复杂度多少？怎么提高？还
是不够高，怎么办？
4. 打印power set。
5. 多线程细节，hashtable细节。
6. 用Java写一个iterator,满足一些要求，细节不记得了，有一点tricky。
7. 给我讲STL里的unique函数是干什么的，让实现，怎么提高效率？
8. 读一个什么文件，问看那些数据我想到些什么，然后写程序求最大，最小，average
之类的。
全写完了，希望大家bless我办OPT或者CPT顺利， 因为这里面可能会有麻烦。 |
g*********s
发帖数: 1782 | 2 三男：
1. 两个圆在什么条件下相交？
还有点麻烦。考虑内切和外切两种情况。
2. m*n的矩阵in place rotation?
a1,a2,a3...,b1,b2,b3,...c1,c2,c3... => a1,b1,c1,a2,b2,c2...?
2*n的情况经典。推广到m*n没想过，也许很简单，也许很麻烦。
白男：
1. n个城市之间的距离要存下来，怎么存最省空间？
二维数组？
2. 前序中序重建树。
经典。
国女：
1. 64 bit的integer,怎么数里面1的个数？
followup: 要是多次使用你怎么办？你不觉得要用空间的太多了吗，怎么办？
用一个表记录0~255的1个数。
2. p*q的matrix,从左下到右上路径数？
followup: 你这个算的会有什么问题？你怎么解决？
经典。递归 => dp
followup: matrix中有障碍呢？
容斥原理？如果有很多障碍，还挺麻烦。找一条路径倒是简单，A*。
三女：
1. m长的array，长度为k的sliding window,求每次slide一下window里的最大值。
然后
问test cases.
经典。
2.问mutex, semaphore概念，出了个多线程的题，一点一点的深究设计。
哪，
【在 l******x 的大作中提到】
: fresh cs master, G家onsite不包括lunch person总共见了4个人，按顺序分别是三男
: 、白男、国女、三女，经历如下：
: 三男：
: 1. 两个圆在什么条件下相交？
: 2. m*n的矩阵in place rotation?
: 看见阿三我心就凉了半截。年纪大了，反应慢，算算术吭哧吭哧，第一题就捣持了
: 半天。第二题就别提了，吭哧到最后，也就是讲了讲这题有什么corner case,难点在哪，
: 说如果换做n*n的就简单多了。三男非常满足的在一边幸灾乐祸的从头笑到尾，把我写
: 的任何一个字，画的图，说得任何一句话都恨不得要记下来。后来他让我写个不是
: in place的了事。回来我google半天，也没有找到这道题在任何地方被提起和讨论过。
|
z**c
发帖数: 625 | 3 请问sliding window那个题的经典做法是什么？
【在 g*********s 的大作中提到】
: 三男：
: 1. 两个圆在什么条件下相交？
: 还有点麻烦。考虑内切和外切两种情况。
: 2. m*n的矩阵in place rotation?
: a1,a2,a3...,b1,b2,b3,...c1,c2,c3... => a1,b1,c1,a2,b2,c2...?
: 2*n的情况经典。推广到m*n没想过，也许很简单，也许很麻烦。
: 白男：
: 1. n个城市之间的距离要存下来，怎么存最省空间？
: 二维数组？
: 2. 前序中序重建树。
|
l*****a
发帖数: 14598 | 4 先顶后看
哪，
【在 l******x 的大作中提到】
: fresh cs master, G家onsite不包括lunch person总共见了4个人，按顺序分别是三男
: 、白男、国女、三女，经历如下：
: 三男：
: 1. 两个圆在什么条件下相交？
: 2. m*n的矩阵in place rotation?
: 看见阿三我心就凉了半截。年纪大了，反应慢，算算术吭哧吭哧，第一题就捣持了
: 半天。第二题就别提了，吭哧到最后，也就是讲了讲这题有什么corner case,难点在哪，
: 说如果换做n*n的就简单多了。三男非常满足的在一边幸灾乐祸的从头笑到尾，把我写
: 的任何一个字，画的图，说得任何一句话都恨不得要记下来。后来他让我写个不是
: in place的了事。回来我google半天，也没有找到这道题在任何地方被提起和讨论过。
|
f*******4
发帖数: 1401 | 5 用一个queue 每次新来一个数就pop掉queue尾部比它小的数，然后插入queue
尾部，每次出去一个数看一下是不是queue的头部
【在 z**c 的大作中提到】
: 请问sliding window那个题的经典做法是什么？
|
R***i
发帖数: 78 | |
z**c
发帖数: 625 | 7 请问时间复杂度是多少？
【在 f*******4 的大作中提到】
: 用一个queue 每次新来一个数就pop掉queue尾部比它小的数，然后插入queue
: 尾部，每次出去一个数看一下是不是queue的头部
|
f*******4
发帖数: 1401 | 8 O(n) 每个元素进去一次出来一次
【在 z**c 的大作中提到】
: 请问时间复杂度是多少？
|
q*******g
发帖数: 110 | |
z**c
发帖数: 625 | 10 不错，多谢！
【在 f*******4 的大作中提到】
: O(n) 每个元素进去一次出来一次
|
|
|
f*******4
发帖数: 1401 | 11 2. m*n矩阵inplace rotation怎么做？如果用二维数组表示
的矩阵inplace rotation过后怎么保存？
1. n个城市之间的距离要存下来，怎么存最省空间？
二维数组就是O(n^2)的空间了吧 如果牺牲一点access时间的话
会不会和minimum spanning tree有关系？
1. 64 bit的integer,怎么数里面1的个数？
followup: 要是多次使用你怎么办？你不觉得要用空间的太多了吗，怎么办？
不理解这个题，“用一个表记录0~255的1个数”不是成了用空间换时间了么
2. p*q的matrix,从左下到右上路径数？
这个我觉得用C(p,q)最简洁 就是从p里选q个
【在 g*********s 的大作中提到】
: 三男：
: 1. 两个圆在什么条件下相交？
: 还有点麻烦。考虑内切和外切两种情况。
: 2. m*n的矩阵in place rotation?
: a1,a2,a3...,b1,b2,b3,...c1,c2,c3... => a1,b1,c1,a2,b2,c2...?
: 2*n的情况经典。推广到m*n没想过，也许很简单，也许很麻烦。
: 白男：
: 1. n个城市之间的距离要存下来，怎么存最省空间？
: 二维数组？
: 2. 前序中序重建树。
|
i******m
发帖数: 1 | 12 Big con! 学习学习！
哪，
【在 l******x 的大作中提到】
: fresh cs master, G家onsite不包括lunch person总共见了4个人，按顺序分别是三男
: 、白男、国女、三女，经历如下：
: 三男：
: 1. 两个圆在什么条件下相交？
: 2. m*n的矩阵in place rotation?
: 看见阿三我心就凉了半截。年纪大了，反应慢，算算术吭哧吭哧，第一题就捣持了
: 半天。第二题就别提了，吭哧到最后，也就是讲了讲这题有什么corner case,难点在哪，
: 说如果换做n*n的就简单多了。三男非常满足的在一边幸灾乐祸的从头笑到尾，把我写
: 的任何一个字，画的图，说得任何一句话都恨不得要记下来。后来他让我写个不是
: in place的了事。回来我google半天，也没有找到这道题在任何地方被提起和讨论过。
|
h**********d
发帖数: 4313 | 13 谢谢分享!
bless opt/cpt 顺利!! |
f***g
发帖数: 214 | 14 三男：
1. 两个圆在什么条件下相交？
就是两圆心和两半径的关系？
比如：!(D > (R1 + R2) || (D + R1) < R2) ？
2. m*n的矩阵in place rotation?
关键是数据是怎么保存的吧。
解决了这个是不是可以rotate m*m
然后递归。
白男：
1. n个城市之间的距离要存下来，怎么存最省空间？
二维数组？
2. 前序中序重建树。
经典。
国女：
1. 64 bit的integer,怎么数里面1的个数？
followup: 要是多次使用你怎么办？你不觉得要用空间的太多了吗，怎么办？
查表 table[256]
2. p*q的matrix,从左下到右上路径数？
followup: 你这个算的会有什么问题？你怎么解决？
经典。可以直接算
followup: matrix中有障碍呢？
DP就行了吧
三女：
1. m长的array，长度为k的sliding window,求每次slide一下window里的最大值。
然后问test cases.
经典。
2.问mutex, semaphore概念，出了个多线程的题，一点一点的深究设计。 |
l******x
发帖数: 225 | 15
2. m*n的矩阵in place rotation?
关键是数据是怎么保存的吧。
解决了这个是不是可以rotate m*m
然后递归。
嗯， 我后来确实想的是这个思路，不过感觉还是很麻烦，我当场估计也写不出来。所
以也不抱憾了。
【在 f***g 的大作中提到】
: 三男：
: 1. 两个圆在什么条件下相交？
: 就是两圆心和两半径的关系？
: 比如：!(D > (R1 + R2) || (D + R1) < R2) ？
: 2. m*n的矩阵in place rotation?
: 关键是数据是怎么保存的吧。
: 解决了这个是不是可以rotate m*m
: 然后递归。
: 白男：
: 1. n个城市之间的距离要存下来，怎么存最省空间？
|
l*****a
发帖数: 14598 | 16 二维数组有一半浪费。。
【在 g*********s 的大作中提到】
: 三男：
: 1. 两个圆在什么条件下相交？
: 还有点麻烦。考虑内切和外切两种情况。
: 2. m*n的矩阵in place rotation?
: a1,a2,a3...,b1,b2,b3,...c1,c2,c3... => a1,b1,c1,a2,b2,c2...?
: 2*n的情况经典。推广到m*n没想过，也许很简单，也许很麻烦。
: 白男：
: 1. n个城市之间的距离要存下来，怎么存最省空间？
: 二维数组？
: 2. 前序中序重建树。
|
C***y
发帖数: 2546 | 17 ajacency list?
【在 l*****a 的大作中提到】
: 二维数组有一半浪费。。
|
l*****a
发帖数: 14598 | 18
64bit,why 255?
how many will u use for 64bit?
2^64???
it should be C(p+q,p)
u need to walk p steps to up and q steps to right.altogether p+q steps
there should have p steps up.then C(p+q,p)it is also C(p+q,q)
【在 f*******4 的大作中提到】
: 2. m*n矩阵inplace rotation怎么做？如果用二维数组表示
: 的矩阵inplace rotation过后怎么保存？
: 1. n个城市之间的距离要存下来，怎么存最省空间？
: 二维数组就是O(n^2)的空间了吧 如果牺牲一点access时间的话
: 会不会和minimum spanning tree有关系？
: 1. 64 bit的integer,怎么数里面1的个数？
: followup: 要是多次使用你怎么办？你不觉得要用空间的太多了吗，怎么办？
: 不理解这个题，“用一个表记录0~255的1个数”不是成了用空间换时间了么
: 2. p*q的matrix,从左下到右上路径数？
: 这个我觉得用C(p,q)最简洁 就是从p里选q个
|
l*****a
发帖数: 14598 | 19 这个不对。
可能会与前面的值比较，时间复杂度就不好说了
【在 f*******4 的大作中提到】
: O(n) 每个元素进去一次出来一次
|
f***g
发帖数: 214 | 20 也有一半的浪费吧
【在 C***y 的大作中提到】
: ajacency list?
|
|
|
f*******4
发帖数: 1401 | 21 1. 我totally不理解2楼说的“用一个表记录0~255的1个数”所以才问。
能科普一下这个查表难道不是空间换时间么？这个是面试官所要的？
2. 对 C(p+q,p) ...
【在 l*****a 的大作中提到】
: 这个不对。
: 可能会与前面的值比较，时间复杂度就不好说了
|
f*******4
发帖数: 1401 | 22 每一个数进queue后只可能被比较一次
具体证明记不得了 可以搜一搜
【在 l*****a 的大作中提到】
: 这个不对。
: 可能会与前面的值比较，时间复杂度就不好说了
|
g*********s
发帖数: 1782 | 23
多次查用这个。
【在 f*******4 的大作中提到】
: 1. 我totally不理解2楼说的“用一个表记录0~255的1个数”所以才问。
: 能科普一下这个查表难道不是空间换时间么？这个是面试官所要的？
: 2. 对 C(p+q,p) ...
|
g*********s
发帖数: 1782 | 24 可以只存上三角部分。
d(x,y) = d(min(x,y), max(x,y)).
【在 l*****a 的大作中提到】
: 二维数组有一半浪费。。
|
l*****a
发帖数: 14598 | 25 你用什么数据结构？
二位数组的话，不存也占空间吧
【在 g*********s 的大作中提到】
: 可以只存上三角部分。
: d(x,y) = d(min(x,y), max(x,y)).
|
g*********s
发帖数: 1782 | 26
0~255 is for 1 byte. 64bit = 8byte.
unsigned char tab[256];
an int64 need 8 times of table lookup.
【在 l*****a 的大作中提到】
: 你用什么数据结构？
: 二位数组的话，不存也占空间吧
|
C***y
发帖数: 2546 | 27 请问第一个m*n矩阵是怎么存储的？
哪，
【在 l******x 的大作中提到】
: fresh cs master, G家onsite不包括lunch person总共见了4个人，按顺序分别是三男
: 、白男、国女、三女，经历如下：
: 三男：
: 1. 两个圆在什么条件下相交？
: 2. m*n的矩阵in place rotation?
: 看见阿三我心就凉了半截。年纪大了，反应慢，算算术吭哧吭哧，第一题就捣持了
: 半天。第二题就别提了，吭哧到最后，也就是讲了讲这题有什么corner case,难点在哪，
: 说如果换做n*n的就简单多了。三男非常满足的在一边幸灾乐祸的从头笑到尾，把我写
: 的任何一个字，画的图，说得任何一句话都恨不得要记下来。后来他让我写个不是
: in place的了事。回来我google半天，也没有找到这道题在任何地方被提起和讨论过。
|
l******x
发帖数: 225 | 28 我不知道标准答案，面试官让我自己设计，最后也没有说答案。我就用的二维数组，
后来捣腾用一维， 反正怎么搞都觉得有很多麻烦。我也就是阐述了这些麻烦。。
【在 C***y 的大作中提到】
: 请问第一个m*n矩阵是怎么存储的？
:
: 哪，
|
C***y
发帖数: 2546 | 29 我的初步想法：
用一维数组存储
先做transposition，这个不是square matrix最麻烦
google了一下，wiki上有算法，
http://en.wikipedia.org/wiki/In-place_matrix_transposition#Non-
然后reverse新matrix的每一行
这题真难，现场很难搞定，除非早就知道这个transposition的算法
【在 l******x 的大作中提到】
: 我不知道标准答案，面试官让我自己设计，最后也没有说答案。我就用的二维数组，
: 后来捣腾用一维， 反正怎么搞都觉得有很多麻烦。我也就是阐述了这些麻烦。。
|
i******s
发帖数: 301 | 30 这题我当年面google的时候也遇到过，特变态，一个国男问的。。。当时是说用一位数
组存储，反正按照C数组的保存方式，写个简单get函数就能拿到第i行j列的数。难点是
首先要找出变换关系，然后要in place转换。。。当时耗了好久，没打出来，然后就挂
了。这题要没碰到过，当场３０分钟内能做出来还真是大牛
【在 C***y 的大作中提到】
: 我的初步想法：
: 用一维数组存储
: 先做transposition，这个不是square matrix最麻烦
: google了一下，wiki上有算法，
: http://en.wikipedia.org/wiki/In-place_matrix_transposition#Non-
: 然后reverse新matrix的每一行
: 这题真难，现场很难搞定，除非早就知道这个transposition的算法
|
|
|
z****o
发帖数: 78 | 31 存储city之间的距离的题目，可以有一下两个假设：
1. city1 到 city2 = city2 到 city1
2. city1 到 city2 距离是非负的。
这样的话，可以计算 cityi 到 cityj 的最短路径的边集S(i,j) = { e1,e2,e3..}
S = S(0,1) U S(0,2) U S(0,3) ..... U S(1,2) U S(1,3) U ..... U S(i,i+1) U S
(i,i+2) U ...
最后存下来S就可以了。这种存法的空间是 |S|*( 2*sizeof(int) + 1* sizeof(double
) );
这个空间去和 ((n-1)+(n-2)+(n-3)+...+2+1)*sizeof(double) 的矩阵存法比较一下，用
空间使用比较省的一种来存。|S|够小的时候用第一种比较好，比如所有的city在一条
线上。
|S|不小的时候用第二种比较省，比如city均匀分布在圆上。 |
l*****a
发帖数: 14598 | 32 确认一下，这个题想把下面这个矩阵rotate 成什么样子？
a1 a2
b1 b2
c1 c2
square_matrices:_Following_the_cycles
【在 C***y 的大作中提到】
: 我的初步想法：
: 用一维数组存储
: 先做transposition，这个不是square matrix最麻烦
: google了一下，wiki上有算法，
: http://en.wikipedia.org/wiki/In-place_matrix_transposition#Non-
: 然后reverse新matrix的每一行
: 这题真难，现场很难搞定，除非早就知道这个transposition的算法
|
f*******4
发帖数: 1401 | 33 赞 问一下 你这个存了S然后我要查比如S(i,j)，该怎么返回呢？
U S
double
，用
【在 z****o 的大作中提到】
: 存储city之间的距离的题目，可以有一下两个假设：
: 1. city1 到 city2 = city2 到 city1
: 2. city1 到 city2 距离是非负的。
: 这样的话，可以计算 cityi 到 cityj 的最短路径的边集S(i,j) = { e1,e2,e3..}
: S = S(0,1) U S(0,2) U S(0,3) ..... U S(1,2) U S(1,3) U ..... U S(i,i+1) U S
: (i,i+2) U ...
: 最后存下来S就可以了。这种存法的空间是 |S|*( 2*sizeof(int) + 1* sizeof(double
: ) );
: 这个空间去和 ((n-1)+(n-2)+(n-3)+...+2+1)*sizeof(double) 的矩阵存法比较一下，用
: 空间使用比较省的一种来存。|S|够小的时候用第一种比较好，比如所有的city在一条
|
z****o
发帖数: 78 | 34 这个只考虑最省存储。如果需要使用距离的话，需要对整个图先run一个APSP，算是解
压缩成矩阵形式。
【在 f*******4 的大作中提到】
: 赞 问一下 你这个存了S然后我要查比如S(i,j)，该怎么返回呢？
:
: U S
: double
: ，用
|
d*********t
发帖数: 33 | 35 应该就是把一个三角形的点阵按序编号，第i个城市和第j个城市之间的距离存储在一个
长度为(N-1)N/2的数组的第(i-2)(i-1)/2+j个位置上，这里只需要考虑i>j的情况。
S
double
，用
【在 z****o 的大作中提到】
: 存储city之间的距离的题目，可以有一下两个假设：
: 1. city1 到 city2 = city2 到 city1
: 2. city1 到 city2 距离是非负的。
: 这样的话，可以计算 cityi 到 cityj 的最短路径的边集S(i,j) = { e1,e2,e3..}
: S = S(0,1) U S(0,2) U S(0,3) ..... U S(1,2) U S(1,3) U ..... U S(i,i+1) U S
: (i,i+2) U ...
: 最后存下来S就可以了。这种存法的空间是 |S|*( 2*sizeof(int) + 1* sizeof(double
: ) );
: 这个空间去和 ((n-1)+(n-2)+(n-3)+...+2+1)*sizeof(double) 的矩阵存法比较一下，用
: 空间使用比较省的一种来存。|S|够小的时候用第一种比较好，比如所有的city在一条
|
g*********s
发帖数: 1782 | 36 sorry, i don't get it. what is "U" here, union? so u just save E?
U S
double
，用
【在 z****o 的大作中提到】
: 存储city之间的距离的题目，可以有一下两个假设：
: 1. city1 到 city2 = city2 到 city1
: 2. city1 到 city2 距离是非负的。
: 这样的话，可以计算 cityi 到 cityj 的最短路径的边集S(i,j) = { e1,e2,e3..}
: S = S(0,1) U S(0,2) U S(0,3) ..... U S(1,2) U S(1,3) U ..... U S(i,i+1) U S
: (i,i+2) U ...
: 最后存下来S就可以了。这种存法的空间是 |S|*( 2*sizeof(int) + 1* sizeof(double
: ) );
: 这个空间去和 ((n-1)+(n-2)+(n-3)+...+2+1)*sizeof(double) 的矩阵存法比较一下，用
: 空间使用比较省的一种来存。|S|够小的时候用第一种比较好，比如所有的city在一条
|
s******c
发帖数: 1920 | 37 c1 b1 a1
c2 b2 a2
【在 l*****a 的大作中提到】
: 确认一下，这个题想把下面这个矩阵rotate 成什么样子？
: a1 a2
: b1 b2
: c1 c2
:
: square_matrices:_Following_the_cycles
|
f*******4
发帖数: 1401 | 38 那你保存的S有什么作用呢？
【在 z****o 的大作中提到】
: 这个只考虑最省存储。如果需要使用距离的话，需要对整个图先run一个APSP，算是解
: 压缩成矩阵形式。
|
z****o
发帖数: 78 | 39 是的 Union
【在 g*********s 的大作中提到】
: sorry, i don't get it. what is "U" here, union? so u just save E?
:
: U S
: double
: ，用
|
z****o
发帖数: 78 | 40 一种存储形式，类似于压缩之后数据。
【在 f*******4 的大作中提到】
: 那你保存的S有什么作用呢？
|
|
|
c****m
发帖数: 179 | 41
可以通过移位转化成255以及更小的，
我觉得存距离那个可以用一维数组表示那个三角阵。
所以想来考点是如何算index？
至于用spanning tree的想法，n-1的空间。但是算距离的时候没有角度信息应该没法算
出来任意两点
的距离吧。而且如果从这个角度说，还不如只存城市的坐标，现算距离。
【在 l*****a 的大作中提到】
: 确认一下，这个题想把下面这个矩阵rotate 成什么样子？
: a1 a2
: b1 b2
: c1 c2
:
: square_matrices:_Following_the_cycles
|
m********7
发帖数: 1368 | |
l******x
发帖数: 225 | 43 总结一下吧，大家基本都找到了答案，还有问题的有：
国女数路径的题，原来大家都assume我不会直接算嘛。。我倒是assume大家都会的。。
问的就是这样有什么问题，怎么解决。
三男转矩阵的题，ls有人给出了wiki的转置的链接，其实我觉得转置和旋转，难度上是
一样的。虽然我之前不知道这个转置算法，但是我感觉提前知道跟不知道差别也不太大，
该纠结还是纠结。首先是wiki上算转换坐标的公式，也太fancy了吧，直接死算不行吗。
而且，wiki上这个算法，并没有解决我的纠结。这个算法，还真不是像2*n的那样是个
有个性的漂亮解法，它的基本想法不就是straightforward的转圈吗？那个转圈，它那里
伪码一写很轻松，真的写代码，到底怎么转？n*n好转，是因为永远在同一个border上
转，一个border上转的不会hurt到其他的，所以不用记录谁转过谁没转过。这m*n一转
起来全乱了，一个不是圈的圈转完了，如果不记录谁转过谁没转过，下一个从哪转起谁
知道？wiki上的做法，也是用log n的空间记录一下谁转过，这个严格来说算 in place
吗？反正，这题的名字就叫纠结！
btw, 原来大家对小公司的题就这么不屑于一聊嘛。。我觉得他家题还不错呀。。
哪，
【在 l******x 的大作中提到】
: fresh cs master, G家onsite不包括lunch person总共见了4个人，按顺序分别是三男
: 、白男、国女、三女，经历如下：
: 三男：
: 1. 两个圆在什么条件下相交？
: 2. m*n的矩阵in place rotation?
: 看见阿三我心就凉了半截。年纪大了，反应慢，算算术吭哧吭哧，第一题就捣持了
: 半天。第二题就别提了，吭哧到最后，也就是讲了讲这题有什么corner case,难点在哪，
: 说如果换做n*n的就简单多了。三男非常满足的在一边幸灾乐祸的从头笑到尾，把我写
: 的任何一个字，画的图，说得任何一句话都恨不得要记下来。后来他让我写个不是
: in place的了事。回来我google半天，也没有找到这道题在任何地方被提起和讨论过。
|
g*********s
发帖数: 1782 | 44 你说最后一个小公司？也没什么新题吧。
大，
吗。
那里
【在 l******x 的大作中提到】
: 总结一下吧，大家基本都找到了答案，还有问题的有：
: 国女数路径的题，原来大家都assume我不会直接算嘛。。我倒是assume大家都会的。。
: 问的就是这样有什么问题，怎么解决。
: 三男转矩阵的题，ls有人给出了wiki的转置的链接，其实我觉得转置和旋转，难度上是
: 一样的。虽然我之前不知道这个转置算法，但是我感觉提前知道跟不知道差别也不太大，
: 该纠结还是纠结。首先是wiki上算转换坐标的公式，也太fancy了吧，直接死算不行吗。
: 而且，wiki上这个算法，并没有解决我的纠结。这个算法，还真不是像2*n的那样是个
: 有个性的漂亮解法，它的基本想法不就是straightforward的转圈吗？那个转圈，它那里
: 伪码一写很轻松，真的写代码，到底怎么转？n*n好转，是因为永远在同一个border上
: 转，一个border上转的不会hurt到其他的，所以不用记录谁转过谁没转过。这m*n一转
|
