Google Onsite

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

第二輪
給一個迷宮 看可不可以走到終點
但如果選擇一個方向走 不能只走一步 要走到底碰到障礙物 才停
也就是說下圖是無解 O是起點 X是終點
#####
#O      #
#  

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

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

是lc 沒寫過
有很多公車 有各自起點終點和價錢
struct bus
{
int start;
int end;
int price;
};

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

第三题，在你的recursive 解法里，你不是已经给出了递归关系式，为什么说不会bottum up 的递归．　
第四题，　我觉得直接上Dijkstra.
求第二题的解法．

第二题：用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. 
   
5. bool dfs(vector<vector<int>>& maze, int i, int j, int d) {
   
6.   if (i < 0 || i >= m || j < 0 || j >= n || maze[i][i]) return false;
   
7.   if (i == goal[0] && j == goal[1]) return true;
   
8.   maze[i][i] = 1; // set as visited
   
9.   // next location in same direction
   
10.   vector<int> next = {i+dirs[d][0], j+dirs[d][1]};
    
11.   // search only same direction if available
    
12.   if (0 <= next[0] && next[0] < m && 0 <= next[1] && next[1] < n && !maze[next[0]][next[1]])
    
13.       return dfs(maze, next[0], next[1], d);
    
14.   // search other directions only if same direction unavailable      
    
15.   else return dfs(maze, i+dirs[(d+1)%4][0], j+dirs[(d+1)%4][1], (d+1)%4) ||
    
16.               dfs(maze, i+dirs[(d-1)%4][0], j+dirs[(d-1)%4][1], (d-1)%4);
    
17. }
    
18. 
    
19. bool canFinish(vector<vector<int>>& maze, vector<int> s, vector<int> e) {
    
20.   if ((m = maze.size()) == 0) return false;
    
21.   if ((n = maze[0].size()) == 0) return false;
    
22.   start = s, goal = e;
    
23.   // search each direction from start
    
24.   return dfs(maze, s[0]+dirs[0][0], s[1]+dirs[0][1], 0) ||
    
25.          dfs(maze, s[0]+dirs[1][0], s[1]+dirs[1][1], 1) ||
    
26.          dfs(maze, s[0]+dirs[2][0], s[1]+dirs[2][1], 2) ||
    
27.          dfs(maze, s[0]+dirs[3][0], s[1]+dirs[3][1], 3);
    
28. }

复制代码

第三轮：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
   
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) {
   
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. }

复制代码

请教第一道题是什么意思？能否解释下“int一直下去”和“有规律”，是会在某点开始重复吗？还有第四题是graph里shortest path问题吗？

hahayufindjob 发表于 2016-11-12 12:32
请教第一道题是什么意思？能否解释下“int一直下去”和“有规律”，是会在某点开始重复吗？还有第四题是gra ...

第一題的string 可以看成

第一題的string 可以看成
for(int i = 1; ; i++)
{
    string += to_string(i);
}

是的第四題

tommy1122337 发表于 2016-11-12 13:59
第一題的string 可以看成
for(int i = 1; ; i++)
{

不是太明白，不用string[i] 算，那么是要统计下stirng中各个char的出现规律吗？

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

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

求大神的第二题解法

第一轮是不是就是lc 上的nth digit?

kevindx1120 发表于 2016-11-13 00:28
第三题，在你的recursive 解法里，你不是已经给出了递归关系式，为什么说不会bottum up 的递归．　
第四题 ...

lz已经说了不会了 莫装逼
装逼遭雷劈