Amazon Interview Question
Software Engineer / DevelopersYou can build a trie and do a dfs.Trie in the sense when we see a.b.c=1,create node a ,b,c,and a leaf 1.
Now when we enconter next eq a.b.d=4,nodes a,b already created so it is enough to attach one more child node "d" to node b.
Now after tree is built do a dfs
This seems like a tree - say a directory tree. As if, 1 is in directory a/b/c, and so on.
- Nix October 17, 2009So, here's my trick:
1) Create a local string str1 from the tokens on left side. For the first input, the string str1 = "abc", but store it in reverse (for reason explained later). So, str1 = "cba".
2) Whenever you hit "=" in input, go through str1 and create xml structure. So, <a><b><c>1
3) Then go thru next token and store it in reverse in a new string str2. So, str2 = "dba".
4) Now do this: ptr = strstr( str1, str2 ). This is first reason I stored tokens in reverse: to use strstr().
5)
(a) if ptr is NULL, close all xml tokens. That is, write </c></b></a> by looking up str1.
(b) if ptr is non NULL, close only xml tags from str1 to ptr. That is, in current case you'd only close </d>.
6) Assign str2 to str1; read next tag; go back to step 3.
That might be it. Comments?