一亩三分地论坛

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

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

google 电面

[复制链接] |试试Instant~ |关注本帖
hison7463 发表于 2016-5-24 10:44:48 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
找人内推三次终于推进去了,由于毕业快一年了,投不了new grad,所以内推的是社招的职位面试听口音是一个白人小哥,人很好,都是笑着在说话. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
题目是:. visit 1point3acres.com for more.
2维坐标找与给定点相邻的点,fellow up k 维坐标找与给定点相邻的点。. from: 1point3acres.com/bbs
比如二维下给定(0,0)这个点,那么相邻的点有(-1,-1),(-1, 0), (-1, 1),(0, -1),(1, -1),(1,0),(1, 1),(0,1)这8个点. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
fellow up一开始没什么思路,小哥给了个提示,让我算3维和4维的个数,我报给他答案后又沉默了差不多有3,4分钟(想想真是笨,都提示得那么明显了),然后想到了用divide and conquer,然后简单解释了一下,开始写代码,大概6,7分钟写完了代码,小哥让我跑下test case,然后找到了bug,修改完之后小哥又问还有什么要改的吗?然后我看了代码大概半分钟左右,小哥说剩5分钟了,我们来问问题吧,面试完后看了下代码,有一个很明显的逻辑错误,但是写的时候太慌张了,居然没有看出来,但是大方向应该是对的,不知道能不能onsite。

评分

1

查看全部评分

yueliu2366 发表于 2016-5-26 02:39:56 | 显示全部楼层
xiaoyujiang 发表于 2016-5-26 00:34
好厉害可以写代码看一下吗?

我自己昨天面已经跪了,跪在了很简单的题目,千万不要以为简单,就去练习,面试的时候也考熟练度的,哎,还是功力不够。你加油! 我写了下代码,希望有帮助:

class Solution {
  
List<List<Integer>> neiborhoods(int nums[]) {
    List<List<Integer>> ret = new ArrayList<List<Integer>>();
    dfs(ret, nums, new ArrayList<Integer>(), 0);
    return ret;
}

void dfs(List<List<Integer>> ret, int nums[], List<Integer> item, int index) {
    if (index == nums.length) {
      //这里for循环,判断一下如果此时的item和所给数组nums完全一样,就不要把这个加进去
      for(int i = 0; i < nums.length; i++) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        if (item.get(i) != nums) {. 1point 3acres 璁哄潧
          ret.add(new ArrayList<Integer>(item));
          return;
        }
      }
      return;
    }
   
      
   item.add(nums[index]);
   dfs(ret, nums, item, index + 1);
   item.remove(item.size() - 1);
-google 1point3acres
   item.add(nums[index] + 1);. 鍥磋鎴戜滑@1point 3 acres
   dfs(ret, nums, item, index + 1);
   item.remove(item.size() - 1);. more info on 1point3acres.com

   item.add(nums[index] - 1);
   dfs(ret, nums, item, index + 1);.鐣欏璁哄潧-涓浜-涓夊垎鍦
   item.remove(item.size() - 1);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}


补充内容 (2016-5-26 02:41):. From 1point 3acres bbs
编译下可以运行,应该没大问题
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-5-24 11:39:11 | 显示全部楼层
这题的input和output分别是什么?
回复 支持 反对

使用道具 举报

 楼主| hison7463 发表于 2016-5-24 12:35:39 | 显示全部楼层
wtcupup 发表于 2016-5-24 11:39
这题的input和output分别是什么?

input是一个k维的坐标点,output是与这个坐标点相邻的所有坐标点
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-5-24 20:34:23 | 显示全部楼层
k维就是3**k - 1个么?然后对每维-1, 0, 1三种情况dfs或循环输出result?
回复 支持 反对

使用道具 举报

mkcing 发表于 2016-5-24 20:54:20 | 显示全部楼层
如何跑test case呢?
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-5-24 20:55:38 | 显示全部楼层
感谢楼主分享,祝福早日拿到onsite! 这题我感觉像是那种典型的递归回溯的题目,这么做行不行。假如给定的是(k1, k2, k3...,kn), 然后就每个ki都可以有三种情况,第一种是本身的值ki, 第二种是ki - 1, 第三种是 ki + 1。 分别对这三种情况进行递归,然后直到kn。 要注意的是最后要去除掉给定的那个序列。这样就可以顺带把follow up也解了。
举个例子,比如二维的话,就有3 * 3 - 1 = 8种结果,如果三维就有3 * 3 * 3 - 1 = 26种结果。
回复 支持 反对

使用道具 举报

 楼主| hison7463 发表于 2016-5-25 01:11:42 | 显示全部楼层
Chi2829 发表于 2016-5-24 20:34
k维就是3**k - 1个么?然后对每维-1, 0, 1三种情况dfs或循环输出result?

对,我用的recursive,但是刚才想了一下其实一个loop就行了
回复 支持 反对

使用道具 举报

 楼主| hison7463 发表于 2016-5-25 01:12:18 | 显示全部楼层
yueliu2366 发表于 2016-5-24 20:55. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
感谢楼主分享,祝福早日拿到onsite! 这题我感觉像是那种典型的递归回溯的题目,这么做行不行。假如给定的 ...
.1point3acres缃
对,就是这样的
回复 支持 反对

