Walmart Labs Interview Question

Country: India

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

Treat it as a graph problem. start node is the start word. adjacent words are words where one of the characters is changed and the result is in the dictionary. Then you can perform a BFS on it to find the shortest path from start to end.

Optimization potential exists:
- dual source BFS
- Accelerate search with a heuristic (A*, guess the remaining distance as the number of characters to change to the end - which is never an overestimation, so you'll find the shortest path)
- Find adjacents: put the dictionary into a Trie where you can navigate the Nodes inside, so you can change characters at single positions (this wins on very large alphabets in practice and loose on reasonable small alphabets due to cache advantages of Hashtable)

- Chris August 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

Good idea Chris. Here's simple implementation.


function Node(word, friends) {
  this.word = word;
  this.friends = friends;

function createGraph(start, dict, visited) {
  visited[start] = true;
  var friendWords = getFriendsWords(start, dict);
  var friends = friendWords.reduce(function(f, fWord) {
    if (!visited[fWord]) {
      f = f.concat( createGraph(fWord, dict, Object.create(visited)) );
    return f;
  }, []);
  var node = new Node(start, friends);
  return node;

function getFriendsWords(word, dict) {
  var result = [];
  for(var i = 0; i < dict.length; ++i) {
    var charDiffCount = getCharDiffCount(word, dict[i]);
    if (charDiffCount === 1) {
      result.push( dict[i] );
  return result;

function getCharDiffCount(a, b) {
  var count = Math.abs(a.length - b.length);
  for(var i = 0; i < a.length; ++i) {
    if (a[i] !== b[i] ) ++count;
  return count;

function printGraph(node) {
  if (node) {

function findShortestPath(root, target, path, result) {
  if (!root) {
  }else if(root.word === target) {
    var currentMinLength = result.minPath ? result.minPath.length : Infinity;
    result.minPath = path.length < currentMinLength ? path.slice() : result.minPath;
  }else {
    var currentPath = [root.word];
    var friends = root.friends;
    for(var i = 0; i < friends.length; ++i) {
      var friend = friends[i];
      path.push( friend.word );
      findShortestPath(friend, target, path, result);

var start = 'SAT';
var end = 'PAN';
var dict = ['RAT', 'PAT'].concat( end );

var root = createGraph(start, dict, {});
var result = {};
findShortestPath(root, end, [], result);
console.log( 'minPath: ' + start + '->' + result.minPath.join('->') );

- tnutty2k8 August 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

# python 3.6.x
Assume a word list of length N where every word has width W
for i in [0..W-1]
    - rotate each word in the list by i
    - sort the list of words
    - compare consecutive words in the sorted list
    - assume the pair of words being compared as tuple (u, v)
    - if the distance between u and v =1
        - add (u,v ) as edge to a graph
let Networkx now find a shortest path from any u to any v
note: the distance between words = D when they differ in D char positions
from operator import itemgetter
import networkx as nx

rotate = lambda s, t: s[len(s) - t:len(s)] + s[0:len(s) - t]
apartby1 = lambda s1, s2: 1 == len([i for i in range(len(s1)) if s1[i] != s2[i]])
g = nx.Graph()

dict = ["SAT", "PAN", "RAT", "PAT", "DAM"]

for t in range(3):
    tdict = []
    for word in dict:
        tdict.append([word, rotate(word, t)])
    sorted(tdict, key=itemgetter(1))

    for w in tdict:
        for wn in tdict[1:len(tdict)]:
            if apartby1(w[1], wn[1]):
                print(" edge {} -> {}".format(w[0], wn[0]))
                g.add_edge(w[0], wn[0])
    result = nx.shortest_path(g, "SAT", "PAN")
    print("path of len {} found, {}".format(len(result), result))
    print ("no path found")

- Makarand August 28, 2017 | Flag Reply

Add a Comment

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


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


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