近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4981|回复: 28
收起左侧

Google Onsite

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

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

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

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

x


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

第二輪
給一個迷宮 看可不可以走到終點
但如果選擇一個方向走 不能只走一步 要走到底碰到障礙物 才停
也就是說下圖是無解 O是起點 X是終點
#####
#O      #. more info on 1point3acres.com
#   X   #
#        #
#####. 1point3acres.com/bbs
. From 1point 3acres bbs
第三輪
給一個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
. more info on 1point3acres.com
第四輪
好像是lc 沒寫過
有很多公車 有各自起點終點和價錢
struct bus
{
int start;. 鍥磋鎴戜滑@1point 3 acres
int end;
int price;
};

給起點跟終點 找出花最少錢的.1point3acres缃

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 444, 订阅: 59
kevindx1120 发表于 2016-11-13 00:28:10 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第三题,在你的recursive 解法里,你不是已经给出了递归关系式,为什么说不会bottum up 的递归. 
第四题, 我觉得直接上Dijkstra.
求第二题的解法.
回复 支持 0 反对 1

使用道具 举报

hahayufindjob 发表于 2016-11-12 12:32:58 | 显示全部楼层
关注一亩三分地微博:
Warald
请教第一道题是什么意思?能否解释下“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);
}. From 1point 3acres bbs

是的第四題
回复 支持 反对

使用道具 举报

hahayufindjob 发表于 2016-11-13 00:41:31 | 显示全部楼层
tommy1122337 发表于 2016-11-12 13:59
第一題的string 可以看成
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
10-99 (2 digit) 的index boundary 9+1 ~ 9+2*90. from: 1point3acres.com/bbs

所以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;

    return to_string(count)[d];.1point3acres缃
}
回复 支持 反对

使用道具 举报

神罗天征 发表于 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. From 1point 3acres bbs
  4.   // cur[kk]:  probability of kk heads in first nn coins
  5.   vector<double> prev(k+1, 0.0), cur(k+1, 0.0);. 鍥磋鎴戜滑@1point 3 acres
  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) {. more info on 1point3acres.com
  10.       cur[kk] = prev[kk-1]*c[nn-1] + prev[kk]*(1-c[nn-1]);  . From 1point 3acres bbs
  11.       prev[kk-1] = cur[kk-1];
  12.     } . 1point3acres.com/bbs
  13.     prev[min(nn,k)] = cur[min(nn,k)];
  14.   }. visit 1point3acres.com for more.
  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]对应的数字在那一层,再看落到哪个数的哪个数字上就好了。
  1. char getChar(int i) {. 1point 3acres 璁哄潧
  2.   if (i < 0) return '\0';. 鍥磋鎴戜滑@1point 3 acres
  3.   int count = 9, nDigits = 0;
  4.   while (i+1 > (++nDigits)*count) { i -= nDigits*count; count *= 10; }. visit 1point3acres.com for more.
  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. from: 1point3acres.com/bbs
第三题列了一下状态转移方程不知道对不对... 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;. visit 1point3acres.com for more.
  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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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. 鍥磋鎴戜滑@1point 3 acres
  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      .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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. . 1point 3acres 璁哄潧
  18. bool canFinish(vector<vector<int>>& maze, vector<int> s, vector<int> e) {
  19.   if ((m = maze.size()) == 0) return false;
  20.   if ((n = maze[0].size()) == 0) return false;
  21.   start = s, goal = e;
  22.   // search each direction from start. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.   return dfs(maze, s[0]+dirs[0][0], s[1]+dirs[0][1], 0) ||
  24.          dfs(maze, s[0]+dirs[1][0], s[1]+dirs[1][1], 1) ||
  25.          dfs(maze, s[0]+dirs[2][0], s[1]+dirs[2][1], 2) ||
  26.          dfs(maze, s[0]+dirs[3][0], s[1]+dirs[3][1], 3);
  27. }
复制代码
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2016-11-26 11:49:28 | 显示全部楼层
zzgzzm 发表于 2016-11-14 05:20
第三轮:LZ已经写了recusive的,这和DP差不多了:时间O(nk),空间O(k)

. more info on 1point3acres.com能解释一下概率是怎么计算的吗?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
碰见概率就蒙蔽
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-23 14:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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