This website is undergoing a re-design (Sat Jul 11 2020)

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

Answer: 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

//
// THIS GIVES A WRONG ANSWER
//
function sum(string) {
  const VOWELS = ["a", "e", "i", "o", "u"];
  return (
    string
      // XXX: This is the problem, we can't lowercase here as it changes the char code
      .toLowerCase()
      .replace(/[^a-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."
  )
);

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

# Changelog