Amazon Interview Question
Software Engineer / DevelopersCountry: United States
how about this one?
#include <iostream>
#include <vector>
using namespace std;
int minsum(vector<vector<int>> &nums){
int n=nums.size();
if(n==0) return -1;
for(int i=1;i<n;i++){
for(int j=0;j<nums[i].size();j++){
// fom top to middle
if(nums[i].size()>nums[i-1].size()){
if(j-1>=0&&j<nums[i-1].size()){
nums[i][j]+= min(nums[i-1][j-1],nums[i-1][j]);
}else if(j==0){
nums[i][j]+=nums[i-1][j];
}else{
nums[i][j]+=nums[i-1][j-1];
}// from mid to bottom
}else{
nums[i][j]+=min(nums[i-1][j],nums[i-1][j+1]);
}
}
}
return nums[n-1][0];
}
/*
[
[2],
[3,4],
[6,5,7],
[4,1,8,3],
[2,5,4],
[6,4],
[1]
]
*/
int main() {
vector<vector<int>> nums={{2},{3,4},{6,5,7},{4,1,8,3},{2,5,4},{6,4},{1}};
cout<<minsum(nums);
/*for(auto num:minsum(nums)){
for(auto n:num)
cout<<n<<" ";
cout<<endl;
}*/
//cout<<"Hello";
return 0;
}
public class MinPath {
public static void main(String[] s){
ArrayList<Integer[]> a = new ArrayList<>();
a.add(new Integer[]{2});
a.add(new Integer[]{3, 4});
a.add(new Integer[]{6 , 5, 7});
a.add(new Integer[]{4, 1, 8, 3});
a.add(new Integer[]{2, 5, 4});
a.add(new Integer[]{6, 4});
a.add(new Integer[]{1});
int minPath = 0;
Iterator iterator = a.iterator();
while (iterator.hasNext()){
Integer[] currentTemp = (Integer[]) iterator.next();
Arrays.sort(currentTemp);
minPath += currentTemp[0];
}
System.out.println(minPath);
}
}
import sys
def mps(a, n, i, j):
if (n-i is 0) or (j >= len(a[i])) or (j < 0):
return sys.maxint
if n-i is 1 and j < len(a[i]):
return a[i][j]
return a[i][j] + min(
mps(a, n, i+1, j-1),
mps(a, n, i+1, j),
mps(a, n, i+1, j+1)
)
print mps([[2],[3,4],[6,5,7],[4,1,8,3],[2,5,4],[6,4],[1]], 7, 0, 0)
print mps([[5],[3,4],[1]], 3, 0, 0)
Interesting problem, this can be solved by transposing to the minimum path problem. Transform your given input array to the following 2-D matrix:
Now "moving to adjacent numbers on the row below" transforms to moving only in the bottom and right directions. Start node is top-left corner, destination node is bottom-right corner. This can be solved with a standard dynamic programming approach, O(n^2) time.
- Killedsteel March 02, 2017