分享今天遇到的三个代码设计

2021/11/25

前言

今天面了我Dream Company的二面,面试官节奏很快,还是电话面试,几乎不让你多讲话,只听他想的结果….搞得我有点紧张,加上本身对这次面试挺重视的…这就更紧张了😭。感觉自己表现得不是特别好,可能这就是大厂吧,不过本质还是自己菜…..。其实我自己也做过面试官和候选人进行交流,站在我的角度来说,我和候选人的目标是一致的,我想知道候选人的真实水平,候选人也想展示自己的真实水平。但是今天的二面感觉是技术leader,可能比较忙,面的人也多。

不过今天收获还是有的,听到一些平时不一样的设计题,我面后也自己思考了一下,感觉很有意思,然后在这里重新总结复盘一下。当然期间有很多问题,例如设计排行榜之类的,因为大家都常问,然后自己项目里面也有广泛落地,这类就不写。

本文相关代码已上传到github

40亿个QQ号码如何去重?

这个其实也属于常见的问题,例如海量日志数据,提取出某日访问百度次数最多的那个IP、寻找热门查询,300万个查询字符串中统计最热门的10个查询、给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?都是海量数据的常见设计。大部分的标答都是使用bitmap来做到时间和空间的平衡,但是因为原来做过大数据相关的工作,如果进行查重我更会倾向于使用MapReduce来处理。当然如果面试官问求中位数,求top-k那我肯定使用bitmap进行排序一遍搞定。

只是单纯的问去重,大家最能想到的就是hash,但是如果直接用hash占用内存是会超过限制的,但是MapReduce就是来解决这个问题,MapReduce是一种计算模型,它把大量数据的工作或者数据分解,最终在将结果合并。本质有点像归并排序,思想就是分而治之,Hadoop就是一种实现了MapReduce模式的开源分布式并行处理框架。

那么对于这个QQ号去重,我们只要把数据进行映射分割交给不同的机器去处理(这个过程做map),最后不断地规约(这个过程叫reduce)。具体来做,我们可以

  1. 我们先采用映射的方法,比如%10000把装载QQ号的文件进行拆分,这样就会分成10000文件,然后分发到不同的结点,每个结点都有负责自己两个文件。
  2. 当大文件转换成小文件以后,每个结点可以把文件加载到自己内存中进行去重,这里使用常见的hash去重就ok。
  3. 每两小文件最终会成为一个去重的更小文件,然后我们再不断地把两个结点文件合并,一直归并到最后只有一个文件。

这样的进行数据划分,结果归约最后就是一个去重的文件了。这个理论其实可以来解答问题,哈希计数,哈希去重。bitMap是一个好答案,但是MapReduce回答也同样不会掉分,相反这类场景设计问题考察的主要自己平时积累以及想法,至少我不会限制候选人去脑洞大开(当然我的面试官也没有,对这个答案还是给予了肯定,hhhh)。

微信抢红包金额怎么分

粗略想法

这个问题好像原来在公众号看过,但看完忘记了。今天突然被问到这个问题,我第一时间不是想着回答,而是我也想知道,这该死的好奇心。平时习以为常的东西,其实都没有从一个工程师的角度去思考原理,真的是失职。

听到题目以后发现盲区,其实非常紧张,都忘记自己思考多少秒了,贸贸然就开始答。自己想法是既然是抢红包,肯定是进行random,那么怎么进行random。要确定每个人的random金额的上届和下界,下界自然是每人都是1分上界是剩余金额-人数 * 1分(因为要保证每个人至少要1分),也就是随机区间是[1分, 剩余金额 - 人数 * 1分]。但是这样会分布不平衡,也就是说不公平,因为先抢到的人会很有优势,因为它可以随机到更大的数字,而越往后的人随机到的平均份额越小。其实我写了代码跑了一下,实际情况来看,使用默认随机种子的情况下几轮下来大头就被拿走了。

假设有10个人,红包总额100分。

第一个人的随机范围是(1,100 - 9),平均可以抢到45.5分,假设这个人抢到了45.5

第二个人的随机范围是 (1, 45.5 - 8),平均可以抢到18.75分,假设这个人抢到了18.75

