Walmart Labs Interview Question
Country: United States
As i understand the problem here dp approach would'nt work as we also have to store the path by which we are getting maximum as to take next square we cheak both the there is no intersection (or square should be common) so its become as a exponential problem and also so much memory for storing the path is not efficient.
i think here better approch is backtracking..please correct if i m wrong..
This seems to be a graph theory problem in disguise: given a directed graph with edge weights, find the maximum value of a path that visits each node at most once.
- Milo234 November 06, 2015The trick is converting the input into a graph you can work on. Say the 2D matrix is of dimension NxN. The graph you need to construct will have one node for every square in the matrix. Additionally it will have N nodes representing the squares immediately left of the first column, i.e. column -1. The edges then become the number of strawberries in the square being arrived at. One trick is that you have to denote that some edges that go from top->bottom and vice versa cause your total strawberries so far to go to 0.
Once you've created this graph, a slightly-modified standard algorithm to compute the maximum value of a walk through the graph from the top cell in the -1 column should be sufficient to solve this.
Code forthcoming when I get more free time.
This problem seems pretty hard. Is Walmart Labs looking for just really smart people with PhDs in Computer Science?