PracHub
QuestionsPremiumLearningGuidesInterview PrepCoaches

Quick Overview

This problem set evaluates proficiency in core algorithms and data structures, including graph traversal and connected-component identification, array partitioning and minimum-swap reasoning, digit-level monotonicity and numerical manipulation, fixed-capacity cache design with O(1) access and eviction policies, and structural comparison of N-ary trees. These tasks are commonly asked in technical interviews to test algorithmic problem-solving and design thinking within the Coding & Algorithms domain, requiring both conceptual understanding and practical implementation skills along with explicit time and space complexity analysis.

  • medium
  • Oracle
  • Coding & Algorithms
  • Software Engineer

Solve Five Coding Problems

Company: Oracle

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

The interview included several coding tasks. Solve each of the following and discuss time and space complexity: 1. Given a 2D grid where `'1'` represents land and `'0'` represents water, return the number of connected land regions. Cells are connected only vertically and horizontally. 2. Given an integer array, you may swap any two elements. Find the minimum number of swaps required so that all even numbers appear before all odd numbers. 3. Given a non-negative integer `n`, return the largest integer less than or equal to `n` whose digits are in nondecreasing order from left to right. 4. Design a fixed-capacity key-value cache with `get(key)` and `put(key, value)` in `O(1)` time. When the cache is full, evict the least recently used entry. Follow-up: explain how to support per-entry expiration. 5. Given two N-ary trees, determine whether they are structurally identical and contain the same values in corresponding nodes. Follow-up: describe an iterative solution.

Quick Answer: This problem set evaluates proficiency in core algorithms and data structures, including graph traversal and connected-component identification, array partitioning and minimum-swap reasoning, digit-level monotonicity and numerical manipulation, fixed-capacity cache design with O(1) access and eviction policies, and structural comparison of N-ary trees. These tasks are commonly asked in technical interviews to test algorithmic problem-solving and design thinking within the Coding & Algorithms domain, requiring both conceptual understanding and practical implementation skills along with explicit time and space complexity analysis.

Part 1: Count Connected Land Regions in a 2D Grid

Given a rectangular 2D grid of characters where '1' means land and '0' means water, return the number of connected land regions. Two land cells belong to the same region only if they touch vertically or horizontally.

Constraints

  • 0 <= number of rows, columns <= 200
  • The grid is rectangular if non-empty
  • Cells are only connected in 4 directions: up, down, left, right

Examples

Input: [['1','1','0','0'],['0','1','0','1'],['1','0','0','1'],['0','0','1','1']]

Expected Output: 3

Explanation: There are three separate land regions.

Input: []

Expected Output: 0

Explanation: An empty grid contains no land.

Input: [['1']]

Expected Output: 1

Explanation: A single land cell is one region.

Input: [['0','0'],['0','0']]

Expected Output: 0

Explanation: There is no land at all.

Hints

  1. Scan every cell. When you find unvisited land, that starts a new region.
  2. Use DFS or BFS to mark every cell in the same region as visited.

Part 2: Minimum Swaps to Put All Even Numbers Before All Odd Numbers

Given an integer array, you may swap any two elements in one move. Return the minimum number of swaps needed so that every even number appears before every odd number. The relative order inside the even group or odd group does not matter.

Constraints

  • 0 <= len(nums) <= 200000
  • -10^9 <= nums[i] <= 10^9
  • Any two positions may be swapped in one operation

Examples

Input: [3,8,5,12,7,6]

Expected Output: 2

Explanation: There are 3 evens, so positions 0..2 must be even. Two odd values are currently in that block.

Input: []

Expected Output: 0

Explanation: No elements means no swaps.

Input: [2,4,6]

Expected Output: 0

Explanation: All values are already even, so the condition is already satisfied.

Input: [1,3,5,2]

Expected Output: 1

Explanation: Only one even exists, so the first position should be even. Swap 1 with 2.

Input: [-2,-3,-4,-5]

Expected Output: 1

Explanation: Two evens exist; one odd appears in the first two positions.

Hints

  1. If there are k even numbers total, then the first k positions must eventually contain all evens.
  2. Count how many odd numbers are currently inside that first block.

Part 3: Largest Integer Less Than or Equal to n with Nondecreasing Digits

Given a non-negative integer n, return the largest integer x such that x <= n and the digits of x are in nondecreasing order from left to right. For example, 1234 is valid, but 1324 is not because 3 > 2.

Constraints

  • 0 <= n <= 10^18
  • The answer must be less than or equal to n
  • Digits in the answer must satisfy d[i] <= d[i+1]

Examples

Input: 1234

Expected Output: 1234

Explanation: The digits are already nondecreasing.

Input: 332

Expected Output: 299

Explanation: 299 is the largest number <= 332 whose digits are nondecreasing.

Input: 10

Expected Output: 9

Explanation: 10 is not valid because 1 > 0.

Input: 0

Expected Output: 0

Explanation: Zero is already valid.

Input: 120

Expected Output: 119

Explanation: 119 is the largest valid answer not exceeding 120.

Hints

  1. Look for the first place from right to left where a digit is smaller than the digit before it.
  2. After decreasing a digit, making every digit to its right equal to 9 gives the largest possible result.

Part 4: Implement a Fixed-Capacity O(1) LRU Cache

Implement an LRU (Least Recently Used) cache with a fixed capacity. Support two operations: put(key, value) inserts or updates a key, and get(key) returns the value if present or -1 otherwise. Both operations must run in O(1) time. When the cache is full and a new key is inserted, evict the least recently used key.

Constraints

  • 0 <= capacity <= 10^5
  • 1 <= number of operations <= 2 * 10^5
  • Keys and values are integers
  • get and put should be O(1) average time

