一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1475|回复: 26
收起左侧

Google Onsite

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

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

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

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

x

. from: 1point3acres.com/bbs
第一輪
給一個string 有規律, 就是int一直下去 123...
給一個index回傳那個char
但不能用這個string 要用算的

第二輪
給一個迷宮 看可不可以走到終點
但如果選擇一個方向走 不能只走一步 要走到底碰到障礙物 才停. 1point3acres.com/bbs
也就是說下圖是無解 O是起點 X是終點
#####
#O      #. 鍥磋鎴戜滑@1point 3 acres
#   X   #
#        #
#####

第三輪
給一個double array (length n) 代表每個硬幣投出正面的機率, input k 求 n硬幣中 k個是正面的機率
我寫遞迴
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

第四輪
好像是lc 沒寫過
有很多公車 有各自起點終點和價錢
struct bus. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
{
int start;
int end;
int price;
}; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

給起點跟終點 找出花最少錢的

评分

1

查看全部评分

kevindx1120 发表于 2016-11-13 00:28:10 | 显示全部楼层
第三题,在你的recursive 解法里,你不是已经给出了递归关系式,为什么说不会bottum up 的递归. 
第四题, 我觉得直接上Dijkstra.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
求第二题的解法.
回复 支持 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 可以看成
for(int i = 1; ; i++)
{
    string += to_string(i);
}

是的第四題
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

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

所以input index, 先算出在哪個區間. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

char getChar(int n)
{
    int sec = 1, secboundary = 9, lastboundary = 0;. 鍥磋鎴戜滑@1point 3 acres
    while(n > secboundary )
    {
        lastboundary = secboundary;
        sec++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        secboundary = secboundary + sec*9*pow(10, sec-1);
    }
    int count = (n - lastboundary)/sec + 9*pow(10, sec-2);. visit 1point3acres.com for more.
    int d = (n - lastboundary)%sec;

    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
问下楼主 第二题 如果障碍物只是在最外面一圈的话 只有 终点和起点在同一行或者同一列或者最外围那一圈才可 ...

是的 上面那圖只是解釋 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
障礙物可以很多. more info on 1point3acres.com
我是用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. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4.   // cur[kk]:  probability of kk heads in first nn coins.1point3acres缃
  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) {
  8.     cur[0] = prev[0]*c[nn-1];
  9.     for (int kk = 1; kk <= min(nn,k); ++kk) {. 鍥磋鎴戜滑@1point 3 acres
  10.       cur[kk] = prev[kk-1]*c[nn-1] + prev[kk]*(1-c[nn-1]);  
  11.       prev[kk-1] = cur[kk-1];
  12.     }
  13.     prev[min(nn,k)] = cur[min(nn,k)];
  14.   }
  15.   return cur[k];
  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]对应的数字在那一层,再看落到哪个数的哪个数字上就好了。. 1point 3acres 璁哄潧
  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; }
  5.   int x = count/9 + i/nDigits, pos = nDigits - i%nDigits;-google 1point3acres
  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
  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);. visit 1point3acres.com for more.
  13.   // search other directions only if same direction unavailable      
  14.   else return dfs(maze, i+dirs[(d+1)%4][0], j+dirs[(d+1)%4][1], (d+1)%4) ||
  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;
  20.   start = s, goal = e;. 1point3acres.com/bbs
  21.   // search each direction from start. Waral 鍗氬鏈夋洿澶氭枃绔,
  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
. visit 1point3acres.com for more.第三轮:LZ已经写了recusive的,这和DP差不多了:时间O(nk),空间O(k)

能解释一下概率是怎么计算的吗?
碰见概率就蒙蔽
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 04:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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