传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 3788|回复: 31
收起左侧

Google Onsite面经

[复制链接] |试试Instant~ |关注本帖
zado 发表于 2015-11-9 23:23:59 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
First Round. Given k stack of coins, take n conins, what is the max sum of the n coins.
eg. stack1: 1, 4, 700, 3. visit 1point3acres.com for more.
        stack2: 5, 10, 6. 鍥磋鎴戜滑@1point 3 acres
        if n = 2, then the max sum should be 5+10
        if n = 3, then the max sum should be 1+4+700
. 1point3acres.com/bbs
Second Round. Array Longest Adjacent Consecutive Sequence
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴eg. [6,1,2,5,3] -- return 2, [6,1,2,3,5] -- return 3

Follow up: Generic Tree Longest Consecutive Sequence
eg.
        1
     / \  \
    5   4  2
        /   \
       7     3
              \
               6.1point3acres缃

return 3

Third Round.
a. Two arrays of string find the common element.
A - HashSet
Follow up: What if the two array are very large (10TB).
A - MergeSort
Follow up: How to improve?

b. Summary Ranges

Fourth Round. . 1point3acres.com/bbs
a. 2Sum Smaller. more info on 1point3acres.com
Given an array of n integers nums and a target, find the number of pair i, j satisfy the condition nums[i] + nums[j] < target.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Follow up: kSum Smaller

评分

1

查看全部评分

本帖被以下淘专辑推荐:

lianlu 发表于 2015-11-10 08:33:55 | 显示全部楼层
hj867955629 发表于 2015-11-10 08:25
stack只是设置一个环境,告诉你只能依次读吧,也可以先把stack读到array里呀

我觉得这才是楼主的解法(二维dp)。
  1. public static int getmaxsum(int[][] nums, int k) {
  2.                 int[][] dp = new int[nums.length][k + 1];// the max sum using first i
  3.                                                                                                         // array, and j numbers
  4.                 for (int j = 0; j <= k; j++) {
  5.                         for (int i = 0; i < dp.length; i++) {
  6.                                 // dp[i][j] = max(dp[i-1][l] + sum{});
  7.                                 dp[i][j] = Math.max(i - 1 >= 0 ? dp[i - 1][j] : 0, j - 1 >= 0 ? dp[i][j - 1] : 0);
  8.                                 int len = nums[i].length;
  9.                                 int sum = 0;
  10.                                 for (int l = 0; j - l - 1 >= 0 && l < len; l++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  11.                                         sum += nums[i][l];
  12.                                         dp[i][j] = Math.max(dp[i][j], (i - 1 >= 0 ? dp[i - 1][j - l - 1] : 0) + sum);
  13.                                 }. more info on 1point3acres.com
  14. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.                         }
  16.                 }

  17.                 return dp[nums.length - 1][k];
  18.         }
复制代码
回复 支持 6 反对 0

使用道具 举报

wyjzhi89 发表于 2015-11-10 08:38:31 | 显示全部楼层
我觉得第一题可以先使用一个二维的数组存储起来的stack 从第0位到第i位的sum。 然后用dp[m][k] 代表从第一个stack到第m个stack 选择了k个元素的最大值。因为每个stack选择的都是最前端的元素,所以dp[m][k]=max(sum[j]+dp[m-1][k-j])( j from 0 to k ) .这样就可以求出来k个stack中的最大值。
回复 支持 3 反对 0

使用道具 举报

JamesJi 发表于 2015-11-13 03:40:24 | 显示全部楼层
请教一下楼主,k sum smaller应该怎么做呀
回复 支持 1 反对 0

使用道具 举报

