【Q142】CVTE笔试

[kangyana]

二面

[kangyana]

1. 时间格式转换

将一天24小时按每半小时划分成48段，我们用一个位图表示选中的时间区间，例如110000000000000000000000000000000000000000000000，表示第一个半小时和第二个半小时被选中了，其余时间段都没有被选中，也就是对应00:00~01:00这个时间区间。一个位图中可能有多个不连续的时间区间被选中，例如110010000000000000000000000000000000000000000000，表示00:00-1:00和02:00-02:30这两个时间区间被选中了。

要求：写一个函数timeBitmapToRanges，将上述规则描述的时间位图转换成一个选中时间区间的数组。 示例输入："110010000000000000000000000000000000000000000000" 示例输出：["00:00~01:00", "02:00~02:30"]

解析：主要考察找规律能力

/**
 * 将48位的时间位图格式化成字符串
 * 规律：1开始，1结束，0跳过。
 * @param {string} bitmap 时间位图，110001010101001010000
 **/
function timeBitmapToRanges(bitmap) {
  let index = 0; // 下标
  const ranges = []; // 范围集合
  // 遍历每一位（单位：半小时)
  while (index < bitmap.length) {
    // 0代表跳过
    if (bitmap[index] === '0') {
      index++;
      continue;
    }
    // 1代表开始，记录下来
    const curRange = {
      start: index, // 初始时间
      end: index, // 结束时间
    };
    // 1代表结束
    while (bitmap[index] === '1') {
      curRange.end = index;
      index++;
    }
    ranges.push(curRange);
  }

  // 格式一下时间
  const result = ranges.map((item) => {
    const startTime = formatTime(item.start * 0.5); // *0.5 是半小时换算小时
    const endTime = formatTime(item.end * 0.5 + 0.5);
    return `${startTime}~${endTime}`;
  });
  return result;
}

/**
 * 格式化时间
 * @param {number} time 时间（格式是小时）
 * @returns {string} 
 */
function formatTime(time) {
  const hour = Math.floor(time);
  // 补全小时
  const hourStr = hour < 10 ? `${0}${hour}` : hour;
  // 补全分钟
  const minute = time % 1 === 0.5 ? '30' : '00';
  return `${hourStr}:${minute}`
}

console.log(timeBitmapToRanges('110001010101001010000'))

[kangyana]

2. 数组随机取值

已知有一个数组 const str = [1,2,3,4,5,6,7,8]; 要求实现一个取随机值的函数fn，可以连续从数组中取出不重复的随机值。可以一直取，当取值的数量超过原数组长度时，则开始新一轮随机。 例如： fn(1) // 3 fn(2) // 5,7 fn(2) // 2,4 fn(1) // 8 fn(2) // 1,6 fn(2) // 5,3 fn(3) // 8,6,1

解析：

const initialStack = [1,2,3,4,5,6,7,8]; // 初始栈
let stack = initialStack.slice(0); // 当前栈

function fn(quantity) {
  const randomArr = []; // 随机数组
  let index = 0;
  while (index < quantity) {
    // 栈重置
    if (stack.length === 0) {
      stack = initialStack.slice(0);
    }
    // 取随机索引
    const randomIndex = Math.floor(Math.random() * stack.length);
    // 取随机值
    randomArr.push(stack[randomIndex]);
    // 删除取过的值
    stack.splice(randomIndex, 1);
    index++;
  }
  // 数组转字符串
  const result = randomArr.join();
  console.log(result);
  return result;
}

[kangyana]

3. 逻辑题

有8个小球，其中一个偏重一些，但是不知道是哪一个。有一个天平，请问最少多少次能够把这个小球找出来？

二分法

• 4 4
• 2 2
• 1 1

3次。

三分法

• 3 3 2，33称一下：
  • 平衡，称2
  • 不平衡，称3
• 1 1

2次。

解析：

本质是：用天平称重的结果，去解除所有不确定度。

在本问题中，所谓总不确定性，一共有8个等可能：

• 第1个小球重
• 第2个小球重
• ……
• 第8个小球重

而天平每次能够提供三种结果：左倾，右倾，平衡。 每一种结果，都提供一些信息，使得我们可以消解一部分不确定性。

直观些表达，可以看做是在状态搜索时，走三个分叉，形如三叉树。