Google new grad phone Interview

下午4点半接到的电话，是一个老印，口音不算太重。
算法题（？）一道，给一个

public interface Table {

  // Set the cell at (x, y) to value.

  public void set(int x, int y, int value);

  // Compute the sum of values from (0, 0) to (x, y), inclusive.

  public int sum(int x, int y);

}
让我实现set 和sum。
给定了size，但要求dynamic fixed size.
我选了2d array
[size=13.3333330154419px]实现了set， sum
[size=13.3333330154419px]要分析time comp

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

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

nt face="Courier New">[size=13.3333330154419px]/edit[size=13.3333330154419px]为自己攒人品




补充内容 (2015-7-15 05:28):
链接发错了，这个才是。请手动粘贴 docs.google.com/a/stevens.edu/document/d/（删掉这里）15jpoZB6UodYRGyrVvLM2Zc37ZBTZZtrdkGQytQ_vf0Q（删掉这里）/edit?usp=sharing

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~

zhuli19901106 发表于 2015-7-15 21:17
二维树状数组，我还以为这种不会出现在电面里呢。。

补充内容 (2015-7-15 21:21):

mum，还好，我答的还蛮顺。期间有几个地方下标弄混了面试官还提示我来着。
就我目前的算法程度，面试做的话应该没有更优化解了吧。

刚发现我的google doc权限设得是只有同校可见，现在已经开放评论权限～

sorry, 这个url是可以访问的： https://docs.google.com/document/d/（删掉这里）15jpoZB6UodYRGyrVvLM2Zc37ZBTZZtrdkGQytQ_vf0Q（删掉这里）/edit?usp=sharing

sorry, 这个url可以访问并评论： docs.google.com/document/d/（删掉这里）15jpoZB6UodYRGyrVvLM2Zc37ZBTZZtrdkGQytQ_vf0Q/edit

祝你好运~~~
弱弱的问一下，电面都是怎么进行的？ 1个手拿电话，一个手敲键盘写代码（和面试官共享一个页面）？

umd2011 发表于 2015-7-15 11:01
祝你好运~~~
弱弱的问一下，电面都是怎么进行的？ 1个手拿电话，一个手敲键盘写代码（和面试官共享一个页 ...

恩，戴耳机啊。

二维树状数组，我还以为这种不会出现在电面里呢。。

补充内容 (2015-7-15 21:21):
要在电面中成功写出二维的，感觉很难。。。面试官有要求更优化的解吗？

andysim3d 发表于 2015-7-15 21:26
mum，还好，我答的还蛮顺。期间有几个地方下标弄混了面试官还提示我来着。
就我目前的算法程度，面试做 ...

用二位树状数组的话，求和与修改都可以到logN，请问这个面试官有要求吗？

zhuli19901106 发表于 2015-7-15 22:25
用二位树状数组的话，求和与修改都可以到logN，请问这个面试官有要求吗？

哦，面试官有强调set不怎么用而sum用的很频繁，所以我考虑了之后选择set O(n^2) sum O(1)的解法。