杰西Jesse 发表于 2015-11-11 03:31:11 | 显示全部楼层
  1. import java.util.*;
  2. class TreeNode{
  3.         int val;
  4.         List<TreeNode> children;
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.         TreeNode(int x){
  6.                 this.val = x;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.                 this.children = new ArrayList<TreeNode>();
  8.         }
  9. }
  10. public class LongestConsecutiveSequence{
  11.         int max = 0;
  12.         public int findArr(int [] nums){
  13.                 if(nums.length<1) return 0;
  14.                 int temp = nums[0];
  15.                 int length = 1;
  16.                 int max = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17.                 for(int i = 1;i<nums.length;i++){
  18.                         if(nums[i]== temp+1)-google 1point3acres
  19.                                 length++;
  20.                         else
  21.                                 length = 1;
  22.                         max = Math.max(max,length);
  23.                         temp = nums[i];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  24.                 }
  25.                 return max;
  26.         }
    . 1point3acres.com/bbs
  27.         public int findTree(TreeNode root){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  28.                 helper(root,1);
  29.                 return max;
  30.         }
  31.         public void helper(TreeNode root,int length){
  32.                 max = Math.max(max,length);
  33.                 if(root == null) return;
  34.                 List<TreeNode> list = new ArrayList(root.children);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  35.                 for(TreeNode t: list){
  36.                         if(t.val==root.val+1)
  37.                                 helper(t,length+1);
  38.                         else helper(t,1);
  39.                 }
  40.         }
  41.         public static void main(String args[]){. 1point3acres.com/bbs
  42.                 LongestConsecutiveSequence lcs = new LongestConsecutiveSequence();
  43.                 int [] nums =  {6,1,2,3,5};.1point3acres缃
  44.                 TreeNode root = new TreeNode(1);
  45.                 TreeNode t2 = new TreeNode(2);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.                 TreeNode t3 = new TreeNode(3);
  47.                 TreeNode t4 = new TreeNode(4);
  48.                 TreeNode t5 = new TreeNode(5);
  49.                 TreeNode t6 = new TreeNode(6);
  50.                 TreeNode t7 = new TreeNode(7);
  51.                 root.children.add(t2);root.children.add(t4);root.children.add(t5);
  52.                 t4.children.add(t7);
  53.                 t2.children.add(t3);t3.children.add(t6);
  54.                 System.out.println(lcs.findArr(nums));
  55.                 System.out.println(lcs.findTree(root));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  56.         }
  57. }
复制代码

第二题,不知道是不是BFS更好一点?
回复 支持 1 反对 0

使用道具 举报

hj867955629 发表于 2015-11-10 06:29:19 | 显示全部楼层
之前代码有点问题,重新写了下https://github.com/hejian2356/-Algorithms/blob/master/GetMaxSumFromTwoStack.java
回复 支持 1 反对 0

使用道具 举报

complete_46 发表于 2015-11-19 07:48:49 | 显示全部楼层
第一题:把所有stack里全pop到一个max heap里,再从max heap里pop出来n个数不就行了?
回复 支持 0 反对 1

使用道具 举报

头像被屏蔽
cc11328 发表于 2015-11-10 00:09:43 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

guoqinlong 发表于 2015-11-10 00:11:41 | 显示全部楼层
楼主大神能说一下第一题的思路吗~~
回复 支持 反对

使用道具 举报

 楼主| zado 发表于 2015-11-10 00:41:29 | 显示全部楼层
cc11328 发表于 2015-11-10 00:09
问下楼主第一题 当n = 4的时候是最大是1+4+700+3 = 708 还是 1+4+700+5 = 710

710,因为可以从第二个stack里面选嘛
回复 支持 反对

使用道具 举报

 楼主| zado 发表于 2015-11-10 00:42:14 | 显示全部楼层
guoqinlong 发表于 2015-11-10 00:11
楼主大神能说一下第一题的思路吗~~

动态规划,二维数组,三重循环。我当时写得不是很好。
回复 支持 反对

使用道具 举报

ssross 发表于 2015-11-10 05:41:56 | 显示全部楼层
楼主第二轮跟我店面问的一模一样哈!
回复 支持 反对

使用道具 举报

 楼主| zado 发表于 2015-11-10 05:45:00 | 显示全部楼层
ssross 发表于 2015-11-10 05:41
楼主第二轮跟我店面问的一模一样哈!

