Halo

A magic place for coding

0%

实习面经 -- 综合版

面试总结之综合总结

   这一部分总结归纳了一些面试中遇到的特别有趣的问题,因为这些都没有正确答案,所以给出的是我个人的观点,欢迎大家补充!

   本博客长期更新,欢迎大家收藏、订阅!


秒杀、抢购系统

  • 难点:
    1. 高并发
    2. 超卖
  • 架构:
    1. 浏览器端:最上层,js 代码
    2. 站点层:这一层访问后端数据,拼接好 HTML 页面返回给浏览器
    3. 服务层:向上游屏蔽底层数据细节,提供数据访问
    4. 数据层:底层数据库
  • 思路:
    1. 将请求拦截在上游
    2. 利用缓存,读多写少
  • 方案:
    1. 浏览器层面
      • 产品:点击后按钮置灰,禁止用户重复提交
      • js 代码:限制用户在 n 秒内只能提交 1 次
    2. 站点层请求拦截与页面缓存
      • 页面静态化
      • 对同一个 UID,限制访问频率,做页面缓存,n 秒内到达站点层的请求,均返回同一个页面
    3. 服务层请求拦截与数据缓存
      • 写请求,做请求队列排队,每次只透过有限的写请求异步写入到数据层,成功则放下一批;如库存不足,则队列里的写请求全部返回 “已售完”
      • 读请求,可以使用 redis。

老虎吃羊问题

  • 问题:在岛上有 100 只老虎和 1 只羊,老虎可以吃草,但更愿意吃羊。如果每次只有一只老虎可以吃羊,而且一旦他吃了羊,他自己就变成羊;而且所有的老虎都是聪明而且完全理性的,他们的第一要务是 ** 生存 **。 请问最后这只羊会不会被吃?如果是 n 只老虎和 1 只羊呢?

  • 问题分析:这类问题是逻辑问题,不需要通过很复杂的算法去解决,我的解决办法就是从 1 开始列举情况。从 1 只老虎开始。

    • 1 只老虎:吃,因为吃了之后就只剩 1 只羊,没有危险;
    • 2 只老虎:不吃,因为吃了之后就变成了第一种情况,而上一种情况是选择吃的;
    • 3 只老虎:吃,因为吃了之后就变成了第二种情况,而上一种情况是选择不吃;

    以此类推,我们可以发现规律:** 如果老虎数目是奇数,则选择吃;如果是偶数,则选择不吃 **


飞机加油问题

  • 问题:已知每个飞机只有一个油箱,飞机之间可以互相加油。一箱油可以供一架飞机绕地球飞半圈。问:为使至少一架飞机绕地球一圈回到起飞时的飞机场,至少需要出动几架飞机?

    • 所有飞机从同一个机场起飞,且必须安全返回机场
    • 不允许中途降落,但可以加油。
  • 问题分析:这个问题直接去想是非常困难的,因为中间有加油的过程,就算从 1 架、2 架这样一种一种情况列举下去,也有可能因为把握不准最佳的加油时机而得出错误的答案。题目要求的是最优解,我们从答案倒推。有一架要完整地绕地球一圈,所以他带的那一箱油必须支持他独自飞行半圈。那么问题现在拆分为两个:

    • 第一,独自飞行的半圈是哪个半圈?
    • 第二,剩下的半圈如何解决油量问题?

    先来看第一个问题,可能直觉上一开始就觉得是后半圈,但是实际情况并不是这样的。首先要理解 ** 加油的代价是由加油点与起点的距离决定的 **,也就是说,加油点与起点越远,加油的代价越高,这是因为与起点越远,能加的油量就越少。我们希望的是尽可能多的油是用于加油,而不是用于支持加油飞机的往返。所以这个加油点需要离起点尽可能地近。因为地球是圆的,所以在起点的飞机可以往两个方向飞,因此可以把加油点设置在 A、B 两点。这样,环绕一圈的飞机的油就需要支持他独自飞 A-B。

    再来看第二个问题,第一问确定了两个加油点之后,会发现其实两段式对称的,也就是说,解决了一个就可以了,因为另一边只是方向反了而已,而且飞机是可以重复使用的。我们用 A 点来分析,要保证 A 点处飞机 1 满油,则需要有飞机 2 给他加油,但是飞机 2 是需要往返的,所以飞机 2 本身的油量是用于往返起点和 A 点的。这样就需要有飞机 3 提供加油的油量,飞机 3 也是需要往返的,所以需要在 C 点处对飞机 1、2 加油。飞机 3 用自己 1/2 油进行往返,剩下的 1/2 分成两份,给飞机 1、2。这样在 C 点处飞机 1、2 都是满油的,所以在 A 点处,飞机 2 就能把 1/4 的油给飞机 1,从而使得飞机 1 在 A 点满油。

    plane problem

    所以这题的答案就是 **3 部飞机,共起飞 5 次 **!

Welcome to my other publishing channels