Interview Coding Exercise – Nested String (Python)

stack-data-structure

Nested String

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

• S is empty;
• S has the form “(U)” or “[U]” or “{U}” where U is a properly nested string;
• S has the form “VW” where V and W are properly nested strings.

For example, the string “{[()()]}” is properly nested but “([)()]” is not.
Write a function: def solution(S) ,that, given a string S consisting of N characters, the function returns 1 if S is properly nested and 0 otherwise.

For example, given S = “{[()()]}”, the function should return 1.For S = “([)()]”, the function should return 0, as explained above.

The assumptions are:

• N is an integer within the range [0..200,000];
• string S consists only of the following characters: “(“, “{“, “[“, “]”, “}” and/or “)”.

Complexity requirements:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Solution (Python)

Stack is a FILO (First In Last Out) data structure. The idea is push a opening tag to the stack and pop one from and check if it matches when we see the closing tag. The only thing you need to pay attention to is to check if the stack is empty when you want to pop an element from the stack.

def IsNested(s):
    stack = []
    for x in s:
        if x in ['(', '{', '[']:
            stack.append(x)
        elif x in [')', '}', ']']:
            if len(stack) == 0:
                return 0
            # Pop an element to see if matches
            y = stack.pop()
            if x == ')' and y != '(':
                return 0
            elif x == ']' and y != '[':
                return 0
            elif x == '}' and y != '{':
                return 0
    return 1     
    
if __name__ == '__main__':
    # Define Test Cases
    testcases = {
        "([)()]": 0,
        "{[()()]}": 1,
        "": 1,
        "{}": 1,
        "[]()": 1,
        ")(": 0,
        "}{()": 0,
        "()[}": 0      
    }
    
    for test in testcases.keys():
        assert testcases[test] == IsNested(test), "Test " + test + " Failed"
    
    print ("All OK.")

Software Engineer Interview Experience

• NVIDIA, I'm Coming Again! This Time I'm Tougher!
• Jane Street First Round Interview Experience (Software Engineer at London)
• Four Facebook (Meta) Interview Experiences
• Three Attempts at Google: My Software Engineer Interview Journey (Is There Only Three Chances in a Lifetime?)
• Two Interview Experience with ByteDance Tiktok London

Interview Tips

• Difference Between Product Design Interview and System Design Interview
• Onsite Interview Tips for Facebook / Google / Microsoft / Amazon / Apple
• 45 Minute Mock Interview (Coding, System Design) + Career Development Advices
• Facebook Interview Tips and Guidance
• Coding Interview Tips for Software Engineers
• What are Big4 Tech Companies looking for in the technical interviews (Phone Screening)?
• How to use the Leetcode's Mock Interview Overview to Nail Your Interview?
• Facebook Onsite Interview Preparation Part 3: How to Ace a Design Interview?
• The Facebook Initial Coding Interview Experience
• Facebook Onsite Interview Preparation Part 2: Coding Questions
• Facebook Onsite Interview Preparation Part 1: Motivation/Bahavior Questions
• A Microsoft Coding Interview Screening for Position Principal Software Engineer
• How to Prepare for an Amazon Interview? My Amazon Interview Experience
• Go to an Interview even if you are not changing your job.
• Last Minute Tips before Phone Interview

Interview Questions

• Interview Coding Exercise - Nested String (Python)
• Some Telephone Interview Questions for C++/C# Software Enginners
• Microsoft Interview Question - Get the Area of the Triangle
• Google Interview Question: Print Messages

–EOF (The Ultimate Computing & Technology Blog) —