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

## Comments

## Post a Comment

Comments are moderated. No spam please.