蚂蚁的笔试一般使用 CodeSandbox (opens new window) 进行在线编程，建议在面试官发出链接前先提前熟悉 CodeSandbox 的使用。

与其他笔试不同，蚂蚁的笔试一般会给出所有测试用例，要求你的代码能够通过所有测试用例，所以 根据用例调整代码 是十分必要的。有时候你需要自己补充测试用例。

实际上，在 这里 (opens new window) 可以看到蚂蚁的一些笔试题目。

1. 下划线转驼峰

将下划线风格的变量名转换成驼峰风格，如： 输入 alipay_first_quiz 返回 alipayFirstQuiz。

注：下划线只会出现在单词中间，不会出现在开头或者结尾。

测试用例：

snake2camel();  // ''
snake2camel(undefined);  // ''
snake2camel(null);  // ''
snake2camel('');  // ''
snake2camel('alipay');  // 'alipay'
snake2camel('alipay_first_quiz');  // 'alipayFirstQuiz'
snake2camel('aaaa_bb_ccc');  // 'aaaaBbCcc'

思路：

将字符串按 '_' 分割，然后将每个单词（第一个除外）的首字母大写，最后拼接起来。

function snake2camel(str) {
  return typeof str === "string" ? str.split('_').map((s, i) => i > 0 ? s[0].toUpperCase() + s.slice(1) : s).join('') : "";
}

2. 驼峰转下划线

将驼峰风格的变量名转换成下划线风格，如： 输入 alipayFirstQuiz 返回 alipay_first_quiz。

测试用例：

camel2snake();  // ''
camel2snake(undefined);  // ''
camel2snake(null);  // ''
camel2snake('');  // ''
camel2snake('alipay');  // 'alipay'
camel2snake('alipayFirstQuiz');  // 'alipay_first_quiz'
camel2snake('aaaaBbCcc');  // 'aaaa_bb_ccc'
camel2snake('AaaaBbCcc');  // 'aaaa_bb_ccc'

思路：

取出每个大写字母，将其替换为 '_'+字母，最后将字符串转换为小写。

function camel2snake(str) {
  return typeof str === "string" && str ? (str[0] + str.slice(1).replace(/([A-Z])/g, "_$1")).toLowerCase() : "";
}

如果不会正则，也可以遍历字符串。

function camel2snake(str) {
  return typeof str === "string" && str ? (str[0] + str.slice(1).split('').map(ch => ch.toUpperCase() === ch ? '_' + ch : ch).join('')).toLowerCase() : "";
}

3. 两数之和

给出一个数组和一个整数目标值 target，你需要找出 2 个数字，他们相加之和等于目标数字，并返回这两个数字的数组下标（升序排序）。

注：你可以假设给出的入参一定可以找出这样 2 个数字，并且是唯一解。

注：数组中同一个数字不能使用两遍。

例子：数组 [3,4,7,15] 目标 10，则 3 + 7 满足目标 10，返回他们的下标 [0, 2]。

测试用例：

findSum([1, 2], 3);  // [0, 1]
findSum([4, 5, 13, 9], 13);  // [0, 3]
findSum([4, 5, 13, 9], 14);  // [1, 3]
findSum([4, 5, 13, 9], 9);  // [0, 1]
findSum([1, 8, 10, 11], 21);  // [1, 3]

思路：

参考力扣第 1 题 两数之和 (opens new window)。

使用哈希表，遍历数组，判断 target - 当前数字 是否在哈希表中，如果在，返回当前数字的下标和 target - 当前数字 的下标，如果不在，将当前数字作为键，下标作为值存入哈希表。

function findSum(arr, target) {
  const map = new Map();
  for (let i = 0; i < arr.length; i++) {
    if (map.has(target - arr[i])) {
      return [map.get(target - arr[i]), i];
    }
    map.set(arr[i], i);
  }
  return [];
}

4. URL 转 query string

输入一个合法的 URL 返回它的 query string 解析结果（数据结构参考下方单元测试）。

测试用例：