使用道具 举报

xiaoyujiang 发表于 2016-5-26 00:34:56 | 显示全部楼层
yueliu2366 发表于 2016-5-24 20:55. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
感谢楼主分享,祝福早日拿到onsite! 这题我感觉像是那种典型的递归回溯的题目,这么做行不行。假如给定的 ...

好厉害可以写代码看一下吗?
回复 支持 反对

使用道具 举报

xiaoyujiang 发表于 2016-5-26 02:36:53 | 显示全部楼层
hison7463 发表于 2016-5-25 01:12. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
对,就是这样的

能具体讲一下怎么实现递归么?
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-5-26 03:00:39 | 显示全部楼层
问下....为什么是相邻的点
回复 支持 反对

使用道具 举报

xiaoyujiang 发表于 2016-5-26 03:15:15 | 显示全部楼层
yueliu2366 发表于 2016-5-26 02:39
我自己昨天面已经跪了,跪在了很简单的题目,千万不要以为简单,就去练习,面试的时候也考熟练度的,哎, ...

item.remove(item.size() - 1); 是什么是什么意思啊? 继续加油吧
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-5-26 03:21:22 | 显示全部楼层
xiaoyujiang 发表于 2016-5-26 03:15
item.remove(item.size() - 1); 是什么是什么意思啊? 继续加油吧

就是之前不是执行了item.add(nums[index]),然后执行dfs么,所以为了保证item不变,要回溯下,执行item.remove(item.size() - 1),删除最后一个元素(也就是执行dfs之前加入的那个nums[index]元素)。你可以举个简单例子,比如nums = {0,0}走一下就知道了
回复 支持 反对

使用道具 举报

comicrudy 发表于 2016-5-27 13:08:13 | 显示全部楼层
可以用dfs吧对每一维的x[i],遍历x[i]-1,x[i],x[i]+1,当然,如果只用求有多少个就更简单。
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-6-4 06:33:06 | 显示全部楼层
  1. public class Solution {
  2.     public List<int[]> solve(int[] p) {
  3.         int k = p.length;
  4.         int[] directions = {-1, 1};
  5.         LinkedList<int[]> ans = new LinkedList<>();
  6.         ans.offer(Arrays.copyOf(p, k));
  7.         for (int i = 0; i < k; ++i) {
  8.             int n = ans.size();
  9.             for (int j = 0; j < n; ++j) {
  10.                 for (int d: directions) {
  11.                     int[] copy = Arrays.copyOf(ans.get(j), k);
  12.                     copy[i] += d;
  13.                     ans.offer(copy);
  14.                 }
  15.             }
  16.         }
  17.         ans.pollFirst();
  18.         return ans;
  19.     }
  20. }
复制代码
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-6-4 07:23:50 | 显示全部楼层
xiaoyujiang 发表于 2016-5-26 03:15
item.remove(item.size() - 1); 是什么是什么意思啊? 继续加油吧

DFS回溯的时候要恢复到上 一状态,这句就是恢复到上一个场景的
回复 支持 反对

使用道具 举报

wzy0791 发表于 2016-6-4 14:14:12 | 显示全部楼层
我的想法是recursion,从一维开始,最后得到3^k个元素,然后remove掉input给的原始点,应该可行
回复 支持 反对

使用道具 举报

wzy0791 发表于 2016-6-5 00:29:48 | 显示全部楼层
wzy0791 发表于 2016-6-4 14:14
我的想法是recursion,从一维开始,最后得到3^k个元素,然后remove掉input给的原始点,应该可行

早上起来又把代码写了写

public static List<int[]> kDimenNeighbors(int[] nums) {
        int k = nums.length;. from: 1point3acres.com/bbs
        List<int[]> res = helper(nums, k);
        res.remove(res.size()-1);.1point3acres缃
        return res;-google 1point3acres
}

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴public static List<int[]> helper(int[] nums, int k) {
-google 1point3acres        List<int[]> res = new ArrayList<>();
        int[] directions = {-1, 1, 0};
        if (k == 1) {
. more info on 1point3acres.com                for (int i : directions) {
                        int[] a = new int[1];
                        a[0] = nums[0]+i;-google 1point3acres
                        res.add(a);
                }
                return res;
        }
        int[] sub = Arrays.copyOf(nums, k-1);
        List<int[]> subres = helper(sub, k-1);
        int cur = nums[nums.length-1];. visit 1point3acres.com for more.
        for (int[] num : subres) {. 鍥磋鎴戜滑@1point 3 acres
                for (int i : directions) {
                        int[] a = Arrays.copyOf(num, k);
                        a[k-1] = cur + i;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        res.add(a);. visit 1point3acres.com for more.
                }
        }. 1point3acres.com/bbs
        return res;
}

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] nums = {0, 0, 0}; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        List<int[]> res = kDimenNeighbors(nums);
        System.out.println(res.size());
        for (int i = 0; i < res.size(); i++) {
                for (int j : res.get(i)) System.out.print(j);
                System.out.println();
        }
       
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 01:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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