亚马逊面试经历 & 常考算法题分享
站长
· 阅读数 3
前言：
笔者在今年五月份的时候面了一次亚马逊，总的来说面试体验还不错，不过有几个点想要和大家聊一下。
本来我看网上说面试算法非常多的，我就搜罗了好多好多算法题，然后整理在下面，以备不时之需。结果面试的时候发现 Developer 和 manager 都没有考，然后技术面给我的感觉还是比较抽象的，developer 问的全是相对比较老的技术，不过后面manager也解释了整体的技术栈还是比较老旧的。
有一点比较奇怪的是，一面技术感觉问的非常浅，问了一会就不问了，然后让我反问，并且和我说“你还有想让我了解的其他方面么”，然后把自己之前在翻译公司和金融方面的实习经历说了一下，技术就没有再聊了。
后面到 manager 面试，manager 就基础了解了一下情况，后面的操作感觉一直在叠甲，什么“我没法确定你一定能来”，“我们要共同决定”，这些操作还是蛮让我迷惑的。
最后挂了，我理解应该是学历挂了，同届 top2 硕感觉还是不少的；然后亚马逊非常看重一个东西，叫“leadership principle”，这个东西我也说不好，可以理解为“企业文化”？在 manager 面的时候，他们说会把你的经历一个一个对着 leadership principle 打勾啥的，然后最后做一个决策。
那么这就是我的面试经历啦～
下面是我做的一些算法题目的整理，大家可以看看呀，基本 lc 都找得到。
常考算法题
1. 归并排序
function mergeSort(arr) {
let len = arr.length
if (len <= 1) return arr
const mid = Math.floor( len / 2 )
let arr1 = mergeSort(arr.slice(0, mid))
let arr2 = mergeSort(arr.slice(mid))
const ans = mergeAdd(arr1, arr2)
return ans
}
function mergeAdd(arr1, arr2) {
let l1 = 0, l2 = 0
let len1 = arr1.length, len2 = arr2.length
let ans = []
while (l1 < len1 && l2 < len2) {
if (arr1[l1] > arr2[l2]) {
ans.push(arr2[l2++])
} else {
ans.push(arr1[l1++])
}
}
return ans.concat(l1 === len1 ? arr2.slice(l2) : arr1.slice(l1))
}
mergeSort([2, 3, 1, 6, 8, 2, 0])
2. 快速排序
function quickSort(arr) {
if (arr.length <= 1) return arr
const equalArr = []
const higherArr = []
const lowerArr = []
const val = arr[0]
arr.forEach(item => {
if (item === val) equalArr.push(item)
else if(item > val) higherArr.push(item)
else lowerArr.push(item)
})
return quickSort(lowerArr).concat(equalArr).concat(quickSort(higherArr))
}
quickSort([2, 3, 1, 6, 8, 2, 0])
3. 判断两棵树是否相同
var isSubtree = function(root, subRoot) {
// corner case: if root is null/undefined we don't go deep
if (!root) return false
// first we deal root and subRoot
const result = subTree(root, subRoot)
if (result) return true
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
function subTree(root, subRoot) {
if (!root && !subRoot) return true
if (!root || !subRoot) return false
if (root.val !== subRoot.val) return false
return subTree(root.left, subRoot.left) && subTree(root.right, subRoot.right)
}
};
4. 求两个字符串相同的连续子串的最大长度及子串。
function findLongestCommonSubstring(s1, s2) {
const m = s1.length;
const n = s2.length;
const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
let maxLen = 0;
let maxI = 0;
let maxJ = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i-1] === s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
maxI = i;
maxJ = j;
}
}
}
}
return maxLen > 0 ? s1.slice(maxI - maxLen, maxI) : '';
}
const s1 = 'ABABC';
const s2 = 'BABCA';
const [maxLen, substring] = findLongestCommonSubstring(s1, s2);
console.log(`Max length: ${maxLen}, substring: ${substring}`);
5. 最长公共子序列
var longestCommonSubsequence = function(text1, text2) {
const l1 = text1.length, l2 = text2.length
const dp = new Array(l1 + 1).fill(0).map(() => new Array(l2 + 1).fill(0))
for (let i=1;i<=l1;i++) {
const c1 = text1[i - 1]
for (let j=1;j<=l2;j++) {
const c2 = text2[j-1]
if (c1 === c2) {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
}
}
}
return dp[l1][l2]
};
6.求乱序数组中出现频率前m的数。要求复杂度O(n)，n为数组长度
function topMFrequentNumbers(nums, m) {
const freqMap = new Map();
// 统计数字出现的频率
for (let i = 0; i < nums.length; i++) {
if (freqMap.has(nums[i])) {
freqMap.set(nums[i], freqMap.get(nums[i]) + 1);
} else {
freqMap.set(nums[i], 1);
}
}
// 将Map转换为数组并按照频率排序
const freqArray = Array.from(freqMap);
freqArray.sort((a, b) => b[1] - a[1]);
// 选取出现频率前m的数字
const result = [];
for (let i = 0; i < m; i++) {
result.push(freqArray[i][0]);
}
return result;
}
函数topMFrequentNumbers输入乱序数字数组和选取的前m个数字，输出出现频率前m的数字。
首先使用Map来统计数组中每个数字出现的频率，得到freqMap。然后将freqMap转换为数组freqArray，按照频率从高到低进行排序。最后选取前m个频率最高的数字，并返回结果。
7. 第二题是打印所有和为sum的数字组合，是leetcode的原题，combination sum III好像是
var combinationSum3 = function(k, n) {
// 用 k 个数合成 n
let min = 0, max = 0
for (let i=0;i<k;i++) {
min += i + 1
max += 9 - i
}
console.log(min, max)
if (n < min || n > max) return []
const res = []
const DFS = (idx, val, sum, obj) => {
if (sum > n || idx > k) return
if (idx === k && sum === n) {
res.push(val)
}
for (let i=1;i<=9;i++) {
if (obj[i]) return
obj[i] = true
val.push(i)
sum += i
DFS(idx + 1, val.slice(), sum, obj)
sum -= i
val.pop()
obj[i] = undefined
}
}
DFS(0, [], 0, {})
return res
};
8. 实现0、1、2组成的字符串序列与0-9，a-z组成字符串序列的互转，规则自定，要求生成的0-9和a-z组成的序列尽可能短。
const BASE36_ENCODE_TABLE = '0123456789abcdefghijklmnopqrstuvwxyz';
function convertToBase36(str) {
let num = 0;
for (let i = 0; i < str.length; i++) {
const digit = Number(str[i]);
num += digit * Math.pow(3, str.length - i - 1);
}
return num.toString(36);
}
function convertToBase10(str) {
let num = 0;
for (let i = 0; i < str.length; i++) {
const digit = BASE36_ENCODE_TABLE.indexOf(str[i]);
num += digit * Math.pow(36, str.length - i - 1);
}
return num;
}
function convertToBase36String(str) {
const base10Number = convertToBase10(str);
let base36String = '';
while (base10Number > 0) {
const remainder = base10Number % BASE36_ENCODE_TABLE.length;
base36String = BASE36_ENCODE_TABLE[remainder] + base36String;
base10Number = Math.floor(base10Number / BASE36_ENCODE_TABLE.length);
}
return base36String;
}
function convertToDigitsAndLetters(str) {
const base10Number = Number(convertToBase10(str));
const digitsAndLetters = base10Number.toString(36);
return digitsAndLetters;
}
convertToBase36(str)函数用于将0、1、2组成的字符串序列转换为base36编码的字符串序列
convertToBase10(str)函数用于将base36编码的字符串序列转换为10进制数字
convertToBase36String(str)函数用于将10进制数字转换为base36编码的字符串序列
convertToDigitsAndLetters(str)函数用于将base36编码的字符串序列转换为0-9和a-z组成的字符串序列
可以根据需要进行调用。需要注意的是，由于JavaScript中Number类型的精度限制，处理超过Number.MAX_SAFE_INTEGER的数据时可能会有误差，需要特别注意。
9. lc17变形
var letterCombinations = function(digits) {
if (!digits) return []
const map = ["", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
const res = []
const DFS = (n, s) => {
if (n === digits.length) {
res.push(s)
return
}
for (let i=0;i<map[Number(digits[n]) - 1].length;i++) {
let str = s
s += map[Number(digits[n]) - 1][i]
DFS(n + 1, s)
s = str
}
}
DFS(0, "")
return res
};
10. lc139
var wordBreak = function(s, wordDict) {
// 使用一个 dp 用来记录我们可以处理的范围
const len = s.length
const wordSet = new Set(wordDict)
const dp = new Array(len + 1).fill(false)
dp[0] = true
for (let i=1;i<=len;i++) {
for (let j=0;j<i;j++) {
if (dp[j] && wordSet.has(s.slice(j, i))) {
dp[i] = true
}
}
}
return dp[len]
};
11. leetcode.200 岛屿数量
DFS
var numIslands = function(grid) {
const dx = [0, 0, 1, -1]
const dy = [1, -1, 0, 0]
let ans = 0
const l1 = grid.length
const l2 = grid[0].length
const DFS = (x, y) => {
if (x >= l1 || y >= l2 || x < 0 || y < 0 || grid[x][y] === '0') return
grid[x][y] = '0'
for (let i=0;i<4;i++) {
DFS(x + dx[i], y + dy[i])
}
}
for (let i=0;i<l1;i++) {
for (let j=0;j<l2;j++) {
if (grid[i][j] === '1') {
ans ++
DFS(i, j)
}
}
}
return ans
};
12. 设计一个微博，功能有发微博、点赞微博、关注别人、查看点赞顺序等。因为这时候还剩十分钟了，所以大概地说了一下设计思路，有哪几个类、每个类有什么属性方法这样就结束了。
class Weibo {
// 首先是一个微博的值
constructor(myPost, myConcern) {
// 我的发布
this.myPost = myPost
// 我的关注
this.myConcern = myConcern
}
postBlog(name, value) {
if(!this.myPost[name]) {
this.myPost[name] = {value: value, likes: []}
}
}
like(tabName, userName) {
if(!this.myPost[name]) {
this.myPost[name] = {value: null, likes: []}
}
this.myPost[name].lieks.push(userName)
}
showLikes(name) {
if (!this.myPost[name].lieks) return;
return this.myPost[name].lieks
}
concernOther(name) {
if(!this.myConcern) {
this.myConcern = []
}
this.myConcern.push(name)
}
}
13. leetcode.121 买卖股票只能一次
var maxProfit = function(prices) {
// first i need a minumize value and a maxVal and there a order
let prev = Infinity, ans = 0
for (let i=0;i<prices.length;i++) {
prev = Math.min(prev, prices[i])
ans = Math.max(ans, prices[i] - prev)
}
return ans
};
14. leetcode.122 买卖股票可以多次
var maxProfit = function(prices) {
const len = prices.length
// 这里注意值需要是 -Infinity
const dp = new Array(len + 1).fill(-Infinity).map(() => new Array(2).fill(-Infinity))
dp[0][0] = 0
prices.unshift(0)
// 这里需要能够相等
for (let i=1;i<=len;i++) {
dp[i][0] = Math.max(dp[i][0], dp[i-1][1] + prices[i])
dp[i][1] = Math.max(dp[i][1], dp[i-1][0] - prices[i])
for (let j=0;j<2;j++) {
dp[i][j] = Math.max(dp[i][j], dp[i-1][j])
}
}
return dp[len][0]
};
16. 每日温度
一个单调栈的题目
var dailyTemperatures = function(temperatures) {
const lineQueue = []
const res = []
for (let i=0;i<temperatures.length;i++) {
if(!lineQueue.length) {
lineQueue.push([temperatures[i], i])
} else {
while (lineQueue.length > 0 && temperatures[i] > lineQueue[lineQueue.length-1][0]) {
res[lineQueue[lineQueue.length-1][1]] = i - lineQueue[lineQueue.length-1][1]
lineQueue.pop()
}
lineQueue.push([temperatures[i], i])
}
}
while(lineQueue.length) {
res[lineQueue[lineQueue.length-1][1]] = 0
lineQueue.pop()
}
return res
};
17. topK
var topKFrequent = function(nums, k) {
const map = new Map()
for (let i=0;i<nums.length;i++) {
if (!map.has(nums[i])) {
map.set(nums[i], 1)
} else {
map.set(nums[i], map.get(nums[i]) + 1)
}
}
const arr = []
for(let a of map) arr.push(a)
const ans = []
arr.sort((a, b) => b[1] - a[1]).forEach((item, idx) => {
if (idx < k) {
ans.push(item[0])
}
})
return ans
};