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")

Find subsequence with the maximum sum

[1, -2, 3, 5, 7] => [3,5,7]
[4, -2, 5] => [5]
[5, -6, 1, 2, 3, 4] => [1,2,3,4]

Solution:

def max_sum_subseq(arr):
    max_sum = 0
    max_start_index = 0
    max_length = 0
    current_sum = 0
    current_start_index = 0
    
    for i in range (0,len(arr)):
        if current_sum == 0 and arr[i] > 0:
             current_start_index = i
             
        current_sum += arr[i]
        if current_sum <= 0:
              current_sum = 0
              continue
       
        if current_sum >= max_sum:
            max_sum = current_sum
            max_length = i - current_start_index + 1
            max_start_index = current_start_index

Find longest ascending series (not same as upsequence problem)

Given a sequence of distinct integers, remove as few elements as possible so that the remaining sequence appears sorted in ascending order.

Example:

1 2 3 8 10 5 6 7 12 9 11 4 0
1 2 3      5 6 7    9 11

Brute force solution:

def arrangements(k,arr):
        if len(arr) == 1:
                return [arr]
        if k == 1:
                return [ [i] for i in arr ]
        else:
                L=[]
                for i in arr:
                        iarr = arr[:]
                        iarr.remove(i)
                        for v in arrangement (k-1,iarr):
                                L.append ( [i] + v )
                return L

def is_ascending(arr):
        res = True
        for i in range(0,len(arr)-1):
                if arr[i] > arr[i+1]:
                        res = False
                        break
        return res

def longest_ascending(arr):
        max_arg = None
        max_size = 0
        for k in range (1,len(arr)):
                argts = arrangements (k,arr)
                for a in argts:
                        if is_ascending(a) and len(a) > max_size:
                                max_size = len(a)
                                max_arg = a

        return max_arg

Depth of binary search tree without using recursion

Write a program to find depth of binary search tree without using recursion

def depth(tree):
   max_depth = 0
   todo = [[tree,0]]
   while len(todo) > 0:
      node,depth = todo.pop(0)
      if not node.left and not node.right:
         if depth > max_depth:
           max_depth = depth
      if node.left:
         todo.push([node.left,depth+1])         
      if node.right:
         todo.push([node.right,depth+1])         

Number of zeroes in factorial of a number

Write a function that returns the number of zeros contained in the factorial of the number that is passed to it.

Ok, so the easy solution is to calculate factorial and then count the nb of zeroes. But we cannot have very large number.
Our solution is to divide the number as we compute it by ten when it's possible and increment the counter:

count = 0
def zeroes(n):
        global count
        if n == 1:
                return 1
        else:
                v = n * zeroes(n-1)
                if v % 10 == 0:
                        print v
                        v /= 10
                        count += 1
                return v

print zeroes (100)
print count

import math
print math.factorial(100)