Algorithms Interview

Store a generic XML document in a relational database

Given a generic XML document as an input, write an algorithm in pseudo-code or in your favorite programming language [^It doesn’t have to compile, but you need to be able to discuss it] that will store this document in an SQL table.

Be mindful that you will need to be able to query the SQL table by element name, attribute name, attribute value, and you will need to reconstruct the XML document from the table.

Start by assuming the XML document will have no text nodes and only attributes, i.e.:

<example>
	<a foo="bar">
		<b />
		<c>
			<d baz="bat" />
		</c>
	</a>
	<e />
</example>

What I look for:

• You understand what XML is and how it works (i.e. elements, attributes, text nodes),
• You understand tree and tree-like data structure,
• You can write an algorithm that traverses a tree,
• You know basic SQL statement required to create table(s) to store a tree-like data structure

Query the table you just made

Write SQL statements that:

• Find all elements where a given attribute has a given value,
• Find all elements whose parent is a given element

Reconstruct an XML document from the SQL tables

Write an algorithm that will reconstruct the XML document from the SQL tables.

Parent pages