《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 5344|回复: 28
收起左侧

Google Onsite

[复制链接] |试试Instant~ |关注本帖
tommy1122337 发表于 2016-11-12 12:08:33 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Google - Other - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x


第一輪
給一個string 有規律, 就是int一直下去 123...
給一個index回傳那個char
但不能用這個string 要用算的
. Waral 鍗氬鏈夋洿澶氭枃绔,
第二輪
給一個迷宮 看可不可以走到終點
但如果選擇一個方向走 不能只走一步 要走到底碰到障礙物 才停
也就是說下圖是無解 O是起點 X是終點
#####
#O      #
#   X   #
#        #. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
#####

第三輪
給一個double array (length n) 代表每個硬幣投出正面的機率, input k 求 n硬幣中 k個是正面的機率. Waral 鍗氬鏈夋洿澶氭枃绔,
我寫遞迴
double P(int n, int k, vector<double> c, int i)
{
    if(n == 0 && k == 0) return 1;
    if(n < k || k < 0) return 0;

    return c[i]*P(n-i, k-i, c, i+1) + (1 - c[i])*P(n-1, k, c, i+1);
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
接著要求寫 botton up 的DP解 我就不會了... 哪個大神教我一下QQ

第四輪. Waral 鍗氬鏈夋洿澶氭枃绔,
好像是lc 沒寫過
有很多公車 有各自起點終點和價錢
struct bus
{
int start;
int end;
int price;
};
. visit 1point3acres.com for more.
給起點跟終點 找出花最少錢的

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 462, 订阅: 111
kevindx1120 发表于 2016-11-13 00:28:10 | 显示全部楼层
第三题,在你的recursive 解法里,你不是已经给出了递归关系式,为什么说不会bottum up 的递归. .鏈枃鍘熷垱鑷1point3acres璁哄潧
第四题, 我觉得直接上Dijkstra.. visit 1point3acres.com for more.
求第二题的解法.
回复 支持 0 反对 1

使用道具 举报

hahayufindjob 发表于 2016-11-12 12:32:58 | 显示全部楼层
请教第一道题是什么意思?能否解释下“int一直下去”和“有规律”,是会在某点开始重复吗?还有第四题是graph里shortest path问题吗?
回复 支持 反对

使用道具 举报

 楼主| tommy1122337 发表于 2016-11-12 13:57:36 | 显示全部楼层
hahayufindjob 发表于 2016-11-12 12:32
请教第一道题是什么意思?能否解释下“int一直下去”和“有规律”,是会在某点开始重复吗?还有第四题是gra ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一題的string 可以看成
回复 支持 反对

使用道具 举报

 楼主| tommy1122337 发表于 2016-11-12 13:59:04 | 显示全部楼层
第一題的string 可以看成-google 1point3acres
for(int i = 1; ; i++)
{.1point3acres缃
    string += to_string(i);
}

是的第四題
回复 支持 反对

使用道具 举报

hahayufindjob 发表于 2016-11-13 00:41:31 | 显示全部楼层
tommy1122337 发表于 2016-11-12 13:59. From 1point 3acres bbs
第一題的string 可以看成
for(int i = 1; ; i++)
{

不是太明白,不用string 算,那么是要统计下stirng中各个char的出现规律吗?
回复 支持 反对

使用道具 举报

 楼主| tommy1122337 发表于 2016-11-13 02:15:34 | 显示全部楼层
hahayufindjob 发表于 2016-11-13 00:41
. 1point3acres.com/bbs不是太明白,不用string 算,那么是要统计下stirng中各个char的出现规律吗?

就是給個index 你要算出對應的char 不能用string[index]
所以要計算1-9(single digit)的index boundary 1 ~ 9
10-99 (2 digit) 的index boundary 9+1 ~ 9+2*90.1point3acres缃

所以input index, 先算出在哪個區間

char getChar(int n)
{
    int sec = 1, secboundary = 9, lastboundary = 0;
    while(n > secboundary )
    {
        lastboundary = secboundary;
        sec++;
        secboundary = secboundary + sec*9*pow(10, sec-1);
    }
    int count = (n - lastboundary)/sec + 9*pow(10, sec-2);
    int d = (n - lastboundary)%sec;
. more info on 1point3acres.com
    return to_string(count)[d];
}
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-11-13 02:36:03 | 显示全部楼层
求大神的第二题解法
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-11-13 02:39:12 | 显示全部楼层
第一轮是不是就是lc 上的nth digit?
回复 支持 反对

使用道具 举报

yhatl 发表于 2016-11-13 11:33:58 | 显示全部楼层
kevindx1120 发表于 2016-11-13 00:28
第三题,在你的recursive 解法里,你不是已经给出了递归关系式,为什么说不会bottum up 的递归. 
第四题 ...

lz已经说了不会了 莫装逼
装逼遭雷劈
回复 支持 反对

使用道具 举报

sophie0815 发表于 2016-11-13 13:57:00 | 显示全部楼层
问下楼主 第二题 如果障碍物只是在最外面一圈的话 只有 终点和起点在同一行或者同一列或者最外围那一圈才可能到达吧?   这样题就很不make sense 啊, 我猜障碍物应该处处存在吧?   这样的话用dfs可以吗?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

 楼主| tommy1122337 发表于 2016-11-13 14:17:01 | 显示全部楼层
sophie0815 发表于 2016-11-13 13:57
问下楼主 第二题 如果障碍物只是在最外面一圈的话 只有 终点和起点在同一行或者同一列或者最外围那一圈才可 ...

是的 上面那圖只是解釋
障礙物可以很多
我是用DFS 一旦選擇方向就一直走到底
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-14 05:20:52 | 显示全部楼层
第三轮:LZ已经写了recusive的,这和DP差不多了:时间O(nk),空间O(k)
  1. double getProb(int k, vector<double>& c) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  2.   int n = c.size(); if (k > n) return 0;
  3.   // prev[kk]: probability of kk heads in first nn-1 coins. 1point 3acres 璁哄潧
  4.   // cur[kk]:  probability of kk heads in first nn coins
  5.   vector<double> prev(k+1, 0.0), cur(k+1, 0.0);
  6.   prev[0] = cur[0] = 1.0;
  7.   for (int nn = 1; nn <= n; ++nn) {. 1point 3acres 璁哄潧
  8.     cur[0] = prev[0]*c[nn-1];
  9.     for (int kk = 1; kk <= min(nn,k); ++kk) {
  10.       cur[kk] = prev[kk-1]*c[nn-1] + prev[kk]*(1-c[nn-1]);  
  11.       prev[kk-1] = cur[kk-1];
  12.     } . more info on 1point3acres.com
  13.     prev[min(nn,k)] = cur[min(nn,k)];
  14.   }
  15.   return cur[k];. from: 1point3acres.com/bbs
  16. }
复制代码
回复 支持 反对

使用道具 举报

zhenjieruan 发表于 2016-11-14 06:16:24 | 显示全部楼层
第三题列了一下状态转移方程不知道对不对... f[n][k]代表在第 n 个硬币有 k个头的概率,那么 f[n][k] = P(n)*f[n-1][k-1] + (1-P(n))*f[n-1][k]
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-14 06:26:56 | 显示全部楼层
第一轮:将s="12345678910111213..." 看成一个Trie,那么第nDigits 层就有9×10^(nDigits -1)个数,每个数有nDigits 个数字。对于给定的index=i看s[\i]对应的数字在那一层,再看落到哪个数的哪个数字上就好了。
  1. char getChar(int i) {
  2.   if (i < 0) return '\0';
  3.   int count = 9, nDigits = 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4.   while (i+1 > (++nDigits)*count) { i -= nDigits*count; count *= 10; }. 1point 3acres 璁哄潧
  5.   int x = count/9 + i/nDigits, pos = nDigits - i%nDigits;
  6.   while (--pos > 0) x /= 10;
  7.   return '0' + x%10;
  8. }
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-14 06:28:22 | 显示全部楼层
zhenjieruan 发表于 2016-11-14 06:16.鐣欏璁哄潧-涓浜-涓夊垎鍦
第三题列了一下状态转移方程不知道对不对... f[n][k]代表在第 n 个硬币有 k个头的概率,那么 f[n][k] = P(n) ...

嗯,我觉得就是这样对n和k做DP就行了。
对n的DP实际可以只用2个变量,省空间。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-14 06:35:30 | 显示全部楼层
hahayufindjob 发表于 2016-11-13 00:41
不是太明白,不用string 算,那么是要统计下stirng中各个char的出现规律吗?

我不是LZ: 这个题是相当于给定一个无穷的stringstream: 123456789101112131415... 问第i个位置的digit是什么?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-14 07:21:25 | 显示全部楼层
第二题:用DFS是不是这个意思. 当用DFS迭代时同时要传当前的方向,然后若在同一方向的位置无障碍物时就只沿这个方向搜索;否则沿垂直的2个方向搜索。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  1. int m, n; // maze dimensions
  2. vector<int> start, goal;
  3. vector<vector<int>> dirs = {{1,0},{0,-1},{-1,0},{0,1}};

  4. bool dfs(vector<vector<int>>& maze, int i, int j, int d) {
  5.   if (i < 0 || i >= m || j < 0 || j >= n || maze[i][i]) return false;
  6.   if (i == goal[0] && j == goal[1]) return true;
  7.   maze[i][i] = 1; // set as visited
  8.   // next location in same direction. more info on 1point3acres.com
  9.   vector<int> next = {i+dirs[d][0], j+dirs[d][1]};
  10.   // search only same direction if available. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.   if (0 <= next[0] && next[0] < m && 0 <= next[1] && next[1] < n && !maze[next[0]][next[1]])
  12.       return dfs(maze, next[0], next[1], d);
  13.   // search other directions only if same direction unavailable      . Waral 鍗氬鏈夋洿澶氭枃绔,
  14.   else return dfs(maze, i+dirs[(d+1)%4][0], j+dirs[(d+1)%4][1], (d+1)%4) || -google 1point3acres
  15.               dfs(maze, i+dirs[(d-1)%4][0], j+dirs[(d-1)%4][1], (d-1)%4);
  16. }

  17. bool canFinish(vector<vector<int>>& maze, vector<int> s, vector<int> e) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  18.   if ((m = maze.size()) == 0) return false;
  19.   if ((n = maze[0].size()) == 0) return false;. From 1point 3acres bbs
  20.   start = s, goal = e;
  21.   // search each direction from start
  22.   return dfs(maze, s[0]+dirs[0][0], s[1]+dirs[0][1], 0) ||
  23.          dfs(maze, s[0]+dirs[1][0], s[1]+dirs[1][1], 1) ||
  24.          dfs(maze, s[0]+dirs[2][0], s[1]+dirs[2][1], 2) ||
  25.          dfs(maze, s[0]+dirs[3][0], s[1]+dirs[3][1], 3);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  26. }
复制代码
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2016-11-26 11:49:28 | 显示全部楼层
zzgzzm 发表于 2016-11-14 05:20
第三轮:LZ已经写了recusive的,这和DP差不多了:时间O(nk),空间O(k)
. visit 1point3acres.com for more.
能解释一下概率是怎么计算的吗? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
碰见概率就蒙蔽
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2016-11-26 11:55:02 | 显示全部楼层
楼主第四题 带权有向图 最短路径 Djkstra算法吗?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-23 15:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表