Interview Stuff

0.md

Technical Interview Notes

Sites for practice

• Code Eval
• CoderByte
• theReq Ruby questions

array_occurrances.md

Count Occurrences in Array

values = [1, 2, 5, 5, 7, 7, 7, 10]
puts values.each_with_object(Hash.new(0)) { |number, counts| counts[word] += 1 }
# => { 1 => 1, 2 => 1, 5 => 2, 7 => 3, 10 => 1 }

This can also be used with letters or words or arrays of anything basically.

Longest string in array

If there's no duplicated strings in the array then you can use.

words = ["fun", "time", "ab"]
puts words.sort_by(&:length).last
# => "time"

Simply calling words.sort would sort based on the alphabetic position of the first letter of each word.

factorials.md

Factorials

There is no builtin for calculating factorials. To calculate factorials:

n = 4
(1..n).inject(:*) || 1
# => 24

fibonacci.md

Fibonacci

The simple looped solution to print out the first n numbers in the Fibonacci sequence looks like this:

def looped_fib(n)
  return 1 if n <= 2

  fib = 3
  n_minus_1, n_minus_2 = 1,1

  3.upto(n) do
    fib = n_minus_1 + n_minus_2
    n_minus_1, n_minus_2 = n_minus_2, fib
  end

  fib
end

puts looped_fib(n)

There's also a recursive solution which looks like this:

def recursive_fib(n)
  n <= 2 ? 1 : recursive_fib(n - 1) + recursive_fib(n - 2)
end

puts recursive_fib(n)

This is slow as balls though because it iterates through the whole sequence three times for each number it calculates. It can be quickened by memoizing the sequence as it calculates.

def cached_fib(n, cache)
  return 1 if n <= 2
  return cache[n] if cache.has_key?(n)
  cache[n] = cached_fib(n - 1, cache) + cached_fib(n - 2, cache)
end

puts cached_fib(n, {})

palindromes.md

Palindromes

Testing if a string is a palindrome is simple:

module StringExtensions
  refine String do
    def palindrome?
      reverse == self
    end
  end
end

There's a simple method for testing whether or not a jumbled up string could be made into a palindrome.

1. Count the number of occurrences of each letter in the string.
2. If there's more than one odd count then you can't make a palindrome.

This algorithm can be expressed in ruby as follows:

module StringExtensions
  refine String do
    def count_letters
      split(//).each_with_object(Hash.new(0)) { |letter, count| count[letter] += 1 }
    end

    def palindromic?
      count_letters.select { |_, occurrences| occurrences.odd? }.count <= 1
    end
  end
end

Finally, the letters of a jumbled up string can be rearranged to form a palindrome with this algo:

module StringExtensions
  refine String do
    def to_palindrome
      return -1 if not palindromic?

      palindrome = []
      occurrences = count_letters

      occurrences.each do |letter, count|
        # This will ignore letters which only occur once since 1/2 = 0
        (count/2).times do
          palindrome.push(letter)
          # NOTE: #unshift can be a slow operation on large arrays because
          # every element of the array must be moved up an index in order to
          # make space for another element at the start. Shouldn't matter here
          # but definitely something to keep in mind. #shift doesn't suffer from
          # the same problems because ruby simply moves the pointer which points
          # to the head of the array.
          palindrome.unshift(letter)
          # Indicate that two of the occurrences have already been applied.
          occurrences[letter] -= 2
          # Delete from the array so that we can iterate over it again
          # in future without re-accounting for any letters.
          occurrences.delete(letter) if occurrences[letter] == 0
        end
      end

      # At this point, only odd occurring letters should be left and there
      # should only be one instance of an odd occurring letter (or else we
      # wouldn't have a palindrome.
      if occurrences.any?
        # Insert this last letter into the centre of the array. #insert
        # suffers from a similar problem as #unshift.
        palindrome.insert((palindrome.length / 2), occurrences.keys.first)
      end

      palindrome.join
    end
  end
end

using StringExtensions

primes.md

Primes

Ruby has a class in the standard library for dealing with primes.

To print the first n primes:

require "prime"
puts Prime.first(n)

The manual method looks like this uses a method called the Sieve of Erathosthenes.

# Generate the first n primes using the Sieve of Erathosthenes.
def primes(upper_limit = 100)
  # Zero and one are not prime numbers.
  primes = (2..upper_limit).to_a
  primes.each do |number|
    # We're going to be nillifying items in the array and we don't want them
    # getting caught up in our logic.
    next if number.nil?

    # Ensure we don't start the stepping loop on a number that's not in the
    # array. We're finished if we try to do that.
    break if number * number > upper_limit

    # Nullify elements in the array starting at number squared and stepping up
    # in increments of number. We start at number squared in order to ensure
    # that the first instance of a particular number doesn't get nillified.
    #
    # Example:
    # 
    #   Initial array = [2, 3, 4, 5, 6, 7, 8, 9, 10]
    #   First iter  (number = 2): [2, 3, nil, 5, nil, 7, nil, 9, nil]
    #   Second iter (number = 3): [2, 3, nil, 5, nil, 7, nil, nil, nil]
    #
    (number * number).step(upper_limit, number) { |n| primes[n] = nil }
  end
  primes.compact!
end

puts @primes = primes

# Test if a number is prime.
def is_prime?(num)
  @primes.include?(num)
end