g家面经

发一个google的电面面经，上周面的，这周还没有联系，估计是要跪
第一轮国人小哥，出的题很简单，关于hash table 的
第二轮，一个在google 7年的大哥，两道题，
1 given an

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

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

choose a point uniformly for the list of rectangles

lyh2017 发表于 2018-3-14 01:24
需要计算 on circle 的点，其实可以计算出一个象限的点 乘4 减去重复计算点，我一开始是这个方法.你这方 ...

你说的对, 稍微改了一下:

1. class Solution {
   
2.     int count (int r) {
   
3.         if (r < 1)
   
4.             return 1;
   
5.         int res = 1 + 4 * r;
   
6.         for (int i = 1; i < r; i++) {
   
7.             res += 4 * (int) Math.sqrt (r * r - i * i);
   
8.         }
   
9.         return res;
   
10.     }
    
11. }

复制代码

跟暴力N^2方法的结果对比了一下, 好像没问题;

1. int circlr(int n)
   
2. {
   
3.     n = abs(n);
   
4.     if(n <1)
   
5.         return 1;
   
6.     int res = 4 * n + 1; // x,0 or 0,y
   
7.    
   
8.     for(int i = 1; i < n; i++)
   
9.     {
   
10.         int x = (int)sqrt(n * n - i * i);
    
11.         if(x > i)
    
12.         {
    
13.             res += 8 * (x - i); // x > y
    
14.         }
    
15.         else if(x == i)    // x == y
    
16.         {
    
17.             res += 4;
    
18.         }
    
19.     }
    
20.     return res;
    
21. }

复制代码

圆上整点请问是要O(N)的还是O(sqrt(N))的？

请教一下第二题是什么意思, 什么叫uniformly for all rectangles?

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

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

tinylic 发表于 2018-3-13 22:02
圆上整点请问是要O(N)的还是O(sqrt(N))的？

o（n）。。。。。。。。。

lyh2017 发表于 2018-3-13 22:43
o（n）。。。。。。。。。

那直接暴力枚举呀，第二题是地里高频面经，按面积加权随机选矩形就行

tinylic 发表于 2018-3-13 22:46
那直接暴力枚举呀，第二题是地里高频面经，按面积加权随机选矩形就行

暴力枚举是O(r^2)吧，不是O(r)？想成一个正方形的话。

求整数个数这个题，是不是跟“原点”的位置也有关系啊？

yiliaobailiao 发表于 2018-3-13 23:37
求整数个数这个题，是不是跟“原点”的位置也有关系啊？

原点位置估计就可以假设在0,0吧, 这种小细节真正面试的时候应该可以交流; O(N)算法有思路吗?

1. class Solution {
   
2.     int count (int r) {
   
3.         if (r < 1)
   
4.             return 1;
   
5.         int res = 1 + 4 * (r - 1 - 1);
   
6.         for (int i = 1; i < r; i++) {
   
7.             res += 4 * (int) Math.sqrt (r * r - i * i);
   
8.         }
   
9.         return res;
   
10.     }
    
11. }

复制代码

不知道这个思路有没没有问题; 不计算on circle的点;

补充内容 (2018-3-14 01:42):
经楼主补充, 这个方法不对;