List prime factors and decompose a num into prime factors

def prime_factors(n):
  """ List all prime numbers up to n """
  prims = []
  for i in range (2, n):
    is_prim = True
    for p in prims:
      if i % p == 0:
        is_prim = False
        break
    if is_prim:
      prims.append(i)

  return prims

def decompose_prime_factors(n):
  """ Decompose a number into prime numbers """
  prims = prime_factors(n)
  powers = [0 for i in range(len(prims))]
  while n > 1:
    for i in range(len(prims)):
      p = prims[i]
      if n % p == 0:
        n /= p
        powers[i] += 1
        break

  return [prims, powers]



if __name__ == '__main__':
  print prime_factors(100)
  print decompose_prime_factors(100)

Implement mergesort and quicksort

def mergesort(arr):

  if len(arr) == 0:
    return []

  if len(arr) == 1:
    return arr

  p = int(len(arr) / 2)
  L = arr[0:p]
  R = arr[p:]

  L = mergesort(L)
  R = mergesort(R)

  i = 0
  j = 0
  M = []

  # Merge the sorted lists
  while i < len(L) or j < len(R):
    if i == len(L):
      M.append(R[j])
      j += 1
    elif j == len(R):
      M.append(L[i])
      i += 1
    elif L[i] < R[j]:
      M.append(L[i])
      i += 1
    else:
      M.append(R[j])
      j += 1

  return M

def quicksort(arr):
  """ This is the simple version. There is also an in-place version
  which does not need an extra storage space """

  if len(arr) == 0:
    return []

  if len(arr) == 1:
    return arr

  # First partition the arr, take last value as pivot
  p = arr[-1]
  L = []
  R = []
  for i in range(len(arr) - 1):
    if arr[i] < p:
      L.append(arr[i])
    else:
      R.append(arr[i])

  # Then recursively sort the left and righ portions
  sortedL = quicksort(L)
  sortedR = quicksort(R)
  new_arr = []
  new_arr.extend(sortedL)
  new_arr.append(p)
  new_arr.extend(sortedR)
  return new_arr

if __name__ == '__main__':
  arr = [10, 34, 2, 43, 5, 100, 12]
  print "QUICK SORT OF ", arr
  print quicksort(arr)
  print "MERGE SORT OF ", arr
  print mergesort(arr)

Implement a trie

class Node:
  value = None
  final = None
  children = None

  def __init__(self, val, final):
    self.value = val
    self.final = final
    self.children = []

class Trie:
  def __init__(self):
    self.root = Node(None, True)

  def search(self, word):
    current_node = self.root
    i = 0

    while len(current_node.children) > 0 and i < len(word):
      found = False
      for child in current_node.children:
        if child.value == word[i]:
          if child.final and i == len(word) - 1:
            return True
          else:
            current_node = child
            i += 1
            found = True
            break
      if not found:
        break

    return False

  def insert(self, word):
    """ Returns true if the word was added and false if the word was
    already there """
    current_node = self.root
    i = 0

    cont = True
    while cont:
      cont = False
      for child in current_node.children:
        if child.value == word[i]:
          if child.final and i == len(word) - 1:
            return False
          else:
            current_node = child
            i += 1
            cont = True
            break

    inserted = False
    while i < len(word):
      if i == len(word) - 1:
        final = True
      else:
        final = False
      new_node = Node(word[i], final)
      current_node.children.append(new_node)
      current_node = new_node
      i += 1
      inserted = True

    return inserted


if __name__ == '__main__':
  trie = Trie()
  print "insert this, is new?", trie.insert("this")
  print "insert that, is new?", trie.insert("that")
  print "insert this, is new?", trie.insert("this")
  print "insert to, is new?", trie.insert("to")
  print "insert tone, is new?", trie.insert("tone")

  print "has this:", trie.search("this")
  print "has to:", trie.search("to")
  print "has tox:", trie.search("tox")
  print "has at:", trie.search("at")