Microsoft Interview Question for Software Engineer / Developers
- 1of 1 vote
Given n rows of integers, such that the ith row (1 <= i <= n) contains i integers, find the path having the maximum weight.- ramdomain October 29, 2014 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.
No. of Rows: 5
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
Interview Type: Phone Interview
Open Chat in New Window