Mercurial > louis > peeves
changeset 0:20fea762903e
Import some exercises and solutions
line wrap: on
line diff
--- /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/.
--- /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.
--- /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.
--- /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.
--- /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; +}
--- /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").
--- /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
--- /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.
--- /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')
--- /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.
--- /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.
--- /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))
--- /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.
--- /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)))
--- /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.
--- /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; +}
--- /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.
--- /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).
--- /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.
--- /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)))
--- /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.
--- /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.
--- /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:].
--- /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].
--- /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"))
--- /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']
--- /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.
--- /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.
--- /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))
--- /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)
--- /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)
--- /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?
--- /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
--- /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)
--- /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.
--- /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
--- /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.
--- /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?
--- /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).
--- /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)])
--- /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.
--- /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.
--- /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.
--- /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))
--- /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; +}
--- /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])
--- /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; +}