parseQueryString();  // {}
parseQueryString('https://google.com');  // {}
parseQueryString('https://google.com?');  // {}
parseQueryString('https://google.com/?name=jeff&nick=dean');  // { name: 'jeff', nick: 'dean' }
parseQueryString('https://google.com/?name=jeff&nick=&');  // { name: 'jeff', nick: '' }
parseQueryString('https://google.com/?name=jeff&name');  // { name: '' }
parseQueryString('https://google.com/?q=%E6%94%AF%E4%BB%98%E5%AE%9D');  // { q: '支付宝' }
parseQueryString('https://google.com/?q=%2F%3F%26%3D%2F%3F%26%3D%2F%3F%26%3D');  // { q: '/?&=/?&=/?&=' }

思路：

首先拿到 URL 中 /? 后面的数据，然后使用 split('&') 拆分成数组，每一项再使用 split('=') 拆分成键值对，最后使用 decodeURIComponent 解码。

function parseQueryString(url) {
  const ans = {};
  if (typeof url === "string") {
    const query = url.split("/?")[1];
    if (query) {
      const queries = query.split("&").map(s => s.split("="));
      for (const [key, value] of queries) {
        if (key) {
          ans[key] = decodeURIComponent(value || ""); // 防止 value 为 undefined
        }
      }
    }
  }
  return ans;
}

扩展：如果要求用正则解析，可以使用 /([^?&=]+)=?([^?&=]*)/g 匹配。

function parseQueryString(url) {
  const ans = {};
  if (typeof url === "string") {
    url = url.slice(url.indexOf("?") > -1 ? url.indexOf("?") + 1 : url.length);
    const reg = /([^?&=]+)=?([^?&=]*)/g;
    const queries = url.match(reg);
    if (queries) {
      queries.forEach(query => {
        const [key, value] = query.split("=");
        if (key) {
          ans[key] = decodeURIComponent(value || "");
        }
      });
    }
  }
  return ans;
}

5. 对象转 query string

将一个 JSON Object 转换成 query string。

如：输入 { a:1, b:2 } 输出 a=1&b=2。

注意：需要考虑 URL 转义的情况，如中文或特殊字符。

测试用例：

toQueryString();  // ''
toQueryString({});  // ''
toQueryString({ a: 1, b: 2 });  // 'a=1&b=2'
toQueryString({ a: 1, b: undefined });  // 'a=1&b='
toQueryString({ a: 1, b: null });  // 'a=1&b='
toQueryString({ a: 1, b: 0 });  // 'a=1&b=0'
toQueryString({ a: '支付宝' });  // 'a=%E6%94%AF%E4%BB%98%E5%AE%9D'
toQueryString({ a: '/?&=/?&=/?&=' });  // 'a=%2F%3F%26%3D%2F%3F%26%3D%2F%3F%26%3D'

思路：

使用 Object.entries 将对象转换成数组，然后将数组中的每一项转换成 key=value 的形式，最后使用 join('&') 拼接成字符串。

function toQueryString(map) {
  if (!map) {
    return "";
  }
  const ans = [];
  for (const [key, value] of Object.entries(map)) {
    ans.push(`${key}=${encodeURIComponent(value == null ? "" : value)}`);
  }
  return ans.join("&");
}

6. 补集

算出两个数组的补集，数组只包含字符串和数字。

补集：如果 b 是 a 的子集，返回存在于 a 不存在于 b 的元素集合，反之返回空集合。

测试用例：

findComplementarySet(['a', 6, 'b', 3], ['b']);  // [3, 6, 'a']
findComplementarySet([1, 11, 111], [2]);  // []

思路：

首先使用 every 判断 b 是否是 a 的子集，如果是，使用 filter 过滤掉 b 中存在的元素，否则返回空数组。

type TElement = string | number;
function findComplementarySet(a: TElement[], b: TElement[]): TElement[] {
  return b.every(item => a.includes(item)) ? a.filter(item => !b.includes(item)) : [];
}

7. 函数生成器

实现一个函数生成器，接收一个原函数和一组 index，生成一个新函数。

调用新函数时，按照 index 数组中定义的顺序将参数传入原函数中。

测试用例：

const originalFunc = function(a: string, b: string, c: string) {
  return [a, b, c];
};
const f = createRearFunc(originalFunc, [2, 0, 1]);
f('foo', 'bar', 'fiz');  // ['bar', 'fiz', 'foo']

思路：

返回一个函数，该函数接收任意个参数，然后使用扩展运算符和 map 将参数按照 index 数组中定义的顺序传入原函数中。

