一亩三分地论坛

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

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

1.6 google 面经(坐等结果中)

[复制链接] |试试Instant~ |关注本帖
prismchen 发表于 2016-1-7 18:26:40 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
一共两场,每场45分钟。
第一场:中国人,很nice,先问java static key word 的用法,基本都达到了,就是class可不可以static我不确定,然后上来一道题

                                                                                                                                                                                                [size=11.000000pt]Given a M by N integer grid in Cartesian coordinates, given also K distinct points in that grid,count the total number of upright rectangles (sides being either horizontal or vertical) in thatgrid.
                                                [size=10.000000pt]Example:
                                                [size=11.000000pt]M = 3, N = 4, points = [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2)]
[size=11.000000pt]

[size=11.000000pt]这里面有三个长方形,大家可以画画看, 所以答案是3. visit 1point3acres.com for more.

暴力解法是O(n^4),我先用 double for loops 找出所有的和x轴平行的边,用hashmap<int edge index, pair<1st x value, 2nd x value>>存,再用double for loops匹配可以组成长方形的边,但是对方告诉我这个complexity和暴力解法一样。然后在他的提示下吧hashmap改成hashmap<pair<1st x value, 2nd x value>, pair frequency>, 然后用组合数算出每一种pair可以组合出多少个长方形,这样就省去了第二个double for loops,所以complexity降为O(n^2)。

. 1point 3acres 璁哄潧
第二场:美国人,女性,直接开始问设计题,要求implement一个Table的interface
.鐣欏璁哄潧-涓浜-涓夊垎鍦

                                                [size=10.000000pt]public interface Table {
void set(int x, int y, int value); // set value at (x,y)
int sum(int x, int y); // sum values from (0, 0) to (x, y) inclusive
                                                [size=10.000000pt]}
[size=10.000000pt]
. 1point3acres.com/bbs
[size=10.000000pt]example:
[size=10.000000pt]0 1 [size=10.000000pt] [size=10.000000pt]2 3
                                                [size=10.000000pt]4 5 [size=10.000000pt] [size=10.000000pt]6 7
                                                [size=10.000000pt]sum(1,1) = 10set(1,1,9)01234967sum(1,1) = 14
[size=10.000000pt]

[size=10.000000pt]比较简单,分了两问,第一是说sum使用频率<<set,所以建了一个2d array,然后set是O(1),sum是O(xy)。
[size=10.000000pt]第二问是说请优化sum,然后我建了另一个[size=13.3333px]2d array来存每个点的sum,每次set完之后来update这个sum array;然后她接着问如果只能用一个2d array怎么办,然后我就只保留第二个2d array,然后用四个相邻(田字形)的sum值来计算被抹去的第一个2d array里面每个entry的值,所以sum就是O(1)。
[size=13.3333px]最后还叫我写了几个tests,就酱。
[size=13.3333px]
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
[size=13.3333px]祝各位好运!
                                        . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                               
                       
               
                                       
                               
                       
               
-google 1point3acres


补充内容 (2016-1-7 21:45):
怎么修改format呀?真心找不到地方

评分

2

查看全部评分

 楼主| prismchen 发表于 2016-1-7 18:29:05 | 显示全部楼层
格式好像有点问题,怎么修改啊求教!
回复 支持 反对

使用道具 举报

nycok 发表于 2016-1-7 18:38:22 | 显示全部楼层
是因为从mitbbs copy过来的缘故么?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-7 19:08:43 | 显示全部楼层
第一题有点难啊。怪不得只让你做一题
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-7 19:25:03 | 显示全部楼层
你中国人是用汉语面试得么?
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-7 21:02:42 | 显示全部楼层
https://leetcode.com/problems/range-sum-query-2d-mutable/  请问楼主第二面是这道题目吗?
回复 支持 反对

使用道具 举报

 楼主| prismchen 发表于 2016-1-7 21:42:37 | 显示全部楼层
