Useful for Coding Exercises

codingchallenge.md

Do as many of the following as you can in the time given. Order of completion does not matter.

CIPHER

Implement a Caesar cipher, both encoding and decoding. The key is an integer from 1 to 25. This cipher rotates the letters of the alphabet (A to Z). The encoding replaces each letter with the 1st to 25th next letter in the alphabet (wrapping Z to A). So key 2 encrypts "HI" to "JK", but key 20 encrypts "HI" to "BC". This simple "monoalphabetic substitution cipher" provides almost no security, because an attacker who has the encoded message can either use frequency analysis to guess the key, or just try all 25 keys.

• Example input: 2, "HI", Expected output: "JK"
• Example input: 20, "HI", Expected output: "BC"

SIEVE OF ERATOSTHENES

The Sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so).

From Wikipedia:

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the smallest prime number.
3. Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ... ; the p itself should not be marked).
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

Write a function to which you pass a max value and return an array of all primes between 2..(max).

CHANGE RETURN PROGRAM

The user enters a cost and then the amount of money given. The program will figure out the change and the number of quarters, dimes, nickels, pennies needed for the change.

Example input: 0.97 Expected output:

    {
      "0.25": 3, 
      "0.10": 2, 
      "0.05": 0, 
      "0.01": 2
    }

INVERTED INDEX

An Inverted Index is a data structure used to create full text search. Given a set of text files, implement a program to create an inverted index. To simplify an array of strings can replace a directory of text files. The search index can be in memory.

Example data:

    [
      "add this string to index",
      "this is in an index",
      "this is an example",
      "the index can be in memory."
    ]

Expected output:

    {
      "index": [0,1,3],
      "an": [0,1,2],
      ...
    }