Examples

Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('put', 4, 4), ('get', 1), ('get', 3), ('get', 4)])

Expected Output: [None, None, 1, None, -1, None, -1, 3, 4]

Explanation: Classic LRU behavior: 2 is evicted first, then 1.

Input: (2, [('put', 1, 1), ('put', 2, 2), ('put', 1, 10), ('put', 3, 3), ('get', 1), ('get', 2), ('get', 3)])

Expected Output: [None, None, None, None, 10, -1, 3]

Explanation: Updating key 1 makes it most recently used, so key 2 is evicted.

Input: (1, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('get', 2)])

Expected Output: [None, None, -1, 2]

Explanation: With capacity 1, inserting 2 evicts 1.

Input: (0, [('put', 1, 1), ('get', 1)])

Expected Output: [None, -1]

Explanation: A cache with capacity 0 stores nothing.

Hints

  1. A hash map gives O(1) access to nodes by key.
  2. A doubly linked list can maintain recency order so you can move nodes and evict the tail in O(1).

Part 5: LRU Cache with Per-Entry Expiration

Implement a fixed-capacity cache with LRU eviction and per-entry expiration. Each put operation includes a TTL (time to live). An entry inserted at time t with ttl expires at time t + ttl and should not be returned by get at or after that time. If the cache is full, remove expired entries first; if it is still full, evict the least recently used unexpired entry.

Constraints

  • 0 <= capacity <= 10^5
  • 1 <= number of operations <= 2 * 10^5
  • Timestamps are nondecreasing
  • ttl >= 0
  • Keys and values are integers

Examples

Input: (2, [('put', 0, 1, 1, 5), ('put', 1, 2, 2, 5), ('get', 2, 1), ('put', 6, 3, 3, 5), ('get', 6, 1), ('get', 7, 3)])

Expected Output: [None, None, 1, None, -1, 3]

Explanation: By time 6, the earlier entries have expired, so key 3 can be inserted without an LRU eviction.

Input: (2, [('put', 0, 1, 1, 10), ('put', 1, 2, 2, 10), ('put', 2, 3, 3, 10), ('get', 3, 1), ('get', 3, 2), ('get', 3, 3)])

Expected Output: [None, None, None, -1, 2, 3]

Explanation: No entries are expired, so inserting key 3 evicts the least recently used key 1.

Input: (1, [('put', 0, 1, 10, 0), ('get', 0, 1), ('put', 1, 1, 20, 2), ('get', 2, 1), ('get', 3, 1)])

Expected Output: [None, -1, None, 20, -1]

Explanation: TTL 0 means the first insertion expires immediately. The second insertion expires at time 3.

Input: (0, [('put', 0, 1, 1, 10), ('get', 5, 1)])

Expected Output: [None, -1]

Explanation: A cache with capacity 0 stores nothing.

Hints

  1. You still need hash map + doubly linked list for LRU order.
  2. A min-heap of expiration times can help lazily remove expired entries before each operation.

Part 6: Check Whether Two N-ary Trees Are Identical

Two N-ary trees are identical if they have the same structure, the same number of children at every corresponding node, and equal values in corresponding positions. Child order matters. Each tree is represented as either None or [value, children], where children is a list of child trees.

Constraints

  • 0 <= number of nodes in each tree <= 10^5
  • Node values are integers
  • Child order matters
  • Input trees are well-formed recursive list representations

Examples

Input: ([1, [[2, []], [3, []]]], [1, [[2, []], [3, []]]])

Expected Output: True

Explanation: Both trees have the same values and child structure.

Input: ([1, [[2, []]]], [1, [[3, []]]])

Expected Output: False

Explanation: The corresponding child values differ.

Input: ([1, [[2, []], [3, []]]], [1, [[3, []], [2, []]]])

Expected Output: False

Explanation: Child order matters, so these trees are not identical.

Input: (None, None)

Expected Output: True

Explanation: Two empty trees are identical.

Input: (None, [1, []])

Expected Output: False

Explanation: One tree is empty and the other is not.

Hints

  1. Compare the current node values first.
  2. Then compare the number of children and recursively compare each child pair in order.

Part 7: Iteratively Check Whether Two N-ary Trees Are Identical

Solve the same N-ary tree identity problem, but do it iteratively instead of recursively. Two trees are identical if they have the same structure and the same values at corresponding nodes, with child order preserved. Each tree is represented as either None or [value, children], where children is a list of child trees.

Constraints

  • 0 <= number of nodes in each tree <= 10^5
  • Node values are integers
  • Child order matters
  • Use an explicit stack or queue instead of recursion

Examples

Input: ([1, [[2, [[3, [[4, []]]]]]]], [1, [[2, [[3, [[4, []]]]]]]])

Expected Output: True

Explanation: The trees are identical, even across multiple levels.

Input: ([1, [[2, []], [3, []]]], [1, [[2, [[3, []]]]]])

Expected Output: False

Explanation: The structures differ.

Input: (None, None)

Expected Output: True

Explanation: Two empty trees are identical.

Input: ([1, [[2, []], [4, []]]], [1, [[2, []], [3, []]]])

Expected Output: False

Explanation: The second child values differ.

Hints

  1. Store pairs of nodes to compare in a stack or queue.
  2. When comparing children, push corresponding child pairs in reverse order if you want left-to-right processing with a stack.
Last updated: May 7, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Compute letter frequencies from encoded string - Oracle (medium)
  • Count closed islands in a grid - Oracle (easy)
  • Implement in-memory data structures and booking API - Oracle (hard)
  • Implement an LRU cache - Oracle (medium)
  • Return a valid course completion order - Oracle (medium)