Solving Interview Problems with Deep Learning

Photo credit: Godzilla vs. Kong

It’s been a while since I’ve practiced programming interview questions, and I worry that my skills are lacking. It’s always important to work through some every now and then to stay sharp so here we go:

Let’s start with Fizz Buzz:

Write a program that prints the numbers from 1 to 100. But for multiples of 3print “Fizz” instead of the number and for the multiples of 5 print “Buzz”. For numbers which are multiples of both 3 and 5 print “FizzBuzz”.

This solution was actually inspired by Joel Grus. We can represent numbers with binary encoding:

import tensorflow as tf
import numpy as np
INPUT_SIZE = 10 # We can encode up to 2^15 numbers with binary encoding.
HIDDEN_SIZE = 100 # Hidden layer of size 100
OUTPUT_SIZE = 4 # One hot encoding for the 4 possible outputs: "Fizz" "Buzz" "FizzBuzz", ""
NUM_EPOCHS = 10000
def binary_encode(number):
    data = np.zeros(INPUT_SIZE)
    for bitshift in range(INPUT_SIZE):
        data[bitshift] = number >> bitshift & 1 # Get the bit at position bitshift
    return data
def fizz_buzz_encode(i):
    if   i % 15 == 0: return np.array([0, 0, 0, 1])
    elif i % 5  == 0: return np.array([0, 0, 1, 0])
    elif i % 3  == 0: return np.array([0, 1, 0, 0])
    else:             return np.array([1, 0, 0, 0])
def fizz_buzz_decode(encoding):
    max_idx = np.argmax(encoding)
    if max_idx == 0:
        return ""
    if max_idx == 1:
        return "fizz"
    if max_idx == 2:
        return "buzz"
    if max_idx == 3:
        return "fizzbuzz"

Now, we can generate some training data (we will generate training data from 101 to 1024) since our actual problem will solve fizzbuzz for 1–100.

X_train = np.array([binary_encode(i) for i in range(101, 2 ** INPUT_SIZE)])
y_train = np.array([fizz_buzz_encode(i) for i in range(101, 2 ** INPUT_SIZE)])

And now, let’s define our multilayer perceptron model that will actually perform the bulk of the work. First, we define the inputs to the model:

X = tf.placeholder('float', [None, INPUT_SIZE])
Y = tf.placeholder('float', [None, OUTPUT_SIZE])

Next, let’s define the weights and biases that we will learn via backpropagation:

w1 = tf.get_variable("w1", [INPUT_SIZE, HIDDEN_SIZE], initializer=tf.random_normal_initializer())
b1 = tf.get_variable("b1", [HIDDEN_SIZE])
w2 = tf.get_variable("w2", [HIDDEN_SIZE, OUTPUT_SIZE], initializer=tf.random_normal_initializer())
b2 = tf.get_variable("b2", [OUTPUT_SIZE])

And now, let’s feed our input through the model:

z1 = tf.add(tf.matmul(X, w1), b1)
a1 = tf.nn.relu(z1)
z2 = tf.add(tf.matmul(a1, w2), b2)

Then, let’s compute the loss and tell tensorflow to minimize that loss:

cost = tf.nn.softmax_cross_entropy_with_logits(logits=z2, labels=Y)
optimizer = tf.train.GradientDescentOptimizer(0.001).minimize(cost)

Now, let’s actually feed our real training data into that model:

init = tf.global_variables_initializer()
with tf.Session() as sess:
    sess.run(init)
    for i in range(NUM_EPOCHS):
        c, o = sess.run([cost, optimizer], feed_dict={X: X_train, Y: y_train})
        print(np.sum(c))
    X_test = np.array([binary_encode(i) for i in range(1, 100)])
    y_test = np.array([fizz_buzz_encode(i) for i in range(1, 100)])
    pred = sess.run(z2, feed_dict={X:X_test, Y:y_test})

And print out the results:

def real_fizz_buzz(i):
    txt = ""
    if i % 3 == 0:
        txt += "fizz"
    if i % 5 == 0:
        txt += "buzz"
    return txt

