一亩三分地论坛

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

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

Google电话面试

[复制链接] |试试Instant~ |关注本帖
leo817 发表于 2016-3-16 11:17:03 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Failfresh grad应届毕业生

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

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

x
星期一电话面试。是一个印度哥哥。之前觉得印度哥哥没什么,因为学校印度人很多,工作地方也是印度人,口音不是那么难以理解啊。但是这次,我晕。不知道是我理解有问题还是怎么着。anyway,上题。

给一个integer array,让你求比array  (where i is from 0 to array.length() - 1) 大的maximum number of element
i.e 就是求每个integer右边比它大的个数,求最大值。
. 1point 3acres 璁哄潧
e.g.

A = [2 3 0 1 5 7 4]
       4 3 4 3 1 0 0   
answer is 4. 1point3acres.com/bbs

不知道是楼主理解能力差还是他表达不好,弄明白题意就整了好长时间。写码也磕磕绊绊。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
印度哥哥提示Divide and conquer... 楼主做的不好,已经挂了。
和这个题很类似,大家可以看看。祝你们好运!求大米
http://www.geeksforgeeks.org/cou ... ents-on-right-side/


补充内容 (2016-3-17 00:21):
老印可能想要的是这个解法。merge sort 大家可以去看看。
https://leetcode.com/discuss/73256/mergesort-solution. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
祝你们好运

评分

3

查看全部评分

mingzhou1987 发表于 2016-3-16 12:16:59 | 显示全部楼层
插入时降序就好了.鏈枃鍘熷垱鑷1point3acres璁哄潧
int Fun(vector<int> nums)
{
        vector<int> t;
        if (nums.empty())return 0;
        vector<int> res(nums.size(), 0);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        for (int i = nums.size() - 1; i >= 0; i--). 1point 3acres 璁哄潧
        {
                int left = 0;
                int right = t.size();
                while (left < right)
                {
                        int mid = left + (right - left) / 2;
                        if (t[mid] <= nums[i])
                        {
                                right = mid;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        }
                        else. 1point 3acres 璁哄潧
                        {
                                left = mid + 1;
                        }
                }. Waral 鍗氬鏈夋洿澶氭枃绔,
                res[i] = right;. From 1point 3acres bbs
                t.insert(t.begin() + right, nums[i]);
        }
        int maxV = 0;
        for (auto i : res)
        {
                maxV = max(maxV, i);
        }
        return maxV;
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴}
回复 支持 反对

使用道具 举报

