一亩三分地论坛

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

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

狗家电面

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

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

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

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

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

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 | 显示全部楼层
祝楼主早日拿到offer!
求问第二题的array是sorted吗。。
回复 支持 反对

使用道具 举报

 楼主| chenzhan171 发表于 2016-6-7 04:34:44 | 显示全部楼层
sapphirew 发表于 2016-6-7 04:27
祝楼主早日拿到offer!. 1point3acres.com/bbs
求问第二题的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?

本质是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。 然后扔进去数一下就好了
. 鍥磋鎴戜滑@1point 3 acres
如果不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.         
  7.         while(v[left]+1.0<=v[right]) left++;
  8.         
  9.         ans = max(ans, right++-left+1);
  10. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  11.     }
  12.    
  13.     return ans;
  14.    
  15. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| 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 {
  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++);. from: 1point3acres.com/bbs
  11.         }
  12.         return ans;
  13.     }

  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});.鐣欏璁哄潧-涓浜-涓夊垎鍦
  17.         System.out.println(ans);. 1point3acres.com/bbs
  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 | 显示全部楼层
. 鍥磋鎴戜滑@1point 3 acres
好像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. Waral 鍗氬鏈夋洿澶氭枃绔,
第二天sorted greedy approach

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

使用道具 举报

handsomecool 发表于 2016-6-10 03:08:42 | 显示全部楼层
readman 发表于 2016-6-10 03:00
那个right++ 是怎么来的...

本来是两行:
  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一次
.鏈枃鍘熷垱鑷1point3acres璁哄潧
你说的太对了....
  1. public class Solution {
  2.     public int maxElementsInOne(double[] arr) {. From 1point 3acres bbs
  3.         int n = arr.length;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4.         // defensive copy
  5.         double[] copy = Arrays.copyOf(arr, n);
    . visit 1point3acres.com for more.
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  13.     }

  14.     public static void main(String... args) {. 1point 3acres 璁哄潧
  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);. 1point3acres.com/bbs
  18.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19. } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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