May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3660|回复: 22
收起左侧

狗家电面

[复制链接] |试试Instant~ |关注本帖
chenzhan171 发表于 2016-6-7 03:00:43 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Pass在职跳槽

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

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

x
面完一周还没消息催了下hr, 刚通知过了, 可以愉快的准备onsite了。分享下电面题。
面试官是个berkeley 本科一路读到phd的黑哥们。

1. 简化版有向图找环, 给一堆edges, 找到eg. 1->2 , 同时2->1的这种边的个数, 比如上面这个例子, 应该返回2。 秒答以后问了下复杂度。

2. 有一个double类型的数组, 找满足 [a, a + 1) 的最长序列含有的元素的个数, eg. [ 1.0 ,1.3 ,1.5 ,2.3, 3.5],  最长的是[1.0 1.3 1.5], 应该返回3。这种小学5年级的数学(数组操作)题对我来说是很困难的, 我直接说暴力解法呗, 然后面试官提醒了下用greedy的方法。 然而代码还是写的很艰难。。。大家可以自己写写O(n)的方法练习一下。


.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

2

查看全部评分

本帖被以下淘专辑推荐:

sapphirew 发表于 2016-6-7 04:27:56 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
祝楼主早日拿到offer!
求问第二题的array是sorted吗。。
回复 支持 反对

使用道具 举报

 楼主| chenzhan171 发表于 2016-6-7 04:34:44 | 显示全部楼层
关注一亩三分地微博:
Warald
sapphirew 发表于 2016-6-7 04:27
祝楼主早日拿到offer!
求问第二题的array是sorted吗。。

恩,面试官的意思是即使原来不sorted也要先sort再说, 主要考察的是sort完以后你能不能O(n)搞出来
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-7 04:46:31 | 显示全部楼层
第二题: two pointers?
回复 支持 反对

使用道具 举报

chenshensheng88 发表于 2016-6-7 04:49:21 | 显示全部楼层
能不能用两个binary search。。。。。
回复 支持 反对

使用道具 举报

chenshensheng88 发表于 2016-6-7 04:50:33 | 显示全部楼层
chenshensheng88 发表于 2016-6-7 04:49
能不能用两个binary search。。。。。

看错惹。。。
回复 支持 反对

使用道具 举报

 楼主| chenzhan171 发表于 2016-6-7 04:58:41 | 显示全部楼层
blackrose 发表于 2016-6-7 04:46
第二题: two pointers?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
本质是two pointer, 不过可以用很少的变量就搞定
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-7 05:21:04 | 显示全部楼层
第二题桶排序吧。。找到min 找到max, 桶是[min,max+1]个integer。 然后扔进去数一下就好了
回复 支持 反对

使用道具 举报

 楼主| chenzhan171 发表于 2016-6-7 11:06:09 | 显示全部楼层
readman 发表于 2016-6-7 05:21
第二题桶排序吧。。找到min 找到max, 桶是[min,max+1]个integer。 然后扔进去数一下就好了
. 1point3acres.com/bbs
如果不sorted用木桶肯定最好, 不过这题假定已经sorted了, 所以针对array本身观察一下规律就可以了
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-7 12:34:57 | 显示全部楼层
第二天sorted greedy approach

  1. int findLongest(vector<double>&v){
  2.    
  3.     int left = 0, right = 0, ans = 0;
  4.    
  5.     while(right<v.size()){
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  6.         . visit 1point3acres.com for more.
  7.         while(v[left]+1.0<=v[right]) left++;
  8.         
  9.         ans = max(ans, right++-left+1);. more info on 1point3acres.com

  10.     }. 1point 3acres 璁哄潧
  11.    
  12.     return ans;
  13.    
  14. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| chenzhan171 发表于 2016-6-7 12:36:49 | 显示全部楼层
handsomecool 发表于 2016-6-7 12:34
第二天sorted greedy approach

对, 就是这样搞。
回复 支持 反对

使用道具 举报

robinali 发表于 2016-6-7 12:50:59 | 显示全部楼层
题二应该就是一次循环,记录所读到的最大子序列就好了吧。 :D
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-6-10 00:04:57 | 显示全部楼层
  1. public class Solution {. 1point 3acres 璁哄潧
  2.     public int maxElementsInOne(double[] arr) {
  3.         int n = arr.length;
  4.         // defensive copy
  5.         double[] sorted = Arrays.copyOf(arr, n);
  6.         Arrays.sort(sorted);

  7.         int ans = 0;
  8.         for (int i = 0, j = 0; j < n; ++j) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.             if (j < n && sorted[j] < sorted[i] + 1) continue;
  10.             ans = Math.max(ans, j - i++);
  11.         }
  12.         return ans;
  13.     }. visit 1point3acres.com for more.

  14.     public static void main(String... args) {
  15.         Solution sol = new Solution();
  16.         int ans = sol.maxElementsInOne(new double[]{1.0, 1.3, 1.5, 2.3, 3.5});. visit 1point3acres.com for more.
  17.         System.out.println(ans);
  18.     }
  19. }
复制代码
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-6-10 00:06:13 | 显示全部楼层
.鐣欏璁哄潧-涓浜-涓夊垎鍦
10行多余j<n,if (sorted[j] < sorted + 1) continue; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-10 02:36:21 | 显示全部楼层

好像bug, 比如[1.1,1.2,1.3,1.4,1.5], ans 最后应该再update一次
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-10 03:00:37 | 显示全部楼层
handsomecool 发表于 2016-6-7 12:34
第二天sorted greedy approach

那个right++ 是怎么来的...
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-10 03:08:42 | 显示全部楼层
readman 发表于 2016-6-10 03:00
那个right++ 是怎么来的...
. Waral 鍗氬鏈夋洿澶氭枃绔,
本来是两行:
  1. ans = max(ans, right-left+1);
  2.         right++;
复制代码
回复 支持 反对

使用道具 举报

jjustc 发表于 2016-6-10 04:59:08 | 显示全部楼层
问一下楼主 第一题 如果 是 1->2->3->4->1 这种环需要找出来吗?
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-6-10 06:09:51 | 显示全部楼层
handsomecool 发表于 2016-6-10 02:36
好像bug, 比如[1.1,1.2,1.3,1.4,1.5], ans 最后应该再update一次

你说的太对了....
  1. public class Solution {. Waral 鍗氬鏈夋洿澶氭枃绔,
  2.     public int maxElementsInOne(double[] arr) {
  3.         int n = arr.length;
  4.         // defensive copy
  5.         double[] copy = Arrays.copyOf(arr, n);
  6.         Arrays.sort(copy);
  7.         int ans = 0, i = 0;
  8.         for (int j = 0; j < n; ++j) {
  9.             if (copy[j] < copy[i] + 1) continue; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10.             ans = Math.max(ans, j - i++);
  11.         }
  12.         return Math.max(ans, n - i);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  14.     public static void main(String... args) {. 1point3acres.com/bbs
  15.         Solution sol = new Solution();
  16.         int ans = sol.maxElementsInOne(new double[]{1.0, 1.3, 1.5, 1.7, 1.9});
  17.         System.out.println(ans);
  18.     }
  19. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| chenzhan171 发表于 2016-6-10 07:51:29 | 显示全部楼层
jjustc 发表于 2016-6-10 04:59
问一下楼主 第一题 如果 是 1->2->3->4->1 这种环需要找出来吗?

不用。字数字数字数
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-24 12:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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