Katkat
Back

Solve Three Coding Interview Problems

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate sorted data, optimize for mathematical properties, and implement efficient data structures for string prefix operations.

Problem 1: Merge and Deduplicate

Given two sorted lists of integers A and B, return a single sorted list containing all unique elements from both. Do not use built-in set functions.

Problem 2: Quadratic Extremum

Given a quadratic function f(x) = ax^2 + bx + c and an integer range [L, R], find the integer x within this range that minimizes f(x). You may assume a is positive.

Problem 3: Prefix Search

Design a data structure that supports the following operations for a dictionary of words:

  • insert(word): Adds a word to the structure.
  • has_prefix(prefix): Returns true if any word in the structure starts with the given prefix, false otherwise.

Examples

Problem 1: Input: A = [1, 2, 4], B = [2, 3, 4] Output: [1, 2, 3, 4]

Problem 2: Input: a=1, b=-4, c=4, L=0, R=5 Output: 2 (since the vertex is at -b/2a = 2, which is inside [0, 5])

Constraints

  • For Problem 1, length of lists 0`.
  • For Problem 3, focus on average case performance for prefixes.

Hints

Hint 1

For merging, use a two-pointer approach and check if the current element is equal to the last added element in the result list to skip duplicates.

Hint 2

For the quadratic function, the minimum of a parabola `ax^2 + bx + c` occurs at `x = -b / 2a`; check the integers immediately surrounding this value that fall within `[L, R]`.

Hint 3

For the prefix search, a Trie (prefix tree) is the most efficient structure, where each node represents a character path.

Follow-up questions

  • How would your approach for Problem 1 change if the input lists were not sorted?
  • How would the solution for Problem 2 change if the parabola opened downwards (a < 0)?
  • How could you modify the Trie to return the count of words that share a specific prefix?