Validating XML Tags in Space Mission Logs — Problem Statement & Solution Guide
Problem Description
Validating XML Tags in Space Mission Logs
You are given a single line string S that represents a sequence of XML‑like tags extracted from a spacecraft’s telemetry log. Each tag is either an opening tag of the form <name> or a closing tag of the form </name>, where name consists only of lowercase English letters (1‑10 characters). Tags appear consecutively without any other characters. Determine whether S is a well‑formed tag sequence: every opening tag must be closed by a later tag with the same name, and the nesting order must be correct (i.e., the tags form a proper stack). Return "Valid" if the sequence satisfies these rules, otherwise return "Invalid".
DSA Pattern Breakdown
DSA Pattern Breakdown
"Validating XML Tags in Space Mission Logs"
WHY DOES IT MATTER?
Proper tag validation prevents malformed telemetry from corrupting downstream analytics pipelines; the stack pattern is the backbone for any nested structure validation, from HTML parsers to compiler syntax checkers.
OPTIMIZATION CHALLENGE
Recognizing that each tag can be processed in constant time and that only the current nesting matters eliminates the need for quadratic rescans, collapsing the problem to a linear scan with a bounded auxiliary structure.
REAL-WORLD CONNECTION
Think of a spacecraft's command hierarchy where higher‑level commands must be completed before lower‑level ones; the stack models this call‑stack like behavior, ensuring commands close in reverse order of opening.
When coding under pressure, first write a tiny parser that extracts tags into a list, then immediately apply the stack check—this separation keeps the logic simple and debuggable.
COMPLEXITY AT A GLANCE
O(n)O(d)Core Theory — Why This Approach?
The validation of XML‑like tags is a classic instance of the well‑formed parentheses problem, generalized to arbitrary tag names. A stack provides a LIFO structure that mirrors the nesting order: every time we encounter an opening tag we push its identifier, and for a closing tag we pop and compare, ensuring the most recent unmatched opening tag matches the current closing tag. Naïve approaches that scan for matching pairs without a stack either require repeated rescanning of the string (leading to O(n^2) time) or resort to recursion that can overflow the call stack on long logs. The optimal paradigm leverages a single pass linear scan combined with a stack, guaranteeing O(n) time and O(k) auxiliary space where k is the maximum nesting depth, which is bounded by the number of tags.
Interview Questions on This Problem
Q1How would you modify the algorithm to also detect duplicate sibling tags that are not allowed in the log format?
Maintain a hash set for each level of the stack; when pushing an opening tag, check if it already exists in the current level's set—if so, reject; otherwise add it. Pop the set when the corresponding closing tag is processed.
Q2If the tag names could include digits and hyphens, how would you adjust the parsing logic?
Update the regular expression or manual parser to accept [a-z0-9-] characters and ensure the closing tag correctly mirrors the exact opening name, keeping the stack comparison unchanged.
Q3Explain how you would handle streaming input where the log is received chunk by chunk rather than as a whole string.
Keep the stack state between chunks; parse each incoming chunk, processing complete tags and deferring incomplete tag fragments to the next chunk, ensuring the stack reflects the current nesting at any point.
Examples
Input
<engine><thruster></thruster></engine>
Output
Valid
Explanation: Push <engine>, push <thruster>, encounter </thruster> matches top, pop, encounter </engine> matches remaining <engine>, pop; stack empty → valid.
Input
<sensor><camera></sensor></camera>
Output
Invalid
Explanation: Push <sensor>, push <camera>, encounter </sensor> does not match top <camera>, mismatch → invalid.
Input
<data></data><log></log>
Output
Valid
Explanation: <data> pushed, </data> matches and pops, stack empty, then <log> pushed and </log> matches; final stack empty → valid.
Constraints
- 1 <= |S| <= 10^5
- Each tag name length is between 1 and 10
- All characters of S belong to '<', '/', '>', or lowercase letters
Optimal Approach & Strategy
Traverse once, using a stack to push opening tags and pop‑compare on closing tags, achieving linear time and space proportional to nesting depth.
Brute Force Approach
Repeatedly search the string for the nearest matching closing tag for each opening tag, removing pairs until none remain, which can degrade to quadratic time.
Verified Code Solutions
const fs = require('fs');
const s = fs.readFileSync(0,'utf8').trim();
function isValid(str){
const stack=[];
for(let i=0;i<str.length;){
if(str[i]!=='<') return false;
const j=str.indexOf('>',i);
if(j===-1) return false;
let tag=str.slice(i+1,j);
let closing=false;
if(tag.startsWith('/')){closing=true; tag=tag.slice(1);}
if(tag.length===0||tag.length>10) return false;
if(!/^[a-z]+$/.test(tag)) return false;
if(closing){
if(stack.length===0||stack[stack.length-1]!==tag) return false;
stack.pop();
}else{
stack.push(tag);
}
i=j+1;
}
return stack.length===0;
}
console.log(isValid(s)?'Valid':'Invalid');#include <bits/stdc++.h>
using namespace std;
bool isValid(const string& s){
vector<string> st;
for(size_t i=0;i<s.size();){
if(s[i]!='<') return false; // malformed
size_t j=s.find('>',i);
if(j==string::npos) return false;
string tag=s.substr(i+1,j-i-1);
bool closing=false;
if(!tag.empty() && tag[0]=='/'){
closing=true;
tag=tag.substr(1);
}
// name validation
if(tag.empty()||tag.size()>10) return false;
for(char c:tag) if(c<'a'||c>'z') return false;
if(closing){
if(st.empty()||st.back()!=tag) return false;
st.pop_back();
}else{
st.push_back(tag);
}
i=j+1;
}
return st.empty();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s; if(!(cin>>s)) return 0;
cout<<(isValid(s)?"Valid":"Invalid");
return 0;
}import java.io.*;
import java.util.*;
public class Main {
private static boolean isValid(String s){
Deque<String> stack = new ArrayDeque<>();
int i=0, n=s.length();
while(i<n){
if(s.charAt(i)!='<') return false;
int j=s.indexOf('>',i);
if(j==-1) return false;
String tag=s.substring(i+1,j);
boolean closing=false;
if(tag.startsWith("/")){
closing=true;
tag=tag.substring(1);
}
if(tag.length()==0||tag.length()>10) return false;
for(char c: tag.toCharArray()) if(c<'a'||c>'z') return false;
if(closing){
if(stack.isEmpty()||!stack.peek().equals(tag)) return false;
stack.pop();
}else{
stack.push(tag);
}
i=j+1;
}
return stack.isEmpty();
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
if(s==null) s="";
System.out.print(isValid(s)?"Valid":"Invalid");
}
}import sys
def is_valid(s: str) -> bool:
stack = []
i = 0
n = len(s)
while i < n:
if s[i] != '<':
return False
j = s.find('>', i)
if j == -1:
return False
tag = s[i+1:j]
closing = False
if tag.startswith('/'):
closing = True
tag = tag[1:]
if not (1 <= len(tag) <= 10):
return False
if not tag.islower():
return False
if closing:
if not stack or stack[-1] != tag:
return False
stack.pop()
else:
stack.append(tag)
i = j + 1
return not stack
if __name__ == "__main__":
s = sys.stdin.read().strip()
print('Valid' if is_valid(s) else 'Invalid')const fs = require('fs');
const s = fs.readFileSync(0,'utf8').trim();
function isValid(str){
const stack=[];
for(let i=0;i<str.length;){
if(str[i]!=='<') return false;
const j=str.indexOf('>',i);
if(j===-1) return false;
let tag=str.slice(i+1,j);
let closing=false;
if(tag.startsWith('/')){closing=true; tag=tag.slice(1);}
if(tag.length===0||tag.length>10) return false;
if(!/^[a-z]+$/.test(tag)) return false;
if(closing){
if(stack.length===0||stack[stack.length-1]!==tag) return false;
stack.pop();
}else{
stack.push(tag);
}
i=j+1;
}
return stack.length===0;
}
console.log(isValid(s)?'Valid':'Invalid');Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.