一亩三分地论坛

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

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

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

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

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

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

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

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

很简单,用sortcolor: https://leetcode.com/problems/sort-colors/ 就可以解决,两个ptr,一个前一个后。LZ不小心有一个bug (for loop 不太对),但是测试的时候找到了。
. visit 1point3acres.com for more.
第二问 ---- 如果这个时候有K个category, 应该怎么办?

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

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

第一要注意的是,之前的function应该变成:. 1point 3acres 璁哄潧

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--;

. From 1point 3acres bbs
这样就不用再次处理之前处理过的category了。

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

第三个要注意的是,在新的sortKCategory里面,while loop的条件
Code:. from: 1point3acres.com/bbs
void sortKCategory(vector<int>& nums, int k){
    if(nums.empty() || k <= 0) return;
    int beginCat = 0, endCat = k-1;. visit 1point3acres.com for more.
    while(beginCat < endCat){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        sortCategory(nums, beginCat++, endCat--);
    }
}

void sortCategory(vector<int>& nums, int low, int high){.1point3acres缃
    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.com/bbs
        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. 帮忙看看我这样是不是更简单一点?
    . 1point3acres.com/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;.1point3acres缃
  8.         while (min < max) {
  9.             while (i <= pr) {
  10.                 if (getCat(nums[i]) == min) {
  11.                     swap(nums, pl, i);
  12.                     i++;
    . 1point3acres.com/bbs
  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--;
  24.         }
  25.     }

  26.     private void swap(int[] colors, int i, int j) {
  27.         int temp = colors[i];
  28.         colors[i] = colors[j];
  29.         colors[j] = temp;
  30.     }
复制代码

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

使用道具 举报

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个全部数一次然后一个一个放回去……
. 鍥磋鎴戜滑@1point 3 acres
我说了这种方法 但是面试官说你再想想其他的
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 03:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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