for i in range(len(X_test)):
    text = fizz_buzz_decode(pred[i])
    true_text = real_fizz_buzz(i + 1)
    print("{}: {} ({})".format(i + 1, text, "✔" if text == true_text else "x"))

Results:

1:  (✔)
2:  (✔)
3:  (x)
...
97:  (✔)
98:  (✔)
99: fizz (✔)
Total Accuracy: 89.89%

For all that work, we achieved an embarrassingly low 90% accuracy. I was going to try to fix this but then quickly lost interest. Let’s move onto something a bit more interesting:

Write a program that counts the number of unique characters in a string.

This sounds like a problem that can be solved with an LSTM. Let’s generate some data.

import tensorflow as tf
import random
import numpy as np
CHARS = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
STRING_LENGTH = 12
num_examples = 10000
# Args:
#   n: Number of examples to generate.
# Returns:
#   strings_v: numpy array of the form (n, STRING_LENGTH, len(CHARS)). One hot encoding of sequences of text
#   strings: Array of actual generated random text:
#   uniques_v: numpy array of the form (n, len(CHARS)). One hot encoding of number of unique characters
#   uniques: numpy array of length n, number of unique characters for each sequence.
def generate_data(n=num_examples):
    chars_to_idx = { c: i for i, c in enumerate(CHARS)}

    strings_v = np.zeros([n, STRING_LENGTH, len(CHARS)])
    strings = [''] * n
    uniques = np.zeros(n)
    uniques_v = np.zeros([n, len(CHARS)])
    for x in range(n):
        for y in range(STRING_LENGTH):
            random.shuffle(CHARS)
            char = CHARS[0]

            strings_v[x][y][chars_to_idx[char]] = 1
            strings[x] += char

        uniques[x] = len(set(strings[x]))
        uniques_v[x][len(set(strings[x])) - 1] = 1

    return strings_v, strings, uniques_v, uniques

Next let’s create our LSTM model:

HIDDEN_LAYERS = 64
X = tf.placeholder("float", [None, STRING_LENGTH, len(CHARS)])
y = tf.placeholder("float", [None, len(CHARS)])
X_seq = tf.unstack(X, STRING_LENGTH, 1)
lstm_cell = tf.contrib.rnn.BasicLSTMCell(HIDDEN_LAYERS)
#sequence of 12 chars to output of 7
outputs, states = tf.contrib.rnn.static_rnn(lstm_cell, X_seq, dtype=tf.float32)
final_output = outputs[-1]
weights = tf.get_variable("weights", [HIDDEN_LAYERS, len(CHARS)], initializer=tf.random_normal_initializer())
biases = tf.get_variable("biases", [len(CHARS)], initializer=tf.random_normal_initializer())
prediction = tf.add(tf.matmul(final_output, weights), biases)
cost = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(logits=prediction, labels=y))
optimizer = tf.train.AdamOptimizer(1e-2)
train_op = optimizer.minimize(cost)

Now, let’s go ahead and run our model:

init = tf.global_variables_initializer()
costs = []
EPOCHS = 300
with tf.Session() as sess:
    sess.run(init)
    for i in range(EPOCHS):
        _, c, _ = sess.run([train_op, cost, prediction], feed_dict={X:X_train, y: y_train})
        costs.append(c)
        if i % 10 == 0:
            print('cost: {}, epoch: {}'.format(c, i))

            X_test, X_test_strings, y_test, y_test_strings = generate_data(100)
            p = sess.run(prediction, feed_dict={X: X_test, y: y_test})
            prediction_idxs = np.argmax(p, axis=1)
            prediction_vals = prediction_idxs + 1
correct = 0.0
            for i in range(len(y_test_strings)):
                string = X_test_strings[i]
                actual_val = y_test_strings[i]
                predicted_val = prediction_vals[i]
                # Print the first 5 examples
                if i < 5:
                    print('string: {}, pred: {}, actual: {}'.format(string, predicted_val, actual_val))

                if predicted_val == actual_val:
                    correct += 1
            print("{}% accuracy\n\n".format(correct * 100 / len(y_test_strings)))

