CareerCup

python

def multiplyList(input,pos,val):
    if pos == len(input):
        return 1
    retVal = multiplyList(input,pos+1,input[pos]*val)
    newretVal = retVal*input[pos]
    input[pos] = retVal*val 
    return newretVal

input = [2,3,1,4]
multiplyList(input,0,1)
print input

python

def combinations(sofar,phno,numpad):
    
    if phno == '' or phno is None: 
        print sofar
        return
    
    for dig in phno:
        options = numpad[int(dig)]
        for op in options:
            combinations(sofar+op,phno[1:],numpad)


numpad = {2: ["A", "B", "C"], 
3: ["D", "E", "F"], 
4: ["G", "H", "I"], 
5: ["J", "K", "L"], 
6: ["M", "N", "O"], 
7: ["P", "Q", "R", "S"], 
8: ["T", "U", "V"], 
9: ["W", "X", "Y", "Z"]};

combinations('','23',numpad)

Merging two lists at a time. The solution is O(N). Where N is the total number of elements.

def merge(l1,l2):
    len1 = len(l1)-1
    len2 = len(l2)-1
    #expand the l1 to the size of l1+l2
    l1.extend([None]*(len2+1))
    #Traverse in reverse.
    for index in range(len(l1))[::-1]: 
        if len1<0 or len2<0:
            break
        if l1[len1] >= l2[len2]:
            l1[index] = l1[len1]
            len1-=1
        else:
            l1[index] = l2[len2]
            len2-=1
        return l1

def sortList(lol):
    mainl = lol[0]
    for l in range(1,len(lol)):
        mainl = merge(mainl,lol[l])
    return mainl

input = [ [2, 5, 10], [25, 100, 105], [7, 56, 42]] 
print sortList(input)

Python

def OneEditApartImpl(big,small,limit,lag):
    hit = 0  
    for index, letters in enumerate(zip(big,small)):
        if letters[0]!=letters[1]:
            hit+=1
            if hit > limit:
                return False     
            return OneEditApartImpl (big[index+1:],small[index+1-lag:],0,0)
    return True       

def OneEditApart(word1,word2):
    len1 = len(word1)
    len2 = len(word2)
    
    #trival: lenght greater than 1
    if abs(len1 - len2) > 1:
        return False
    
    #trival: string are equal 
    if word1 == word2:
        return True
    
    #non trial cases
    if(len1==len2):
        return OneEditApartImpl(word1,word2,1,0)
    elif(len1>len2):
        return OneEditApartImpl(word1,word2,1,1)
    else:
        return OneEditApartImpl(word2,word1,1,1)
        

assert OneEditApart("cat", "dog") == False 
assert OneEditApart("cat", "cats") == True 
assert OneEditApart("cat", "cut") == True 
assert OneEditApart("cat", "cast") == True 
assert OneEditApart("cat", "at") == True 
assert OneEditApart("cat", "acts") == False

Think in terms of a substitution cipher. String1 is the input, we apply a cipher and we get the string2. The problem is can we find a substitution cipher or in other words, are the strings isomorphic.

To check if two stings are isomorphic, one would not have keep counts. Below O(1) space implementation(bitVector implementation) that works for alphabets.

public class Isomorphic {

    public boolean isIsomorphic(String word1, String word2){
        long bitMap1 = 0;
        long bitMap2 = 0;
        long mask1 = 0;
        long mask2 = 0;
        for (int i=0;i<word1.length();i++){
            long res1,res2;
            
            //left shift 1, the ascii value amount of times 
            mask1 = 1 << (int)(word1.charAt(i));
            mask2 = 1 << (int)(word2.charAt(i));

            //XOR the mask
            res1 = bitMap1 ^ mask1 ;
            res2 = bitMap2 ^ mask2 ;
            
            //either both have to be 0 or both have to be non-zero
            if((res1>0 && res2>0) || (res1==0&& res2==0)){
                bitMap1|= mask1;
                bitMap2|= mask2;
                continue;
            }
            return false;
        }
        return true;
    }
}

@Ramesh N: Good solutions to a subtly tricky problem.

The code prints all forms without duplicates. This question (solution) is in "Cracking the coding interview" Book.

def paren(left,right,string):
    if(left == 0 and right == 0):
        print string
    if(left>right):
        return
    if (left > 0):
        paren(left-1,right,string+"(")
    if (right > 0):
        paren(left,right-1,string+")")

def parentheses(n):
    paren(n/2,n/2,"")

parentheses(6)

output:
((()))
(()())
(())()
()(())
()()()

I have a similar implementation as yours in the same thread.(in python as well). The thing is you have a string "==" inside the loop. "==" is an operation that takes O(M), where m is the size of the smaller string. The program takes O(N*M). To avoid that "==" I had to use a dictionary.

The Algorithm will take O(N) time and O(Constant) space. Python.

def reArrange(elements):
    elementCount = len(elements)
    for i in range(0,elementCount)[::2]:
        #subList will have atmost 3 elements
        subList = (elements[i:i+3]) 
        
        if(len(subList)>1):
            #again subList is atmost 3 elements long. 
            #sorting 3 elements is a  constant time operation.
            subList= sorted(subList)
            #If the sublist has 3 elements then swap the last two
            if(len(subList)>2): 
                temp = subList[-1]
                subList[-1] = subList[-2]
                subList[-2] = temp
            #copy subList back to the element list
            for index in range(0,len(subList)):
                elements[i+index] = subList[index]
    return elements

print reArrange([10,3,4,5,6,7,1,2,9,8])

#output: 3, 10, 4, 6, 1, 7, 2, 9, 5, 8

Here we build the hash with all the suffixes of the longer string. Only the keys are truncated to the size of smaller string. Time Complexity O(N) with a hash ofcourse. Written in Python.

def isSubString(mainString,subString):
    subStrLen = len(subString)
    #hash
    suffixHash = {}
    for i in range(0,len(mainString)):
        key = mainString[i:i+subStrLen] 
        suffixHash[key] = True

    print suffixHash.keys() 

    if subString in suffixHash:
        print "True"
    else:
        print "False"

isSubString("hellothisiscool", "isi")

The program is not linear. "Equals" takes O(n) inside the while loop.