传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 4008|回复: 19
收起左侧

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

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

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

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

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

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

给定一个API getCategory(int n), return {L| M| H} 三种category.鐣欏璁哄潧-涓浜-涓夊垎鍦

第一问 --- 给定一个Array, [4,2,5,7,8,9], 对于每一个int,有一个category,sort them by category
.1point3acres缃
很简单,用sortcolor: https://leetcode.com/problems/sort-colors/ 就可以解决,两个ptr,一个前一个后。LZ不小心有一个bug (for loop 不太对),但是测试的时候找到了。
. more info on 1point3acres.com
第二问 ---- 如果这个时候有K个category, 应该怎么办?. From 1point 3acres bbs

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

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

第一要注意的是,之前的function应该变成:
.鐣欏璁哄潧-涓浜-涓夊垎鍦
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--;


这样就不用再次处理之前处理过的category了。
.1point3acres缃
第二个要注意的是,其实之前的sortCategory也可以处理只有两种Category的case,不用担心, 直接call

第三个要注意的是,在新的sortKCategory里面,while loop的条件
Code:
void sortKCategory(vector<int>& nums, int k){. 鍥磋鎴戜滑@1point 3 acres
    if(nums.empty() || k <= 0) return;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    int beginCat = 0, endCat = k-1;
    while(beginCat < endCat){
        sortCategory(nums, beginCat++, endCat--);. 1point 3acres 璁哄潧
    }
}

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条件. From 1point 3acres bbs
        if(getCategory(nums) == low) swap(nums, nums[front++]); //注意为什么不用decrease i!
        if(getCategory(nums) == high) swap(nums[i--], nums[back--]); //注意为什么要decrease i! 会问你的. more info on 1point3acres.com
    }
}


评分

2

查看全部评分

本帖被以下淘专辑推荐:

wtcupup 发表于 2016-11-5 14:03:11 | 显示全部楼层
  1. 帮忙看看我这样是不是更简单一点?. From 1point 3acres bbs
  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++;
  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;. 1point 3acres 璁哄潧
  22.             min++;. 鍥磋鎴戜滑@1point 3 acres
  23.             max--;
  24.         }. 1point3acres.com/bbs
  25.     }.1point3acres缃
  26. .1point3acres缃
  27.     private void swap(int[] colors, int i, int j) {
  28.         int temp = colors[i];. From 1point 3acres bbs
  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.1point3acres缃
荷兰国旗问题排序。话说回来,为啥不k个全部数一次然后一个一个放回去……
.1point3acres缃
我说了这种方法 但是面试官说你再想想其他的
回复 支持 反对

使用道具 举报

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 | 显示全部楼层
通排序


紫薯紫薯
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| jinyyy666 发表于 2017-8-16 11:44:56 | 显示全部楼层
douch 发表于 2017-6-25 14:54
小弟有个很弱的问题请教lz 这种sort k colors为啥不直接排序呢?

应该也是可以的 但是因为是基于之前问的 我就按照之前的思路顺着想下去了
回复 支持 反对

使用道具 举报

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

不知道楼主能不能看到我的回复.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主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-9-25 23:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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