推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

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

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

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

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

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

x
FB 实习 新鲜的一面面筋! 回馈地里!!
大家很多人提到了一道sort color的变种,我今天就遇到了,趁现在还记得详细跟大家说一下。

. 鍥磋鎴戜滑@1point 3 acres给定一个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, 应该怎么办?. 鍥磋鎴戜滑@1point 3 acres
. from: 1point3acres.com/bbs
顺着上一题的思路,我的想法是将(0,1,。。。,k-1) category 分成(0)--> L, (1, k-2) -->M, (k-1) --> H, 然后相同的思想继续call之前的function,然后reduce为 (1,k-2)的range,重复之前的事情

大家可以再仔细想想这里面有什么问题。
. from: 1point3acres.com/bbs
第一要注意的是,之前的function应该变成:.1point3acres缃

sortCategory(nums, low, high) (low and high is the corresponding int of the "L" and "H" category)
要记得把front和back一个指针变一下,如下:

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


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

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

第三个要注意的是,在新的sortKCategory里面,while loop的条件
Code:
void sortKCategory(vector<int>& nums, int k){. From 1point 3acres bbs
    if(nums.empty() || k <= 0) return;
    int beginCat = 0, endCat = k-1;
    while(beginCat < endCat){
        sortCategory(nums, beginCat++, endCat--);
    }
}

void sortCategory(vector<int>& nums, int low, int high){
    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条件
.1point3acres缃        if(getCategory(nums) == low) swap(nums, nums[front++]); //注意为什么不用decrease i!
        if(getCategory(nums) == high) swap(nums[i--], nums[back--]); //注意为什么要decrease i! 会问你的
    }. from: 1point3acres.com/bbs
}. 鍥磋鎴戜滑@1point 3 acres


评分

2

查看全部评分

本帖被以下淘专辑推荐:

wtcupup 发表于 2016-11-5 14:03:11 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
  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;. 鍥磋鎴戜滑@1point 3 acres
  7.         int min = 1, max = k;
  8.         while (min < max) {
  9.             while (i <= pr) {
  10.                 if (getCat(nums[i]) == min) {. visit 1point3acres.com for more.
  11.                     swap(nums, pl, i);
  12.                     i++;
  13.                     pl++;
  14.                 } else if (getCat(nums[i]) == max) {
  15.                     swap(nums, pr, i);
  16.                     pr--;
  17.                 } else {
  18.                     i++;
  19.                 }
  20.             }
  21.             i = pl;
  22.             min++;
  23.             max--;-google 1point3acres
  24.         }
  25.     }

  26.     private void swap(int[] colors, int i, int j) {
  27.         int temp = colors[i];
  28.         colors[i] = colors[j];. Waral 鍗氬鏈夋洿澶氭枃绔,
  29.         colors[j] = temp;. from: 1point3acres.com/bbs
  30.     }
复制代码

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

使用道具 举报

w3039126 发表于 2016-11-5 14:12:12 | 显示全部楼层
关注一亩三分地微博:
Warald
好详细,先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分享。. 1point3acres.com/bbs
mark一下。
回复 支持 反对

使用道具 举报

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

使用道具 举报

FightForTomo 发表于 2017-6-25 17:01:27 | 显示全部楼层
通排序


紫薯紫薯
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-25 03:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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