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


一亩三分地论坛

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

facebook实习一面新鲜面经---高频变种sortCategory!

[复制链接] |试试Instant~ |关注本帖
jinyyy666 发表于 2016-11-5 06:04:10 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 实习@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
FB 实习 新鲜的一面面筋! 回馈地里!!
大家很多人提到了一道sort color的变种,我今天就遇到了,趁现在还记得详细跟大家说一下。
.1point3acres缃
给定一个API getCategory(int n), return {L| M| H} 三种category

第一问 --- 给定一个Array, [4,2,5,7,8,9], 对于每一个int,有一个category,sort them by category

很简单,用sortcolor: https://leetcode.com/problems/sort-colors/ 就可以解决,两个ptr,一个前一个后。LZ不小心有一个bug (for loop 不太对),但是测试的时候找到了。

第二问 ---- 如果这个时候有K个category, 应该怎么办?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

顺着上一题的思路,我的想法是将(0,1,。。。,k-1) category 分成(0)--> L, (1, k-2) -->M, (k-1) --> H, 然后相同的思想继续call之前的function,然后reduce为 (1,k-2)的range,重复之前的事情

大家可以再仔细想想这里面有什么问题。

第一要注意的是,之前的function应该变成:

sortCategory(nums, low, high) (low and high is the corresponding int of the "L" and "H" category).鐣欏璁哄潧-涓浜-涓夊垎鍦
要记得把front和back一个指针变一下,如下:. 1point 3acres 璁哄潧

while(getCategory(nums[front]) < low) front++;
while(getCategory(nums[back]) > high) back--;


这样就不用再次处理之前处理过的category了。

第二个要注意的是,其实之前的sortCategory也可以处理只有两种Category的case,不用担心, 直接call

第三个要注意的是,在新的sortKCategory里面,while loop的条件
Code:
void sortKCategory(vector<int>& nums, int k){
-google 1point3acres    if(nums.empty() || k <= 0) return;
    int beginCat = 0, endCat = k-1;
    while(beginCat < endCat){
        sortCategory(nums, beginCat++, endCat--);
    }.鏈枃鍘熷垱鑷1point3acres璁哄潧
}

void sortCategory(vector<int>& nums, int low, int high){. 1point3acres.com/bbs
    if(nums.empty())  return;
    int front = 0, back = nums.size()-1;
    while(getCategory(nums[front]) < low) front++;
    while(getCategory(nums[back]) > high) back--;

    for(int i = front; i <= back; ++i){  //注意for loop条件
        if(getCategory(nums) == low) swap(nums, nums[front++]); //注意为什么不用decrease i!
        if(getCategory(nums) == high) swap(nums[i--], nums[back--]); //注意为什么要decrease i! 会问你的
    }
}


评分

2

查看全部评分

本帖被以下淘专辑推荐:

wtcupup 发表于 2016-11-5 14:03:11 | 显示全部楼层
  1. 帮忙看看我这样是不是更简单一点?
  2. public void sortKCategory(int[] nums, int k) {
  3.        //assume getCat returns 1, ...k
  4.         int pl = 0;
  5.         int pr = nums.length - 1;
  6.         int i = 0;
  7.         int min = 1, max = k;
  8.         while (min < max) {
  9.             while (i <= pr) {
  10.                 if (getCat(nums[i]) == min) {
  11.                     swap(nums, pl, i);
  12.                     i++;. more info on 1point3acres.com
  13.                     pl++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.                 } else if (getCat(nums[i]) == max) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.                     swap(nums, pr, i);
  16.                     pr--;
  17.                 } else {
  18.                     i++;
  19.                 }
  20.             }
  21.             i = pl;
  22.             min++;
  23.             max--;.1point3acres缃
  24.         }
  25.     }

  26. . more info on 1point3acres.com
  27.     private void swap(int[] colors, int i, int j) {
  28.         int temp = colors[i];
  29.         colors[i] = colors[j];
  30.         colors[j] = temp;
  31.     }
复制代码

补充内容 (2016-11-5 14:34):
貌似是一样的==
回复 支持 0 反对 1

使用道具 举报

w3039126 发表于 2016-11-5 14:12:12 | 显示全部楼层
好详细,先mark,赞楼主
回复 支持 反对

使用道具 举报

 楼主| jinyyy666 发表于 2016-11-5 23:59:21 | 显示全部楼层
