XML encoding

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
5 upvotes
Asked in companies
UberFacebookApple

Problem statement

The eXtensible Markup Language (XML) is a simple text-based format for representing information. The syntax for XML is as follows:

  1. Element => TAG Attributes END Child END
  2. Attribute => TAG Value

  • Value: String value.
  • TAG: Default mapping to an integer value.
  • Child: List of ‘Elements’ or a single ‘Value’. Never both.
  • End: Encoded as 0.

You are given an ‘Element’ object and the mapping of each ‘TAG’ to an integer value. The task is to encode this ‘Element’ using the ‘TAG’ mapping and return the resultant string.

Example: 
Element object:
<codingNinjas course=“InterviewPreparation” type=“IndividualCourse”>
    <topic name=“Aptitude”>CourseContents</topic>
</codingNinjas>

Tag mapping:
‘codingNinjas’ => 1, ‘topic’ => 2, ‘courseName’ => 3, ‘type’ => 4, ‘topicName’ => 5

The given element is ‘codingNinjas’, and it has a single child element ‘topic’. The element ‘codingNinjas’ has two attributes having tags as ‘course’ and ‘type’. The element ‘topic’ has one attribute with the tag as ‘name’. So, the encoded string is: 

‘1 3 InterviewPreparation 4 IndividualCourse 0 2 5 Aptitude 0 CourseContents 0 0’
Note: 
1. ‘END’ is always encoded as 0.
2. An ‘Element’ can have zero or multiple ‘Attributes’.
Function description: 
The function ‘encodeXML’ has the following parameters:
Pointer to an ‘Element’ object.
Mapping of ‘TAG’ name (string) to an integer value.
Structure of ‘Element’ and ‘Attribute’ object:
Element {
    String tag;
    List<Attribute> attributes;
    List<Element *> child;
    String value;
}
Attribute {
    String tag;
    String value;
}

If ‘Element’ stores a list of child elements, then ‘(Element => values)’ stores an empty string.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the count of elements, including nested elements.

The following ‘N’ blocks of lines contain the description of ‘N’ elements. Each block is as follows:

 1. Each block’s first line contains three space-separated values, integer ‘ID’ denoting the element’s id, ‘M’ denoting the number of ‘Attributes’, and a string denoting the element’s ‘tag’. The ‘ID’ is used later on to identify the child elements.
 2. The next ‘M’ lines contain two space-separated integers denoting the ‘tag’ and ‘value’ of each ‘Attribute’.
 3. The next line contains either of the following:
     a. If the element stores a value, it contains the integer 0 and a string denoting the ‘value’ in the element, separated by space.
     b. Otherwise, an integer ‘C’ denoting the number of child elements.

The next ‘N - 1’ lines contain two space-separated integers, ‘A’ and ‘B’, the element with ‘id’ as ‘B’ is the child of the element with ‘id’ as ‘A’. The given ‘Element’ object always has ‘id’ equal to ‘1’ and has no parent.

The next line of each test case contains an integer ‘S’ denoting the number of ‘tags’.

The next ‘S’ lines of each test case contain two space-separated values, a string denoting the ‘tag’ name and an integer mapped to this ‘tag’.
Output format: 
For each test case, return the encoded string.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
2 <= N <= 1000

The count of ‘Attributes’ of all elements doesn’t exceed 1000.
The string ‘Value’ is non-empty and contains only ‘a-z’ and ‘A-Z’ characters.

Time Limit: 1 sec

Sample input 1:

2
3
1 1 title
problem XML
1
2 1 input
name SampleOne
1
3 0 output
0 SomeValue
1 2
2 3
5
title 6
problem 7
input 8
name 9
output 10
3
1 2 title
problem knapsack
difficulty medium
2
2 1 input
name SampleOne
0 SomeValue
3 0 approach
0 code
1 2
1 3
6
title 6
problem 7
input 8
name 9
approach 11
difficulty 13

Sample output 1:

6 7 XML 0 8 9 SampleOne 0 10 0 SomeValue 0 0 0
6 7 knapsack 13 medium 0 8 9 SampleOne 0 SomeValue 0 11 0 code 0 0

