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?

- Milo234 November 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

You can use Djikstra algorithm to reach the destination point.

- Kuber January 05, 2016 | Flag Reply
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.

- Kuber January 05, 2016 | Flag Reply
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.

- celicom May 06, 2016 | Flag Reply
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..

- Usman malik September 06, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More