CareerCup

I think we can construct here a Trie ..with / as root and all the other as its children

import java.util.Hashtable;
public class Test{
public static void main(String[] args){
class Dir{
Hashtable<String,Dir> dirs;
Hashtable<String,String> files;
String name;
Dir(boolean isDir,String name){
if(isDir){
dirs = new Hashtable<String,Dir>();
files = new Hashtable<String,String>();
}
this.name = name;
}
boolean isDir(){
if(dirs!=null)return true;
return false;
}
Dir addDir(String name){
Dir dir = dirs.get(name);
if(dir==null)
dir = dirs.put(name,new Dir(true,name));
return dir;
}
String addFile(String name){
String file = files.get(name);
if( file == null )
file = files.put(name,name);
return file;
}
}
String[] problem = {"\\", "\\Documents\\",
"\\Documents\\School\\", "\\Documents\\School\\Project.docx",
"\\Documents\\Work\\", "\\Pictures\\", "\\Pictures\\me.jpg"};
Dir solution = new Dir(true,"\\");
for(String s:problem ){
int index=1;
int lastindex=1;
Dir dir = solution;
System.out.println("checking :"+s);
while((index=s.indexOf('\\',lastindex))!=-1){
String str= s.substring(lastindex,index);
dir = dir.addDir(str);
System.out.println("Added dir:"+str);//+": index==>"+index +" :lastIndex==>"+lastindex);
lastindex=index+1;
}
if(lastindex <s.length()-1){
String file= s.substring(lastindex);
dir.addFile(file);
System.out.println("Added file:"+file);
}
}
}
}

>>> Jay Shri Ram - Data ek Raam, bhikhari sari duniya ||

This be the structure of the node
struct node {
string data;
hash_map<string,struct node*> children };

Let root node be a dummy node. node *root=new node(); root->data="dummy";

1. Scan the input string.
2. str1= getNextString(); eg. \documents\school\
3. str= getNextToken(str1) ; eg. "\"
3. node *p=root;
4. while(str!=NULL) {
4.1 if(p->children[str]==NULL) {
4.1.1 node *temp=new node(); temp->data=str; p->children[str]=temp; }
4.2 p=p->children[str];
4.3 str=getNextToken(str1); eg. "\" done, now "documents" and so on...
}
5. Go to step 2. //Finish all strings

_/\_ Siyawar Ramchandra ki jai _/\_

def gen_tree(paths):
root = {}
paths.remove('\\')
for p in paths:
nodes = p.split('\\')[1:]
is_dir = False
if nodes[-1] == '':
nodes = nodes[:-1]
is_dir = True
curr = root
prev = None
for node in nodes:
if not curr.has_key(node):
curr[node] = {}
prev = curr
curr = curr[node]
if not is_dir:
prev[node] = None
return root

def gen_tree(paths):
root = {}
paths.remove('\\')
for p in paths:
nodes = p.split('\\')[1:]
is_dir = False
if nodes[-1] == '':
nodes = nodes[:-1]
is_dir = True
curr = root
prev = None
for node in nodes:
if not curr.has_key(node):
curr[node] = {}
prev = curr
curr = curr[node]
if not is_dir:
prev[node] = None
return root

def gen_tree(paths):
root = {}
paths.remove('\\')
for p in paths:
nodes = p.split('\\')[1:]
is_dir = False
if nodes[-1] == '':
nodes = nodes[:-1]
is_dir = True
curr = root
prev = None
for node in nodes:
if not curr.has_key(node):
curr[node] = {}
prev = curr
curr = curr[node]
if not is_dir:
prev[node] = None
return root

Why can't we just make a tree of strings? Since this is an ordered array, it won't be hard. When you want to add an element, start at the root node and traverse down until you find a node whose value is a substring of what you want to insert but it's children are not. For example \Documens\Work would insert itself under Documents because it contains \Documents\ as substring but not \Documents\School. Then when you insert you delete the parent-substring from the node so you're only leaving the relative path.

Input : files[1 ........ N]

function call : getTree(files,1)

Node getTree(files, int start)
  {
      if (start < files.length)
              return NULL;

      root = new Node(files[start])

      root.left = getTree(files, start*2)
      root.right = getTree(files, start*2 +1)

      return root;

   }


Explanation : 
          ith node's lc = files[2*i]
           ith node's rc = files[2*i + 1]
         …. so we can construct the tree recursively