type TAnyFunction = (...args: any[]) => any;
function createRearFunc(func: TAnyFunction, index: number[]): TAnyFunction {
  return function (...args: any[]) {
    return func(...index.map(i => args[i]));
  };
}

8. 找出文件路径的共同父级目录

给定一组文件路径，找出它们共同的的父级目录。

如果不存在共同的父级目录，返回 null。

测试用例：

findParentDirectory(['/home/admin/vue', '/home/admin/react']);  // '/home/admin'
findParentDirectory(['/home/admin/react/src', '/home/admin/react', '/home/admin/react/src/index.js']);  // '/home/admin/react/src'
findParentDirectory(['/usr/bin', '/etc/config']);  // null

思路：

每个路径都用 split('/') 分割，然后遍历第一个路径的每一项，如果该项在其他路径中也存在，则将该项加入到结果中，否则跳出循环。

共同的父级目录不会超过第一个路径的长度，所以可以遍历第一个路径的每一项。

function findParentDirectory(paths: string[]): string | null {
  const ans = [];
  const dirs = paths.map(path => path.split('/'));
  for (let i = 0; i < dirs[0].length; i++) {
    const dir = dirs[0][i];
    if (dirs.every(d => d[i] === dir)) {
      ans.push(dir);
    } else {
      break;
    }
  }
  return ans.length > 1 ? ans.join('/') : null;
}

9. 重排字符串，使相邻字符不同

重新排列一个字符串，使得每个相邻字符都不同，列出所有情况。

字符串只包含小写字母或者数字。

测试用例：

reorganize('aabb');  // ['abab', 'baba']
reorganize('aaabbbb');  // ['bababab']
reorganize('aabbbc');  // ['ababcb', 'abcbab', 'bababc', 'babacb', 'babcab', 'babcba', 'bacbab', 'bcabab', 'bcbaba','cbabab']
reorganize('1bbbbb');  // []

思路：

使用递归。对字符串的每个字符，将其放在首位，然后对剩余的字符串进行递归，如果剩余字符串重排结果的首位和当前字符不同，则将当前字符和剩余字符串重排结果拼接起来，并加入到 Set 集合去重。

function reorganize(str) {
  const n = str.length;
  if (n === 1) {
    return [str];
  }
  const ans = new Set();
  for (let i = 0; i < n; i++) {
    for (const rest of reorganize(str.slice(0, i) + str.slice(i + 1))) {
      if (rest[0] !== str[i]) {
        ans.add(str[i] + rest);
      }
    }
  }
  return Array.from(ans);
}

10. 数学处理函数

实现一个数学处理的能力，支持链式调用，包括 平方、n 次方、取绝对值。

console.log(myCalculator(-2).abs().sqr().pow(3).getValue()); // 输出64

其中

• abs: 求绝对值
• sqr: 求平方
• pow：求幂

测试用例：

myCalculator(-2).abs().sqr().pow(3).getValue();  // 64

思路：

使用 new 关键字的话就很简单，是一个简单的构造函数题。但是这里给的示例没有使用 new 关键字，所以可以返回一个对象，这个对象的每个方法都返回 this，也就是自身，这样就可以实现链式调用。

function myCalculator(num: number) {
  return {
    num: num,
    abs() {
      this.num = Math.abs(this.num);
      return this;
    },
    sqr() {
      this.num = this.num * this.num;
      return this;
    },
    pow(n: number) {
      this.num = Math.pow(this.num, n);
      return this;
    },
    getValue() {
      return this.num;
    },
  };
}

11. LRU 缓存

LRU 缓存机制，即采用最近最少使用的缓存策略。它的原则是，如果一个数据最近没有被访问到，那么它将来被访问的几率也很小，也就是说当限定的内存空间已没有其他空间可用时，应该把最久没有访问到的数据去除掉。

实现一个 LRU 缓存，提供 get 和 put 两个操作。

另外为了简单起见，key 和 value 都是整数值，并且 value 只为正整数。

因此在 get 操作中，当 key 不存在时，返回 -1 即可。

加分项：除实现功能外，要求两个操作的时间复杂度都是 O(1)。

测试用例：

const aLRU = new LRUCache(2);
aLRU.put(1, 1);
aLRU.put(2, 2);
aLRU.get(1); // 访问一次 key:1
aLRU.put(3, 3); // 因为容量是 2，push key: 3 后，会清除最久未使用的 key: 2 的数据
aLRU.get(2); // -1，key: 2 已经清除

