Interview Question
- 0of 0 votes
AnswerAmazon receives marketplace sellers (clients) requests in XML format. Sometimes, the clients software makes mistakes and omit certain nodes starting or ending tags (or both). Amazon, being the earth most customer friendly company, still wants to honor the client’s request by converting this malformed XML to well-formed XML. Given a malformed XML as string, you have to return the structure that the input XML follows .
- saurabh March 31, 2012 in India
Following are the assumptions you can make:
1. XML follows the structure below :-
a. Any parent node ( say with tag A ) can have multiple children but only of the same tag ( say B ).
b. A tag can occur only at the exactly one level in the XML Structure ( say tag B can only occur at the level 2)
c. There is single leaf node tag.
2. For a given XML input, it will honor only a unique XML structure.
3. All node tag names are unique.
4. There is a single root node which is always present in the input XML.
Input Format:
Only line in the input contains a malformed string.
Output Format:
Print in a single line, space separated list of tags in the structure. Tags that are more closer to root has to be printed before the ones that are farther.
Sample Input:
<A><B></B><D><C></C></D><B><D></D></B></A>
Sample Output:
A B D C
Explanation:
The actual XML structure is root with tag 'A' . Root has two children each having tag 'B'. Each of the node with tag 'B' has one child with tag 'D' and finally each of the node with tag 'D' has one children with tag 'C'. The well-formed string for this case is "<A><B><D><C></C></D></B><B><D><C></C></D></B><B><D><C></C></D></B></A>" and in the sample input some of the tags were missing.
Constraints: The number of nodes is not more than 10,000. Size of tag string is less than 20.| Report Duplicate | Flag | PURGE
Algorithm
Hi, can u please share ur experience and questions in case u had an interview with Amazon recently .. Did you try for Amazon hyd /blr ? . Thanks
- vikdp01 March 31, 2012