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)

Printing all possible combinations of brackets

Write a function Brackets(int n) that prints all combinations of well-formed brackets. For Brackets(3) the output would be

((())) (()()) (())() ()(()) ()()()

def brackets(n):
        if n == 2:
                return ["()"]
        else:
                L = []
                for b in brackets(n-2):
                        L.append( "(" + b + ")" )
                        L.append( "()" + b )
                        if not b.find ( "((" ):
                                L.append( b + "()" )
                return L

print brackets(2)
print brackets(6)

Print all possible variations of a password

An iterative version that has been implemented and tested:

def variations(str, char_variations):
        result = []
        for i in range(0,len(str)):
                tmp_result = []
                c = str[i]
                vars = char_variations.get(c)
                if vars is None:
                        vars = []
                vars = vars + [c]

                if len(result) > 0:
                        for partial_r in result:
                                for v in vars:
                                        tmp_result.append(partial_r + v)
                else:
                        for v in vars:
                                tmp_result.append(v)

                result = tmp_result

        return result


char_variations = { 'a': ['0','o'] , 'l': ['1' , 'I'] }

print variations ('allo' , char_variations)

An here is a recursive version that has been implemented and tested

def variations(str,char_variations):
        if len(str) == 0:
                return []

        c = str[0]
        vars = char_variations.get(c)

        if len(str) == 1:
             if vars:
                  return vars
             else:
                  return [c]

        if vars is None:
                vars = []
        vars = vars + [c]
        

        subL = variations (str, char_variations)
        L = []

        for l in subL:
                 for v in vars:
                        L += [ v + l ]
        
        return L

char_variations = { 'a': ['0','o'] , 'l': ['1' , 'I'] }

print map ( str , variations (list ('allo') , char_variations) )

Binary search and array rotation

The following solution has been implemented and verified:

def binsearch(arr, val, start, end):
    if start == end and arr[start] <> val:
       return -1
    index = (end+start)/2
    if val == arr[index]:
       return index
    elif val < arr[index]:
       return binsearch(arr, val, start , index)
    elif val > arr[index]:
       return binsearch(arr, val, index , end)

arr = range(1,8)
print arr
print binsearch ( arr , 3, 0, len(arr) )
print binsearch ( arr , 7, 0, len(arr) )

Additionnal question:
The array was rotated. How would search in it?

Answer, find the index of max value, iMax and in the previous function, replace

    index = (end+start)/2

by

    index = (iMax + (end+start)/2) % len(arr)

Print out all combinations of k numbers out of 1...N

e.g. when k = 2, n = 4
Print out 12, 13, 14, 23, 24, 34

def combi (k,arr):
        if k == 1:
                return [[i] for i in arr]
        elif k == 0 or len(arr) == 0:
                return []

        L = []
        for i in range (0,len(arr)):
                arr2 = arr[:]
                arr2.remove(arr[i])
                for v in  combi (k-1 , arr2):
                        L.append( [arr[i]] + v )

        return L

print combi ( 2 , range(1,4) ) 
 

One limitation with this function is that it returns 14 but also 41
The following code solves this problem

def combi2 (k,arr):
        if k == 1:
                return [[i] for i in arr]
        elif k == 0 or len(arr) == 0:
                return []

        L = []
        arr2 = arr[:]
        while len(arr2) > 0:
                val = arr2.pop(0)

                for v in  combi (k-1 , arr2):
                        L.append( [val] + v )

        return L

Given two events, each with a start and end time, implement a boolean check to see if they overlap

if t1.start < t2.end and t2.start < t1.end
    return true
else
    return false

Lowest common ancestor

// Lowest common ancestor in an unordered binary tree given two values
// Not a binary search tree. Unordered binary tree.
// Find the lowest common ancestor of the two nodes represented by val1 and val2
// No Guarantee that val1 and val2 exist in tree. If one value doesn't exist in the tree return NULL.
// There are NO duplicate values
// You can use extra memory, helper functions. You can modify the node struct but you can't add a parent pointer.
// You have to beat O(N*N) for a solution. Where N is the number of the nodes in the tree.

Answer
A = List of the ancestors of A (see function below)
B = List of the ancestors of B
compare A and B

Complexity = O(N+N+N) = O(N) [see note below to reduce complexity]

def ancestor(tree,val):
  if tree.left and tree.left.val == val:
         return [tree]
  elif tree.right and tree.right.val == val:
         return [tree]
  else:
     if tree.left:
       l_ancestors = ancestor(tree.left,val)
       if len(l_ancestors) > 0:
          return [tree] + l_ancestors
     if tree.right:
       r_ancestors = ancestor(tree.right,val)
       if len(r_ancestors) > 0:
          return [tree] + r_ancestors
     return []  

Note: if we had been using a balanced, the maximum number of ancestors would have been log(N)-1 instead of N. Thus, the overall complexity would have been O(log(N))

Find the first letter in a string that does not have a pair.

