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