mrhohn 发表于 2016-3-16 12:38:34 | 显示全部楼层
mingzhou1987 发表于 2016-3-16 12:16
插入时降序就好了
int Fun(vector nums)
{

插入排序复杂度是O(N^2)吧?看老印的提示感觉是期望NlogN的解法
回复 支持 反对

使用道具 举报

lby1989825 发表于 2016-3-16 16:10:15 | 显示全部楼层
楼主你被烙印坑了,这题超难的,具体算法参考leetcode 315题
回复 支持 反对

使用道具 举报

 楼主| leo817 发表于 2016-3-17 00:18:02 | 显示全部楼层
mrhohn 发表于 2016-3-16 12:38
插入排序复杂度是O(N^2)吧?看老印的提示感觉是期望NlogN的解法

是的 老印需要的是nlogn的解法
回复 支持 反对

使用道具 举报

 楼主| leo817 发表于 2016-3-17 00:18:37 | 显示全部楼层
lby1989825 发表于 2016-3-16 16:10
楼主你被烙印坑了,这题超难的,具体算法参考leetcode 315题

谢谢啊 leetcode没刷完就面了。谢谢指出题目。祝你好运哦
回复 支持 反对

使用道具 举报

lby1989825 发表于 2016-3-17 04:52:30 | 显示全部楼层
leo817 发表于 2016-3-17 00:18
谢谢啊 leetcode没刷完就面了。谢谢指出题目。祝你好运哦
.1point3acres缃
也祝你好运,不过一轮电面就出这个题真的太不应该了。说实话,很多人onsite碰到的题都没你这个难
回复 支持 反对

使用道具 举报

elvisxyu 发表于 2016-3-17 05:03:29 | 显示全部楼层
stack从右往左走
和求数字右边第一个大于本身的题有点像
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-31 10:23:11 | 显示全部楼层
其实建树也可以啊, 如果建平衡树的话也是O(nlgn), 写了下代码,建的普通树
  1. public class CountOfLargerNumbersAfterSelf {. visit 1point3acres.com for more.
  2. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.         public static void main(String[] args) {
  4.                 int[] arr = {2, 3, 0, 1, 5, 7, 4};. From 1point 3acres bbs
  5.                 int[] res = getCountOfLargerNumbersAfterSelf(arr);
  6.                 for (int i : res) {
  7.                         System.out.println(i);
  8.                 }
  9.         }
  10.         .鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.         static class Node {
  12.                 int val;
  13.                 int dup = 1;
  14.                 int sum;.鏈枃鍘熷垱鑷1point3acres璁哄潧

  15.                 Node left, right;
  16.                 public Node(int v, int s) {
  17.                         val = v;
  18.                         sum = s;
  19.                 }
  20.         }
  21.        
  22.         public static int[] getCountOfLargerNumbersAfterSelf(int[] arr) {
  23.                 if (arr == null || arr.length == 0) {
  24.                         return new int[0];
  25.                 }
  26.                
  27.                 Node root = null;
  28.                 int[] res = new int[arr.length];
  29.                 for (int i = arr.length - 1; i >= 0; i--) {
  30.                         root = helper(root, res, arr[i], i, 0);
  31.                 }. 1point3acres.com/bbs
  32.                
  33.                 return res;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  34.         }

  35.         private static Node helper(Node root, int[] res, int num, int i, int preSum) {
  36.                 if (root == null) {
  37.                         root = new Node(num, 0);
  38.                         res[i] = preSum;
  39.                         return root;
  40.                 }
  41.                 if (root.val == num) {
  42.                         root.dup++;
  43.                         preSum += root.sum;
  44.                         res[i] = preSum;
  45.                 } else if (root.val > num) {
  46.                         preSum += root.dup + root.sum;
  47.                         root.left = helper(root.left, res, num, i, preSum);
  48.                 } else {
  49.                         root.sum++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  50.                         root.right = helper(root.right, res, num, i, preSum);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  51.                 }.1point3acres缃
  52.                 return root;-google 1point3acres
  53.         }
  54.        
  55. }
复制代码
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-3-31 10:40:43 | 显示全部楼层
bobzhang2004 发表于 2016-3-31 10:23. 鍥磋鎴戜滑@1point 3 acres
其实建树也可以啊, 如果建平衡树的话也是O(nlgn), 写了下代码,建的普通树
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
普通树是O(n^2)
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-3-31 10:41:34 | 显示全部楼层
这个题目, 没有刷过题, 或者说没有背过题, 几乎不可能在第一轮电话面试中用merge sort做出来吧。。
回复 支持 反对

使用道具 举报

 楼主| leo817 发表于 2016-3-31 10:43:14 | 显示全部楼层
hyj143 发表于 2016-3-30 21:41
这个题目, 没有刷过题, 或者说没有背过题, 几乎不可能在第一轮电话面试中用merge sort做出来吧。。

我去人肉试题 你要加油哦!
回复 支持 反对

使用道具 举报

z6403456 发表于 2016-3-31 10:54:41 | 显示全部楼层
明天 面试 求好运!!!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-31 10:58:45 | 显示全部楼层
leo817 发表于 2016-3-31 10:43
我去人肉试题 你要加油哦!

其实这个题google面经中出现过几次
回复 支持 反对

使用道具 举报

 楼主| leo817 发表于 2016-3-31 12:34:43 | 显示全部楼层
bobzhang2004 发表于 2016-3-30 21:58
其实这个题google面经中出现过几次

恩 应该是 我准备不充分 经常看你贴代码 祝你好运哦
回复 支持 反对

使用道具 举报

 楼主| leo817 发表于 2016-3-31 12:34:59 | 显示全部楼层
z6403456 发表于 2016-3-30 21:54
明天 面试 求好运!!!

稳稳的 加油啊!
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-28 04:55:24 | 显示全部楼层
leetcode 315. Count of Smaller Numbers After Self,和这个很像。电面考这个太难了
回复 支持 反对

使用道具 举报

831128 发表于 2016-5-26 10:27:26 | 显示全部楼层
被黑了, 电面出这题, 没看过的不可能做出来,就算看过也超了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 14:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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