Solve three DSA problems: trie, window, intervals
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
1) Design and implement an autocomplete service. Support insert(word) to add a word and suggest(prefix) to return up to five existing words that start with prefix; if fewer than five exist, return all of them. Use a trie-based design; specify the ordering of suggestions (e.g., lexicographic) and the time/space complexities.
2) You are given two arrays: value[0..n-1] of integers and decrypted[0..n-1] of 0/1 flags (1 means already decrypted), plus an integer k. You may perform at most one operation: choose a contiguous subarray whose length is at most k and treat every index in that subarray as decrypted for scoring. The score is the sum of value[i] over all indices that are decrypted after the operation. Compute the maximum achievable score and provide an O(n) algorithm.
3) You are given a list of closed integer ranges [li, ri]. Merge any ranges that overlap or touch (i.e., ri >= lj -
1) and return the merged list sorted by start. Implement the function and analyze its complexity.
Quick Answer: This multi-part question evaluates proficiency with core data structures and algorithms — specifically trie-based string indexing and autocomplete design, sliding-window/prefix-sum optimization for maximizing a one-shot decrypted range, and interval merging — within the Coding & Algorithms domain, emphasizing practical implementation, complexity analysis and edge-case handling. It is commonly asked in technical interviews to assess the ability to design efficient data structures and linear-time algorithms, reason about time/space trade-offs and ordering constraints, and demonstrate both conceptual understanding and practical application through clear complexity analysis.