Codesignal: XML tags.

Description.md

XML tags

You want to create your local database containing information about the things you find the coolest.
You used to store this information in xml documents, so now you need to come up with an algorithm that will convert the existing format into the new one. First you decided to choose a structure for your scheme, and to do it you want to represent xml document as a tree, i.e. gather all the tags and print them out as follows:

tag1()
 --tag1.1(attribute1, attribute2, ...)
 ----tag1.1.1(attribute1, attribute2, ...)
 ----tag1.1.2(attribute1, attribute2, ...)
 --tag1.2(attribute1, attribute2, ...)
 ----tag1.2.1(attribute1, attribute2, ...)
...

where attributes of each tag are sorted lexicographically.

You are a careful person, so the structure of the xml is neatly organized is such a way that:

• there is a single tag at the root level;
• each tag has a single parent tag (i.e. if there are several occurrences of tag a, and in one occurrence it's a child of tag b and in the other one it's a child of tag c, then b = c);
• each appearance of the same tag belongs to the same level.

Given an xml file, return its structure as shown above. The tags of the same level should be sorted in the order they appear in xml, and the attributes should be sorted lexicographically.

Note: you are given xml represantation in one line.

Example

for

xml =
"<data>
    <animal name="cat">
    	<genus>Felis</genus>
        <family name="Felidae" subfamily="Felinae"/>
        <similar name="tiger" size="bigger"/>
    </animal>
    <animal name="dog">
        <family name="Canidae" member="canid"/>
        <order>Carnivora</order>
        <similar name="fox" size="similar"/>
    </animal>
</data>"

the output should be

xmlTags(xml) =
["data()",
 "--animal(name)",
 "----genus()",
 "----family(member, name, subfamily)",
 "----similar(name, size)",
 "----order()"]

Input/Output

• [execution time limit] 4 seconds (py3)
• [input] string xml
• xml file as a string.
• Guaranteed constraints:
• 7 ≤ xml.length ≤ 1000.
• [output] array.string
• A list representing the structure of the xml file as described above.

Test 2

Input:
xml: "<products><product><TITLE> product #1 </TITLE><PRICE> 10.00 </PRICE></product><product><TITLE> product #2 </TITLE><PRICE> 20.00 </PRICE></product></products>"
Expected Output:
["products()", 
 "--product()", 
 "----TITLE()", 
 "----PRICE()"]

solution.rb

import xml.etree.ElementTree as ET
def xmlTags(xml):
    root = ET.fromstring(xml)
    dictionary = dict()
    answer =  rec(root,0,[], dictionary)
    print(dictionary)
    return ["{}({})".format(x,", ".join(dictionary[x])) for x in answer]
def rec(root, deep, arr, dictionary):
    tag = root.tag
    prefix = "--" * deep
    attribs = sorted(root.attrib)
    
    line = prefix + tag 
    if line not in dictionary:
        dictionary[line] = attribs
        arr.append(line)
    else:
        x = dictionary[line]
        dictionary[line] = sorted(list(set(attribs+x)))
    for x in root:
        rec(x, deep+1, arr, dictionary)
    return arr

At last I solved the XMLTags problem. First create list of tags, and use dictionary to save attributes list for each tag. Because each tag type have only one parent, and only one level, it is possible to use a level-prefix and tag name as a key for dictionary, and as a element of a list. Also use dictionary to track insertions in answer array. Eventually map through out the answer array and add list of attributes in parentheses. The dictionary plays two roles in my code. Role number one: save attributes for tag, role number two avoiding duplication of tags names.