ramdomain
BAN USER
Questions (1)
Comments (2)
Reputation 70
- 1of 1 vote
AnswersGiven n rows of integers, such that the ith row (1 <= i <= n) contains i integers, find the path having the maximum weight.
- ramdomain in India
Path traversal rules:
1. A valid path sequence would be top-down i.e. begins with the integer in the first row, and traverses all rows selecting only one integer in each row.
2. From any jth integer in the ith row i.e row[i][j], traversal can happen either downward (i.e to row[i+1][j]) or diagonally downward to the right (i.e to row[i+1][j+1])
The weight of a Path is the sum of values of integers in the Path sequence.
Sample Input:
No. of Rows: 5
4
2 9
15 1 3
16 92 41 44
8 142 6 4 8
Expected Output: 4, 2, 15, 92, 142 (Max weight is 255)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Solution using DP in Python. O(n^2).
- ramdomain October 29, 2014