Эти вопросы вдохновлены реальными интервью по программированию, с подробными решениями, которые четко проведут вас через каждую основную концепцию.
Добейтесь исключительных успехов в программировании интервью, решая по одной задаче каждый день.
Вопрос 1
Учитывая отображение a = 1, b = 2, … z = 26 и закодированное сообщение, посчитайте, сколько способов его можно расшифровать.
Например, сообщение ‘111’ даст 3, поскольку его можно расшифровать как ‘aaa’, ‘ka’, and ‘ak’.
Можно предположить, что сообщения поддаются декодированию. Например, ‘001’ не допускается.
Решение
Во-первых, мы определяем функцию isDecodable(message), которая возвращает 1, если сообщение может быть декодировано, иначе 0.
function isDecodable(message) {
for (let i = 0; i < message.length; i++) {
var parsed = parseInt(message[i], 10)
if (isNaN(parsed)) {
return false
}
if ((parsed > 0 && parsed < 27) != true) {
return false
}
}
return true
}
Далее мы предполагаем, что сообщения являются декодируемыми. Для решения проблемы в этом случае мы используем решение на основе рекурсии.
Если длина строки равна 1, всегда есть 1 способ ее декодирования, так что это наш базовый случай.
'1':
['1']
----------
F('1') = 1if (message.length <=1) {
return 1
}
Если длина равна 2, у нас всегда есть 1 способ со всеми цифрами отдельно, плюс один, если число меньше, мы также используем этот способ как базовый.
'12':
['1', '2']
['12']
---------------------
F('12') = f('12') + 1
Если длина равна 3, мы можем использовать результаты предыдущих вычислений, потому что мы уже знаем, как работать с более короткими строками.
F('123') = f('1') * F('23') + F('12') * f('3') = 3
Наконец, все последующие случаи могут быть рассчитаны таким образом.
F('4123') = f('4') * F('123') + f('41') * F('23') = 3
Окончательный исходный код этой задачи
function decode_cnt_no_zero(message) {
let length = message.length
if (length <=1) {
return 1
}
if (length >=2) {
var parsed = parseInt(message.substring(0,2),10)
if (parsed >=0 && parsed <= 26) {
return (decode_cnt_no_zero(message.substring(1,length))
+ decode_cnt_no_zero(message.substring(2, length)))
}
return decode_cnt_no_zero(message.substring(1, length))
}
}
Давайте попробуем изучить наше решение.
- Результат декодирования 1 строки равен 1.
decode_cnt_no_zero(“1”) << 1
- Результат декодирования 12-й строки равен 2.
decode_cnt_no_zero(“12”) <<
- Результат декодирования строки 123 равен 3.
decode_cnt_no_zero(“123”) << 3
- Результат декодирования строки 4123 равен 3.
decode_cnt_no_zero(“4123”) << 3
Вопрос 2
Учитывая поток элементов, слишком большой для хранения в памяти, выберите случайный элемент из потока с одинаковой вероятностью.
Решение
Возвращает функцию, которая для каждого потока элементов выбирает случайный элемент.
const selectRandomizer = function () {
let streamCount = 0
let selected
const rand = function (stream) {
for (let i = 0; i < stream.length; i++) {
streamCount++
if (streamCount === 0) selected = stream[i]
else if (Math.random() <= 1 / streamCount) {
selected = stream[i]
}
}
return selected
}
return rand
}
Вопрос №3
Строитель хочет построить ряд из N домов, которые могут быть K разных цветов. У него есть цель минимизировать затраты, гарантируя, что никакие два соседних дома не будут одного цвета.
Дана матрица N на K, где n-я строка и k-й столбец представляют стоимость строительства n-го дома k-го цвета, верните минимальную стоимость для достижения этой цели.
Решение
Возвращает минимальную стоимость строительства N домов K разных цветов, при этом никакие два соседних дома не могут быть одного цвета.
Вот решение с временной сложностью O(NKK) и пространственной сложностью O(NK).
const minCostHouseColorInitialSolution = function(costs) {
if (costs.length === 0) return 0
const n = costs.length
const k = costs[0].length
// 2d array with n length and k rows
const dp = [...Array(n)].map(() => Array(k))
// fill first row
for (let col = 0; col < k; col++) {
dp[0][col] = costs[0][col]
}
for (let row = 1; row < n; row++) {
// Finding the lowest costs for each column in this row
for (let col = 0; col < k; col++) {
dp[row][col] = Number.MAX_SAFE_INTEGER
for (let numCol = 0; numCol < k; numCol++) {
// we dont want the same column, as that is 2 houses of same color
if (numCol !== col) {
dp[row][col] = Math.min(
dp[row][col],
dp[row - 1][numCol] + costs[row][col]
);
}
}
}
}
let minCost = Number.MAX_SAFE_INTEGER;
// get minimum of last row in dp table
for (let col = 0; col < k; col++) {
minCost = Math.min(minCost, dp[n - 1][col])
}
return minCost
}
Далее, по-прежнему O(NKK) временная сложность, но O(K) пространственная сложность.
const minCostHouseColorII = function (costs) {
if (costs.length === 0) return 0
const n = costs.length
const k = costs[0].length
const dp1 = [] // the last row
const dp2 = [] // the current row
// start the first row of costs, as the last row, and build from the second row onwards
for (let i = 0; i < k; i++) {
dp1[i] = costs[0][i]
}
for (let row = 1; row < n; row++) {
for (let j = 0; j < k; j++) {
// Finding the lowest costs for each column in this row
dp2[j] = Number.MAX_SAFE_INTEGER;
for (let m = 0; m < k; m++) {
if (m !== j) {
dp2[j] = Math.min(dp2[j], dp1[m] + costs[row][j])
}
}
}
// copy all the current row to last row
for (let j = 0; j < k; j++) {
dp1[j] = dp2[j]
}
}
let minCost = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < k; i++) {
minCost = Math.min(minCost, dp1[i])
}
return minCost
}
Наконец, вот лучшее решение с временной сложностью O(NK) и пространственной сложностью O(1).
const minCostHouseColorBest = function (costs) {
if (costs.length === 0) return 0
const n = costs.length
const k = costs[0].length
let min1 = 0
let min2 = 0
let idx1 = -1
for (let i = 0; i < n; i++) {
let m1 = Number.MAX_SAFE_INTEGER
let m2 = Number.MAX_SAFE_INTEGER
let idx2 = -1
for (let j = 0; j < k; j++) {
let cost = costs[i][j]
cost += j === idx1 ? min2 : min1
if (cost < m1) {
m2 = m1
m1 = cost
idx2 = j
} else if (cost < m2) {
m2 = cost
}
}
min1 = m1
min2 = m2
idx1 = idx2
}
return min1;
}
Легко, верно?
