Write a function (in pseudo-code) called dumpList that takes as its parameters a string and a reference to an arbitrarily complex nested list and prints the value of each list element on a separate line. The value of each line should be preceded by the string and numbers indicating the depth and index of the element in the list. Assume that the list contains only strings and other nested lists.

Let’s take a look at an example of what we want exactly in the dumpList function. Suppose that you are given the following nested list. A nested list is just a list that contains other lists as well – so in the list below you see that it also contains the lists [‘a’,’b’,’c’] and [‘eggs’] :

List = ['a string', ['a','b','c'], 'spam', ['eggs']] 


And, suppose that the string passed in to the dumpList function is called ‘Foo’, then the output of dumpList(‘Foo’, List) would look like this:

Foo.0:  a string
Foo.1.0: a
Foo.1.1 : b
Foo.1.2: c
Foo.2: spam
Foo.3.0: eggs


The dumpList function should be less than 20 lines of pseudo-code.

This question was asked in a Google interview for a software engineering position.

It’s obviously important to thoroughly understand any question before you answer it, so that you don’t miss anything. With that in mind, let’s make sure that we clarify what is being asked here. The main thing to take note of in this question is the part that says "arbirtrarily complex nested list". What that means is that the function we are being asked to write should be able to handle a list that can be as deep as the creator of the list would like it to be. In the example given above, we have a list that is only 2 levels deep, but you could potentially have something that’s 100 or even 10000 levels deep – so, our function should be able to handle any depth within the list.




Now that an important point has been clarified, we should come up with a sound strategy to solve this problem. Take a close look at the question – it uses words like ‘nested’ and ‘depth’. Words like these should generally get you to start thinking recursively – so this is an interview question that has to do with recursion (as you may have already guessed from the title of the page!).

Because the list can contain other lists as elements, we need to be sure to check to see if each element is a list. If the element is a list then we want to make a recursive call, passing in a new string with the current depth of the list. If the element is not a list then we want to print out the current string and then the element itself. Now that you know this interview question requires a recursive solution – try to work this one out on your own and see what you come up with before you read our solution.

Here’s what the function would look like in pseudo code:

Solution to the recursion interview question

dumpList(String x, &list)
{
  for(int y = 0; y < list.length(); y++)
  {
    if(list[y] is a list)
      dumpList(x.y, list[y]);  //recursive call

    else
      print "x.y:  ", list[y];
  }
}




You can see in our solution that we simply iterate through the length of the list and if another list is found then a recursive call is made. Note that in the recursive call we pass in the string "x.y" - this way, in the context of the recursive call, x will become x.y - which allows the string to grow larger as the calls to nested lists grow larger. And, we know that if we have a list inside of another list then the recursive call will continue to handle it. If that doesn't make sense then just plug the actual values from the example given above into the function so that you really understand how it works - and also read our Recursion tutorial. Inside the for loop, if we come across an element that is not a list itself then we know that we have a single element, and we can just print it out along with the string that is passed in to the function.

Hopefully you've learned something useful from this recursion interview question - we think it's a good one because it's so deceptively simple, but it seems so complicated.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

  • snehgin

    sorry it was my mistake. the pseudo code is correct only

  • snehgin

    from the sample, we have to print ‘foo.1.0: a’, but with given code this will not be possible. ‘print “x.y: “, list[y];’ will print only foo.1: a or foo.0.a and not foo.1.0: a

  • sun

    this is pseudocode, the x.y represents a string. it will be converted to a string in real code. x is the Foo and y is the index as the example above (at the beginning of the problem)

  • vivek

    unable to understand recursive call..why are you passing x.y.
    please clarify.