Katkat
Back

Implement encryption and constant-time random set

AxonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to implement a cryptographic XOR-based transformation and design a randomized data structure with O(1) performance using an array-based map.

Part 1: Symmetric XOR Cipher

Implement a function symmetric_cipher(data: str, key: str) -> str. The function should transform the input data string by performing a bitwise XOR operation between each character in the data and the corresponding character in the key (repeated cyclically if the key is shorter than the data). The result should be returned as a string of the resulting character codes.

Part 2: RandomizedSet

Design a data structure RandomizedSet that supports the following operations in expected O(1) time:

  • insert(val: int): Inserts val into the set if not present. Returns True if the set did not contain the specified element.
  • remove(val: int): Removes val from the set if present. Returns True if the set contained the specified element.
  • getRandom(): Returns a random element from the current set of elements. Each element must have the same probability of being returned.

Examples

# Part 1
symmetric_cipher("hello", "abc") 
# ('h'^'a'), ('e'^'b'), ('l'^'c'), ('l'^'a'), ('o'^'b')

# Part 2
rs = RandomizedSet()
rs.insert(1)  # returns True
rs.remove(2)  # returns False
rs.insert(2)  # returns True
rs.getRandom() # returns 1 or 2
rs.remove(1)  # returns True
rs.getRandom() # returns 2

Constraints

  • data length up to 10^5.
  • key length at least 1.
  • val is a 32-bit integer.
  • All operations must be amortized O(1).

Hints

Hint 1

For the cipher, use the `ord()` function to get the integer representation of a character and the `chr()` function to convert the result back.

Hint 2

To achieve O(1) removals in the set, maintain a dynamic array of values and a hash map that stores the index of each value in that array.

Hint 3

When removing an element from the array in the set, swap the element you want to remove with the last element in the array and then pop the last element to maintain O(1) time.

Follow-up questions

  • How would you modify the XOR cipher to be more secure against frequency analysis attacks?
  • What changes would be necessary to the RandomizedSet if duplicate elements were allowed?
  • If getRandom() must be thread-safe in a multi-threaded environment, what locking mechanisms would you implement?