Walmart Labs Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

The 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?

Comment hidden because of low score. Click to expand.
0
of 2 vote

You can use Djikstra algorithm to reach the destination point.

Comment hidden because of low score. Click to expand.
0
of 2 vote

You should use Dijkstra's algorithm.
Traverse with all possible path and at the end you can choose maximum one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I wonder how u make 22 from the second matrix... Also, why do u use -1 in sample matrix if it was called 0 in the rules? I agree with Kuber - to solve it use Dijkstra for max 3N graphs.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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..

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.