思路：

参考力扣第 146 题：LRU 缓存 (opens new window)。

为了实现 O(1) 的时间复杂度，我们可以使用 Map。Map 本身的顺序就是插入顺序，所以我们可以使用 Map 来实现 LRU 缓存。

class LRUCache {
  /**
   * @param capacity 容量
   */
  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map(); // 缓存
  }
  capacity: number;
  map: Map<number, number>;

  get(key: number): number {
    if (!this.map.has(key)) {
      return -1;
    }
    const value = this.map.get(key);
    this.map.delete(key); // 更新key到最后
    this.map.set(key, value);
    return value;
  }

  put(key: number, value: number): void {
    if (this.map.has(key)) {
      this.map.delete(key); // 更新key到最后
    }
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      this.map.delete(this.map.keys().next().value); // 取出第一个删掉
    }
  }
}

12. 并发执行异步任务

给出一组异步任务方法，和允许同时执行的个数，实现一个方法，用于并发执行异步任务。

• 当有任务执行完毕后，自动补充任务，始终保持正在执行的任务有 concurrency 个。
• 返回 { resolved: [], rejected: [] }。

测试用例：

const tasks = [
  () => new Promise((resolve) => setTimeout(resolve, 1000)),
  () => Promise.resolve('foo'),
  () => fetch('https://codesandbox.io'),
  () => Promise.reject(new Error('tttttttttttttt')),
  () => 'bar',
  () =>
    new Promise((resolve) => {
      const img = new Image();
      img.src =
      'https://gw.alipayobjects.com/mdn/member_frontWeb/afts/img/A*h7o9Q4g2KiUAAAAAAAAAAABkARQnAQ';
      img.onload = resolve;
      img.width = 0;
      img.height = 0;
      document.body.append(img);
    }),
];
const { resolved, rejected } = await parallel(tasks, 2);
resolved.length; // 4
rejected.length; // 1

思路：

使用 Set 来存储正在执行的任务。

每次从列表里传入一个任务，但不要执行，给任务注册 then 和 catch 回调。由于回调返回一个 Promise，我们可以将这个 Promise 放入 Set 中。在回调中，我们将这个 Promise 从 Set 中删除。

每当 Set 的大小达到 concurrency 时，我们就使用 await 执行一个任务，这里可以使用 Promise.race 来实现。

最后，再使用同样的方法，等待所有任务执行完毕。

提示

由于任务可能不是 Promise，所以我们需要使用Promise.resolve() 将其包装成 Promise。

为什么不直接把任务本身的 Promise 放入 Set 中呢？

如果 Promise 被 reject，那么在 await 时，会抛出异常，导致后续任务无法执行。

type TAsyncTask = () => Promise<unknown> | unknown;
async function parallel(
  tasks: TAsyncTask[],
  concurrency: number,
): Promise<{ resolved: unknown[]; rejected: unknown[] }> {
  const ans = { resolved: [], rejected: [] };
  const executing = new Set();
  for (const task of tasks) {
    const p = Promise.resolve(task());
    const e = p
      .then((res) => {
        executing.delete(e);
        ans.resolved.push(res);
      })
      .catch((err) => {
        executing.delete(e);
        ans.rejected.push(err);
      });
    executing.add(e);
    if (executing.size >= concurrency) {
      await Promise.race(executing);
    }
  }
  while (executing.size) {
    await Promise.race(executing);
  }
  console.log(executing);
  console.log(ans);
  return ans;
}

13. 判断一个链路是否对称闭环

判断一个链路是否对称闭环。

测试用例：

isSymmetricalClosed("1->2"); // false
isSymmetricalClosed("1"); // true
isSymmetricalClosed("1->5->3->5->1"); // true
isSymmetricalClosed("1->2->3->1"); // false

思路：

简单双指针。

function isSymmetricalClosed(str) {
  const arr = str.split("->");
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    if (arr[left] !== arr[right]) {
      return false;
    }
    left++;
    right--;
  }
  return true;
}

14. 顺序打印列表

顺序打印一个列表，两次打印间需要有时间间隔。

测试用例：

printList([1, 2, 3, 4], 5);
// 1，（等待5秒）2，（等待5秒）3，（等待5秒）4

思路：

使用 setTimeout。