cost: 0.0496655665338, epoch: 280
string: eeaccbdeagac, pred: 6, actual: 6.0
string: gefaddbbcfac, pred: 7, actual: 7.0
string: acedcbgdcagf, pred: 7, actual: 7.0
string: aadebcdacefg, pred: 7, actual: 7.0
string: abeeaebcbbag, pred: 5, actual: 5.0
100% accuracycost: 0.0413268692791, epoch: 290
string: ebbfbfaebede, pred: 5, actual: 5.0
string: fgaccdbabedg, pred: 7, actual: 7.0
string: dgdcbaefcdad, pred: 7, actual: 7.0
string: ffagdfedccad, pred: 6, actual: 6.0
string: gfggfgbebcdb, pred: 6, actual: 6.0
99% accuracy

Hopefully the interviewer won’t be disappointed that we cannot solve this problem for any string that’s greater than MAX_LENGTH, but overall, it achieved a 99% accuracy. I didn’t deal with variable length inputs in this case, we could’ve easily done that by adding padding.

Now, instead of just printing out the number of unique characters, print out the actual unique characters in the order they appear.

Ex: “acabdb” => “acbd”

Oof. Thats a much tougher problem. In this case, the value we need to return is a sequence of characters instead of a single character or number so we will need some form of sequence to sequence model in order to learn this relationship.

import numpy as np
import tensorflow as tf
from tensorflow.contrib import rnn
import random
#"abc" => "abc"
#"aabbac" => "abc"
#"abacd" => "abcd"
MAX_LENGTH = 6 # Max length of 6 
chars = ["a", "b", "c", "d", "e", "f"]
all_chars = chars + [' '] # Space for padding
NUM_EXAMPLES = 50000
# Args:
#   n: number of examples to generate
# Returns:
#   strings: list of strings that may contain duplicates
#   solutions: strings without duplicates
#   strings_v: One hot encoding of strings with duplicates (without padding)
#   solutions_v: One hot encoding of solutions (with padding)
def generate_data(n=NUM_EXAMPLES):
    all_chars_to_idx = { c:i for i, c in enumerate(all_chars) }
    strings_v = np.zeros((NUM_EXAMPLES, MAX_LENGTH, len(all_chars)))
    solutions_v = np.zeros((NUM_EXAMPLES, MAX_LENGTH, len(all_chars)))

    strings = [''] * NUM_EXAMPLES
    solutions = [''] * NUM_EXAMPLES

    for i in range(NUM_EXAMPLES):
        for l in range(MAX_LENGTH):
            char = random.choice(chars) # only sample from valid characters
            strings[i] += char
            if char not in solutions[i]:
                solutions[i] += char

        # Pad solutions strings
        num_missing = MAX_LENGTH - len(solutions[i])
        solutions[i] += ' ' * num_missing

    for x in range(len(strings)):
        for y in range(MAX_LENGTH):
            string_char = strings[x][y]
            strings_v[x][y][all_chars_to_idx[string_char]] = 1

            solution_char = solutions[x][y]
            solutions_v[x][y][all_chars_to_idx[solution_char]] = 1

    return strings, solutions, strings_v, solutions_v

Again, we can one hot encode the sequences, but this time, we will add some padding since the length of the output string is variable. Instead of trying to return a variable length sequence, we will just return a sequence that is equal to the length of the input, and pad the output with spaces.

For example, “abdab” would map to a string of the same length, but with spaces as padding: “abd “.

Let’s create a test and training split.

