Katkat
Back

Solve Five Coding Problems

OracleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This set tests proficiency across five key algorithmic domains: graph theory, array manipulation, numerical properties, cache design, and tree traversal.

Coding Challenge: Five-Part Proficiency Test

Please provide solutions for the following five tasks. For each, analyze the time and space complexity.

1. Connected Components

Given an undirected graph represented by an adjacency list adj, return the total number of connected components. def count_components(n: int, adj: dict) -> int

2. Minimum Swaps to Sort

Given an array of $n$ distinct integers, find the minimum number of swaps required to sort the array in ascending order. def min_swaps(nums: list[int]) -> int

3. Monotonic Digits

Given an integer n, return the largest number less than or equal to n such that the digits are in non-decreasing order (e.g., 332 -> 299). def largest_monotonic(n: int) -> int

4. LRU Cache Design

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get(key) and put(key, value) with O(1) average time complexity.

5. N-ary Tree Structural Equality

Given two N-ary trees, determine if they are structurally identical (the same shape and same values at each node). class Node: val; children: list[Node] def are_identical(root1: Node, root2: Node) -> bool

Example

Example for Task 2: Input: [4, 3, 2, 1] Output: 2 Explanation: Swap 4 and 1 -> [1, 3, 2, 4], then swap 3 and 2 -> [1, 2, 3, 4].

Edge Cases

  • Empty graphs or trees.
  • Arrays already sorted or in reverse order.
  • Cache operations with capacity 1.

Hints

Hint 1

For graph connectivity, consider using either BFS or DFS to traverse each unvisited node.

Hint 2

For the minimum swaps problem, treat the indices as a graph where an edge exists between an element's current position and its target sorted position.

Hint 3

For the LRU cache, a combination of a doubly linked list and a hash map is the standard approach to achieve O(1) performance.

Follow-up questions

  • How would your LRU cache implementation change if the cache had to be thread-safe in a multi-threaded environment?
  • For the N-ary tree equality check, how would you modify the algorithm if the order of children did not matter?
  • Can you solve the minimum swaps problem if the array contains duplicate values?