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