# HG changeset patch
# User Louis Opter <kalessin@kalessin.fr>
# Date 1372559431 25200
# Node ID 20fea762903ea17b2f0ddd2cb7423e8e1e1777c9

Import some exercises and solutions

diff -r 000000000000 -r 20fea762903e README.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/README.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,45 @@
+Peeves
+======
+
+Annoying things every programmer should know and will be asked during job
+interviews, especially phone screens.
+
+This is not a complete nor canonical list of exercises, moreover the solutions
+present here are only examples. If you find incorrect things or want to add new
+problems let me know!
+
+Some questions have hints, it's totally okay to read them.
+
+And some questions have additional twists, you don't have to do them but you
+should at least think about what they imply.
+
+Tips
+----
+
+Use the language you are the more used to. Prefer scripting languages like
+Python (you definitely want slices, built-in lists, dictionaries and Unicode
+support). You'll find some solutions in C here but I actually never did
+anything in C during an interview.
+
+During phone screens you'll be coding on something like collabedit_, during
+on-site interviews you'll be coding on a whiteboard. In both cases you won't be
+able to take a trial and error approach; keep that in mind and work on these
+exercises using a textbook.
+
+.. _collabedit: http://collabedit.com/
+
+Also
+----
+
+You'll also get dumb questions like “What is a zombie process”, “What's the
+between hard and symbolic links”, “How many hosts in a /22 ?”. Be prepared for
+some scripting exercises. You should have done some sysadmin and be familiar
+with Linux.
+
+This doesn't include design or troubleshooting questions, I can give you some
+in private.
+
+Instead of phone screens, some companies can ask you to do a small project at
+home, again use the tools you are the most familiar with.
+
+More lulz: http://projecteuler.net/.
diff -r 000000000000 -r 20fea762903e arrays/atof/hints.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/atof/hints.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,4 @@
+Hints
+=====
+
+Recode atoi first and simply use it twice.
diff -r 000000000000 -r 20fea762903e arrays/atof/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/atof/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,5 @@
+atof
+====
+
+Recode a function that takes a string like "223.52" or "-42.51" and returns a
+float.
diff -r 000000000000 -r 20fea762903e arrays/crosses/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/crosses/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,9 @@
+“Draw” Crosses in a Matrix
+==========================
+
+Write an algorithm such that if an element in an MxN matrix is 0 is entire row
+and column is set to 0.
+
+.. note::
+
+   I actually didn't get this during an interview but it seems to be a classic.
diff -r 000000000000 -r 20fea762903e arrays/crosses/solution.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/crosses/solution.c	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,58 @@
+/*
+ * Write an algorithm such that if an element in an MxN matrix is 0 is entire
+ * row and column is set to 0.
+ */
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+char array[4][4] = {
+    { 'x', 'x', '0', 'x'},
+    { 'x', 'x', 'x', 'x'},
+    { 'x', '0', 'x', 'x'},
+    { 'x', 'x', 'x', 'x'}
+};
+enum { size = 4 };
+
+void
+print_array(char array[][4])
+{
+    for (int i = 0; i != size; i++) {
+        for (int j = 0; j != size; j++) 
+            printf(" %c", array[i][j]);
+        printf("\n");
+    }
+}
+
+void
+bomb_array(char array[][4])
+{
+    bool rows[size] = { false, };
+    bool columns[size] = { false, };
+
+    for (int i = 0; i != size; i++) {
+        for (int j = 0; j != size; j++) {
+            if (array[i][j] == '0') {
+                rows[i] = true;
+                columns[j] = true;
+            }
+        }
+    }
+    for (int i = 0; i != size; i++) {
+        for (int j = 0; j != size; j++) {
+            if (rows[i] || columns[j])
+                array[i][j] = '0';
+        }
+    }
+}
+
+int
+main(void)
+{
+    print_array(array);
+    printf("Bombing array…\n");
+    bomb_array(array);
+    print_array(array);
+    return EXIT_SUCCESS;
+}
diff -r 000000000000 -r 20fea762903e arrays/identify_string_rotation/questions.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/identify_string_rotation/questions.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,7 @@
+Identify String Rotation
+========================
+
+Assume you have a metho isSubstring which checks if one word is a substring of
+another. Given two strings, s1 and s2, write a function that checks if s2 is a
+rotation of s1 using a single call to isSubstring (i.e: "waterbottle" is a
+rotation of "erbottlewat").
diff -r 000000000000 -r 20fea762903e arrays/identify_string_rotation/solution.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/identify_string_rotation/solution.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,1 @@
+# Concat the two strings
diff -r 000000000000 -r 20fea762903e arrays/mini_fnmatch/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/mini_fnmatch/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,7 @@
+minifnmatch
+===========
+
+Write a fnmatch(string, pattern) → bool function that supports the * and ?
+metacharacters. See fnmatch(3).
+
+.. note:: Stéphane got this.
diff -r 000000000000 -r 20fea762903e arrays/mini_fnmatch/solution.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/mini_fnmatch/solution.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,97 @@
+#!/usr/bin/env python
+
+# Only support * and ?
+
+def fnmatch(name, pat):
+    if not pat:
+        return not name
+
+    namelen = len(name)
+    patlen = len(pat)
+
+    name_idx = 0
+    pat_idx = 0
+    while name_idx < namelen and pat_idx < patlen:
+        if pat[pat_idx] == '?':
+            pat_idx += 1
+            name_idx += 1
+        elif pat[pat_idx] == '*':
+            nextchar_pat = None if pat_idx + 1 == len(pat) else pat[pat_idx + 1]
+            if nextchar_pat is None:
+                return True
+            if nextchar_pat == name[name_idx]:
+                pat_idx += 2
+            name_idx += 1
+        elif name[name_idx] == pat[pat_idx]:
+            name_idx += 1
+            pat_idx += 1
+        else:
+            return False
+    return True
+
+def fnmatch_r(name, pat):
+    if not name:
+        return True
+    if not pat:
+        return not name
+    if pat[0] == '*':
+        nextchar_pat = None if len(pat) == 1 else pat[1]
+        if nextchar_pat is None:
+            return True
+        if nextchar_pat == name[0]:
+            pat = pat[2:]
+        return fnmatch_r(name[1:], pat)
+    if pat[0] == '?' or name[0] == pat[0]:
+        return fnmatch_r(name[1:], pat[1:])
+    return False
+
+if __name__ == "__main__":
+    assert fnmatch("toto.py", "*")
+    print('assert fnmatch("toto.py", "*") → ok')
+    assert fnmatch("toto.py", "*.py")
+    print('assert fnmatch("toto.py", "*.py") → ok')
+    assert not fnmatch("toto.py", "*.c")
+    print('assert not fnmatch("toto.py", "*.c") → ok')
+    assert fnmatch("toto.py", "toto.*")
+    print('assert fnmatch("toto.py", "toto.*") → ok')
+    assert fnmatch("/dev/sda1", "/dev/sda?")
+    print('assert fnmatch("/dev/sda1", "/dev/sda?") → ok')
+    assert fnmatch("/dev/sdb1", "/dev/sd?1")
+    print('assert fnmatch("/dev/sdb1", "/dev/sd?1") → ok')
+    assert fnmatch("aaa", "???")
+    print('assert fnmatch("aaa", "???") → ok')
+    assert fnmatch("aaa", "?*")
+    print('assert fnmatch("aaa", "?*") → ok')
+    assert fnmatch("aaa", "???*")
+    print('assert fnmatch("aaa", "???*") → ok')
+    assert not fnmatch("aaa", "bbb")
+    print('assert not fnmatch("aaa", "bbb") → ok')
+    assert fnmatch("", "")
+    print('assert fnmatch("", "") → ok')
+    assert not fnmatch("toto", "")
+    print('assert not fnmatch("toto", "") → ok')
+
+    assert fnmatch_r("toto.py", "*")
+    print('assert fnmatch_r("toto.py", "*") → ok')
+    assert fnmatch_r("toto.py", "*.py")
+    print('assert fnmatch_r("toto.py", "*.py") → ok')
+    assert not fnmatch_r("toto.py", "*.c")
+    print('assert not fnmatch_r("toto.py", "*.c") → ok')
+    assert fnmatch_r("toto.py", "toto.*")
+    print('assert fnmatch_r("toto.py", "toto.*") → ok')
+    assert fnmatch_r("/dev/sda1", "/dev/sda?")
+    print('assert fnmatch_r("/dev/sda1", "/dev/sda?") → ok')
+    assert fnmatch_r("/dev/sdb1", "/dev/sd?1")
+    print('assert fnmatch_r("/dev/sdb1", "/dev/sd?1") → ok')
+    assert fnmatch_r("aaa", "???")
+    print('assert fnmatch_r("aaa", "???") → ok')
+    assert fnmatch_r("aaa", "?*")
+    print('assert fnmatch_r("aaa", "?*") → ok')
+    assert fnmatch_r("aaa", "???*")
+    print('assert fnmatch_r("aaa", "???*") → ok')
+    assert not fnmatch_r("aaa", "bbb")
+    print('assert not fnmatch_r("aaa", "bbb") → ok')
+    assert fnmatch_r("", "")
+    print('assert fnmatch("", "") → ok')
+    assert not fnmatch_r("toto", "")
+    print('assert not fnmatch("toto", "") → ok')
diff -r 000000000000 -r 20fea762903e arrays/pack_values_at_beginning/hints.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/pack_values_at_beginning/hints.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,4 @@
+Hints
+=====
+
+Span the array from the end.
diff -r 000000000000 -r 20fea762903e arrays/pack_values_at_beginning/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/pack_values_at_beginning/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,8 @@
+Pack values
+===========
+
+Given an array of integer and a specific integer value (e.g: 4) you need to
+move all the integer with that value (in the array) at the beginning of the
+array. The order of the other elements must not change.
+
+.. note:: Stéphane got this.
diff -r 000000000000 -r 20fea762903e arrays/pack_values_at_beginning/solution.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/pack_values_at_beginning/solution.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,34 @@
+#!/usr/bin/env python
+
+# Given an array of integer and a specific integer value (e.g: 4) you need to
+# move all the integer with that value (in the array) at the beginning of the
+# array. The order of the other elements must not change.
+
+import random
+
+def pack(array, n):
+    src = dest = len(array) - 1
+
+    while src >= 0:
+        while src >= 0 and array[src] == n:
+            src -= 1
+        if src >= 0 and src != dest:
+            array[dest] = array[src]
+        src -= 1
+        dest -= 1
+
+    while dest != -1:
+        array[dest] = n
+        dest -= 1
+
+array = [random.choice(range(10)) for i in range(15)]
+n = random.choice(range(10))
+print("array = {0}, n = {1}".format(array, n))
+pack(array, n)
+print("array = {0}".format(array))
+print("****")
+array = [7, 9, 0, 8, 2, 3, 9, 9, 9, 2, 5, 6, 6, 0, 1]
+n = 9
+print("array = {0}, n = {1}".format(array, n))
+pack(array, n)
+print("array = {0}".format(array))
diff -r 000000000000 -r 20fea762903e arrays/rle/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/rle/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,8 @@
+RLE
+===
+
+Code a RLE_ function that takes a string as input.
+
+.. _RLE: https://en.wikipedia.org/wiki/Run-length_encoding
+
+.. note:: Stéphane got this.
diff -r 000000000000 -r 20fea762903e arrays/rle/solution.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/rle/solution.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,31 @@
+#!/usr/bin/env python
+
+def rle_8b(buf):
+    acc = 1
+    ret = []
+    n = len(buf)
+    i = 1
+    while i < n:
+        if buf[i] != buf[i - 1]:
+            ret.append((acc, buf[i - 1]))
+            acc = 1
+        if buf[i] == buf[i - 1]:
+            if acc == 2**8 - 1:
+                # NOTE: the rationale for doing that is to later decode the
+                # file (it's easier if you know on how many bits the length is
+                # encoded). You don't have to dot it.
+                ret.append((acc, buf[i]))
+                acc = 1
+            else:
+                acc += 1
+        i += 1
+    ret.append((acc, buf[i - 1]))
+    return ret
+
+buf1 = "fjesffffffflllllljf"
+buf2 = "fehs1111233"
+buf3 = 256 * "a" + 512 * "C"
+
+print("rle_8b({0}) → {1}".format(buf1, rle_8b(buf1)))
+print("rle_8b({0}) → {1}".format(buf2, rle_8b(buf2)))
+print("rle_8b({0}) → {1}".format(buf3, rle_8b(buf3)))
diff -r 000000000000 -r 20fea762903e arrays/rotate_matrix_90/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/rotate_matrix_90/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,6 @@
+Rotate Matrix
+=============
+
+Rotate the given n*n matrix by 90°.
+
+.. note:: Andrea got this.
diff -r 000000000000 -r 20fea762903e arrays/rotate_matrix_90/solution.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/rotate_matrix_90/solution.c	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,93 @@
+#define _BSD_SOURCE
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+int even_array[4][4] = {
+    {1, 2, 3, 4},
+    {5, 6, 7, 8},
+    {9, 10, 11, 12},
+    {13, 14, 15, 16}
+};
+
+int odd_array[3][3] = {
+    {1, 2, 3},
+    {4, 5, 6},
+    {7, 8, 9}
+};
+
+int
+abs(int v)
+{
+    return v ? v >= 0 : v * -1;
+}
+
+void
+swap(int *a, int *b)
+{
+    int save = *b;
+    *b = *a;
+    *a = save;
+}
+
+void
+print_array(int array[][4], int size)
+{
+    printf("Array %1$d×%1$d:\n", size);
+    for (int i = 0; i != size; i++) {
+        for (int j = 0; j != size; j++) 
+            printf(" %2d", array[i][j]);
+        printf("\n");
+    }
+}
+
+void
+rotate_90(int array[][4], int size)
+{
+    int i;
+    int j;
+    int next_i;
+    int next_j;
+    int value;
+
+    for (int layers = 0; layers != size / 2; layers++) {
+        for (int rounds = layers; rounds != size - 1 - layers; rounds++) {
+            i = layers;
+            j = rounds;
+            value = array[i][j];
+            do {
+                next_j = abs(size - 1 - i);
+                next_i = j;
+                printf("%d (%d, %d) → (%d, %d)\n", value, i, j, next_i, next_j);
+                usleep(250000);
+                swap(&value, &array[next_i][next_j]);
+                print_array(array, size);
+                i = next_i;
+                j = next_j;
+            } while (next_i != layers || next_j != rounds);
+        }
+    }
+}
+
+int
+main(void)
+{
+    // http://c-faq.com/aryptr/pass2dary.html
+#if 0
+    print_array(odd_array, 3);
+    printf("rotating…\n");
+    rotate_90(odd_array, 3);
+    printf("rotated…\n");
+    print_array(odd_array, 3);
+
+    printf("***\n");
+#endif
+  
+    print_array(even_array, 4);
+    printf("rotating…\n");
+    rotate_90(even_array, 4);
+    printf("rotated…\n");
+    print_array(even_array, 4);
+
+    return EXIT_SUCCESS;
+}
diff -r 000000000000 -r 20fea762903e arrays/tail/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/tail/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,9 @@
+Tail
+====
+
+Recode ``tail -n 10``.
+
+Twists
+------
+
+- The file is huge.
diff -r 000000000000 -r 20fea762903e arrays/tokenize/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/tokenize/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,10 @@
+Tokenize
+========
+
+Write a function tokenize(string) → [word1, word2…].
+
+Twists
+------
+
+- Same thing but with a filename in input (i.e: you have to load the file);
+- Handle punctuation (i.e: consider commas like a spaces).
diff -r 000000000000 -r 20fea762903e arrays/word_count/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/word_count/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,10 @@
+Word Count
+==========
+
+Given a string, count the words in the string.
+
+Twists
+------
+
+- Same thing with a file;
+- Same thing without keeping the full file in memory.
diff -r 000000000000 -r 20fea762903e arrays/word_count/wc.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/arrays/word_count/wc.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,33 @@
+#!/usr/bin/env python
+
+def wc(buf):
+    word_count = 0
+    line_count = 0
+    i = 1
+    n = len(buf)
+
+    while i < n and buf[i].isspace():
+        if buf[i] == "\n":
+            line_count += 1
+        i += 1
+    while i < n - 1:
+        if not buf[i - 1].isspace() and buf[i].isspace():
+            word_count += 1
+            while i < n - 1 and buf[i].isspace():
+                if buf[i] == "\n":
+                    line_count += 1
+                i += 1
+        else:
+            i += 1
+    if not buf[i].isspace():
+        word_count += 1
+
+    return word_count, line_count
+
+s1 = "rhje rhesr    jrelskj   "
+s2 = "fjesl\n ffjesl  jfes  \n\nfjles fls\n \n"
+s3 = " fjeksl fjkels ff"
+
+print("wc({0}) = {1}".format(s1, wc(s1)))
+print("wc({0}) = {1}".format(s3, wc(s3)))
+print("wc({0}) = {1}".format(s2.replace("\n", "\\n"), wc(s2)))
diff -r 000000000000 -r 20fea762903e combinations_permutations/combinations/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/combinations_permutations/combinations/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,10 @@
+Combinations
+============
+
+Recode itertools.combinations_.
+
+.. _itertools.combinations: http://docs.python.org/3/library/itertools.html?highlight=itertools.combinations#itertools.combinations
+
+.. note:: You might want to check: https://en.wikipedia.org/wiki/Combinations
+
+.. note:: Stéphane got this wrapped in a lottery story.
diff -r 000000000000 -r 20fea762903e combinations_permutations/permutations/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/combinations_permutations/permutations/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,10 @@
+Permutations
+============
+
+Recode itertools.permutations_.
+
+.. _itertools.permutations: http://docs.python.org/3/library/itertools.html?highlight=itertools.permutation#itertools.permutations
+
+.. note:: You might want to check: https://en.wikipedia.org/wiki/Permutations
+
+.. note:: I didn't get this, but it looks like a classic.
diff -r 000000000000 -r 20fea762903e combinations_permutations/phone_to_words/hints.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/combinations_permutations/phone_to_words/hints.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,4 @@
+Hints
+=====
+
+Recurse on number[1:].
diff -r 000000000000 -r 20fea762903e combinations_permutations/phone_to_words/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/combinations_permutations/phone_to_words/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,19 @@
+Phone Number to Words
+=====================
+
+Picture a telephone keypad and write a function that takes a phone number in
+argument (as a string) and return the list of possible words that map to this
+number (the words don't have to be valid dictionary words).
+
+The following function is provided:
+
+.. code-block:: python
+
+   def d2l(digit):
+        return {
+            "2": "abc", "3": "def",
+            "4": "ghi", "5": "jkl", "6": "mno",
+            "7": "pqrs", "8": "tuv", "9": "wxyz"
+        }[digit]
+
+Example: p2w("23") → [ad, ae, af, bd, be, bf, cd, ce, cf].
diff -r 000000000000 -r 20fea762903e combinations_permutations/phone_to_words/solution.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/combinations_permutations/phone_to_words/solution.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,25 @@
+#!/usr/bin/env python
+
+def d2l(digit):
+    return {
+        "2": "abc",
+        "3": "def",
+        "4": "ghi",
+        "5": "jkl",
+        "6": "mno",
+        "7": "pqrs",
+        "8": "tuv",
+        "9": "wxyz"
+    }[digit]
+
+def p2w(number):
+    if len(number) == 1:
+        return [letter for letter in d2l(number)]
+    letters = d2l(number[0])
+    acc = []
+    for i in letters:
+        acc.extend([i + s for s in p2w(number[1:])])
+    return acc
+
+print(p2w("23"))
+print(p2w("234"))
diff -r 000000000000 -r 20fea762903e combinations_permutations/similar_words/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/combinations_permutations/similar_words/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,15 @@
+Similar Words
+=============
+
+Write a function that take a word in argument. Return the list of words that
+have a distance <= 1 from the given word. (i.e: the list of words that are only
+different by one letter from the given word).
+
+Possible edits: add, remove or change a letter.
+
+A function ``is_in_dictionary(word) → bool`` is provided.
+
+For example, if we had this dictionary: ['bat', 'cat', 'batt', 'beetle']::
+
+    similar('bat') → ['bat', 'cat', 'batt']
+    similar('cat') → ['bat', 'cat']
diff -r 000000000000 -r 20fea762903e combinations_permutations/word_combs/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/combinations_permutations/word_combs/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,8 @@
+Words Combinations
+==================
+
+Given an array of letters (i.e: a string), generate all the possible words
+using these letters and return them sorted by length. Once an input letter has
+been used it cannot be re-used.
+
+A function ``is_in_dictionary(word) → bool`` is provided.
diff -r 000000000000 -r 20fea762903e graphs_trees/bstget/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/bstget/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,4 @@
+BSTGet
+======
+
+Return the nth node from a binary search tree.
diff -r 000000000000 -r 20fea762903e graphs_trees/bstget/solution.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/bstget/solution.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,94 @@
+#!/usr/bin/env python
+
+
+class Node:
+    def __init__(self, val):
+        self.right = None
+        self.left = None
+        self.val = val
+
+
+def tree_insert(root, val):
+    if val > root.val:
+        if root.right is None:
+            root.right = Node(val)
+            return
+        tree_insert(root.right, val)
+    else:
+        if root.left is None:
+            root.left = Node(val)
+            return
+        tree_insert(root.left, val)
+
+
+def tree_print(root):
+    def _tree_print(root):
+        if root is None:
+            return
+        _tree_print(root.left)
+        if root.left:
+            print("    {0} -> {1} [color=blue];".format(root.val, root.left.val))
+        if root.right:
+            print("    {0} -> {1} [color=red];".format(root.val, root.right.val))
+        _tree_print(root.right)
+
+    print("digraph G {")
+    _tree_print(root)
+    print("}")
+
+
+# This is not optimal, the version below is better
+def bstget(root, n):
+    stack = []
+    visited = []
+    i = 0
+    it = root
+
+    while it:
+        if it in visited:
+            print(it.val)
+            i += 1
+            if i == n:
+                return it
+        else:
+            if it.right:
+                stack.append(it.right)
+            stack.append(it)
+            if it.left:
+                stack.append(it.left)
+            visited.append(it)
+        it = stack.pop() if stack else None
+
+    return None
+
+
+def bstget2(root, n):
+    stack = []
+    i = 0
+    it = root
+    while stack or it:
+        if it:
+            stack.append(it)
+            it = it.left
+        else:
+            it = stack.pop()
+            print(it.val)
+            i += 1
+            if i == n:
+                return it
+            it = it.right
+
+    return None
+
+if __name__ == "__main__":
+    root = Node(0)
+    tree_insert(root, 2)
+    tree_insert(root, 9)
+    tree_insert(root, 1)
+    tree_insert(root, 5)
+    tree_insert(root, 6)
+    tree_insert(root, 3)
+    tree_insert(root, 4)
+    tree_print(root)
+    print("4th node is {0}".format(bstget(root, 4).val))
+    print("4th node is {0}".format(bstget2(root, 4).val))
diff -r 000000000000 -r 20fea762903e graphs_trees/find_flag/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/find_flag/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,17 @@
+Find the Flag
+=============
+
+Given:
+
+.. code-block:: python 
+
+   def maze_has_flag(x, y): # x, y coordinates → bool
+       return x == 3 and y == 5 # for example
+
+   def maze_has_move(x1, y1, x2, y2): # can you move from point a to b → bool
+       return True # for example
+
+Write this function to find the flag in the maze and display the traversed
+coordinates::
+
+   maze_find_flag(size_x, size_y, start_x, start_y)
diff -r 000000000000 -r 20fea762903e graphs_trees/find_flag/solution.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/find_flag/solution.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,68 @@
+#!/usr/bin/env python
+
+# given:
+
+def maze_has_flag(x, y): # x, y coordinates → bool
+    return x == 3 and y == 5
+
+def maze_has_move(x1, y1, x2, y2): # can you move from point a to b → bool
+    return True
+
+# write this to find the flag in the maze and display the coordinates walked on
+# def maze_find_flag(size_x, size_y, start_x, start_y):
+
+class Node:
+    def __init__(self, x, y, visited):
+        self.x = x
+        self.y = y
+        self.visited = visited
+
+class Maze:
+    def __init__(self, size_x, size_y):
+        self._size_x = size_x
+        self._maze = [False] * (size_x * size_y)
+
+    def _get(self, x, y):
+        return self._maze[y * self._size_x + x]
+
+    def visit(self, x, y):
+        print("visiting {0}, {1}".format(x, y))
+        self._maze[y * self._size_x + x] = True
+
+    def up(self, node):
+        x = node.x
+        y = node.y + 1
+        return Node(x, y, self._get(x, y))
+
+    def down(self, node):
+        x = node.x
+        y = node.y - 1
+        return Node(x, y, self._get(x, y))
+
+    def left(self, node):
+        x = node.x - 1
+        y = node.y
+        return Node(x, y, self._get(x, y))
+
+    def right(self, node):
+        x = node.x + 1
+        y = node.y
+        return Node(x, y, self._get(x, y))
+
+def maze_find_flag(size_x, size_y, start_x, start_y):
+    maze = Maze(size_x, size_y)
+    queue = [Node(start_x, start_y, False)]
+
+    while queue:
+        cur = queue.pop()
+        maze.visit(cur.x, cur.y)
+        if maze_has_flag(cur.x, cur.y):
+            return True
+        adjacents = [
+            maze.up(cur), maze.down(cur), maze.left(cur), maze.right(cur)
+        ]
+        for node in filter(lambda n: not n.visited, adjacents):
+            if maze_has_move(cur.x, cur.y, node.x, node.y):
+                queue.insert(0, node)
+
+maze_find_flag(10, 10, 4, 4)
diff -r 000000000000 -r 20fea762903e graphs_trees/link_tree_levels/hints.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/link_tree_levels/hints.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,5 @@
+Hints
+=====
+
+- What kind of traversal should you do to solve this?
+- How do you do this kind of traversal?
diff -r 000000000000 -r 20fea762903e graphs_trees/link_tree_levels/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/link_tree_levels/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,21 @@
+Link Node at the Same Height in a Binary Tree
+=============================================
+
+Given a binary tree, turn each level of the tree into a linked list from left
+to right. The binary tree node already have a field for the reference/pointer
+to build the list.
+
+::
+
+                 1 -> NULL
+          2      ->      4 -> NULL
+     5   ->   6   ->   7 -> 8 -> NULL
+   9      ->    10    ->      11 -> NULL
+
+
+.. code-block:: python
+
+   class Node:
+     left = None
+     right = None
+     sibling = None
diff -r 000000000000 -r 20fea762903e graphs_trees/link_tree_levels/solution.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/link_tree_levels/solution.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,57 @@
+# NOTE: this is just a dump of my phone screen.
+
+               1 -> NULL
+       2      ->      4 -> NULL
+  5   ->   6   ->   7 -> 8 -> NULL
+9      ->    10    ->      11 -> NULL
+
+
+class Node:
+  left = None
+  right = None
+  sibling = None
+  
+# Fail…
+def link_right_sibling(root):
+  stack = []
+  
+  it = root
+  while it:
+    if stack:
+      it.sibling = stack[-1]
+    if it.right:
+      stack.append(it.right)
+    if it.left:
+      it = it.left
+    elif stack:
+      it = stack.pop()
+    else:
+      break
+      
+# Fail…
+def link_right_sibling(root, right=None):
+  if not root:
+    return
+  root.sibling = right
+  link_right_sibling(root.left, root.right)
+  link_right_sibling(root.right)
+  
+def link_right_sibling(root):
+  if not root:
+    return
+    
+  li = [root, None]
+  it = li.pop(0)
+  while it:
+    if li:
+      it.sibling = li[0]
+    if it.left:
+      li.append(it.left)
+    if it.right:
+      li.append(it.right)
+    if not li:
+      break
+    it = li.pop(0)
+    if it is None:
+      li.append(None)
+      it = li.pop(0)
diff -r 000000000000 -r 20fea762903e graphs_trees/next_smallest_integer_in_bst/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/next_smallest_integer_in_bst/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,5 @@
+Find the Next Smallest Integer in a BST
+=======================================
+
+Write the function ``next_smallest(root, n) → int`` that takes a binary search
+tree in parameter and return the biggest integer in the tree which is < n.
diff -r 000000000000 -r 20fea762903e graphs_trees/next_smallest_integer_in_bst/solution.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/next_smallest_integer_in_bst/solution.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,31 @@
+# NOTE: just a dump from the phone screen.
+
+class Node:
+  def __init__(self, val):
+     self.right = None
+     self.left = None
+     self.val = val
+
+# Not perfect, if the n is not in tree then the biggest element of the tree is
+# not returned.
+#
+# Or if the tree is just a root node, then it doesn't work (that edge case
+# could be solved with a separate function for the recursion).
+#
+# (Also actually untested, but looks like it works)
+     
+def next_smallest(root, n):
+  if root is None:
+    return
+
+  rv = next_smallest(root.left, n)
+  if rv is not None:
+    return rv
+  
+  if root.right == n:
+    return root.val
+
+  rv = next_smallest(root.right, n)
+  if rv is not None:
+    return rv
+  return None
diff -r 000000000000 -r 20fea762903e graphs_trees/wordpath/hints.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/wordpath/hints.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,6 @@
+Hints
+=====
+
+This is like a tree traversal.
+
+Each generated word is a node in the tree.
diff -r 000000000000 -r 20fea762903e graphs_trees/wordpath/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/wordpath/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,14 @@
+Wordpath
+========
+
+Write a function ``wordpath(word1, word2)`` that print all the permutations
+needed to go from word1 to word2.
+
+The only accepted permutation is to change a letter. Each generated word must
+be in the dictionary, and a ``is_in_dictionary(word) → bool`` function is
+provided.
+
+Twists
+------
+
+- What is the time complexity?
diff -r 000000000000 -r 20fea762903e graphs_trees/wordpath/solution.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graphs_trees/wordpath/solution.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,3 @@
+# I didn't write it, but this is an iterative breadth-first tree traversal
+# (i.e: you generate the words, enqueue them on a queue, dequeue from the queue
+# until it's empty or you found the second word).
diff -r 000000000000 -r 20fea762903e misc/choice/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/misc/choice/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,10 @@
+“Random” Choice
+===============
+
+Write a function that takes a list of weighted values and returns a random
+value according to its weigh:
+
+.. code-block:: python
+
+   # → 1/2 chances of returning c, 1/3 b, 1/6 a (saying this should help)
+   choice([("a", 1), ("b", 2), ("c", 3)])
diff -r 000000000000 -r 20fea762903e misc/draw_a_circle/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/misc/draw_a_circle/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,10 @@
+Circle
+======
+
+Given a function ``draw_pixel(x, y)`` draw a circle.
+
+.. note::
+
+   I didn't get this, but it seems to be asked at Valve and I think it's "fun".
+   There is many way to do this, and you should Google them once you tried your
+   own.
diff -r 000000000000 -r 20fea762903e misc/sqrt/hints.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/misc/sqrt/hints.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,4 @@
+Hints
+=====
+
+Bruteforce, then optimize.
diff -r 000000000000 -r 20fea762903e misc/sqrt/question.rst
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/misc/sqrt/question.rst	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,7 @@
+Sqrt
+====
+
+Recode the function ``sqrt(n, precision)`` which returns an approximation of
+the given precision of the square root of the given number.
+
+.. note:: Stéphane got this.
diff -r 000000000000 -r 20fea762903e misc/sqrt/solution.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/misc/sqrt/solution.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,30 @@
+#!/usr/bin/env python
+
+
+def sq(n):
+    return n * n
+
+
+def sqrt(n, precision):
+    pivot = n / 2.
+    left_halve = (0, pivot)
+    right_halve = (pivot, n)
+    while 1:
+        halve_size = left_halve[1] - left_halve[0]
+        if sq(left_halve[0]) <= n <= sq(left_halve[1]):
+            pivot = left_halve[0] + halve_size / 2.
+            if halve_size <= precision:
+                return pivot
+            left_halve = (left_halve[0], pivot)
+            right_halve = (pivot, left_halve[1])
+        else:
+            pivot = right_halve[0] + halve_size / 2.
+            if halve_size <= precision:
+                return pivot
+            left_halve = (right_halve[0], pivot)
+            right_halve = (pivot, right_halve[1])
+
+
+print(sqrt(42, 1))
+print(sqrt(4, 0.0011))
+print(sqrt(2422.423, 0.1))
diff -r 000000000000 -r 20fea762903e stacks_lists/fifo_from_two_lifos/fifo.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/stacks_lists/fifo_from_two_lifos/fifo.c	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,117 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+struct lifo
+{
+    struct lifo *next;
+    int         value;
+};
+
+struct fifo
+{
+    struct lifo *head;
+    struct lifo *tail;
+};
+
+void
+push(struct lifo **head, struct lifo *e)
+{
+    assert(e);
+
+    e->next = *head;
+    *head = e;
+}
+
+struct lifo *
+pop(struct lifo **head)
+{
+    assert(head);
+
+    if (!*head)
+        return NULL;
+    struct lifo *e = *head;
+    *head = e->next;
+    return e;
+}
+
+void
+print(struct lifo *head)
+{
+    for (; head; head = head->next)
+        printf("%d ", head->value);
+    printf("\n");
+}
+
+
+void
+enqueue(struct fifo *queue, int value)
+{
+    struct lifo *new_head = calloc(1, sizeof(*new_head));
+    new_head->value = value;
+    push(&queue->head, new_head);
+
+    struct lifo *new_tail = calloc(1, sizeof(*new_head));
+    new_tail->value = value;
+    if (!queue->tail) {
+        push(&queue->tail, new_tail);
+        return;
+    }
+    struct lifo *reversed = NULL;
+    for (struct lifo *it = pop(&queue->tail); it; it = pop(&queue->tail))
+        push(&reversed, it);
+    push(&reversed, new_tail);
+    for (struct lifo *it = pop(&reversed); it; it = pop(&reversed))
+        push(&queue->tail, it);
+}
+
+int
+dequeue(struct fifo *queue)
+{
+    assert(queue->tail);
+    assert(queue->head);
+
+    struct lifo *e;
+
+    if (queue->head == queue->tail)  {
+        e = queue->tail;
+        queue->tail = NULL;
+        free(queue->head);
+        queue->head = NULL;
+    } else {
+        e = pop(&queue->tail);
+        struct lifo *reversed = NULL;
+        for (struct lifo *it = pop(&queue->head); it; it = pop(&queue->head))
+            push(&reversed, it);
+        free(pop(&reversed));
+        for (struct lifo *it = pop(&reversed); it; it = pop(&reversed))
+            push(&queue->head, it);
+    }
+
+    int ret = e->value;
+    free(e);
+    return ret;
+}
+
+
+int
+main(void)
+{
+    struct fifo queue = { .head = NULL, .tail = NULL };
+
+    for (int i = 0; i != 5; i++)
+        enqueue(&queue, i);
+
+    print(queue.head);
+    print(queue.tail);
+
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+    enqueue(&queue, 42);
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+    printf("dequeue(&queue) = %d\n", dequeue(&queue));
+
+    return EXIT_SUCCESS;
+}
diff -r 000000000000 -r 20fea762903e stacks_lists/pancakes/pancakes.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/stacks_lists/pancakes/pancakes.py	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,62 @@
+#!/usr/bin/env python
+
+
+def flip_pancakes(pancakes, index):
+    print(
+        "{0} → flip at {1} ({2}) (biggest_sorted={3}, biggest_unsorted={4}) → ".format(
+            pancakes, index, pancakes[index], pancakes[find_biggest_sorted(pancakes)], pancakes[find_biggest_unsorted(pancakes)]
+        ),
+        end=""
+    )
+    for i in range(int((index + 1) / 2)):
+        tmp = pancakes[index - i]
+        pancakes[index - i] = pancakes[i]
+        pancakes[i] = tmp
+    print("{0}".format(pancakes))
+
+
+def is_sorted(pancakes):
+    for i in range(1, len(pancakes)):
+        if pancakes[i - 1] > pancakes[i]:
+            return False
+    return True
+
+
+def find_biggest(pancakes):
+    biggest = pancakes[0]
+    biggest_idx = 0
+    for i in range(1, len(pancakes)):
+        if pancakes[i] > biggest:
+            biggest = pancakes[i]
+            biggest_idx = i
+    return biggest_idx
+
+
+def find_biggest_sorted(pancakes):
+    for i in reversed(range(1, len(pancakes))):
+        if i != find_biggest(pancakes[:i + 1]):
+            return i
+    return 0
+
+
+def find_biggest_unsorted(pancakes):
+    biggest = pancakes[0]
+    biggest_idx = 0
+    for i in range(1, find_biggest_sorted(pancakes) + 1):
+        if pancakes[i] > biggest:
+            biggest = pancakes[i]
+            biggest_idx = i
+    return biggest_idx
+
+
+def sort_pancakes(pancakes):
+    while not is_sorted(pancakes):
+        biggest_unsorted = find_biggest_unsorted(pancakes)
+        flip_pancakes(pancakes, biggest_unsorted)
+        biggest_sorted = find_biggest_sorted(pancakes)
+        flip_pancakes(pancakes, biggest_sorted)
+        biggest_unsorted = find_biggest_unsorted(pancakes)
+
+
+if __name__ == "__main__":
+    sort_pancakes([7, 5, 4, 8, 2, 1])
diff -r 000000000000 -r 20fea762903e stacks_lists/remove_list_duplicates/remove_duplicates.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/stacks_lists/remove_list_duplicates/remove_duplicates.c	Sat Jun 29 19:30:31 2013 -0700
@@ -0,0 +1,73 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+struct list
+{
+    struct list *next;
+    struct list *prev;
+    int         value;
+};
+
+void
+print(struct list *head)
+{
+    for (; head; head = head->next)
+        printf("%d ", head->value);
+    printf("\n");
+};
+
+void
+insert(struct list **head, int value)
+{
+    struct list *node = malloc(sizeof(*node));
+    node->prev = NULL;
+    node->next = *head;
+    node->value = value;
+    if (*head)
+        (*head)->prev = node;
+    *head = node;
+}
+
+struct list *
+remove_node(struct list *node)
+{
+    assert(node);
+    node->prev->next = node->next;
+    if (node->next)
+        node->next->prev = node->prev;
+    struct list *next = node->next;
+    free(node);
+    return next;
+}
+
+void
+remove_duplicates(struct list *head)
+{
+    for (struct list *target = head; target; target = target->next) {
+        for (struct list *it = target->next; it;) {
+            if (it->value == target->value) {
+                it = remove_node(it);
+            } else {
+                it = it->next;
+            }
+        }
+    }
+}
+
+int
+main(void)
+{
+    struct list *head = NULL;
+
+    for (int i = 5; i != 0; i--)
+        insert(&head, i);
+    for (int i = 1; i <= 5; i++)
+        insert(&head, i);
+    
+    print(head);
+    remove_duplicates(head);
+    print(head);
+
+    return EXIT_SUCCESS;
+}