Tuesday, May 7, 2013

Interview Question

Problem:

For a given pyramid find out the largest possible sum of numbers while travelling down from the top.

========================================================================

EXAMPLE 1:


1

2 3

4 5 6


The possible routes going down on this pyramid would be

1+2+4

1+2+5

1+3+5

1+3+6


ANS: 10

========================================================================

EXAMPLE 2:


1

2 3

4 5 6

7 8 9 1


The possible routes going down on this pyramid would be

1+2+4+7

1+2+4+8

1+2+5+8

1+2+5+9

1+3+5+8

1+3+5+9

1+3+6+9

1+3+6+1


ANS: 19

Solution in Python:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def findMaxHeight(items,pyramidHeight):
    '''
    This def returns the greatest path.
    Logic:  From second last line for each element find if its left or right child is greatest.
            Replace that element with sum of that element and the greatest child.
            In the end we'll have replace the pyramid with sum of greatest element.
            The only remaining element at [0][0] is the answer
    '''
    
    i = pyramidHeight - 2
    while i >= 0:
        j = 0
        while j <= i:
            greaterPath = items[i+1][j] if items[i+1][j] > items[i+1][j+1] else items[i+1][j+1]
            items[i][j] = items[i][j] + greaterPath
            j = j + 1
        i = i - 1
    
    return items[0][0]
        


def readDataFromFile(fileName):
    items = []
    pyramidHeight = 0
    i = 0
    firstLine = True
    for line in open(fileName):
        line = line.splitlines()[0]
        if firstLine:
            firstLine = False
            pyramidHeight = int(line)
            continue
        #create 2d list
        items.append([])
        #splits each line by "," and converts it to int and generates another list
        items[i] = [int(x) for x in line.split(",")]
        i = i + 1
        
    if pyramidHeight != i:
        print "Houston, We've Got a Problem\nPyramid height specified in file doesn't match"
        assert False
        
    return items,pyramidHeight
    

print "Greatest path for pyramid 1 is %s" % findMaxHeight(*readDataFromFile("pyramid1.txt"))
print "Greatest path for pyramid 2 is %s" % findMaxHeight(*readDataFromFile("pyramid2.txt"))

0 comments:

Post a Comment

Comments are moderated. No spam please.