赞
踩
大家好,我是蔓越莓曲奇,目前在准备找工作,后续两个月打算做一些前端基础知识跟面经的文章
这次先分享的是华为 OD 的面经
不得不说,Boss 直聘上之后华为在主动聊候选人
总体流程
笔试只 AC 了前两道,最后一道没做出来,华为的笔试要熟悉 ACM 的答题方法,这里你完成牛客的练习基本可以正常作答了OJ 输入输出练习
现代计算机系统中通常存在多级的存储设备,针对海量 workload 的优化的一种思路是将热点内存页优先放到快速存储层级,这就需要对内存页进行冷热标记。
一种典型的方案是基于内存页的访问频次进行标记,如果统计窗口内访问次数大于等于设定阈值,则认为是热内存页,否则是冷内存页。
对于统计窗口内跟踪到的访存序列和阈值,现在需要实现基于频次的冷热标记。内存页使用页框号作为标识。
第一行输入为 N,表示访存序列的记录条数,0 < N ≤ 10000。
第二行为访存序列,空格分隔的 N 个内存页框号,页面号范围 0 ~ 65535,同一个页框号可能重复出现,出现的次数即为对应框号的频次。
第三行为热内存的频次阈值 T,正整数范围 1 ≤ T ≤ 10000。
第一行输出标记为热内存的内存页个数,如果没有被标记的热内存页,则输出 0 。
如果第一行 > 0,则接下来按照访问频次降序输出内存页框号,一行一个,频次一样的页框号,页框号小的排前面。
小华按照地图去寻宝,地图上被划分成 m 行和 n 列的方格,横纵坐标范围分别是 [0, n-1] 和 [0, m-1]。
在横坐标和纵坐标的数位之和不大于 k 的方格中存在黄金(每个方格中仅存在一克黄金),但横坐标和纵坐标之和大于 k 的方格存在危险不可进入。小华从入口 (0,0) 进入,任何时候只能向左,右,上,下四个方向移动一格。
请问小华最多能获得多少克黄金?
题目描述:
疫情期间需要大家保证一定的社交距离,公司组织开交流会议。
座位一排共 N 个座位,编号分别为 [0, N - 1] , 要求员工一个接着一个进入会议室,并且可以在任何时候离开会议室。
满足:
每当一个员工进入时,需要坐到最大社交距离(最大化自己和其他人的距离的座位);
如果有多个这样的座位,则坐到 索引最小 的那个座位。
输入描述:
会议室座位总数 seatNum 。(1 <= seatNum <= 500)
员工的进出顺序 seatOrLeave 数组,元素值为 1,表示进场;元素值为负数,表示出场(特殊:位置 0 的员工不会离开)。
例如 - 4 表示坐在位置 4 的员工离开(保证有员工坐在该座位上)
输出描述:
最后进来员工,他会坐在第几个位置,如果位置已满,则输出 - 1 。
做一套关于性格测试的题目
总体技术面不是很难
1-16
主管面
这些你问 hr 要题库,或者在 CSDN 上搜,都可以得到一些题目进行练习,不过没有答案,下面是我写的一些参考答案
题目一:
题目描述:定义构造三叉搜索树规则如下:
每个节点都存有一个数,当插入一个新的数时,从根节点向下寻找,直到找到一个合适的空节点插入。
const q1 = (list) => { if (list.length === 0) return0; function TreeNode(val, left, right, mid) { this.val = val === undefined ? 0 : val; this.left = left === undefined ? null : left; this.right = right === undefined ? null : right; this.mid = mid === undefined ? null : this.mid; } const root = new TreeNode(list[0]); let ret = 0; for (let i = 1; i < list.length; i++) { const cur = list[i]; const traverse = (node) => { if (node.left === null) { if (cur < node.val - 500) { node.left = new TreeNode(list[i]); return 1; } } if (node.mid === null) { if (cur >= node.val - 500 && cur <= node.val + 500) { node.mid = new TreeNode(list[i]); return 1; } } if (node.right === null) { if (cur > node.val + 500) { node.right = new TreeNode(list[i]); return 1; } } if (node.left) { const nodeLevel = traverse(node.left); if (nodeLevel) return nodeLevel + 1; } if (node.mid) { const nodeLevel = traverse(node.mid); if (nodeLevel) return nodeLevel + 1; } if (node.right) { const nodeLevel = traverse(node.right); if (nodeLevel) return nodeLevel + 1; } return 1; }; let tmp = 0; tmp = traverse(root); ret = Math.max(ret, tmp); } return ret + 1; };
题目二:
题目描述:服务之间交换的接口成功率作为服务调用关键质量特性,某个时间段内的接口失败率使用一个数组表示,数组中每个元素都是单位时间内失败率数值,数组中的数值为0-100的整数,给定一个数值(minAverageLost)表示某个时间段内平均失败率容忍值,即平均失败率小于等于minAverageLost,找出数组中最长时间段,如果未找到则直接返回null
题目一:
题目描述:给定用户密码输入流input,输入流中字符’<’表示退格,可以清除前一个输入的字符,请编写程序,输出最终得到的密码字符,并判断密码是否满足如下的密码安全要求。
密码安全要求如下:
1密码长度>=8
2密码至少需要包含1个大写字母
3密码至少需要包含1个小写字母
4密码至少需要包含1个数字
5密码至少需要包含1个字母和数字以外的非空白特殊字符
const q1 = (string) => { const input = string.split(""); let stack = []; for (let i = 0; i < input.length; i++) { if (input[i] === "<") { stack.pop(); } else { stack.push(input[i]); } } let password = stack.join(""); let hasUpper = /[A-Z]/.test(password); let hasLower = /[a-z]/.test(password); let hasDigit = /\d/.test(password); let hasSpecial = /[^\w\s]/.test(password); let lengthValid = password.length >= 8; let typeValid = hasUpper && hasLower && hasDigit && hasSpecial; return lengthValid && typeValid; };
题目二:
题目描述:给定一个字符串s,最多只能进行一次变换,返回变换后能得到的最小字符串(按照字典序进行比较)。变换规则:交换字符串中任意两个不同位置的字符
const q2 = (str) => { const len = str.length; const sortArr = str.split("").sort((a, b) => a.charCodeAt() - b.charCodeAt()); const ret = str.split(""); let i = 0; while (sortArr[i] === ret[i] && i < len) { i++; } console.log("i: ", i, sortArr[i]); if (i !== len) { const idx = ret.findLastIndex((item) => item === sortArr[i]); console.log("idx: ", idx); [ret[i], ret[idx]] = [ret[idx], ret[i]]; } return ret.join(""); }; // console.log("q2 ", q2("acdefb")); // console.log("q2 ", q2("bcdefa")); // console.log("q2 ", q2("ababab"));
题目三:
题目描述:
给定M(0<M<=30)和字符(a-z),从中取出任意字符(每个字符只能用一次)拼接长度为N(0<N<=5)的字符串,要求相同的字符不能相邻,计算出给定的字符列表能拼接出多少种满足条件的字符串,输入非法或者无法拼接出满足条件的字符串则返回0
DFS
const q3 = (str, n) => { let i = 0; let map = {}; while (i < str.length) { if (map[str[i]]) { map[str[i]]++; } else { map[str[i]] = 1; } i++; } let ret = 0; const dfs = (count, x) => { console.log("count, x: ", count, x); if (count === n) { ret += 1; return; } else { const keyList = Object.keys(map); for (let i = 0; i < keyList.length; i++) { const nextStr = keyList[i]; if (x !== nextStr) { map[nextStr] -= 1; dfs(count + 1, nextStr); map[nextStr] += 1; } else { continue; } } } }; dfs(0, ""); console.log("ret: ", ret); return ret; };
题目一:
题目描述:橱窗里有一排宝石,不同宝石对应不同价格,宝石价格标记为gems[i],0<=i<n,n=gems.length,宝石可同时出售0个或多个,如果同时出售多个,则要求出售的宝石编号连续;例如客户最大购买宝石个数为m,购买的宝石编号必须为gems[i],gems[i+1]…gems[i+m-1](0<=i<n,m<=n),假设你当前拥有总面值为value的钱,请问最多能购买到多少个宝石,如无法购买宝石,则返回0
滑动窗口
const q1 = (list, value) => { let ret = 0; let l = 0; let r = 0; let sum = 0; while (r < list.length) { sum += list[r]; while (sum > value && l <= r) { sum -= list[l]; l++; } if (sum <= value) { ret = Math.max(r - l + 1, ret); } r++; } return ret; };
题目二:
题目描述:XX市机场停放了多架飞机,每架飞机都有自己的航班号CA3385,CZ6678,SC6508等,航班号的前2个大写字母(或数字)代表航空公司的缩写,后面4个数字代表航班信息。但是XX市机场只有一条起飞用跑道,调度人员需要安排目前停留在机场的航班有序起飞。为保障航班的有序起飞,调度员首先按照航空公司的缩写(航班号前2个字母)对所有航班进行排序,同一航空公司的航班再按照航班号的后4个数字进行排序最终获得安排好的航班的起飞顺序。请编写一段代码根据输入的航班号信息帮助调度员输出航班的起飞顺序。
sort
const q2 = (list) => { const getInfo = (id) => { return [id.slice(0, 2), id.slice(2)]; }; return list.sort((a, b) => { const [aCompony, aCode] = getInfo(a); const [bCompony, bCode] = getInfo(b); if (aCompony === bCompony) return Number(aCode) - Number(bCode); else { return aCompony.localeCompare(bCompony); // if (aCompony[0] === bCompony[0]) // return aCompony[1].charCodeAt() - bCompony[1].charCodeAt(); // return aCompony[0].charCodeAt() - bCompony[0].charCodeAt(); } }); };
题目三:
题目描述:给定一个字符串,只包含字母和数字,按要求找出字符串中的最长(连续)子串的长度,字符串本身是其最长的子串,子串要求:1、只包含1个字母(a~z,A~Z),其余必须是数字;2、字母可以在子串中的任意位置;如果找不到满足要求的子串,如全是字母或全是数字,则返回-1
双指针
const q3 = (str) => { let ret = 0; for (let i = 0; i < str.length; i++) { if (/[a-zA-Z]/.test(str[i])) { let l = i; let r = i; while (l >= 1) { if (/\d/.test(str[l - 1])) l--; else { break; } } while (r < str.length) { if (/\d/.test(str[r + 1])) r++; else { break; } } ret = Math.max(ret, r - l + 1); } } return ret === 0 ? -1 : ret; }; console.log(q3("a5")); console.log(q3("aBB9")); console.log(q3("abC124ACb"));
题目一:
题目描述:小朋友出操,按学号从小到大排成一列;小明来迟了,请你给小明出个主意,让他尽快找到他应该排的位置。算法复杂度要求不不高于nLog(n);学号为整数类型,队列规模<=10000;
题目二:
题目描述:机器人搬砖,一共N堆砖存放在N个不同的仓库中,第i堆砖中有bricks[i]块砖头,要求在8小时内搬完。机器人每小时能搬砖的数量取决于有多少能量格,机器人一个小时中只能在一个仓库中搬砖,机器人的能量格每小时补充一次且能量格只在这一个小时有效,为使得机器人损耗最小化尽量减小每次补充的能量格数。为了保障在8小时内能完成搬砖任务,请计算每小时给机器人充能的最小能量格数。备注:1、无需考虑机器人补充能量格的耗时2、无需考虑机器人搬砖的耗时3、机器人每小时补充能量格只在这一个小时中有效
题目三:
题目描述:一只贪吃的猴子,来到一个果园,发现许多串香蕉排成一行,每串香蕉上有若干根香蕉。每串香蕉的根数由数组number给出。猴子获取香蕉,每次都只能从行的开头或者末尾获取,并且只能获取N次,求猴子最多能获取多少根香蕉。
前缀和
const q3 = (list, n) => { const len = list.length; const leftArr = [0]; const rightArr = [0]; for (let i = 1; i <= n; i++) { leftArr[i] = list[i - 1] + leftArr[i - 1]; rightArr[i] = list[len - i] + rightArr[i - 1]; } let ret = 0; for (let i = 0; i <= n; i++) { let curSum = leftArr[i] + rightArr[n - i]; ret = Math.max(curSum, ret); } console.log("ret: ", ret); return ret; }; q3([1, 2, 2, 7, 3, 6, 1], 3); q3([1, 2, 3], 3);
题目一:
程序员小明打了一辆出租车去上班。出于职业敏感,他注意到这辆出租车的计费表有点问题,总是偏大。出租车司机解释说他不喜欢数字4,所以改装了计费表,任何数字位置遇到数字4就直接跳过,其余功能都正常。比如:1、23再多一块钱就变为25;2、39再多一块钱变为50;3、399再多一块钱变为500;
题目三:
小扇和小船今天又玩起来了数字游戏,小船给小扇一个正整数n(1<=n<=1e9),小扇需要找到一个比n大的数字m,使得m和n对应的二进制中1的个数要相同(如4对应二进制100,8对应二进制1000,1的个数都为1),现在求m的最小值。
leetcode 下一个数
var q2 = function (num) { if (num >= 2147483647) return [-1, -1]; const generate = (list) => { let count = 0; for (let i = 0; i < list.length; i++) { if (list[i] === "1") count += 1; } let zeroCount = list.length - count; const zeroString = "0".repeat(zeroCount); const oneString = "1".repeat(count); return [zeroString + oneString, oneString + zeroString]; }; let arr = (num.toString(2) + "").split(""); let m; //smaller let n; //higher for (let i = 0; i < arr.length - 1; i++) { const tmp = arr.slice(i, i + 2).join(""); if (tmp === "01") { m = i; } if (tmp === "10") { n = i; } } let smaller = [...arr]; let higher = [...arr]; let highRet; let smallerRet; if (m == undefined) { higher.unshift("0"); m = 0; } higher.splice(m, 2, "1", "0"); const higherRest = higher.splice(m + 2); highRet = parseInt(higher.join("") + generate(higherRest)[0], 2); if (n !== undefined) { smaller.splice(n, 2, "0", "1"); } else { smaller.splice(0, 0, "0"); n = 0; } const smallRest = smaller.splice(n + 2); smallerRet = parseInt(smaller.join("") + generate(smallRest)[1], 2); if (num === 1) smallerRet = -1; return [highRet, smallerRet]; };
题目一:
题目描述:绘图机器的绘图笔初始位置在原点(0,0),机器启动后其绘图笔按下面规则绘制直线:1)尝试沿着横向坐标轴正向绘制直线,直到给定的终点值E2)期间可通过指令在纵坐标轴方向进行偏移,并同时绘制直线,偏移后按规则1绘制直线;指令的格式为X offsetY,表示在横坐标X沿纵坐标方向偏移,offsetY为正数表示正向偏移,为负数表示负向偏移。
给定了横坐标终点值E、以及若干条绘制指令,请计算绘制的直线和横坐标轴、以及X=E的直线组成图形的面积。
模拟即可
const q1 = (target, list) => { let ret = 0; let curY = 0; let curX = 0; for (let i = 0; i < list.length; i++) { const [targetX, moveY] = list[i]; ret += Math.abs((targetX - curX) * curY); curX = targetX; curY += moveY; } ret += Math.abs((target - curX) * curY); return ret; }; q1(10, [ [1, 1], [2, 1], [3, 1], [4, -2], ]); q1(4, [ [0, 1], [2, -2], ]);
题目二:
题目描述:在一个大型体育场内举办了一场大型活动,由于疫情防控的需要,要求每位观众的必须间隔至少一个空位才允许落座。现在给出一排观众座位分布图,座位中存在已落座的观众,请计算出,在不移动现有观众座位的情况下,最多还能坐下多少名观众。
模拟即可,注意两侧边界
const q2 = (list) => { let ret = 0; for (let i = 0; i < list.length; ) { let j = i; while (list[j] === 0 && j < list.length) { j++; } if (i !== j) { if (j - i == 2 && (i === 0 || j === list.length - 1)) { ret += 1; } else { ret += ((j - i) / 2) >> 0; } i = j; } else { i++; } } return ret; }; q2([1, 0, 0, 0, 1]); q2([0, 0, 0, 0, 1, 0, 1, 0, 0]);
题目三:
题目描述:实现一个模拟目录管理功能的软件,输入一个命令序列,输出最后一条命令运行结果。支持命令:1)创建目录命令:mkdir目录名称,如mkdir abc为在当前目录窗帘abc目录,如果已存在同名目录也不执行任何操作。此命令无输出。2)进入目录命令:cd目录名称,如cd abc为进入abc目录,特别地,cd…为返回上级目录,如果目录不存在则不执行任何操作。此命令无输出。3)查看当前所在路径命令:pwd,输出当前路径字符串
模拟
const q3 = (list) => { const fileObject = {}; const path = []; for (let i = 0; i < list.length; i++) { const cmd = list[i]; switch (cmd) { case "cd..": { if (path.length > 0) { path.pop(); } break; } case "pwd": { console.log(path.join(",")); break; } default: { const [command, fileName] = cmd.split(" "); console.log("command, fileName: ", command, fileName); if (command === "cd") { path.push(fileName); } else { let curObj = fileObject; for (let i = 0; i < path.length; i++) { curObj = curObj[path[i]]; } if (!Reflect.has(curObj, fileName)) { curObj[fileName] = true; } } break; } } } return; }; q3(["mkdir abc", "cd abc", "pwd"]);
题目一:
题目描述:特定大小的停车场,数组cars[]表示,其中1表示有车,0表示没车。车辆大小不一,小车占一个车位(长度1),货车占两个车位(长度2),卡车占三个车位(长度3),统计停车场最少可以停多少辆车,返回具体的数目
贪心思想即可
const parkingCar = (list) => { let ret = 0; for (let i = 0; i < list.length; ) { if (list[i] === 0) { i++; continue; } let tmp = 0; while (list[i] === 1 && i < list.length) { tmp++; i++; } ret += (tmp / 3) >> 0; tmp = tmp % 3; ret += (tmp / 2) >> 0; tmp = tmp % 2; ret += tmp; } console.log("ret: ", ret); return ret; }; parkingCar([1, 1, 0, 0, 1, 1, 1, 0, 1]); parkingCar([1, 0, 1]);
题目二:
题目描述:小明在玩一个游戏,游戏规则如下:在游戏开始前,小明站在坐标轴原点处(坐标值为0)。给定一组指令和一个幸运数,每个指令都是一个整数,小明按照指定的要求前进或者后退指定的步数。前进代表朝坐标轴的正方向走,后退代表朝坐标轴的负方向走。幸运数为一个整数,如果某个指令正好和幸运数相等,则小明行进步数加1。
模拟
const q2 = (list, num) => { let cur = 0; let ret = 0; for (let i = 0; i < list.length; i++) { let move = list[i]; if (move === num) { if (move >= 0) move += 1; else move -= 1; } cur += move; ret = Math.max(ret, cur); } console.log("ret: ", ret); return ret; }; q2([-5, 1, 6, 0, -7], -5); q2([-5, 1], 2);
题目三:
题目描述:
有一棵二叉树,每个节点由一个大写字母标识(最多26个节点)。现有两组字母,分别表示后序遍历(左孩子-右孩子-父节点)和中虚遍历(左孩子-父节点-右孩子)的结果,请输出层次遍历的结果
function TreeNode(val, left, right) { this.val = val === undefined ? 0 : val; this.left = left === undefined ? null : left; this.right = right === undefined ? null : right; } var buildTree = function (inorder, postorder) { if (inorder.length === 1) return new TreeNode(inorder[0], null, null); if (inorder.length === 0) return null; const root = postorder[postorder.length - 1]; const idx = inorder.findIndex((item) => item === root); const left = buildTree(inorder.slice(0, idx), postorder.slice(0, idx)); const right = buildTree( inorder.slice(idx + 1), postorder.slice(idx, postorder.length - 1) ); return new TreeNode(root, left, right); };
var levelOrder = function (root) { if (!root) return []; const ret = []; const stk = [root]; const tmp = []; while (stk.length > 0) { tmp.push(stk.shift()); if (stk.length === 0 && tmp.length > 0) { ret.push(tmp.map((item) => item && item.val)); while (tmp.length > 0) { const node = tmp.shift(); node.left && stk.push(node.left); node.right && stk.push(node.right); } } } return ret; };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。