Home

Code interview challenges and their solutions

Gunar Gessner

Gunar Gessner

Jun 27, 2020

Code challenges suck. I mean, I like to do they on my own time, but that's just a hobby. In no way do they 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 retribution. Hope that if we're faced with one of the challenges below, we get to search on the internet and 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 from the internet.

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

A team organizing a university career fair has a list of companies along with their respective arrival times and their duration of stay. Only one company can present at any time. Given each company's arrival time and the duration they will stay, determine the maximum number of presentations that can be hosted during the career fair.

Example

The first company arrives at time 1 and stays for 2 hours. At time 3, two companies arrive, but only 1 can stay for either 1 or 2 hours. The next companies arrive at times 5 and 7 and do not conflict with any others. In total, there can be a maximum of 4 promotional events.

n = 5
arrival = [1, 3, 3, 5, 7]
duration = [2, 2, 1, 2, 1]

Function Description

Complete the function maxEvents:

maxEvents has the following parameter(s):
    int arrival[n]:  an array of integers where ith element is the arrival time of the ith company
    int duration[n]:  an array of integers where ith element is the duration that the ith company's stay at the career fair
Returns:
    int: the maximum number of promotional events that can be hosted 
Constraints:
  1 < n < 50
  1  < arrival[i] < 1000
  1 < duration[i] < 1000
Both the 'arrival' array and 'duration' array will have an equal number of elements

Solution

This is a scheduling problem. We can solve most such 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 a MAX(COST)

; [[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))

; HackerRank 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))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; code inserted by hackerrank for input parsing
(def fptr (get (System/getenv) "OUTPUT_PATH"))
(def arrival-count (Integer/parseInt (clojure.string/trim (read-line))))
(def arrival [])
(doseq [_ (range arrival-count)] (def arrival (conj arrival (Integer/parseInt (clojure.string/trim (read-line))))))
(def duration-count (Integer/parseInt (clojure.string/trim (read-line))))
(def duration [])
(doseq [_ (range duration-count)] (def duration (conj duration (Integer/parseInt (clojure.string/trim (read-line))))))
(def result (maxEvents arrival duration))
(spit fptr (str result "\n") :append true)

# 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;

Sign up for the newsletter


Read other stuff