Code interview challenges and their solutions
Gunar Gessner
Jun 27, 2020
Code challenges don't represent our ability as software engineers. Unless, of course, you're going to be writing high-perfomance code— like for blockchains or embedded systems (which I have)— but that's 1% of the market. To build React pages, we do not need to be good at code golf.
This is my small contribution. I hope that if we're faced with one of the challenges below, we get to land on this page. Copy and paste the answer. And go do something more important with your life. YOLO.
These solutions aren't perfect. I have invested as little time as possible in each of them— often copy/pasting things.
Go forth and be pragmatic.
# Fibonacci Sum
The Fibonacci sequence begins like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 (each number is the sum of the previous two)
What is the sum of all odd numbers in the Fibonacci sequence that are less than 10,000?
function sumFibonacci(num) {
// x[i-2]
let fib0 = 0;
// x[i-1]
let fib1 = 1;
// x[i]
let fib = 1;
let sum = fib0;
while (fib < num) {
if (isOdd(fib)) {
sum += fib1;
}
fib = fib0 + fib1;
fib1 += fib0;
fib0 = fib1 - fib0;
}
return sum;
function isOdd(n) {
return n % 2;
}
}
console.log(sumFibonacci(10000));
// 14328
# Legionaries
In the range 1 - 13 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13) the digit 1 occurs 6 times.
In the range, 1 - 2,660 (half the number of Romans in a legion), expressed in Roman numerals, how many times does the numeral “X” occur?
function sum(max) { let count = 0; for (let i = 1; i <= max; i++) { const roman = toRoman(i); roman.replace(/X/g, () => { count++; }); } return count; function toRoman(num) { if (typeof num !== "number") throw Error(); const digits = String(num).split(""); const key = [ "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM", "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC", "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" ]; let roman_num = ""; let i = 3; while (i--) { roman_num = (key[+digits.pop() + i * 10] || "") + roman_num; } return Array(+digits.join("") + 1).join("M") + roman_num; } } console.log(sum(2660));
Answer: 3977
# Numeric Palindromes Sum
A palindrome is a word, number, phrase, or another sequence of characters which reads the same backward as forward, such as madam, racecar, or the number
108001
What is the sum of all numeric palindromes that are less than 10,000?
// source: https://www.geeksforgeeks.org/generate-palindromic-numbers-less-n/
function createPalindrome(input, b, isOdd) {
let n = input;
let palin = input;
// checks if number of digits is odd or even
// if odd then neglect the last digit of input in
// finding reverse as in case of odd number of
// digits middle element occur once
if (isOdd) {
n = Math.floor(n / b);
}
// Creates palindrome by just appending reverse
// of number to itself
while (n > 0) {
palin = palin * b + (n % b);
n = Math.floor(n / b);
}
return palin;
}
function generateNumbericPalindromes(n) {
let number;
let output = [];
// Run two times for odd and even length palindromes
for (let j = 0; j < 2; j++) {
// Creates palindrome numbers with first half as i.
// Value of j decided whether we need an odd length
// of even length palindrome.
let i = 1;
while ((number = createPalindrome(i, 10, j % 2)) < n) {
output.push(number);
// (cout << number) << " ";
i++;
}
}
return output;
}
console.log(
generateNumbericPalindromes(10000).reduce((acc, next) => acc + next, 0)
);
Answer: 545040
# Epigram on Failure
Given the following quote by Alan Perlis
“Dealing with failure is easy: Work hard to improve. Success is also easy to handle: You’ve solved the wrong problem. Work hard to improve.”
Considering only the alphabetical characters, consonants having the value of their ASCII codes, and vowels having the inverse value of their ASCII codes, what is the sum of the sentence?
Example: Taking the word “iffy”, the ASCII code of “i” is 105, it’s inverse is -105. The ASCII value of ‘f’ is 102. The ASCII y of “y” is 121. The sum of “iffy” = 220
function sum(string) { const VOWELS = ["a", "e", "i", "o", "u"]; return ( string .replace(/[^a-zA-Z]*/g, "") .split("") .reduce((acc, char, array) => { return acc + char.charCodeAt(0) * (isVowel() ? -1 : 1); function isVowel() { return VOWELS.includes(char); } }, 0) ); } require("assert").equal(sum("iffy"), 220); console.log( sum( "Dealing with failure is easy: Work hard to improve. Success is also easy to handle: You’ve solved the wrong problem. Work hard to improve." ) );
Thanks to Abdussamad Bello for emailing me a better way to select upper and lower case characters using regex.
# University Career Fair
I've received a DMCA notification from HackerRank for this question. So I can't publish here the question verbatim. I'll keep the solution here though for historical purposes.
Solution
This can be analyzed as scheduling problem. We can solve most scheduling problems using Dijkstra's algorithm. I've decided to solve it using Clojure.
; ; We're solving this using Dijkstra's algorithm, where: ; 1. The graph is generated on-the-fly (i.e. get-children) ; 2. The cost of all edges is 1 (so that we count them) ; 3. We're looking for MAX(COST) as opposed to MIN(COST) which is usually the case with Dijkstra's algo ; [[index start duration]] (defn get-triads [arrival duration] (sort-by second (map vector (range) arrival duration))) ; Finds time-blocks that start after the given one has ended (defn get-children [triads start duration] (let [end (+ start duration)] ; XXX(perf): Triads are sorted by start-time, so we could loop over the remaining triads only. (filter (fn [[i s d]] (>= s end)) triads))) ; {index [cost parent]} (defn get-dijkstras-costs [triads] (reduce (fn [outer-acc [node-index node-start node-duration]] (let [children (get-children triads node-start node-duration) outer-acc-two (update outer-acc node-index #(or % [1 nil]))] (reduce (fn [costs [child-index]] (let [node-cost-tuple (or (get costs node-index) [0 nil])] (update costs child-index (fn [child-cost-tuple] (let [child-cost (or (first child-cost-tuple) 0) new-cost (inc (first node-cost-tuple))] (if (> new-cost child-cost) [new-cost node-index] child-cost-tuple ))) ))) outer-acc-two children)) ) {} triads)) ; HR expects camelCase (def maxEvents (comp (partial apply max) (partial map (comp first val)) get-dijkstras-costs get-triads)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; tests (use '[clojure.test :only [is]]) (is (= 4 (max-events [1 3 3 5 7] [2 2 1 2 1]))) (is (= 3 (max-events [1 3 5] [2 2 2]))) (is (= (max-events [1] [1]) 1))
# Sorted Anagram Position
Given a string of letters (case insensitive), you can create the set of all words with those same letters (and the same frequency)
Example:
"abab" => ["aabb", "abab", "abba", "baab", "baba", "bbaa"]
If you sort this set of words, you can assign a rank to the input word based on where it is in the sorted list.
abab = 2
Write a function that takes in a string and returns it's rank. Your function must accept any word 25 characters or less (repeated characters OK), and must complete in < 500ms.
Examples
aaab = 1
abab = 2
baaa = 4
coolword = 406
beekeeper = 63
zoologist = 57649
Tests
var test = require('tape'), sortedAnagramPosition = require('./sortedAnagramPosition'); test('Output matches known results', function (t) { var knownResults = { mississippi: 13737, aaab: 1, abab: 2, baaa: 4, coolword: 406, beekeeper: 63, zoologist: 57649 }; for (var word in knownResults) { t.equal(sortedAnagramPosition(word), knownResults[word]); } t.end(); }); test('Completes in less than 500ms', function (t) { var timestamp, duration, maxDuration = 500; timestamp = new Date(); sortedAnagramPosition('abcdefghijklmnopqrstuvwxyz'); duration = (new Date()) - timestamp; t.deepEqual(true, (duration < maxDuration)); timestamp = new Date(); sortedAnagramPosition('chmpftbwoopgavchzdjzkptxlz'); duration = (new Date()) - timestamp; t.deepEqual(true, (duration < maxDuration)); t.end(); });
Solution
// Author: Gunar C. Gessner <gunar@gunargessner.com>
// Date: 2015-11-12
// ---------------------------- Permutation Index ----------------------------
// Counts the number of anagrams for unique prefixes that precede it alphabetically
//
// e.g. MISSISSIPPI: letter frequencies are I: 4, M: 1, P: 2, S: 4
// The number of anagrams that start with I is 10!/(3!1!2!4!) = 12600
// The number of anagrams that start with MII is 8!/(2!0!2!4!) = 420
// The number of anagrams that start with MIP is 8!/(3!0!1!4!) = 280
// ...
//
// Further reading:
// - https://en.wikipedia.org/wiki/Multinomial_theorem#/Multinomial_coefficients
// - http://stackoverflow.com/a/18646156/1456173
// - http://stackoverflow.com/a/5131575/1456173
/**
* Factorial calculation
* @param {(number|number[]|object)} A number, an array of numbers or an object with number values.
* @return {number|array|object} Returns the same object type as the input
*/
var factorial = (function (n) {
var memo = {};
return function (n) {
if (typeof n === 'object') return Object.keys(n).map(function (key) { return factorial(n[key]); });
if (n === 0 || n === 1) return 1;
if (n in memo) return memo[n];
memo[n] = factorial(n-1) * n;
return memo[n];
};
}());
/**
* Converts an object to an array
* @param {object|array} Object
* @returns {array}
*/
var toArray = function (object) {
return Object.keys(object).map(function (key) { return object[key]; });
};
/**
* Reduces an object/array to the sum of its values
* @param {object|number[]} Object
* @returns {number} Sum
*/
var sum = function (object) {
if (typeof object !== 'object') return object;
return toArray(object).reduce(function (sum, next) {
return sum + next;
}, 0);
};
/**
* Divides a number by the values of an object
* @param {number} Number
* @param {object|number[]} Object
* @returns {number} Quotient
*/
var divideByMany = function (number, object) {
return toArray(object).reduce(function (a, b) {
return a / b;
}, number);
};
/**
* Calculates multinomial coefficient
* @param {object} An associative array of character frequencies
* @param {string} [char] A character to leave out one instance of
* @returns {number} Quotient
*/
var countAnagrams = function (frequencies, char) {
if (frequencies[char] !== undefined) {
// Clone object
frequencies = Object.assign({}, frequencies);
// Considering leaving out one "char"
frequencies[char] -= 1;
}
// Factorial of the total number of characters
// divided by the factorials of the frequencies
var numOfChars = sum(frequencies);
var factorials = factorial(frequencies);
return divideByMany(factorial(numOfChars), factorials);
};
/**
* Calculates character frequency in an array
* @param {string[]} chars An array of chars
* @returns {object} Character frequency
*/
var charFrequency = function (array) {
var sum = {};
array.map(function (char) {
sum[char] = sum[char] || 0;
sum[char]++;
});
return sum;
};
/**
* Calculates the permutation index for a given word
* a.k.a. sorted anagram position
* @param {string} word
* @param {array} [rank] Initial index value
* @returns {number} Anagram rank / Permutation index
*/
var sortedAnagramPosition = function (word, rank) {
var frequencies = charFrequency(word.split('').sort());
var uniqueChars = Object.keys(frequencies);
rank = rank || 0;
rank += uniqueChars.filter(function (char) {
return char < word[0];
}).map(function (char) {
return countAnagrams(frequencies, char);
}).reduce(function (sum, next) {
return sum + next;
}, 0);
if (word.length > 1) return sortedAnagramPosition(word.substr(1), rank);
else return rank+1;
};
module.exports = sortedAnagramPosition;
