《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4380|回复: 22
收起左侧

狗家电面

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

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

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

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

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)的方法练习一下。




评分

2

查看全部评分

本帖被以下淘专辑推荐:

sapphirew 发表于 2016-6-7 04:27:56 | 显示全部楼层
祝楼主早日拿到offer!. Waral 鍗氬鏈夋洿澶氭枃绔,
求问第二题的array是sorted吗。。
回复 支持 反对

使用道具 举报

 楼主| chenzhan171 发表于 2016-6-7 04:34:44 | 显示全部楼层
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?

本质是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。 然后扔进去数一下就好了
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
如果不sorted用木桶肯定最好, 不过这题假定已经sorted了, 所以针对array本身观察一下规律就可以了
回复 支持 反对

使用道具 举报

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

  1. int findLongest(vector<double>&v){
  2.     . 1point 3acres 璁哄潧
  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.     . from: 1point3acres.com/bbs
  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 {
  2.     public int maxElementsInOne(double[] arr) {
  3.         int n = arr.length;
  4.         // defensive copy
  5.         double[] sorted = Arrays.copyOf(arr, n);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.     }

  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);
  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-google 1point3acres
第二天sorted greedy approach
. 1point 3acres 璁哄潧
那个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. From 1point 3acres bbs
好像bug, 比如[1.1,1.2,1.3,1.4,1.5], ans 最后应该再update一次
.1point3acres缃
你说的太对了....
  1. public class Solution {
  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);. 1point3acres.com/bbs
  7.         int ans = 0, i = 0;
  8.         for (int j = 0; j < n; ++j) {. 1point3acres.com/bbs
  9.             if (copy[j] < copy[i] + 1) continue;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.             ans = Math.max(ans, j - i++);
  11.         }
  12.         return Math.max(ans, n - i);
  13.     }.1point3acres缃

  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, 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 下一条

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

custom counter

GMT+8, 2017-11-23 06:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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