第二个人的随机范围是 (1, 18.75 - 7),平均可以抢到11.75分,假设这个人抢到了11.75

……

虽然我例子中举的是平均值,但是依次往后会越来越小这是必然的。

仔细思考

事后仔细思考,其实发现我这个思路是可以的,因为确定随机是上界和下界是第一步,只不过目前上界是不公平的,那么如果我们把这个上界变成是根据剩下剩余人数进行动态调整到一个合理的区间。但是怎么找这个值。我在网上翻了翻,发现看到一个二倍均值法,使用二倍均值法来确定每个人的红包金额上界,做法是把红包金额除以人数然后在乘以两倍,相当于区间是[1, 剩余金额 / 剩余人数 * 2]。我的理解是这个上界每次都会根据剩余金额和剩余人数进行调整,在一定程度上可以保证分布公平,因为遵循正态分布,所以就整体数学期望来看其实是公平的。比如下面

假设有10个人,红包总额是100分。

第一个人的随机范围是 (1,100/10*2),平均10块钱,假设这个人抢到了10

第二个人的随机范围是 (1,90/9*2),也是平均10块钱,假设这个人抢到了10

….

第十个人的随机范围是 (1,10/1*2),平均10块钱,假设这个人抢到了10

这样一波下来,如果遵循这个分布,其实大家拿的钱都差不多。但是既然是随机,也会出现平均值波动的情况,比如下面

假设有10个人,红包总额是100分。

第一个人的随机范围是 (1,100/10*2),假设这个人抢到了15

第二个人的随机范围是 (1,85/9*2 = 18.888),假设这个人抢到了15

第三个人的随机范围是 (1,70/9*2 = 15.555),假设这个人抢到了15

可以看到,这样的话,其实对于后面的人来说也是不太公平的,因为第一个人[0,20]的区间,就是因为第一个人随机了多一点,就会影响后面人的区间。但是动态调整了上界这样在一定程度不会让值相差特别多,我使用代码实现了一遍。发现结果还行

代码太长了,代码已上传到github

30个人抢100分钱
第1抢到了4分, 还剩下96分, 区间是[1, 6.666667]
第2抢到了5分, 还剩下91分, 区间是[1, 6.620690]
第3抢到了2分, 还剩下89分, 区间是[1, 6.500000]
第4抢到了1分, 还剩下88分, 区间是[1, 6.592593]
第5抢到了3分, 还剩下85分, 区间是[1, 6.769231]
第6抢到了4分, 还剩下81分, 区间是[1, 6.800000]
第7抢到了4分, 还剩下77分, 区间是[1, 6.750000]
第8抢到了1分, 还剩下76分, 区间是[1, 6.695652]
第9抢到了5分, 还剩下71分, 区间是[1, 6.909091]
第10抢到了4分, 还剩下67分, 区间是[1, 6.761905]
第11抢到了5分, 还剩下62分, 区间是[1, 6.700000]
第12抢到了5分, 还剩下57分, 区间是[1, 6.526316]
第13抢到了6分, 还剩下51分, 区间是[1, 6.333333]
第14抢到了4分, 还剩下47分, 区间是[1, 6.000000]
第15抢到了1分, 还剩下46分, 区间是[1, 5.875000]
第16抢到了3分, 还剩下43分, 区间是[1, 6.133333]
第17抢到了1分, 还剩下42分, 区间是[1, 6.142857]
第18抢到了4分, 还剩下38分, 区间是[1, 6.461538]
第19抢到了2分, 还剩下36分, 区间是[1, 6.333333]
第20抢到了5分, 还剩下31分, 区间是[1, 6.545455]
第21抢到了1分, 还剩下30分, 区间是[1, 6.200000]
第22抢到了6分, 还剩下24分, 区间是[1, 6.666667]
第23抢到了1分, 还剩下23分, 区间是[1, 6.000000]
第24抢到了4分, 还剩下19分, 区间是[1, 6.571429]
第25抢到了3分, 还剩下16分, 区间是[1, 6.333333]
第26抢到了4分, 还剩下12分, 区间是[1, 6.400000]
第27抢到了5分, 还剩下7分, 区间是[1, 6.000000]
第28抢到了1分, 还剩下6分, 区间是[1, 4.666667]
第29抢到了3分, 还剩下3分, 区间是[1, 6.000000]
最后一个已经抢完, 金额为3
已经抢完, 总共金额为100分