strings, solutions, strings_v, solutions_v = generate_data()
split_at = len(strings) - (len(strings) // 10)
strings_train = strings[:split_at]
solutions_train = solutions[:split_at]
X_train = strings_v[:split_at]
y_train = solutions_v[:split_at]
strings_test = strings[split_at:]
solutions_test = solutions[split_at:]
X_test = strings_v[split_at:]
y_test = solutions_v[split_at:]

Now we can set up our model. Let’s start with the encoder:

encoded_input = tf.placeholder(tf.float32, shape=(None, MAX_LENGTH, len(all_chars)))
decoded_input = tf.placeholder(tf.float32, shape=(None, MAX_LENGTH, len(all_chars)))
with tf.name_scope("basic_rnn_seq2seq") as scope:
    encoded_sequence = tf.unstack(encoded_input, MAX_LENGTH, 1)
    encoder_cell = rnn.BasicLSTMCell(128, forget_bias=1.0)
    encoded_outputs, states = rnn.static_rnn(encoder_cell, encoded_sequence, dtype=tf.float32)

And now, the decoder:

with tf.name_scope("lstm_decoder") as scope:
    decoded_sequence = tf.unstack(decoded_input, MAX_LENGTH, 1)
    decoder_cell = rnn.BasicLSTMCell(128, reuse=True)
    decoded_outputs, _ = rnn.static_rnn(decoder_cell, decoded_sequence, initial_state=states, dtype=tf.float32)

Now, we can compute the predictions by multiplying the decoder’s hidden layer output with a fully connected layer:

with tf.name_scope("fully_connected") as scope:
    weights = tf.get_variable('weights', (128, len(all_chars)), initializer=tf.random_normal_initializer())
    biases = tf.get_variable('biases', (len(all_chars)), initializer=tf.random_normal_initializer())

    predictions = []
    encoded_sequence = tf.unstack(decoded_input, MAX_LENGTH, 1)
for output in decoded_outputs:
        prediction = tf.add(tf.matmul(output, weights), biases)
        predictions.append(prediction)
concatenated_outputs = tf.stack(predictions, 0)
    concatenated_outputs = tf.transpose(concatenated_outputs, perm=[1, 0, 2])
    concatenated_inputs = tf.concat(decoded_input, 0)

Now, we can compute the loss:

cost = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(logits=concatenated_outputs, labels=concatenated_inputs))
# FC Layer
optimizer = tf.train.AdamOptimizer(1e-2)
train_op = optimizer.minimize(cost)

And now let’s run our model:

def decode_guess(one_hot):
    return ''.join([all_chars[m] for m in np.argmax(one_hot, axis=1)])
init = tf.global_variables_initializer()
costs = []
with tf.Session() as sess:
    sess.run(init)
    for i in range(30):
        e, r, c, t, c_out, c_in = sess.run([encoded_outputs, predictions, cost, train_op, concatenated_outputs, concatenated_inputs], feed_dict={encoded_input: X_train, decoded_input: y_train})
        costs.append(c)
        if i % 5 == 0:
            print('training cost: {}, epoch: {}'.format(c, i))

            results = sess.run(predictions, feed_dict={encoded_input: X_test, decoded_input: y_test})
            guesses = np.array(results).transpose(1, 0, 2)
            for i in range(5):
                string = strings_test[i]
                solution = solutions_test[i]
                guess_decoded = decode_guess(guesses[i])
                print("{}: {} - {}".format(string, solution, guess_decoded))

            correct = 0.0
            for i in range(len(strings_test)):
                string = strings_test[i]
                solution = solutions_test[i]
                guess_decoded = decode_guess(guesses[i])
                if i < 5:
                    print("input: {}, solution: {}, prediction: {}".format(string, solution, guess_decoded))
if solution == guess_decoded:
                    correct += 1

            print("{} % accuracy".format(correct / len(strings_test) * 100))

And here are the results:

training cost: 2.07600975037, epoch: 0
cebbdf: cebdf  -       
dffcbc: dfcb   -       
aadeab: adeb   -       
faceec: face   -       
bfaeec: bfaec  -       
0.0 % accuracy...training cost: 0.219934388995, epoch: 25
cebbdf: cebdf  - cebdf 
dffcbc: dfcb   - dfcb  
aadeab: adeb   - adeb  
faceec: face   - face  
bfaeec: bfaec  - bfaec 
100.0 % accuracy

It looks like by 25 epochs, our model has a fairly good understanding of how to solve this problem.

Please do not solve real interview problems in this way.