1.6 google 面经（坐等结果中）

一共两场，每场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

暴力解法是O（n^4），我先用 double for l

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

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

"ArialMT">[size=13.3333px]最后还叫我写了几个tests，就酱。
[size=13.3333px]

[size=13.3333px]祝各位好运！
                                       
                               
                       
               
                                       
                               
                       
               



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

写了下第一题code，

1. public class RectanglesNumber {
   
2. 
   
3.         static class  Point {
   
4.                 int x;
   
5.                 int y;
   
6. 
   
7.                 public Point(int x, int y) {
   
8.                         this.x = x;
   
9.                         this.y = y;
   
10.                 }
    
11.         }
    
12. 
    
13.         public static int getRectanglesNumber(int m, int n, Point[] points) {
    
14.                 if (points == null || points.length == 0) {
    
15.                         return 0;
    
16.                 }
    
17.                 HashMap<Integer, List<Point>> map = new HashMap<Integer, List<Point>>();
    
18.                 for (Point p : points) {
    
19.                         if (!map.containsKey(p.y)) {
    
20.                                 map.put(p.y, new ArrayList<Point>());
    
21.                         }
    
22.                         map.get(p.y).add(p);
    
23.                 }
    
24.                 HashMap<String, Integer> pairMap = new HashMap<String, Integer>();
    
25.                 for (List<Point> list : map.values()) {
    
26.                         for (int i = 0; i < list.size() - 1; i++) {
    
27.                                 for (int j = i + 1; j < list.size(); j++) {
    
28.                                         String key = list.get(i).x + "#" + list.get(j).x;
    
29.                                         if (pairMap.containsKey(key)) {
    
30.                                                 pairMap.put(key, pairMap.get(key) + 1);
    
31.                                         } else {
    
32.                                                 pairMap.put(key, 1);
    
33.                                         }
    
34.                                 }
    
35.                         }
    
36.                 }
    
37.                 int res = 0;
    
38.                 for (int val : pairMap.values()) {
    
39.                         if (val > 1) {
    
40.                                 res += (val * (val - 1)) / 2;
    
41.                         }
    
42.                 }
    
43.                
    
44.                 return res;
    
45.         }
    
46.        
    
47.         public static void main(String[] args) {
    
48.                 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)};
    
49.                 int res = getRectanglesNumber(3, 4, points);
    
50.                 System.out.println(res);
    
51.         }
    
52. }
    

复制代码

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

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

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

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

格式好像有点问题，怎么修改啊求教！

是因为从mitbbs copy过来的缘故么？

第一题有点难啊。怪不得只让你做一题

你中国人是用汉语面试得么？

https://leetcode.com/problems/range-sum-query-2d-mutable/  请问楼主第二面是这道题目吗？

xiaozhuxiaozhu 发表于 2016-1-7 19:25
你中国人是用汉语面试得么？

当然是英语呀

prismchen 发表于 2016-1-7 21:42
那道题是premium question，我打不开

http://codingmelon.com/2015/12/1 ... table-leetcode-308/  check this link