除此之外还发现一个缺点,就是最后一个人抢到的绝对是不公平的,因为他只能拿别人签完剩下的。我仔细思考了一下这个问题,这真的是悖论,一方面是随机,一方面又要保证没人能拿到的钱尽量概率一致。看了很多博客,大部分人也是对这个不是很满意,他们提出一种时间和复杂度都更高的“线性切割法”的算法,思想是把总金额数值抽象成一条绳子,对绳子进行切割,一共切人数-1刀。这样每人切得的金额就是绳子的占比,我想落地下来,但是发现要考虑的点很多,难度有点大,就放弃了。参考三使用的是类似的算法来分割一个数字,感兴趣的可以了解。

打乱扑克牌

这个题目说实话我原来在学校刚开始学C语言的时候做过这个题,不知道是我自学的视频里面的题目还是买的教材里面的题目。但是因为紧张没想出很好地方法,甚至我听到这个题目时紧张到让面试官讲一下重新讲一下具体的场景….其实是想拖延时间,让我有更多的时间进行思考,但是我能感受到那个时候面试官已经翻白眼了….这也是电话面试的缺陷,电话中长时间不说话进行思考挺尴尬的,不如视频或现场面试中可以进行眼神交流或者让对方看到你思考的表现。

最终我小心翼翼问是否可以用jdk的api,面试官很友好说可以,那我给出的方法是Collections.shuffle();,面试官问我知道这个是怎么实现的,这个我真不知道,只能说没看过这部分的源码。其实面试官应该是先让我实现shuffle()代码的,因为我事后看了一下,其实使用Random()来做随机洗牌的,唉,但是在沉着一点印象就能好一点了。面试中其实我也说到一种多线程完成,我觉得这个其实也可以,但是当时没有很好地思路,所以没有继续往下说,这里我分享我的事后思考的代码。

  /**
   * 花色的list
   */
  List<String> colors = Lists.newArrayList("黑桃", "红心", "梅花", "方块");

  /**
   * 字面值的list. 使用双流合并, 因为很懒不愿意打2-10, 就用IntStream来生成了
   */
  List<String> numbers = Stream.concat(IntStream.rangeClosed(2, 10).mapToObj(String::valueOf),
      Stream.of("A", "J", "K", "Q")).collect(Collectors.toList());

先定义一下结构,两个Set,里面分别是花色和字面值。再次提示哦,代码已上传到github

Collections.shuffle()

  @Test
  public void collectionShuffleTest() {
    // 进行组合
    List<String> result = colors.stream()
        .flatMap(color -> numbers.stream().map(number -> color + number))
        .collect(Collectors.toList());

    // 进行打乱
    Collections.shuffle(result);
    // 在console输出(为了方便看, 转成pretty的json)
    System.out.println(JSON.toJSONString(result, SerializerFeature.PrettyFormat));
  }

随机数swap

  @Test
  public void randomSwapTest() {
    // 进行组合
    List<String> result = colors.stream()
        .flatMap(color -> numbers.stream().map(number -> color + number))
        .collect(Collectors.toList());

    // 进行打乱52次
    for (int count = result.size(); count > 0; count--) {
      // 生成对换的随机数
      int site1 = RandomUtil.randomInt(0, result.size() - 1);
      int site2 = RandomUtil.randomInt(0, result.size() - 1);
      // 进行wap
      String temp = result.get(site1);
      result.set(site1, result.get(site2));
      result.set(site2, temp);
    }

    // 在console输出(为了方便看, 转成pretty的json)
    System.out.println(JSON.toJSONString(result, SerializerFeature.PrettyFormat));
  }

代码其实很简单,和写业务代码差不多,这么简单当时我没啥想不到呢。不过我看了一下,感觉空间复杂度很高,一方面每次需要生成两个随机数的坐标,另外一方面每次swap需要一个额外的空间。但是这并不是数字交换所以也没办法进行位运算优化,而且我研究了一下Collections.shuffle()的实现,和我这个差不多。

