Problem title
Difficulty
Avg time to solve

Number of Longest Increasing Subsequence
Moderate
--
Longest String Chain
Moderate
--
Minimum ASCII Delete Sum for Two Strings
Moderate
--
Divisible Set
Moderate
--
Partition Array for Maximum Sum
Moderate
--
Eulerian Circuit
Hard
--
Find if Path Exists in Graph
Easy
45 mins
Critical Connections in a Network
Hard
--
Is Graph Bipartite?
Moderate
--
Valid Arrangement of Pairs
Hard
--

XML encoding

Difficulty: MEDIUM
Contributed By
Avg. time to solve
15 min
Success Rate
85%

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.
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
Reset Code
Full screen
copy-code
Console