Training Python

I use this repository to Data structures, algorithms and my solutions to programming puzzles.

Data structures

Strings and arrays

• Dynamic array class
• Test for all unique chars
• Test for all unique chars in place
• Reverse string
• Remove duplicate chars
• Check two strings for being anagrams
• String replace
• Reverse words
• Rotate NxN matrix in place
• Set column and row to zero if cell in matrix is zero
• Check if string is rotation of another

Linked lists

• List class
• Remove duplicates
• Find nth last element
• Remove node given only its object
• Sum linked lists with one digit per node
• Find beginning of circle

Stacks and queues

• Stack class
• Queue class
• Three stacks using a single array
• Stack that finds min in O(1)
• Large stack using sub stacks, allowing pop on main and sub stacks
• Solve Hanoi towers using stacks
• Queue by using two stacks
• Sort stack using only push, pop, peek and empty

Trees and graphs

• Heap class
• Binary search tree class
• Red black tree class
• B+ tree class
• Trie class
• Undirected graph class
• Traverse a tree in depth first order
• Traverse a tree in breadth first order using a queue
• Traverse a tree in order using constant space
• Directed graph class
• Check if tree is balanced
• Check if two nodes are connected in directed graph
• Create balanced binary tree from sorted array
• Get list of all nodes of depth n in a binary search tree
• Find successor in a binary search tree with parent pointers
• Find first common ancestor of two nodes in an unordered binary tree
• Given two large trees, check if the first is a subtree of the second
• Find all sub paths in a binary tree that sum up to x

Hashmaps and sets

• Hashmap class
• Hashset class

Algorithms

Bit manipulation

• Create bit range
• Copy bit range
• String to float, printing error when loosing data
• Print next smaller and larger numbers with same amount of set bits
• Count different bits of two numbers
• Swap every second bit with its predecessor
• Find missing number from array of consecutive integers with just
  comparing single bits
• Murmur hash

Recursion

• Count paths on grid with obstacles from top left to bottom right
• Find all permutations of a string
• Find all sub sets of a set
• Find all proper combinations of n parentheses
• Bucket fill
• Count representations of a price with coins of 25, 10, 5 and 1
• Find all chess boards with 8 queens so that they don't intersect

Sorting and searching

• Bucket sort
• Quick sort
• Merge sort
• Merge sorted arrays where the first has empty buffer at the end to hold
  the second
• Order array so that anagrams are next to each other
• Find in array that is sorted but has many empty elements in between
• Find in matrix where each column and row is sorted
• Given pairs of height and weight, compute larges tower where above is
  always both shorter and lighter

Mathematical

• Of a telephone number find all letter representations from the dial pad
• Given n vertex polygon, compute probability of collision of n randomly
  headed walkers starting at the edges
• Subtraction, multiplication and division using plus operator
  and control flow statements
• Find nth smallest number with only prime factors 3, 5 and 7
• Count occurences of given digit in all numbers up to n

Graphics

• Draw animated sine wave in console

Memory limits

• Read and write file
• External merge sort
• A bloom filter
• Find integer that is not contained in a text file of 4 billion numbers

Concepts

Object oriented Design

• Design data structures for generic deck of cards
• Design a musical juke box
• Design a chess game
• Design data structures for online book reader system
• A jigsaw puzzle and solve it

System design

• Thread pool
• Data structure for large friend network
• Design web crawler and avoid infinite loops
• Write chat server and client