HTML Reverser

Image placeholder 9899

(This question has been seen in the interviews of the following companies: Google)

Build HTML Reverser

Given <A>(hello)(<P>ab</P>)(<S>hi</S>)</A> Return <A>(<S>ih</S>)(<P>ba</P>)(olleh)</A>


#recursion
def reverse(html):
    if not html:
        return

    tag, html = stripOuterTag(html)
    listOfTrunks = divideTrunks(html)
    #print listOfTrunks
    if len(listOfTrunks) == 1:
        return listOfTrunks[0][::-1] if not tag else addTag(listOfTrunks[0][::-1], tag)
    
    listOfTrunks = listOfTrunks[::-1]
    listOfTrunks = [reverse(trunk) for trunk in listOfTrunks]
    
    return addTag("".join(listOfTrunks), tag)

#split up elements in the same level
'''e.g. "hello

xyzab

hi" into ["hello", "

xyzab

", "hi"] ''' def divideTrunks(html): ls = [] while html: idxOfOpenP = html.find('<') if idxOfOpenP > 0: ls.append(html[0: idxOfOpenP]) html = html[idxOfOpenP:] else: tag = html[1: html.find('>')] endTag = '' idxOfEndTag = html.find(endTag) ls.append(html[0: idxOfEndTag len(endTag)]) html = html[idxOfEndTag len(endTag):] return ls ''' remove and return the surrounding tag e.g. "\hi\" into \, "hi" ''' def stripOuterTag(html): if not html or html[0] != '<': return None, html tag = html[: html.find('>') 1] return tag, html[len(tag): len(html) - len(tag) -1]



Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.