Katkat
Back

Solve Stack and String Shift Problems

ByteDanceSite Reliability Engineer · Technical Screen
MediumSite Reliability EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle nested validation using stacks and coordinate transformation using modular arithmetic on strings.

Part 1: Balanced Delimiters

Given a string s containing only characters '(', ')', '{', '}', '[', and ']', write a function is_valid(s) that returns True if the string is balanced. A string is balanced if every opening bracket has a corresponding closing bracket of the same type and they are closed in the correct order.

Part 2: Circular Character Shift

Given a string text and an integer shift, write a function apply_shift(text, shift) that shifts each character in text by shift positions in the alphabet. Assume text contains only lowercase English letters. The shift should be circular (e.g., shifting 'z' by 1 results in 'a'). Handle large values of shift efficiently.

Examples

# Part 1
is_valid("()[]{}") # Output: True
is_valid("(]")       # Output: False

# Part 2
apply_shift("abc", 1)  # Output: "bcd"
apply_shift("xyz", 2)  # Output: "zab"

Constraints

  • 0 <= len(s) <= 10^4
  • 0 <= shift <= 10^9
  • Part 1: You must use a stack-based approach.
  • Part 2: The time complexity should be O(n), where n is the length of text.

Hints

Hint 1

For Part 1, use a stack to store opening brackets and compare them with the top of the stack whenever a closing bracket is encountered.

Hint 2

For Part 2, use modular arithmetic `(ord(char) - ord('a') + shift) % 26` to determine the new character position.

Hint 3

Remember that a shift of 26 is equivalent to a shift of 0; use the modulo operator on the shift value before iterating through the string.

Follow-up questions

  • How would you modify the bracket validation to handle non-bracket characters mixed into the string?
  • If the shift value were negative, how would you adjust your modular arithmetic to handle wrapping from 'a' back to 'z'?
  • What is the space complexity of your solutions, and can you optimize the space for the shift operation?