斗鱼面试题

[into-piece]

function lottery(whiteList, participant){}

whiteList:类型字符串数组,意义是表示从其他系统中计算出来的活跃用户，如果这批用户参与抽奖，则必定让他中奖。长度不超过1万

participant:类型字符串数组,意义是表示此次活动中真正参与抽奖的用户，长度约是10万。

函数希望从participant返回 2 万个用户，表示中奖用户，优先选取whiteList上的用户，若不在whiteList上，对participant 剩余的随机选取即可。

[into-piece]

/**
 *
 * @param {*} whiteList 活跃用户
 * @param {*} participant 抽奖用户
 */
function lottery(whiteList: string[], participant: string[]): string[] {
  const pLen = participant.length,
    wLen = whiteList.length,
    targetNum = 20000, // 中奖客户数量
    obj = {};
  if (pLen === 0) return [];
  if (pLen <= targetNum) return participant; // 参与抽奖用户少于等于中奖目标用户数，参与抽奖的用户全部中奖
  let result: string[] = [];
  let i = 0;
  const map = new Map();
  while (i < wLen && result.length <= targetNum) {
    const pIndex = participant.indexOf(whiteList[i]);
    if (pIndex !== -1) {
      map.set(pIndex, true);
      result.push(whiteList[i]);
    }
    i++;
  }

  while (result.length < targetNum) {
    const index = Math.floor(Math.random() * pLen);
    if (map.has(index)) continue;
    result.push(participant[index]);
    map.set(index, true);
  }

  return result;
}

const whiteList = Array.from({ length: 10000 }, (v, k) => "" + k);
const participant = Array.from({ length: 100000 }, (v, k) => "" + k);
console.time("lottery initialize");
console.log(lottery(whiteList, participant));
console.timeEnd("lottery initialize");

[into-piece]

/**
 *
 * @param {*} whiteList 活跃用户
 * @param {*} participant 抽奖用户
 */
function lottery(whiteList: string[], participant: string[]): string[] {
  const pLen = participant.length,
    wLen = whiteList.length,
    targetNum = 20000, // 中奖客户数量
    pObj: any = {}, //空间
    wObj: any = {}; //空间
  if (pLen === 0) return [];
  if (pLen <= targetNum) return participant; // 参与抽奖用户少于等于中奖目标用户数，参与抽奖的用户全部中奖
  let result: string[] = [];
  let i = 0;
  const map = new Map();

  for (let i = 0; i < participant.length; i++) {
    const element = participant[i];
    pObj[element] = true;
    if (i < wLen) {
      wObj[whiteList[i]] = true;
    }
  }

  Object.keys(wObj).forEach((key) => {
    if (pObj[key]) {
      result.push(key);
      delete pObj[key];
    }
  });

  const arr = Object.keys(pObj);
  while (result.length < targetNum) {
    const index = Math.floor(Math.random() * arr.length);
    if (map.has(index)) continue;
    result.push(arr[index]);
    map.set(index, true);
  }

  return result;
}

const whiteList = Array.from({ length: 10000 }, (v, k) => "" + k);
const participant = Array.from({ length: 100000 }, (v, k) => "" + k);
console.time("Array initialize");
console.log(lottery(whiteList, participant));
console.timeEnd("Array initialize");