wtcupup 发表于 2016-1-7 21:02
https://leetcode.com/problems/range-sum-query-2d-mutable/  请问楼主第二面是这道题目吗?

那道题是premium question,我打不开
回复 支持 反对

使用道具 举报

 楼主| prismchen 发表于 2016-1-7 21:42:53 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-7 19:25
你中国人是用汉语面试得么?

当然是英语呀
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-7 21:50:07 | 显示全部楼层
prismchen 发表于 2016-1-7 21:42
那道题是premium question,我打不开

http://codingmelon.com/2015/12/1 ... table-leetcode-308/  check this link
回复 支持 反对

使用道具 举报

 楼主| prismchen 发表于 2016-1-7 23:33:31 | 显示全部楼层
wtcupup 发表于 2016-1-7 21:50
http://codingmelon.com/2015/12/17/range-sum-query-2d-mutable-leetcode-308/  check this link

感觉大意差不多,你这个还略微复杂写。主要就是你要在optimal set()和optimal sum()之前swtich,然后要求只能用一个2D array
回复 支持 反对

使用道具 举报

 楼主| prismchen 发表于 2016-1-8 18:02:26 | 显示全部楼层
nycok 发表于 2016-1-7 18:38
是因为从mitbbs copy过来的缘故么?

不是,是从pdf上copy过来的
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-5 10:28:18 | 显示全部楼层
写了下第一题code,
  1. public class RectanglesNumber {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  2.         static class  Point {
  3.                 int x;
  4.                 int y;

  5.                 public Point(int x, int y) {. 1point 3acres 璁哄潧
  6.                         this.x = x;
  7.                         this.y = y;
  8.                 }
  9.         }

  10.         public static int getRectanglesNumber(int m, int n, Point[] points) {
  11.                 if (points == null || points.length == 0) {
  12.                         return 0;
  13.                 }
  14.                 HashMap<Integer, List<Point>> map = new HashMap<Integer, List<Point>>(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.                 for (Point p : points) {
  16.                         if (!map.containsKey(p.y)) {
  17.                                 map.put(p.y, new ArrayList<Point>());
  18.                         }
  19.                         map.get(p.y).add(p);
  20.                 }
  21.                 HashMap<String, Integer> pairMap = new HashMap<String, Integer>();
  22.                 for (List<Point> list : map.values()) {
  23.                         for (int i = 0; i < list.size() - 1; i++) {
  24.                                 for (int j = i + 1; j < list.size(); j++) {. From 1point 3acres bbs
  25.                                         String key = list.get(i).x + "#" + list.get(j).x;. From 1point 3acres bbs
  26.                                         if (pairMap.containsKey(key)) {
  27.                                                 pairMap.put(key, pairMap.get(key) + 1);
  28.                                         } else {
  29.                                                 pairMap.put(key, 1);
  30.                                         }
  31.                                 }
  32.                         }
  33.                 }
  34.                 int res = 0;
  35.                 for (int val : pairMap.values()) {
  36.                         if (val > 1) {. visit 1point3acres.com for more.
  37.                                 res += (val * (val - 1)) / 2;
  38.                         }
  39.                 }
  40.                 .鐣欏璁哄潧-涓浜-涓夊垎鍦
  41.                 return res;
  42.         }
  43.        
  44.         public static void main(String[] args) {
  45.                 Point[] points = {new Point(0, 1), new Point(0, 2), new Point(1, 0), new Point(1, 2), new Point(2, 0), new Point(2, 1), new Point(3, 0), new Point(3, 1), new Point(3, 2)};
  46.                 int res = getRectanglesNumber(3, 4, points);
  47.                 System.out.println(res);
  48.         }
  49. }
复制代码
回复 支持 反对

使用道具 举报

dangertrip 发表于 2016-2-5 10:35:11 | 显示全部楼层
Inner class can be static.
回复 支持 反对

使用道具 举报

涂鸦ayli 发表于 2016-2-7 01:16:52 | 显示全部楼层
楼主出结果了吧》 我面试都过了16天了还没结果  心好虚
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 11:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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