CareerCup

We gonna create hashMap for every parent and have ArrayList of childs
For Each line in the file(e.g. 4,17,Scott)
1. Check if parent (17) is present in Hash
1a If No create and Arraylist and add (4,Scott) in that.
1b If yes add (4,Scott) in the existing ArrayList.
2. Now start with 0 and print the output

NOTE : Solution works only when 0 is the root directory. If NOT we will need to track for a node that does NOT have any parent.

python code
#dictionary of file-id:Node where Node is { id, parent, children}
#then do a pre-order traversal on the root Node (id = '0')

class Node:
    def __init__(self, id, name=None, parent=None):
        self.id = id
        self.name = name
        self.parent = parent
        self.children = []

    def __str__(self):
        return "%s:%s" % (self.name, self.id)

f = open("input.txt", 'r')

files = {}

def preorder(n, tab_count):
    print "%s %s" % ("  "*tab_count, n)
    for child in n.children:
        preorder(child, tab_count+1)

for l in f.readlines():
    id, pid, name = map(lambda x: x.strip(), l.split(","))

    if(files.has_key(id)):
        n = files[id]
        n.name = name
        n.parent = pid 
    else:
        n = Node(id, name, pid)
        files[id] = n

    if (not files.has_key(pid)):
        files[pid] = Node(pid)

    files[pid].children.append(n)

roots = filter(lambda x: x.parent is None, files.values())
map(lambda root: preorder(root, 1), roots)

//use 2 Hash<ID, TreeNode> h1 and h2> first(h1) one will have the ID as the key and here we have all the elements, the second(h2) one will have ParentID as key and the elements there will be only the elements that still haven’t been attached to their parent where after all the elements from the file are taken we will iterate to remove the elements from. The structure that will keep the elements in order will be a tree(where the keys will be the Names) structure with a NIL root where we attach all the elements with ParentID = 0. So here is what we do:

1.) we add the NIL node in the h1 with id 0
2.) start traversing nodes from the file
2.1) we check if the parent id is in the h1.
2.1.1) if it exists we add the new node as a child to it
2.1.2) if it DOES NOT exist we add the new element under h2
2.2) we add the new element in the h1.
2.3) check if the element ID exists in h2.
2.3.1) if it exists we add the element from h2 as a child to the new element and remove the element from h2.
3.) finally take from h1 the node with ID = 0(NIL node) as the root and do an inorder traverse of the tree is the answer

public class TreeNode implements Comparable<TreeNode>{
  String name;
  Integer parentId, Integer id;
  Set<TreeNode> children;
 
  public TreeNode (String name, Integer id, Integer parentId) {
   this.name = name;
   this.children = new TreeSet<TreeNode>();
   …....
  }
  public int compareTo(TreeNode other) {return this.name.comaperTo(other.name);}
 }
 
 public class Item {
  int parentId, id;
  String name;
 }
 
 //Implementation
 public void printMailBox (Item[] fromFile){
  Map<Integer, TreeNode> h1 = new HashMap<Integer, TreeNode>();
  Map<Integer, List<TreeNode>> h2 = new HashMap<Integer, List<TreeNode>>();
  TreeNode currElement = new TreeNode(null, null, null);
  h1.put(0, currElement); //1
 
 //2
 for (int i = 0; i < fromFile.length; i++) {
  currElement = new TreeNode(fromFile[i].name, fromFile[i].id, fromFile[i].parentId);
  
  //2.1
  if (h1.containsKey(currElement.parentId)){
   TreeNode parent = h1.get(currElement.parentId);
   parent.children.put(currElement);
  } else {
   if (!h2.containsKey(currElement.parentId))
    h2.put(currElement.parentId, new LinkedList<TreeNode>());
   
   h2.get(currElement.parentId).add(currElement);
  }
 
  //2.2
  h1.put(currElement.id, currElement);
  
  //2.3
  if (h2.containsKey(currElement.id)) {
   Iterator<TreeNode> iter = h2.get(currElement.id).iterator();
   while (iter.hasNext())
    currElement.children.put(iter.next());
   
   h2.remove(currElement.id);
  }
 }
 //3. Simple inorter print.
 //Implementation skipped
 }

First of all, given the input and output format, it is sure that ( other than 0, root ), parent Id would be greater than ID. otherwise we can not get it sorted right away.

for solving this, we can maintain a map like
< parentID, < ID, name > >

Thus this will hold values in this format,
<0, <1, Spock >
<17, McCoy> >
< 17, < 4, Scott >
<9, Kirk >

Once the structure is finished, iterate reversely on the root element in a Depth First Traverse manner, that is... once 17 comes while iterating on the children of '0', print 17 and iterate on children of 17 ( if any ), and subsequently move to next node in the children's list of '0'.

You can have a look at my solution in my github profile: /leafac/puzzles/tree/master/mailbox-folders