function printList(list, delay) {
  for (let i = 0; i < list.length; i++) {
    setTimeout(() => console.log(list[i]), delay * 1000 * i);
  }
}

15. 找出树中最大的节点

从一个树状数据结构中，找出值最大的一个节点。

测试用例：

const tree = {
  id: "i1",
  value: 17,
  left: {
    id: "i3",
    value: 83,
    left: { id: "i4", value: 101 },
    right: { id: "i9", value: 22 }
  },
  right: {
    id: "i11",
    value: 26
  }
};
findMaxNode(tree); // { id: "i4", value: 101 }
findMaxNode({ id: "i1", value: 10 }); // { id: "i1", value: 10 }
findMaxNode({ id: "i1", value: 10, left: { id: "i2" } }); // { id: "i1", value: 10 }

思路：

使用递归，每次返回当前树的最大节点。

function findMaxNode(tree) {
  let { left, right, ...max } = tree; // 不取 left 和 right
  if (tree.left) {
    const leftMax = findMaxNode(tree.left);
    if (leftMax.value > max.value) {
      max = leftMax;
    }
  }
  if (tree.right) {
    const rightMax = findMaxNode(tree.right);
    if (rightMax.value > max.value) {
      max = rightMax;
    }
  }
  return max;
}

16. 日程安排类

实现一个日程安排函数，可以不断地登记行程安排，但不允许时间上出现三重重叠。

• 三重重叠的含义为：有某个日期，同时被三次登记覆盖到
• 不考虑不同月份，并且假定每个月都是 31 天
• book(1, 10)，两个数字入参的含义为预定 1~10 号
• 函数返回 true 代表预定成功，返回 false 代表预定失败

测试用例：

const mySchedule = new Calendar();
mySchedule.book(0, 0); // false
mySchedule.book(32, 35); // false
mySchedule.book(1, 10); // true
mySchedule.book(8, 14); // true
mySchedule.book(12, 16); // true
mySchedule.book(22, 30); // true
mySchedule.book(2, 9); // false
mySchedule.book(18, 20); // true
mySchedule.book(13, 17); // false

思路：

本题数据范围很小，直接使用数组模拟即可。

如果数据范围很大，可以使用差分数组或线段树。可以参考力扣第 731 题 我的日程安排表 II (opens new window)。

class Calendar {
  constructor() {
    this.days = new Array(31).fill(0);
  }
  book(start, end) {
    if (start < 1 || start > 31 || end < 1 || end > 31 || start > end) {
      return false;
    }
    if (this.days.slice(start - 1, end).some(v => v >= 2)) {
      return false;
    }
    for (let i = start - 1; i < end; i++) {
      this.days[i]++;
    }
    return true;
  }
}

17. 一维数组转多维数组

实现一个一维数组转多维数组的方法 chunk，接收两个参数：一维数组 array 以及转换后数组的长度 length。

测试用例：

chunk(undefined); // []
chunk(null); // []
chunk([1, 2, 3, 4, 5]); // [[1, 2, 3, 4, 5]]
chunk([1], 1); // [[1]]
chunk([1], 2); // [[1]]
chunk([1, 2, 3, 4, 5], 2); // [[1, 2], [3, 4], [5]]

思路：

使用 reduce 将数组分组。

function chunk(array, length = 1) {
  if (!Array.isArray(array)) {
    return [];
  }
  return array.reduce((acc, cur) => {
    const last = acc[acc.length - 1];
    if (!last || last.length === length) {
      acc.push([cur]);
    } else {
      last.push(cur);
    }
    return acc;
  }, []);
}

18. 数组拍平

实现一个数组拍平方法，接受指定层数的拍平，默认为完全拍平。

禁止使用 Array.prototype.flat。

测试用例：

flatten([1, [2, [3, [4]], 5]]); // [1, 2, 3, 4, 5]
flatten([1, [2, [3, [4]], 5]], 1); // [1, 2, [3, [4]], 5]
flatten([1, [2, [3, [4]], 5]], 2); // [1, 2, 3, [4], 5]

思路：

使用递归，递归层数为指定层数。

function flatten(array, depth = Infinity) {
  if (depth === 0) return array;
  return array.reduce((acc, val) => {
    if (Array.isArray(val)) {
      return acc.concat(flatten(val, depth - 1));
    }
    return acc.concat(val);
  }, []);
}