Google Snapchat跪经

招工季🔚结束，发一下最后两公司的跪经。。。
Google NYC：
1. LC 308
2. 判断一个矩阵是不是balabala矩阵。 特点是对角线的值都相等。都是从左上↖到↘右下方向的对角线。矩阵可能是square 也可能是rectangle。
follow up：
矩阵很大，内存存不下咋办
每次只能读两行，怎么判断，要写代码： 方法是保留上一行然后行行做对比，因为两行的对角线有一个offset是1，直接比较index 相差offset的值。没写完。。。但国人小哥说就当我写出来了。。。。。
3. guess number higher or lower I & II

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

f">进行两次交易：返回max profit 和两次分别的buy and sell price
写的有bug，结果测了几个我感觉不对。。。面试官就让我换值。。看来几下还说cool，就结束了。很方。。。。


snap onsite 当天知道google 跪了。。。snap 面完第二天也跪了。。。
希望大家都offer 多多 ：）

神罗天征 发表于 2016-12-11 03:33
请问一下这个积分怎么算的吗？

记3位选手分别为p1,p2,p3. 令x1, x2, x3分别为“第1，2，3次抽样产生出的随机距离”（注意，p1的起始距离是min(x1, x2, x3)，而不一定是x1。p2和p3皆以此类推）。那么x1, x2, x3之间的大小关系总共有6种可能，每种可能的概率均为1/6，即P(x1 < x2 < x3)=1/6，P(x1 < x3 < x2)=1/6...。为简单起见，我们仅讨论x1 < x2 < x3这种情况，因为此时每位选手pi和其对应xj的下标恰好是相同的(i == j)。

这种情况下，如果p1要赢，那么必然有下列不等式成立
2x1 < x2...(1)
3x1 < x3 ... (2)
0 < x1 < x2 < x3 < 1 ... (3)
x1 < 1/3 ... (4) (由(2) (3) 合并可得 ）。

因此，我们要考虑的是x1, x2的取值范围分别是[0, 1/3]和[2x1, 1]。接下来我们要考虑x1和x2取该范围内的每一种组合时，x3的取值范围应当是什么，才能满足上面4个不等式（主要是和x3有关的(2)和(3)）？

对x2分段讨论：当2x1 < x2 < 3x1时，只要(2)成立，那么x2 < x3这一前提(即(3))自动成立；当3x1 < x2时，只要x2 < x3这一前提成立，那么(2)就自动成立。因此，在这两种情况下，我们都可以只考虑一个条件，因为当一个条件满足时，另外一个条件会自动满足。

因此，就有下面的积分式：



这个结果是在x1 < x2 < x3的特定大小关系下的概率，即P(p1 wins, x1 < x2 < x3)。而P(p1 wins) = P(p1 wins,  x1 < x2 < x3) + P(p1 wins,  x1 < x3 < x2) + P(p1 wins,  x2 < x1 < x3) ... = 4/54 + 4/54 + 4/54 ... = 4/54 * 6 = 4/9。

P(p2 wins)，P(p3 wins)都可以用类似的方式来计算

oldfish 发表于 2016-12-10 05:28
我只会直接积分的笨方法，相当麻烦......

相当于算一个立方体内被一些平面围成的体积

我用积分算的结果也是4/9, 2/9和1/3。但是实际用MATLAB和python模拟的结果都是[7/18, 5/18, 1/3]. 虽然第一个人赢面大的结论没变，但是这可能说明：

1. 我们用的积分的方法有问题
2. MATLAB和python的随机数产生器有问题
3. 我用的模拟程序的实验方法有问题

1. 
   
2. nExp = 1000000;
   
3. x = sort(rand(nExp, 3), 2);
   
4. v = repmat([1 2 3], nExp, 1);
   
5. t = x./v;
   
6. [~, winner] = max(t, [], 2);
   
7. for i = 1:3
   
8.     fprintf('prob %d: %.3f\n', i, sum(winner == i)/nExp*100)
   
9. end

复制代码

prob 1: 38.891
prob 2: 27.753
prob 3: 33.356

补充内容 (2016-12-11 01:17):
抱歉代码确实写错了，请无视

赞lz. offer 马上就来了。加油！！

额楼主面的狗家基本都是原题么，楼主感觉跪在哪里了

求大神讲解第二题，实在是太难……

判断对角矩阵，可以只存第一行加第一列，parallel computing比较每个对角线

1mile的那个有4/9的概率赢

luofeidream 发表于 2016-12-9 10:24
额楼主面的狗家基本都是原题么，楼主感觉跪在哪里了

可能跪在 我没有料到是原题？？。。。。。。

ryc111 发表于 2016-12-9 16:42
1mile的那个有4/9的概率赢

大神能否详解一下 (*^__^*)

ryc111 发表于 2016-12-9 16:42
1mile的那个有4/9的概率赢

好像三个概率分别是4/9, 2/9, 1/3，但是请教一下大神怎么算的呢

神罗天征 发表于 2016-12-10 04:44
好像三个概率分别是4/9, 2/9, 1/3，但是请教一下大神怎么算的呢

我只会直接积分的笨方法，相当麻烦......

相当于算一个立方体内被一些平面围成的体积

需要把各种情况讨论清楚......折腾了我20分钟才算出来 4/9 一个数字