Katkat
Back

Solve sliding-window, flattening, decode, and O(1) random set

BloombergSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle nested data structures through recursive parsing, maintain efficient state using hash maps and dynamic arrays, and implement sliding window techniques to manage constraints in a stream.

Part 1: String Decoding

Given an encoded string, return its decoded version. The encoding rule is k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. k is guaranteed to be a positive integer.

Example: Input: s = "3[a]2[bc]" Output: "aaabcbc"

Part 2: O(1) Randomized Set

Design a data structure RandomizedSet that supports inserting, removing, and getting a random element from the set, all in average O(1) time complexity.

  • insert(val): Inserts val into the set if not present.
  • remove(val): Removes val from the set if present.
  • getRandom(): Returns a random element from the current set of elements.

Implementation

Provide the function signatures for the following:

def decodeString(s: str) -> str:
    pass

class RandomizedSet:
    def __init__(self):
        pass

    def insert(self, val: int) -> bool:
        pass

    def remove(self, val: int) -> bool:
        pass

    def getRandom(self) -> int:
        pass

Edge Cases

  • For decodeString: Handle nested brackets (e.g., "2[a3[b]]") and empty strings.
  • For RandomizedSet: Handle cases where you attempt to remove an element that does not exist or fetch a random element from an empty set.

Hints

Hint 1

For string decoding, use a stack to keep track of the current multiplier and the partial string being built as you encounter nested brackets.

Hint 2

For the randomized set, maintain a list to store elements for O(1) indexing and a dictionary to map values to their indices in that list to allow O(1) removal.

Hint 3

When removing an element from the list in the RandomizedSet, swap the target element with the last element in the list and then pop the last element to maintain O(1) complexity.

Follow-up questions

  • How would you modify the decodeString function to handle cases where the input string might be malformed, such as unbalanced brackets?
  • If the RandomizedSet needed to allow duplicate values, how would your data structure design change?
  • Explain how the memory complexity of the decodeString solution changes if the input contains highly nested structures versus many repetitions.