Amazon Recent 30

Question 1

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return “” if not possible.

Answer 1

Intuition
Take high-frequency characters alternately and insert them to form the string.
Example: “aabbccad” → “ababacdcd” (take ‘a’ first, then ‘d’).
Generate the string ensuring that the most occurring elements are not adjacent.

Algorithm
Generate a max heap of (count, char).
Iterate while elements exist in the max heap:
Pop the most frequent character and add it to the result.
Add the previous (count, char) back if present.
Update the previous as the current popped node, dont add it to heap.
The above process enables alternate addition of elements.

Final Check
Return the resultant string only if its length matches the original string else empty string.
Time Complexity (TC)
Heap operations: O(N)O(N)
Heap build: O(log⁡N)O(\log N)
Time Complexity: O(Nlog⁡N)
Space Complexity (SC)

Question 2

You are given a 2D integer matrix grid of size n x m, an integer array limits of length n, and an integer k. The task is to find the maximum sum of at most k elements from the matrix grid such that:

The number of elements taken from the ith row of grid does not exceed limits[i].

Return the maximum sum.

Answer 2

Input: Grid of numbers n×m.
Output: Maximum sum of at most k elements from the matrix.
Constraints:
Maximum number of elements taken from the i-th row ≤ limits[i].

1. Algorithm
   Sort all row elements in ascending order.
   Create a max heap to efficiently retrieve the largest elements.
   Traverse the grid:
   Add the last (largest) limits[row] elements from each row to the heap.
   Pop at most k elements from the heap and sum them up.
2. Time Complexity (TC)
   Sorting all rows: O(nmlog⁡m)
   Creating the heap: O(nmlog⁡(nm))
   Popping k elements from heap: O(klog⁡(nm))
   Total: O(nmlog⁡m+nmlog⁡(nm)+klog⁡(nm))

Question 3

LRU Cache

Answer 3

sf

Question 4

Queue using Stack

Answer 4

Use two stacks

S1: push stack
S2: pop stack

Case: Push, push, push, pop
Push all 3 in S1 O(1)
Pop: Pop all from S1, put in S2 - O(N)
Pop from S2 to remove the front

Leave the state of stacks as it is.

Case: Push, Pop, Push, Pop
Push: Push to S1
Pop: Pop from S2 if elements present
Push: Push to S1
Pop: if no elements in S2, Pop all from S1 - O(N), give S2 top.

Case:
Empty: If both the stacks are empty, return True.
TC: Amortized O(1). Only if pop stack is empty, it takes O(N) for moving all the elements from S1 to S2

Question 5

Stack using Queue

Answer 5

Single Queue

Pop-heavy:
Push - O(N)
Pop - O(1)

Push: Add to queue, Keep popping, while the front of queue is not current inserted element. Simultaneously append to queue.
Pop: Front of queue is top

Push-heavy:
Push - O(1)
Pop - O(N)

Push: Simply append to queue.
Pop: Remove from queue curr_queue_len - 1 times and append at the end. Pop the front after the loopl.

Question 6

Min Stack

Answer 6

Perform Push, Pop. Top and GetMin operation on a stack in O(1) time.

Stunt: Store minimum at that state of stack, alongside the element in stack

[ (element, curr_min), (element, curr_min), (element, curr_min)]