1.6 google 面经(坐等结果中)

原帖地址:一亩三分地

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

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.
Example:
M = 3, N = 4, points = [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2)]

这里面有三个长方形,大家可以画画看, 所以答案是3

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

第二场:美国人,女性,直接开始问设计题,要求implement一个Table的interface

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
}

0 1 2 3
4 5 6 7
sum(1,1) = 10
set(1,1,9)01234967
sum(1,1) = 14

比较简单,分了两问,第一是说sum使用频率<