Thursday, October 23, 2014

Displaying the contents of an arbitrarily complex nested list - Coding Interview Question

Question:

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. 

Code (Java):

import java.util.Random; 

class Node{
    String value;
    Node next;
    Node subList;
    
    Node(String value){
        this.value = value;  
    }
}

public class dumpList {
    
    /*
        Just constructing a random list
    */
    public static Node buildList(){
        Node node[] = new Node[10];
        Random rand = new Random();
        
        node[0] = new Node("first");  
        
        //Setting random string values
        for(int i=1;i<node.length;++i){
            node[i] = new Node(Character.toString((char)(97+rand.nextInt(26))));
            node[i-1].next = node[i];
        } 
        
        Node newNode = new Node("This");
        node[3].subList = newNode;
        newNode.next = new Node("is");
        newNode.next.subList = new Node("a");
        newNode.next.subList.next = new Node("line");
        newNode.next.subList.next.subList = new Node("!!");
        return node[0];
    }
    
    //The actual function
    public static void dumpList(String string, Node node){
        int i = 0;
        string+="."; 
        
        while(node!=null){ 
            System.out.println(string+i+": "+node.value);
            Node subList = node.subList;
                if(subList != null)
                    dumpList(string+i, subList);
            node = node.next; 
            i++;
        }
    }
    
    public static void main(String[] args){
        dumpList("Foo", buildList());
    }
}
Output:

Foo.0: first
Foo.1: o
Foo.2: g
Foo.3: o
Foo.3.0: This
Foo.3.1: is
Foo.3.1.0: a
Foo.3.1.1: line
Foo.3.1.1.0: !!
Foo.4: w
Foo.5: v
Foo.6: p
Foo.7: i
Foo.8: z
Foo.9: x

No comments:

Post a Comment