Explanation of sample input 1:

Test case 1: 
The given element is ‘title’ having XML format as follows:
<title problem=“XML”>
    <input name=“SampleOne”>
        <output>SomeValue</output>
    </input>
</title>
So, the encoded string is: 
‘6 7 XML 0 8 9 SampleOne 0 10 0 SomeValue 0 0 0’

Test case 2:
The given element is ‘title’ having XML format as follows:
<title problem=“knapsack” difficulty=“medium”>
    <input name=“SampleOne”>SomeValue</input>
    <approach>code</approach>
</title>
So, the encoded string is:
‘6 7 knapsack 13 medium 0 8 9 SampleOne 0 SomeValue 0 11 0 code 0 0’

Sample input 2:

2
2
1 0 topic
1
2 1 input
name CaseOne
0 document
1 2
3
topic 2
input 8
name 9
1
1 3 output
name CaseThree
problem sorting
difficulty easy
0 SomeValue
4
output 10
name 9
problem 7
difficulty 13

Sample output 2:

2 0 8 9 CaseOne 0 document 0 0
10 9 CaseThree 7 sorting 13 easy 0 SomeValue 0
Hint

Try to solve this problem using recursion.

Approaches (1)
Use recursion

To encode an element, we need to encode its 'TAG' and ‘attributes’. If it doesn’t store a ‘VALUE’, we need to encode its children in the given order. For encoding the children, we first encode their 'TAG' and ‘attributes’, then encode their children, and so on. We stop this process when we reach an element that stores a ‘VALUE’. So, we need to encode the list of child elements recursively. 

 

Create a helper function ‘encodeHelper’ that takes parameters as an ‘element’ object, 'TAG' to integer mapping, and references to a string. The helper function encodes the passed element and appends it to the ‘RESULT’. After that, it traverses through the list of child elements and makes recursive calls to itself with the child element as a parameter. In the recursive call, it appends the encoded child element to ‘RESULT’. The recursion ends when an element that stores a ‘VALUE’ is reached.

 

The helper function, ‘encodeHelper(Object ‘ELEMENT’, Map 'TAG_TO_INT', String& ‘RESULT’)’:

 

  • Append ‘RESULT’ with the integer mapped to the 'TAG' of ‘ELEMENT’.
  • Run a loop where ‘i’ iterates through the list of attributes in ‘ELEMENT’:
    • Append ‘RESULT’ with the integer mapped to the 'TAG' of attribute ‘i’.
    • Append ‘RESULT’ with the ‘VALUE’ stored in the attribute ‘i’.
  • If the ‘VALUE’ in the ‘ELEMENT’ is not ‘NULL’, then append ‘RESULT’ with ‘VALUE’.
  • Else, run a loop where ‘i’ iterates through the list of children in ‘ELEMENT’:
    • Call the function ‘encodeHelper’ with parameters (‘i’, 'TAG_TO_INT', ‘RESULT’).

 

In the ‘encodeXML’ function, we call ‘encodeHelper’ with parameters: (object of input ‘ELEMENT’, given 'TAG' to integer mapping, an empty string ‘RESULT’). The string ‘RESULT’ stores the converted output string.

 

  • Initialize ‘RESULT’ as an empty string.
  • Call function ‘encodeHelper’ with parameters (object of input ‘ELEMENT’, given 'TAG' to integer mapping, ‘RESULT’).
  • Return ‘RESULT’ as the answer.
Time Complexity

O(N + M), where ‘N’ is the count of ‘Elements’ and ‘M’ is the count of ‘Attributes’ of all elements.

 

The hash table used for ‘tag’ to integer mapping has an average lookup time of ‘O(1)’. We visit all ‘Elements’ and their respective ‘Attributes’ only once. Hence, the time complexity is ‘O(N + M)’.

Space Complexity

O(N), where ‘N’ is the count of ‘Elements’.

 

In the worst case, when each ‘Element’ has precisely one child element except for the last element, the size of the recursion stack used will be ‘N’.

Code Solution
(100% EXP penalty)
XML encoding
Full screen
Console