是个美国小哥问的?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-10 05:59:59 | 显示全部楼层
guoqinlong 发表于 2015-11-10 00:11
楼主大神能说一下第一题的思路吗~~

仅供参考,测试了楼主的两个都是对的.1point3acres缃
public int getMax(int n) {
                int[] nums1 = {1, 4, 700, 3}, nums2 = {5, 10, 6};
                int len1 = nums1.length, len2 = nums2.length;
                int[][][] dp = new int[len1+1][len2+1][n];
                for (int k = 0; k < n; k++) {
                        dp[len1][k][k] += nums2[k];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
                for (int k = 0; k < n; k++) {
                        dp[k][len2][k] += nums1[k];
                }.1point3acres缃
                for (int k = 0; k < n; k++) {
                        for (int j = 0; j < len1; j++) {
                                for (int i = 0; i < len2; i++) {
                                        if (k == 0) {
                                                dp[j][k] = Math.max(nums1[j], nums2);
                                        }. 鍥磋鎴戜滑@1point 3 acres
                                        else {
                                                dp[j][k] = Math.max(nums1[j]+dp[j+1][k-1], nums2+dp[j][i+1][k-1]);
                                        }
                                }
                        }
                }
                return dp[0][0][n-1];
        }-google 1point3acres

补充内容 (2015-11-10 06:00):
. from: 1point3acres.com/bbs 有些下标被论坛吞了。。
回复 支持 反对

使用道具 举报

winterOfChicago 发表于 2015-11-10 06:28:01 来自手机 | 显示全部楼层
请教楼主 第一题k stacks怎么做的
回复 支持 反对

使用道具 举报

lianlu 发表于 2015-11-10 07:28:34 | 显示全部楼层
hj867955629 发表于 2015-11-10 06:29
之前代码有点问题,重新写了下https://github.com/hejian2356/-Algorithms/blob/master/GetMaxSumFromTwoSt ...

怎么由two array推广到k stacks? 是先全部读出来存在array里了?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-10 08:25:39 | 显示全部楼层
lianlu 发表于 2015-11-10 07:28. From 1point 3acres bbs
怎么由two array推广到k stacks? 是先全部读出来存在array里了?

stack只是设置一个环境,告诉你只能依次读吧,也可以先把stack读到array里呀
回复 支持 反对

使用道具 举报

abcd1992719g 发表于 2015-11-10 08:38:47 | 显示全部楼层
请教楼主 第一题k stacks怎么做的
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-10 08:48:03 | 显示全部楼层
lianlu 发表于 2015-11-10 08:33
我觉得这才是楼主的解法(二维dp)。

你这个确实更好啦,学习了

.鏈枃鍘熷垱鑷1point3acres璁哄潧补充内容 (2015-11-10 08:48):
请问怎么贴代码贴成你这样的?
回复 支持 反对

使用道具 举报

eeyyabc 发表于 2015-11-10 09:49:45 | 显示全部楼层
楼主能把这个问题仔细讲讲吗?What if the two array are very large (10TB). A - MergeSort。是说把两个array分别external sort之后再一段一段load进内存比较?谢啦
回复 支持 反对

使用道具 举报

ssross 发表于 2015-11-10 11:17:09 | 显示全部楼层
zado 发表于 2015-11-10 05:45
是个美国小哥问的?

是的哈!听声音像个白人小哥!应该是同一个人!风格一模一样!
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-10 13:41:44 | 显示全部楼层
2Sum smaller的思路是什么?我现在想到的方法是sort。有O(n)的解法么?

回复 支持 反对

使用道具 举报

 楼主| zado 发表于 2015-11-10 22:48:17 | 显示全部楼层
maomaoxiong 发表于 2015-11-10 13:41
2Sum smaller的思路是什么?我现在想到的方法是sort。有O(n)的解法么?

就是leetcode 3sum smaller的变形,先sort array,然后左右两个指针往中间走。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-21 22:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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