/**
 * Swaps the two specified elements in the specified array.
 */
private static void swap(Object[] arr, int i, int j) {
    Object tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

下次有想到更好地方案再来补充

尝试使用多线程

因为有随机性质,所以想过多线程的非公平锁竞争方案,如果把要排的内容放到一个队列里面显然怎么执行都是有序的,除非你随机读取或者随机放置,但是这和多线程就没有啥关系了。

最简单的版本就是使用JDK的ForkJoinPool.commonPool()线程池,利用Stream的parallel把每个元素进行分散并发添加到最后的结果容器当中,实测下来可能是碍于并行度不高的原因,虽然可以打散,但是连花色的情况比较多,可以替换Stream的线程池自己调整并行度,效果应该会好很多。

@Test
@SuppressWarnings("all")
public void parallelStreamTest() {
  // 先构建扑克牌
  List<String> rawList = colors.stream()
      .flatMap(color -> numbers.stream().map(number -> color + number))
      .collect(Collectors.toList());

  // 创建容器
  List<String> result = new ArrayList<>(sumCount);

  // 使用副作用进行并行添加到容器中
  rawList.parallelStream().forEach(result::add);

  // 在console输出(为了方便看, 转成pretty的json)
  System.out.println(JSON.toJSONString(result, SerializerFeature.PrettyFormat));
  System.out.println(result.size());
}

然后自己实现了一下,发现比想象中的难好多啊;我想过把所有牌面按照花色分组,然后四个组(线程)竞争一把ReentrantLock的非公平锁,然后使用condition来控制随机顺序,每个组是一个装有该花色所有牌面的Queue,然后每次随机到这个线程就出队一个元素到结果容器中。我也想过分成花色组和面值组然后进行然后每个组的花色都对面值进行并行的扫一遍,面值也是队列扫一个就出队一个。但是判断临界值和操作逻辑无法保证原子性,线程安全问题频出,想了一下午了,最终落地了这样的方案

 @Test
  @SneakyThrows
  @SuppressWarnings("all")
  public void multithreadingTest() {
    // 把花色先分好
    List<Queue<String>> rawList = colors.stream()
        .map(color -> numbers.stream().map(number -> color + number)
            .collect(Collectors.toCollection(LinkedList::new)))
        .collect(Collectors.toList());

    List<String> result = new ArrayList<>(sumCount);
    // 偷懒使用jdk自带的线程池
    ExecutorService executor = Executors.newCachedThreadPool();
    CountDownLatch countDownLatch = new CountDownLatch(colorCount);

    for (int i = 0; i < colorCount; i++) {
      int current = i;
      ReentrantLock lock = new ReentrantLock();
      for (int count = 1; count <= numberCount; count++) {
        executor.execute(() -> {
          lock.lock();
          if (CollectionUtil.isNotEmpty(rawList.get(current))) {
            result.add(rawList.get(current).poll());
          }
          lock.unlock();
        });
      }
      countDownLatch.countDown();
    }

    // 防止主线程提前结束
    countDownLatch.await(10, TimeUnit.SECONDS);

    // 在console输出(为了方便看, 转成pretty的json)
    System.out.println(JSON.toJSONString(result, SerializerFeature.PrettyFormat));
    System.out.println(result.size());
  }

先说明,这个是线程安全问题的,不能够每次都按照预期发挥作用,但是忙活一下午也要给自己也交代,等以后有时间在继续优化优化,我也希望各位大佬给一点思路或者指出问题。

后言

其实都是很简单的问题,而且都没有标准答案,写程序嘛其实怎么写用朴素暴力写出来都能AC。但是其中的思考、方案、复杂度才是最有意思的事情,以后有时间我还要在研究研究。

参考

  1. 微信红包的架构设计简介
  2. golang实现二倍均值算法和抢红包的方法

  3. 线性最佳分割算法

(转载本站文章请注明作者和出处 没有气的汽水



┌┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐
├ 文章已经完啦, 想要第一时间收到文章更新可以关注↓ ┤
└┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┘

Post Directory






下面是评论区,欢迎大家留言探讨或者指出错误哈