first_positions = zeroes (26)
nb_occs = zeroes (26)
for in range (0,len(s)):
    index = s[i] - '0'
    if nb_occs[index] == 0
       first_positions[index] = i
       nb_occs[index] += 1

then simply iterate on nb_occs and return minimum corresponding value in first_positions where nb_occs == 1

Given a set of characters, print out all possible permutations.

take out one element of the list at a time
generate a new list with that element and the permutations of the list except that element (recursive), return the new list

perm(l) 
        if len(l) = 0:
                return []
        elif len(l) == 1:
                return [l]
        else
                P = []
                for e in l:
                        v = l\e
                        P.add ( [e] + perm(v) )
                        return P  

Given a binary tree, print out the elements in order. Without recursion.

L = [node]
do{
        nextLevel=[]
        while L is not empty:
                n = pop(L)
                print n.val
                if n.left 
                        nextLevel.add(n.left)
                if n.right
                        nextLevel.add(n.right)
        L=nextLevel 
} while (nextLevel is not empty)

Count the nb of bits in an integer

General idea: shr bits one by one and see if the dropped bit was 0 or 1

total_b = 0
x = y
while (x > 0)
x = y >> 1 # shift one bit to the right
b = 0
if (y - 2*x == 0)
b = 0
else
b = 1
if b = 1
total_b++

Extract common elements btw two arrays

solution 1: pretty bad
complexity: O(sA x sB)
worst case: j goes to sB j goes to sB again... sAxsB
best case: sA

A, B


for i = 0 ; i < size(A); i++)
for j = 0 ; j < size(B) ; j++)
if Ai = Bi
print Ai
break

solution 2: sort the arrays first Note on sorting: * quicksort avergage complexity is O(Nxlog(N)), worst case is O(NxN) * heapsort is more interesting because it's worstcase complexity is also O(Nxlog(N))

minA, minB = 0
while (minA < sA and minB < sB)
if A[minA] < A[minB]
minA++
elif A[minA] > B[minB]
minB++
else
print A[minA]
minA++
minB++

Generate all possible words from a number and a phone keyboard

Each key on the telephone represents a list of letters. Given a telephone number, please write a program to output all the possible strings the telephone number represents.

E.g.
phone number has 8 digits
every key has 3 letters
nb of possible strings: 3^8

recursive approach:

// n = list of digits
// get_letters return a list of characters associated to a given digit (actually returns a list of singleton lists)
rec (n)
        if n = []
                return []
        else
                letters = get_letters(n[0])
                res = []
                for l in letters:
                        res.append( 
               l.extend(rec ( right-hand_side (n) ) ) )
                return res

Check if a graph is bipartite

setA
setB
bipa = True
for e in edges
        if e0 in setA
                if e1 in setB
                       continue
                elif e1 in setA
                       bipa = False
                       break
                else
                       put e1 in setB

        elif e0 in setB
                if e1 in setA
                       continue
                elif e1 in setB
                       bipa = False
                       break
                else
                       put e1 in setA

        else
                if e1 in setA
                      put e0 in setB
                elif e1 in setB
                      put e0 in setA
                else
                      put e0 in setA
                      put e1 in setB

Given two binary trees, return true if they have same elements (irrespective of tree structure)

We need to traverse the trees and compare their elements.
We could traverse each tree and store each of their different elements in two arrays. Then we sort the array and verify that they are identical.

Question/Assumption: What about the frequency of items? With the previous approach we do not take into account the fact that some items may be repeated a different nb of times

Given a string, remove all chars from the string that are present in say another string called filter

solution 1: advantage is that we do not duplicate the string
k = 0
while s[i] <> 0
        found = 0
        for j = 0 ; j < sFilter ; j++
                if s[i] == filter[j]
                        found = 1
                        break
        if ! found
                s[k++] = s[i]
        i++
s[k] = 0   

Print nodes in a tree

       1
      / \
     2   3
    / \   \
   4   5   6
      /
     7
     
1234567

or 

1
23
456
7

Solution:

# recursive version
def print_tree(L):
        newL = []
        for n in L:
                print n
                if n.left <> None:
                        newL.append(n.left)
                if n.right <> None:
                        newL.append(n.right)
        print_tree(newL)
        print "\n"

Comment: we should use a queue structure and replace the loop with bottom() and the append with top() in order to avoid to have to create a list at each iteration

# iterative version
L = [n]
while (len(L)>0):
        newL = []
        for n in L:
                print n
                if n.left <> None:
                        newL.append(n.left)
                if n.right <> None:
                        newL.append(n.right)
        print "\n"
        L = newL

Count words in a string

def count_words(s):
        nb_words = 0
        in_word = 0
        i = 0
        while s[i] <> 0:
                if s[i] <> ' ':
                        if in_word:
                                i++
                        else:
                                nb_words++
                                in_word = 1
                else:
                        in_word = 0
                        i++

