How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Axon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Axon during technical interviews.

Implement encryption and constant-time random set

Company: Axon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are asked about two coding topics from an onsite interview: 1. **Key-based string encryption** Briefly explain the idea of shared-secret encryption: both sides use the same secret key, and the key determines how plaintext is transformed into ciphertext. Then implement a simple encryption function to make the task precise: - Input: a plaintext string `s` of lowercase English letters and a non-empty lowercase key `k` - Encryption rule: repeat the key as needed. For each character `s[i]`, shift it forward in the alphabet by `k[i % k.length] - 'a'` positions, wrapping around from `z` to `a` - Output: the encrypted string Example: - `s = "attack"`, `k = "dog"` - Output: `"dhzdqq"` 2. **Randomized set with O(1) operations** Design a data structure for unique integers that supports the following operations in average `O(1)` time: - `insert(val)`: add `val` if it is not already present; return whether the insertion happened - `remove(val)`: remove `val` if it is present; return whether the removal happened - `getRandom()`: return a uniformly random element currently in the set

Quick Answer: This question evaluates understanding of symmetric shared-secret string transformation and the design of a randomized set supporting expected O(1) operations, testing skills in cryptographic string manipulation and data-structure algorithmic reasoning.

Part 1: Repeating-Key Shift Encryption

In shared-secret encryption, both sender and receiver know the same secret key. In this simplified version, the key controls how much each plaintext character is shifted. Given a lowercase plaintext string s and a non-empty lowercase key k, repeat the key as needed. For each position i, shift s[i] forward in the alphabet by the amount k[i % len(k)] - 'a', wrapping around from 'z' to 'a'. Return the encrypted string.

Constraints

0 <= len(s) <= 200000
1 <= len(k) <= 200000
s and k contain only lowercase English letters 'a' to 'z'

Examples

Input: ("abcxyz", "bcd")

Expected Output: "bdfyac"

Explanation: The repeated key is bcdbcd, giving shifts 1, 2, 3, 1, 2, 3. Applying them to abcxyz produces bdfyac.

Input: ("", "abc")

Expected Output: ""

Explanation: An empty plaintext has no characters to encrypt, so the result is an empty string.

Input: ("z", "b")

Expected Output: "a"

Explanation: The key character b means shift by 1. Shifting z by 1 wraps around to a.

Input: ("hello", "a")

Expected Output: "hello"

Explanation: The key character a means shift by 0, so every character stays the same.

Input: ("ace", "zebra")

Expected Output: "zgf"

Explanation: Only the first three key characters are used: z, e, b, which correspond to shifts 25, 4, and 1. So a -> z, c -> g, and e -> f.

Hints

Convert each character to a number from 0 to 25, apply the shift, then convert back to a character.
The key repeats, so the shift for position i comes from k[i % len(k)].

Part 2: Simulate a Randomized Set with O(1) Operations

Design a data structure for unique integers that supports insert, remove, and getRandom in average O(1) time. For this coding problem, you will simulate the data structure through a function.\n\nUse the standard array + hash map strategy: successful insert appends the value to the end of an internal array, and successful remove deletes a value in O(1) by swapping the last array element into the removed element's position and then popping the last slot.\n\nTo make outputs deterministic for testing, getRandom will not use true randomness. Instead, the j-th getRandom operation uses picks[j] and returns the element at index picks[j] % len(current_array) from the current internal array. Return the result of every operation in order.

Constraints

0 <= len(operations) <= 200000
-10^9 <= val <= 10^9 for insert/remove operations
len(picks) equals the number of 'getRandom' operations
'getRandom' is never called when the set is empty

Examples

Input: ([('insert', 1), ('insert', 2), ('getRandom',), ('remove', 1), ('insert', 2), ('getRandom',)], [1, 0])

Expected Output: [True, True, 2, True, False, 2]

Explanation: After inserting 1 and 2, the array is [1, 2]. The first getRandom uses 1 % 2 = 1, so it returns 2. Removing 1 swap-deletes it, leaving [2]. Inserting 2 again fails because 2 is already present. The second getRandom uses 0 % 1 = 0, so it returns 2.

Input: ([('remove', 5), ('insert', 5), ('insert', 5), ('getRandom',), ('remove', 5)], [3])

Expected Output: [False, True, False, 5, True]

Explanation: Removing 5 first fails because the set is empty. Inserting 5 succeeds, inserting it again fails, getRandom returns 5 because it is the only element, and removing 5 then succeeds.

Input: ([('insert', 10), ('insert', 20), ('insert', 30), ('remove', 20), ('getRandom',), ('remove', 10), ('getRandom',)], [5, 2])

Expected Output: [True, True, True, True, 30, True, 30]

Explanation: Removing 20 must swap the last element 30 into its position, so the array becomes [10, 30]. The first getRandom uses 5 % 2 = 1 and returns 30. Removing 10 then moves 30 to index 0, leaving [30]. The last getRandom returns 30.

Input: ([('insert', -3), ('insert', -1), ('remove', -3), ('getRandom',), ('insert', -3), ('getRandom',)], [10, 1])

Expected Output: [True, True, True, -1, True, -3]

Explanation: After removing -3, the remaining array is [-1]. The first getRandom returns -1. Inserting -3 again succeeds, making the array [-1, -3]. The second getRandom uses 1 % 2 = 1 and returns -3.

Input: ([], [])

Expected Output: []

Explanation: With no operations, the result is an empty list.

Hints

Use a list for O(1) random access by index, and a dictionary mapping value -> index for O(1) membership and updates.
When removing a value from the middle of the list, swap in the last element so you can pop in O(1).

Quick Overview

This question evaluates understanding of symmetric shared-secret string transformation and the design of a randomized set supporting expected O(1) operations, testing skills in cryptographic string manipulation and data-structure algorithmic reasoning.