一亩三分地论坛

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

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

Google Onsite面经

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

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

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

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

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
        stack2: 5, 10, 6
        if n = 2, then the max sum should be 5+10. visit 1point3acres.com for more.
        if n = 3, then the max sum should be 1+4+700
. 1point 3acres 璁哄潧
Second Round. Array Longest Adjacent Consecutive Sequence. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
eg. [6,1,2,5,3] -- return 2, [6,1,2,3,5] -- return 3

.1point3acres缃Follow up: Generic Tree Longest Consecutive Sequence
eg.. visit 1point3acres.com for more.
        1
. visit 1point3acres.com for more.     / \  \
    5   4  2
        /   \
       7     3. 鍥磋鎴戜滑@1point 3 acres
              \
               6
. more info on 1point3acres.com
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?
.1point3acres缃. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
b. Summary Ranges

Fourth Round.
a. 2Sum Smaller
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;. from: 1point3acres.com/bbs
  9.                                 int sum = 0;
  10.                                 for (int l = 0; j - l - 1 >= 0 && l < len; l++) {
  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.                                 }

  14.                         }
  15.                 }

  16.                 return dp[nums.length - 1][k];
  17.         }
复制代码
回复 支持 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{. 鍥磋鎴戜滑@1point 3 acres
  3.         int val;
  4.         List<TreeNode> children;
  5.         TreeNode(int x){
  6.                 this.val = x;
  7.                 this.children = new ArrayList<TreeNode>();. From 1point 3acres bbs
  8.         }
  9. }. more info on 1point3acres.com
  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)
  19.                                 length++;
  20.                         else
  21.                                 length = 1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.                         max = Math.max(max,length);
  23.                         temp = nums[i];
  24.                 }
  25.                 return max;
  26.         }
  27.         public int findTree(TreeNode root){
  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);
  35.                 for(TreeNode t: list){
  36.                         if(t.val==root.val+1)
  37.                                 helper(t,length+1);
  38.                         else helper(t,1);
  39.                 }-google 1point3acres
  40.         }
  41.         public static void main(String args[]){. 鍥磋鎴戜滑@1point 3 acres
  42.                 LongestConsecutiveSequence lcs = new LongestConsecutiveSequence();
  43.                 int [] nums =  {6,1,2,3,5};
  44.                 TreeNode root = new TreeNode(1);
  45.                 TreeNode t2 = new TreeNode(2);. 鍥磋鎴戜滑@1point 3 acres
  46.                 TreeNode t3 = new TreeNode(3);
  47.                 TreeNode t4 = new TreeNode(4);
    . 1point3acres.com/bbs
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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 | 显示全部楼层
问下楼主第一题 当n = 4的时候是最大是1+4+700+3 = 708 还是 1+4+700+5 = 710
回复 支持 反对

使用道具 举报

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. more info on 1point3acres.com
楼主大神能说一下第一题的思路吗~~
-google 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];
                }
                for (int k = 0; k < n; k++) {
                        for (int j = 0; j < len1; j++) {
                                for (int i = 0; i < len2; i++) {
                                        if (k == 0) {. 1point3acres.com/bbs
                                                dp[j][k] = Math.max(nums1[j], nums2);
                                        }
                                        else {
                                                dp[j][k] = Math.max(nums1[j]+dp[j+1][k-1], nums2+dp[j][i+1][k-1]);
                                        }
                                }
. from: 1point3acres.com/bbs                         }
                }
                return dp[0][0][n-1];
        }. visit 1point3acres.com for more.

补充内容 (2015-11-10 06:00):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
有些下标被论坛吞了。。
回复 支持 反对

使用道具 举报

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-google 1point3acres
怎么由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. more info on 1point3acres.com
我觉得这才是楼主的解法(二维dp)。

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

补充内容 (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)的解法么?. Waral 鍗氬鏈夋洿澶氭枃绔,

回复 支持 反对

使用道具 举报

 楼主| zado 发表于 2015-11-10 22:48:17 | 显示全部楼层
maomaoxiong 发表于 2015-11-10 13:41
2Sum smaller的思路是什么?我现在想到的方法是sort。有O(n)的解法么?
. more info on 1point3acres.com
就是leetcode 3sum smaller的变形,先sort array,然后左右两个指针往中间走。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 09:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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