Oracle·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Oracle SWE interview with three coding and design problems. The questions ranged from classic data structure implementation to a slightly tricky array optimization problem. Nothing too wild but the second question had a subtle edge case that I think I fumbled.

Questions Asked (3)

Design and implement an autocomplete service with an insert(word) method and a suggest(prefix) method that returns up to five words starting with that prefix. Use a trie, explain your ordering strategy, and analyze time and space complexity.

Algorithms & Data StructuresSystem Design

Author's notes

I'd done trie problems before so this felt familiar at first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and assumptions, then describe the trie data structure and how it supports insert and suggest operations. Explain the ordering strategy (e.g., lexicographical or frequency-based) and how to efficiently retrieve up to five suggestions. Finally, analyze time and space complexity for both operations.

Pro tip: Mention that storing the top suggestions at each node can optimize the suggest operation to O(1) after the prefix is found, but this increases space usage. Discuss the trade-off between time and space, and consider whether the word list is static or dynamic.

1. Clarify Requirements and Assumptions

Ask about expected input size, whether suggestions should be ordered by frequency or lexicographically, and if the word list is static or dynamic. Confirm that the service should return up to five words.

2. Design the Trie Structure

Describe a trie where each node represents a character and has children pointers (e.g., array or hashmap) and a flag indicating the end of a word. Optionally, store additional data like frequency or top suggestions at each node.

3. Implement insert(word)

Traverse the trie, creating nodes as needed, and mark the final node as a word end. If using frequency, increment the count. Update any cached top suggestions along the path if applicable.

4. Implement suggest(prefix)

Traverse the trie to the node corresponding to the prefix. Then perform a traversal (e.g., DFS) to collect up to five words in the desired order. If using cached suggestions, return them directly.

5. Analyze Complexity and Trade-offs

For insert: O(L) time, O(L) space per word. For suggest: O(P + K) where P is prefix length and K is the number of nodes visited to collect suggestions, or O(P) if cached. Discuss space overhead of caching and alternatives like ternary search trees.

Key Points to Mention

Trie node structure: children (array of size 26 or hashmap), isEndOfWord flag, optional frequency or top suggestions list.
Ordering strategy: lexicographical order via DFS with sorted children, or frequency-based by storing counts and using a priority queue.
Efficient retrieval of top 5: either traverse and collect all words then sort, or maintain a min-heap of size 5 during traversal, or precompute top suggestions at each node.
Time complexity: insert O(L), suggest O(P + K) where K is the number of nodes visited to collect up to 5 words; with caching, suggest O(P).
Space complexity: O(N*L) for trie, where N is number of words and L is average length; caching adds O(N*L) in worst case but can be optimized.
Trade-offs: caching improves suggest time but increases insert time and space; consider if the dataset is static (precompute) or dynamic (update on insert).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Given an array of integer values and a parallel array of 0/1 flags indicating whether each index is already decrypted, plus an integer k, find the maximum score you can achieve by selecting at most one contiguous subarray of length at most k and treating all its indices as decrypted. Score is the sum of values at all decrypted indices. Solve in O(n).

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one tripped me up more than I expected.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Reframe the problem as maximizing the gain from flipping a window of length at most k, where gain is the sum of values at indices that are not yet decrypted. Use a sliding window to compute the maximum gain in O(n), then add the base score of already decrypted indices.

Pro tip: Clarify edge cases upfront (e.g., k=0, all decrypted, negative values) and mention that the window can be shorter than k; this shows attention to detail and avoids incorrect assumptions.

1. Understand the problem and define terms

Restate the problem: you have a base score from already decrypted indices, and you can decrypt a contiguous subarray of length at most k. The goal is to maximize the total score.

2. Compute base score and gain array

Calculate the sum of values where flag is 1 (base score). Create an array where each element is the value if flag is 0, else 0, representing the potential gain from decrypting that index.

3. Find maximum subarray sum with length constraint

Use a sliding window of size up to k to find the maximum sum of the gain array over any contiguous subarray of length at most k. This can be done in O(n) by maintaining a running sum and updating the maximum.

4. Combine and return result

Add the maximum gain to the base score to get the maximum possible total score. Handle edge cases such as k=0 or no negative gains by ensuring the window sum is at least 0 (i.e., you can choose an empty subarray).

Key Points to Mention

Time complexity O(n) and space complexity O(1) or O(n) depending on implementation.
Sliding window technique for maximum sum subarray of length at most k.
Handling of negative values: the optimal window might be empty if all gains are negative.
Edge cases: k=0, k >= n, all flags 1, all flags 0.
The base score is fixed; only the gain from flipping 0s to 1s matters.
The window length can be less than k; we are not forced to take exactly k elements.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Given a list of closed integer ranges, merge all overlapping or adjacent ranges and return the result sorted by start. Two ranges should merge if they touch, meaning the end of one is at least the start of the next minus one. Implement the function and analyze complexity.

Algorithms & Data Structures

Author's notes

Pretty standard merge intervals.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the definition of 'touching' and confirm input assumptions. Then, sort the ranges by start, iterate through them, and merge overlapping or adjacent ranges into a result list. Finally, analyze time and space complexity, noting the O(n log n) sorting step and O(n) merging step.

Pro tip: Mention that sorting is necessary for efficiency and that in-place merging can save space if the input can be modified. Also, discuss edge cases like empty input or single range to show thoroughness.

1. Clarify requirements and edge cases

Ask about input format, whether ranges are inclusive, and if the input can be modified. Confirm that 'touching' means end + 1 >= next start.

2. Sort the ranges

Sort the list of ranges by their start value. This ensures that any overlapping or adjacent ranges will be consecutive.

3. Iterate and merge

Initialize a result list with the first range. For each subsequent range, if it overlaps or touches the last range in the result, merge them by updating the end; otherwise, append it.

4. Analyze complexity

State that sorting takes O(n log n) time, merging takes O(n) time, so overall O(n log n). Space is O(n) for the result, or O(1) extra if merging in-place.

Key Points to Mention

Sorting by start is crucial for linear merging.
Merge condition: current.start <= last.end + 1 (for integer ranges).
Time complexity: O(n log n) due to sorting.
Space complexity: O(n) for output, or O(1) extra if in-place.
Edge cases: empty list, single range, all ranges merge into one.
Stability of sorting not required, but sorting by start is sufficient.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.