写业务代码, 可能会碰到一些架构上的问题, 但性能不是重点, 很少接触真正的算法.
最近听播客, 道长介绍在硅谷面试时, 一般初级软件工程师就是算法题, 资深之后 才会有架构题, 越资深算法就越不重要.
但代码与性能是一方面, 另一方面, 能否理解问题, 解决问题, 这是任何人都需要的.
我们的前端笔试题已经很久没更新了, 后端则没有正式的笔试题. 春季招聘正需要, 就打算去 LeetCode 上抄那么几道题应对招聘.
最近的一道中等难度的题是: Minimum Number of Frogs Croaking
根据 Hints, 用 JavaScript 写了答案, 思路应该是清晰的, 效率也可以接受. 参考 Hints 写的答案都是基础方法, 但软件工程应该就是使用最简单的思路去解决问题.
以下是具体答案:
Runtime: 76 ms, faster than 85.98% of JavaScript online submissions. Memory Usage: 37.1 MB, less than 100.00% of JavaScript online submissions. (2020-04-22 17:22:18 +8)
/**
* @param {string} croakOfFrogs
* @return {number}
*/
var minNumberOfFrogs = function (croakOfFrogs) {
let max = 0;
const m = { c: 0, r: 0, o: 0, a: 0, k: 0 };
for (const v of croakOfFrogs) {
if (!"croak".includes(v)) {
return -1;
}
if (v === "k") {
m.c -= 1;
m.r -= 1;
m.o -= 1;
m.a -= 1;
if (m.c >= max) {
max = m.c + 1;
}
} else {
m[v] += 1;
if (m.c < m.r || m.r < m.o || m.o < m.a || m.a < m.k) {
return -1;
}
}
}
if (m.c !== 0) {
return -1;
}
return max;
};
这里给出一些我用过的测试:
const test = [
["cccroacrkroakroakcroakoak", 4],
["cccroacrkroakroakcroakaok", -1],
["croakcrook", -1],
["croakcroak", 1],
["croakcroa", -1],
["croakcroac", -1],
];
for (const [v, r] of test) {
const it = minNumberOfFrogs(v);
if (it !== r) {
throw new Error(`${v} 的结果应该为 ${r}, 却是 ${it}`);
}
}
我最初的答案是这样的:
/**
* @param {string} croakOfFrogs
* @return {number}
*/
var minNumberOfFrogs0 = function (croakOfFrogs) {
return croakOfFrogs
.split("k")
.map((v) => cDisplayTime(v))
.reduce((acc, v) => {
if (v > acc) {
return v;
}
return acc;
}, 0);
};
function cDisplayTime(str) {
let count = 0;
for (const v of str) {
if (v === "c") {
count += 1;
}
}
return count;
}
这个答案性能不是重点, 看起来也更简单. 但不能找出错误参数. 然后我才意识到, 这道题麻烦的是校验错误.
然后老老实实依照 Hints 写了最终的答案.
Hints:
- keep the frequency of all characters from “croak” using a hashmap.
- For each character in the given string, greedily match it to a possible “croak”.
第二天早上又花了一点时间写了两个版本:
通用版: https://leetcode.com/submissions/detail/328828305/
性能版: https://leetcode.com/submissions/detail/328832285/
再翻看大家的讨论, 看到其他语言基本与我的性能版思路一致, 但通用版大家都没怎么写.
在我目前的实际工作中, 性能要求并不高, 我们更期望可读性强的代码.
这道题前前后后, 写代码, 整理思路, 发帖, 花了两三个小时, 我想 改动一下是可以作为笔试题了.
通用版代码就不写了, 以下是性能版源代码:
/**
* @param {string} croakOfFrogs
* @return {number}
*/
var minNumberOfFrogs = function (croakOfFrogs) {
// 多出的数量
let max = 0;
// 储存鸣叫数量
let c = 0;
let r = 0;
let o = 0;
let a = 0;
let k = 0;
for (let i = 0; i < croakOfFrogs.length; i++) {
const v = croakOfFrogs[i];
switch (v) {
case "c":
c += 1;
break;
case "r":
r += 1;
if (r > c) {
return -1;
}
break;
case "o":
o += 1;
if (o > r) {
return -1;
}
break;
case "a":
a += 1;
if (a > o) {
return -1;
}
break;
case "k":
k += 1;
if (k > a) {
return -1;
}
if (c - k > max) {
max = c - k;
}
break;
default:
return -1;
}
}
if (c !== k) {
return -1;
}
return max + 1;
};