Arrays, Hashing & Heaps

Okta's coding rounds run practical, but the first screen and one or two onsite rounds still lean on the array, hashing, and heap staples every backend loop shares. The problems that recur are not obscure. Each fits in a sentence: reshape an array without division, build a container whose every operation is O(1), keep a running median as numbers stream in, rank users by score. An interviewer can pose one, watch you talk it through, then push with a follow-up.

The through-line is that Okta grades the conversation as much as the code. Interviewers here expect you to state the approach, name the data structure, and reason about complexity before you type, then write a full working solution with the edge cases covered. A correct answer delivered silently reads worse than a slightly slower one you narrated cleanly. The four most-reported problems from this family follow, each drilled end to end with the follow-up Okta tends to add next.

How Okta frames it

Three framings show up repeatedly. The pure screen is a standard easy-to-medium problem that wants a clean optimal solution and a crisp complexity argument. Product of Array Except Self, paired with a graph problem, is a reported first-round set. The design-with-hashing problem asks you to build a small container to a contract. The trick is picking the right pair of structures so every operation stays O(1). Insert Delete GetRandom is the canonical one, and it has opened a staff loop. The data-stream problem hands you numbers one at a time and asks for an answer maintained on the fly, which is where heaps earn their place. Find Median from a Data Stream is the most-repeated named problem in the Okta coding rounds, and it has been asked as a full staff round on its own.

The three moves to know

Each of the four problems below is really one of three reusable moves. Learn the move and the specific problem falls out of it.

Move 1: the prefix/suffix sweep

When each output slot depends on everything to its left and everything to its right, two passes beat any nested loop. Sweep left carrying the running result of everything before i, then sweep right carrying everything after it, and combine. Nothing between the two ends is ever recomputed.

answer = [1] * n
prefix = 1
for i in range(n):          # everything strictly LEFT of i
    answer[i] = prefix
    prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):   # everything strictly RIGHT of i
    answer[i] *= suffix
    suffix *= nums[i]

Move 2: the value-to-index map with swap-remove

To make insert, remove, and random access all O(1), store the values in a flat array, so a random pick is one index lookup. Add a hash map from each value to where it lives in that array, so remove is a lookup instead of a scan. The one trick that makes remove O(1) is to overwrite the removed slot with the last element and shrink the array, then repair the moved element's recorded index. No shifting.

Move 3: two balanced heaps

To track the middle of a stream, split the numbers into a lower half and an upper half. Keep the lower half in a max-heap (its top is the largest small number) and the upper half in a min-heap (its top is the smallest large number). Keep their sizes within one of each other, and the median is either the larger heap's top or the average of the two tops. Every insert is a couple of heap operations; the median is a peek.

Asked at Okta

These are the array, hashing, and heap problems reported most often across Okta's screens and onsite coding rounds. Build each until the approach, the edge cases, and the follow-up are automatic.

1

Find Median from Data Stream: Two Balanced Heaps

HardSignature problem

Problem

Numbers arrive one at a time. After any number of insertions you may be asked for the median of everything seen so far. The median is the middle value when the count is odd, and the average of the two middle values when it is even.

Implement MedianFinder:
- addNum(num) ingests one number from the stream.
- findMedian() returns the median of all numbers added so far.

Both operations must be efficient enough to interleave freely over a long stream.

Input: addNum(1), addNum(2), findMedian()

Output: 1.5

Two numbers, so the median is their average.

Input: ...then addNum(3), findMedian()

Output: 2.0

Now [1,2,3], so the middle value is 2.

How this uses the pattern

Keep a max-heap of the smaller half and a min-heap of the larger half, sizes within one. The median reads off the heap tops in O(1); each insert is O(log n).

Find Median from Data Stream: Two Balanced Heaps

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["MedianFinder",[]],["addNum",[1]],["addNum",[2]],["findMedian",[]],["addNum",[3]],["findMedian",[]]]Expected: [null,null,null,1.5,null,2.0]

Input: [["MedianFinder",[]],["addNum",[6]],["findMedian",[]],["addNum",[10]],["addNum",[2]],["findMedian",[]]]Expected: [null,null,6.0,null,null,6.0]

Input: [["MedianFinder",[]],["addNum",[5]],["addNum",[5]],["addNum",[5]],["addNum",[5]],["findMedian",[]]]Expected: [null,null,null,null,null,5.0]

Need a hint? (3 available)

The Okta angle

This is the most-repeated named coding problem in the Okta loop, reported as its own staff round and expected with the optimal two-heap solution rather than a re-sort. Okta interviewers push on the balancing logic: how you keep the two halves within one element of each other, and why that invariant makes the median a constant-time peek. Be ready to explain why a single sorted structure is O(n) per insert and the two heaps are O(log n).

Take it further

A common escalation constrains the values, for example "every number is an integer between 0 and 100." That unlocks a counting-array solution: bucket by value, and the median is found by walking the buckets to the middle rank. Inserts drop to O(1) and the median walk is bounded by the fixed range, not the stream length.

Show solution & walkthrough

2

Product of Array Except Self: Prefix/Suffix Sweep

MediumCommonly asked

Problem

Given an integer array nums, return an array answer where answer[i] is the product of every element of nums except nums[i].

You must solve it without using the division operator, and the intended solution runs in O(n) time. The array may contain zeros and negative numbers.

Input: nums = [1,2,3,4]

Output: [24,12,8,6]

