Google new grad phone Interview

andysim3d 发表于 2015-7-15 22:47
哦，面试官有强调set不怎么用而sum用的很频繁，所以我考虑了之后选择set O(n^2) sum O(1)的解法。

哦，那就简单多了。祝楼主好运，不过建议你把二维树状数组搞懂哦，onsite面这种难度很正常的。

楼主你好， 请问 sum 是指算行列式的值吗？

RiverZ 发表于 2015-7-15 23:12
楼主你好， 请问 sum 是指算行列式的值吗？

计算从 0，0 到x,y所有值的和

弱弱的问一下 二维树状数组 怎么进行logN的?

say543 发表于 2015-7-17 06:33
弱弱的问一下 二维树状数组 怎么进行logN的?

抱歉，当时没说仔细，单次操作应该是log N * log M
这儿有个topcoder的资料：https://www.topcoder.com/communi ... nary-indexed-trees/

zhuli19901106 发表于 2015-7-17 15:00
抱歉，当时没说仔细，单次操作应该是log N * log M
这儿有个topcoder的资料：https://www.topcoder.com/ ...

树状数组不会的, 用线段树啊....
某大神不说过么...树状数组能干的, 线段树都能

zhuli19901106 发表于 2015-7-15 22:51
哦，那就简单多了。祝楼主好运，不过建议你把二维树状数组搞懂哦，onsite面这种难度很正常的。

多谢啦，我已经看完了树状数组的算法了。

readman 发表于 2015-7-18 00:56
树状数组不会的, 用线段树啊....
某大神不说过么...树状数组能干的, 线段树都能

但这两者编码难度还是有差别的。。线段树明显复杂了些

zhuli19901106 发表于 2015-7-18 01:54
但这两者编码难度还是有差别的。。线段树明显复杂了些

public static void add(int[][] t, int r, int c, int value) {
                for (int i = r; i < t.length; i |= i + 1)
                        for (int j = c; j < t[0].length; j |= j + 1)
                                t[i][j] += value;
        }

        public static int sum(int[][] t, int r, int c) {
                int res = 0;
                for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
                        for (int j = c; j >= 0; j = (j & (j + 1)) - 1)
                                res += t[i][j];
                return res;
        }

        public static int sum(int[][] t, int r1, int c1, int r2, int c2) {
                return sum(t, r2, c2) - sum(t, r1 - 1, c2) - sum(t, r2, c1 - 1) + sum(t, r1 - 1, c1 - 1);
        }

        public static int get(int[][] t, int r, int c) {
                return sum(t, r, c, r, c);
        }

        public static void set(int[][] t, int r, int c, int value) {
                add(t, r, c, -get(t, r, c) + value);
        }

        public static void main(String[] args) {
                int[][] t = new int[4][4];
                add(t, 0, 0, 1);
                add(t, 0, 1, 1);
                add(t, 1, 0, 1);
                add(t, 1, 1, 1);

                System.out.println(4 == sum(t, 0, 0, 3, 3));// 1+1+1+1 + 0000...
        }

补充内容 (2015-7-18 03:12):
- - 好难在电面写...

readman 发表于 2015-7-18 03:12
public static void add(int[][] t, int r, int c, int value) {
                for (int i = r; i < t.length; i |= ...

嗯，如果思路很熟的话，代码简洁就是一大优势了。面试时代码一长就容易紧张，然后就容易出bug~