wtcupup 发表于 2016-11-5 14:03
补充内容 (2016-11-5 14:34):
貌似是一样的==

对的 你的code应该是对的 你可以自己再随便跑一个test case试试看
回复 支持 反对

使用道具 举报

 楼主| jinyyy666 发表于 2016-11-5 23:59:25 | 显示全部楼层
wtcupup 发表于 2016-11-5 14:03
补充内容 (2016-11-5 14:34):
貌似是一样的==

对的 你的code应该是对的 你可以自己再随便跑一个test case试试看
回复 支持 反对

使用道具 举报

1451427216 发表于 2016-11-6 02:37:01 | 显示全部楼层
多谢楼主,先mark住
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-11-6 23:48:31 | 显示全部楼层
k color的话,觉得k pass 更容易理解跟code。当然也是two ptr的思路
回复 支持 反对

使用道具 举报

xuzhikun 发表于 2016-11-7 01:43:08 | 显示全部楼层
http://www.lintcode.com/en/problem/sort-colors-ii/这应该是第二问对应的题
回复 支持 反对

使用道具 举报

南慕伦 发表于 2016-11-7 02:57:07 | 显示全部楼层
荷兰国旗问题排序。话说回来,为啥不k个全部数一次然后一个一个放回去……
回复 支持 反对

使用道具 举报

 楼主| jinyyy666 发表于 2016-11-8 01:02:37 | 显示全部楼层
南慕伦 发表于 2016-11-7 02:57
荷兰国旗问题排序。话说回来,为啥不k个全部数一次然后一个一个放回去……

我说了这种方法 但是面试官说你再想想其他的
回复 支持 反对

使用道具 举报

Lilzy 发表于 2016-11-8 01:25:15 | 显示全部楼层
感觉是LC sort Color和Lintcode sort Color ii的相似版
回复 支持 反对

使用道具 举报

knight0clk 发表于 2017-1-27 01:09:35 | 显示全部楼层
楼主的方法挺好,这里指示感觉用sort k color解决的话,复杂度是O(nk),对吧?可能有时候换成quick sort O(n log n)是个更好的选择?
回复 支持 反对

使用道具 举报

rsm 发表于 2017-1-27 02:22:43 | 显示全部楼层
赞lz分享。
mark一下。
回复 支持 反对

使用道具 举报

douch 发表于 2017-6-25 14:54:08 | 显示全部楼层
小弟有个很弱的问题请教lz 这种sort k colors为啥不直接排序呢?
回复 支持 反对

使用道具 举报

FightForTomo 发表于 2017-6-25 17:01:27 | 显示全部楼层
通排序. Waral 鍗氬鏈夋洿澶氭枃绔,


紫薯紫薯
回复 支持 反对

使用道具 举报

celia0417 发表于 2017-7-5 07:52:12 | 显示全部楼层
感謝樓主啊!!!
回复 支持 反对

使用道具 举报

 楼主| jinyyy666 发表于 2017-8-16 11:44:56 | 显示全部楼层
douch 发表于 2017-6-25 14:54
小弟有个很弱的问题请教lz 这种sort k colors为啥不直接排序呢?
.1point3acres缃
应该也是可以的 但是因为是基于之前问的 我就按照之前的思路顺着想下去了
回复 支持 反对

使用道具 举报

sugar 发表于 2017-9-7 07:02:25 | 显示全部楼层
jinyyy666 发表于 2017-8-16 11:44. visit 1point3acres.com for more.
应该也是可以的 但是因为是基于之前问的 我就按照之前的思路顺着想下去了

不知道楼主能不能看到我的回复
楼主follow up的思路很好,但是实际测试结果好像是有问题的
比如这组数据3, 1, 2, 0, 1, 3, 2, 2, 4, 6, 7, 0, 1, 2
结果是0 0 1 1 1 2 2 2 2 3 3 6 4 7
楼主有时间可以测试下,看看,谢谢。
另外楼主贴的代码也有些小问题。
回复 支持 反对

使用道具 举报

oscarlyz 发表于 2017-9-7 08:48:50 | 显示全部楼层
感觉楼上讲的很清楚啊。。学习了。。。
回复 支持 反对

使用道具 举报

lcq123 发表于 2017-9-7 10:11:47 | 显示全部楼层
wtcupup 发表于 2016-11-5 14:03
补充内容 (2016-11-5 14:34):
貌似是一样的==

great solution!!!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-18 01:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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