answer[0] = 2*3*4 = 24, answer[1] = 1*3*4 = 12, and so on.

Input: nums = [-1,1,0,-3,3]

Output: [0,0,9,0,0]

Only the slot holding the single zero gets a non-zero product; every other slot multiplies in that zero.

How this uses the pattern

Two passes: one accumulating the product of everything to the left of each index, one accumulating everything to the right, multiplied together.

Product of Array Except Self: Prefix/Suffix Sweep

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[1,2,3,4]]Expected: [24,12,8,6]

Input: [[-1,1,0,-3,3]]Expected: [0,0,9,0,0]

Input: [[2,3]]Expected: [3,2]

Input: [[0,0,5]]Expected: [0,0,0]

Need a hint? (3 available)

The Okta angle

This has opened an Okta first-round coding screen paired with a graph problem, so it is a warm-up that still has to be clean. The no-division rule is the whole test: it blocks the one-line "total product / nums[i]" answer and forces the prefix/suffix idea. Interviewers here want you to state the two-pass plan and its O(n) time and O(1) extra space (the output array does not count) before you write a line.

Take it further

The common escalation is to allow division and ask you to handle it robustly. That sounds easier but hides a trap: a single zero makes total / nums[i] a divide-by-zero, and two or more zeros make every answer zero. The clean division solution counts zeros first, then branches.

Show solution & walkthrough

3

Insert Delete GetRandom O(1): Duplicates Allowed

HardCommonly asked

Problem

Design a collection that supports inserting values, removing values, and returning a uniformly random element, all in average O(1) time. Duplicate values are allowed, so the same value can be stored several times.

Implement RandomizedCollection:
- insert(val) adds one occurrence of val and returns true if val was not already present, false otherwise.
- remove(val) removes one occurrence of val if present and returns whether anything was removed.
- getRandom() returns an element chosen uniformly at random from the current multiset, so a value stored three times is three times as likely to be returned.

Input: insert(1), insert(1), insert(2), remove(1), getRandom()

Output: true, false, true, true, then 1 or 2

After the removes the collection holds one 1 and one 2, so getRandom returns each with probability 1/2.

How this uses the pattern

Keep a flat list of values for O(1) random access, plus a map from each value to the SET of indices where it currently lives. Remove by swapping the target with the last element.

Insert Delete GetRandom O(1): Duplicates Allowed

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["RandomizedCollection",[]],["insert",[1]],["insert",[1]],["insert",[2]],["remove",[1]],["insert",[3]],["remove",[2]]]Expected: [null,true,false,true,true,true,true]

Input: [["RandomizedCollection",[]],["insert",[5]],["insert",[5]],["remove",[5]],["remove",[5]],["remove",[5]]]Expected: [null,true,false,true,true,false]

Input: [["RandomizedCollection",[]],["remove",[9]],["insert",[9]],["remove",[9]],["remove",[9]]]Expected: [null,false,true,true,false]

Need a hint? (3 available)

The Okta angle

This has opened an Okta staff coding loop, and it is the design-with-hashing archetype in its hardest common form. Okta wants the reasoning out loud. Why does a plain list make remove O(n)? Why does a plain map lose the ability to pick a uniform random element? And why do the two together, with a swap-remove, hit O(1) on all three? The duplicates twist is the escalation on the no-duplicates version, so expect to justify why an index set per value is what makes it work.

Take it further

A frequent contrast is the no-duplicates version, RandomizedSet. It is genuinely simpler: each value maps to a single index instead of a set of indices, so remove is one reassignment with no set surgery. Being able to derive one from the other on the spot is the signal they want.

Show solution & walkthrough

4

Top Users by Score: Bounded Heap Selection

MediumCommonly asked

Problem

You are given a list of score events, each a pair [userId, score]. A user may appear many times. Return the k users with the highest single best score, ordered from highest to lowest. Break ties between equal best scores by smaller userId first.

If a user posts several scores, only their maximum counts toward the ranking.

Input: events = [[1,50],[2,80],[1,90],[3,70],[2,60]], k = 2

Output: [1,2]

Best scores are user 1 -> 90, user 2 -> 80, user 3 -> 70. The top two are users 1 and 2.

Input: events = [[1,90],[2,90],[3,50]], k = 2

Output: [1,2]

Users 1 and 2 tie at 90; the smaller id (1) ranks first.

How this uses the pattern

Reduce to each user's best score in a hash map, then use a size-k min-heap to keep only the top k without sorting everyone.

Top Users by Score: Bounded Heap Selection

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[[1,50],[2,80],[1,90],[3,70],[2,60]], 2]Expected: [1,2]

Input: [[[1,90],[2,90],[3,50]], 2]Expected: [1,2]

Input: [[[7,10],[8,40],[9,40],[7,55]], 2]Expected: [7,8]

Input: [[[4,20]], 3]Expected: [4]

Need a hint? (3 available)

The Okta angle

An Okta coding round posed exactly this shape: use a priority queue to sort users by their highest score. It is the practical face of the heap pattern, where the win is selecting the top k with a bounded heap rather than sorting the whole population. Okta interviewers care that you reduce to each user's best first, then reason about why a size-k heap is O(n log k) and beats a full O(n log n) sort when k is small.

Take it further

The natural variant is to rank by cumulative score instead of the single best: sum every user's events rather than taking the max. The selection machinery is identical; only the aggregation step changes, which is a clean way to show you separated "how you score a user" from "how you pick the top k."

Show solution & walkthrough