Get all combinations of 3 elements of an array of ints and print those that sum to 0

// input an array of ints [1, 2, 3, 4, 5, -6]
// print = output all 3-tuples that sum to zero (1, 5, -6) (2, 4, -6)

FIRST WE ASSUME that ints are all DIFFERENT
combi(n,s):

for i = 0 ; i < n ; i++
        for j = i+1 ; j < n ; j++
                for k = j+1 ; k < n ; k++
                        if s[i]+s[j]+s[k] == 0
                                print i,j,k



SECOND WE ASSUME THat the ints are SORTED

for i = 0 ; i < n ; i++
        for j = i+1 ; j < n ; j++
                for k = j+1 ; k < n ; k++
                        if s[i]+s[j]+s[k] == 0:
                                print i,j,k
                        elif s[i]+s[j]+s[k] > 0:
                                break

Find the longest upsequence in a string

def longuest_upsequence(s):
        lg_start_index = 0
        lg_size = 1
        current_size = 0
        current_index = 0
        for i in range (0 , len(s) - 1):
                if s[i] < s[i+1]:
                        if current_size > lg_size:
                                lg_start_index = current_index
                                lg_size = current_size
                        curent_index = i
                        current_size = 1
                else:
                        current_size++

Check is string a is prefix of string b

def prefix (a, b):
        i=0
        while a[i] <> 0
                if b[i] == 0:
                        return false
                if a[i]<>b[i]:
                        return false
        return true

prefix ('' , 'f') = 1
prefix ('f', '') = 1
perfix ('f','fg') = 1

Reverse a list

def reverse(n):
        previous = n
        current = n.next

        while current:
                next = current.next
                current.next = previous
                previous = current
                current = next
        return current

Merge two sorted array

Question is:

Let's say that we have two arrays A[1...n] and B[1...2n]:
- the first n elements of both arrays are sorted in ascending order
- the last n elements of B are empty

can you write some pseudo code to put all elements in a globally sorted order?


Solution:
General idea: start from the end of the array

        i = n-1
        j = i
        k = 2n - 1
        while ( k )
                if i == 0
                       B[k--] = A[j]
                       j--
                elsif j == 0
                       B[k--] = B[i]
                       i--
                elsif (B[i] < A[j])
                       B[k--] = A[j]
                       j--
                elsif A[j] =< B[i]
                       B[k--] = B[i]
                       i--
     

Implement division without using * / %

I'll start by implementing multiplication to warm up

The first function relies on binary operation (shr and shl). It is way too complex but it is the first one I came up with. It looks ok but I haven't checked it. The second one is what I should have come up with at first.

def multiply (n,p)
        r = 0
        while p
                p2 = shr (p)
                if (p == 2*p + 1)
                        r += n
                n = shl(n)
                p = p2
        return r

def multiply2 (n,p)
        r = 0
        for k = 0 ; k < p k++
                r += n
        return r

Now for division, we understand that it will be almost as easy as multiply2.
General idea: we need to find q so that n = pq+r with r < p

Extract the N largest floating point numbers from a large file of floating point numbers

General idea; We use a sorted list to store the N largest numbers and we insert new items as we go. If we need to insert and the list size has reached N, we also delete the lowest value

Lsize=0
while f in stream:
        if L = None
                L = new List
                L.val = f
                L.next = NULL
                Lsize++
        elsif L.val >= f
                continue
        else // L.val < f
                current = L
                while current
                        if current.val > f:
                                next = current.val.next
                                current.next = new List
                                current.next.next = next
                                current.next.val = f
                                if Lsize = N
                                        L = L.next
                        current = current.next    

Given a list of integers, some of which may be negative, extract the pair that sums to the largest number.

a = t[0]
b = t[1]
max = a + b
for i in range(1,len(t))
        ta = t[i]
        for j in range(i+1,len(t))
                tb = t[j]
                if ta + tb > max
                        a = ta
                        b = tb

print a,b

Implement stack using a queue

General idea: in order to pop an element, we need to extract all the elements and insert them at the beginning of the queue execpt for the last one that needs to be returned. push is easy, simply add to the top if the queue is not filled up.

Here is the pseudo-code for the push function:

K = queue actual size of the queue
N = max queue size
for i = K ; i < N ; i++
     q.top(None)
for i = 0 ; i < K - 1 ; i++
     q.bottom (q.bottom())
return q.bottom()

Generate all anagrams of a string

def perm(t):
       if len(t) == 0:
               return []
       if len(t) == 1:
               return [t]
       else:
               L = []
               for i in range (0, len(t)):
                       selected_c = [t[i]]
                       subL = []
                       for j in range (0,i):
                               subL.append(t[j])
                       for j in range (i+1,len(t)):
                               subL.append(t[j])
                       V = perm(subL)
                       for s in perm(subL):
                               L.append(selected_c + s)
               return L

print map ( "".join , perm (list("ANNA")))
  

As usual other solutions to this problem exist