PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates implementation and algorithmic skills across core data structures and array/interval algorithms, specifically hashing (hash map design including collision handling and resizing), interval merging and intersection logic, and array optimization problems such as maximum container area and trapped rainwater.

  • easy
  • Amazon
  • Coding & Algorithms
  • Software Engineer

Implement Interview Coding Problems

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Solve the following independent coding tasks from a new-grad software engineering interview. 1. Implement a hash map from scratch. - Support integer keys and integer values. - Implement `put(key, value)`, `get(key)`, and `remove(key)`. - `get(key)` should return the stored value if the key exists; otherwise return `-1`. - Do not use built-in hash table, dictionary, map, set, or collection libraries. You may use primitive arrays and your own node/classes. - Handle collisions correctly and explain how your design could resize when the load factor becomes too high. 2. Solve interval problems. - Part A: Given an unsorted list of closed intervals `[start, end]`, merge all overlapping intervals and return a sorted list of non-overlapping intervals. - Part B follow-up: Given two lists of pairwise-disjoint, sorted closed intervals, return all intersections between intervals from the two lists. 3. Solve water-container array problems. - Part A: Given an array of non-negative integers where each value represents the height of a vertical line at that index, choose two lines that, together with the x-axis, form a container holding the maximum possible area of water. Return that maximum area. - Part B follow-up: Given an array of non-negative integers representing an elevation map, compute how much rain water can be trapped after raining.

Quick Answer: This question evaluates implementation and algorithmic skills across core data structures and array/interval algorithms, specifically hashing (hash map design including collision handling and resizing), interval merging and intersection logic, and array optimization problems such as maximum container area and trapped rainwater.

Part 1: Implement a Hash Map From Scratch

Process a sequence of hash-map operations without using Python's built-in dict, set, or any other hash-table library. Support integer keys and integer values with `put(key, value)`, `get(key)`, and `remove(key)`. Collisions must be handled correctly. Return the result of every `get` operation in order. A strong design uses separate chaining and can resize the bucket array when the load factor becomes too high.

Constraints

  • 0 <= len(operations) == len(arguments) <= 2 * 10^5
  • Each key and value is a signed 32-bit integer
  • `arguments[i]` has length 2 for `put` and length 1 for `get` and `remove`
  • Do not use built-in hash table types such as dict, map, set, or collections-based hash maps

Examples

Input: (["put", "put", "get", "put", "get", "remove", "get"], [[1, 10], [2, 20], [1], [2, 25], [2], [1], [1]])

Expected Output: [10, 25, -1]

Explanation: Basic insert, update, and delete operations.

Input: (["put", "put", "get", "get", "remove", "get", "get"], [[1, 7], [9, 3], [1], [9], [1], [9], [1]])

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

Explanation: Keys 1 and 9 collide when the initial capacity is 8, so this checks collision handling.

Input: ([], [])

Expected Output: []

Explanation: Edge case: no operations.

Input: (["put", "get", "get", "remove", "get"], [[-5, 4], [-5], [0], [-5], [-5]])

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

Explanation: Handles negative keys and missing keys.

Hints

  1. Use an array of buckets. Each bucket can store a linked list of key-value pairs to resolve collisions.
  2. Track how many keys are stored. When `size / capacity` gets too large, create a larger bucket array and rehash all existing nodes.

Part 2A: Merge Overlapping Intervals

Given an unsorted list of closed intervals `[start, end]`, merge all overlapping intervals and return a sorted list of non-overlapping intervals. Because the intervals are closed, `[1, 4]` and `[4, 5]` should be merged into `[1, 5]`.

Constraints

  • 0 <= len(intervals) <= 10^5
  • -10^9 <= start <= end <= 10^9
  • Intervals are closed, so sharing an endpoint counts as overlapping

Examples

Input: [[1, 3], [2, 6], [8, 10], [15, 18]]

Expected Output: [[1, 6], [8, 10], [15, 18]]

Explanation: The first two intervals overlap and merge into `[1, 6]`.

Input: [[1, 4], [4, 5]]

Expected Output: [[1, 5]]

Explanation: Closed intervals that touch at an endpoint are merged.

Input: []

Expected Output: []

Explanation: Edge case: empty input.

Input: [[5, 7]]

Expected Output: [[5, 7]]

Explanation: Edge case: a single interval stays unchanged.

Hints

  1. Sort the intervals by their start value first.
  2. Keep a result list and compare each interval with the last merged interval.

Part 2B: Find Intersections Between Two Sorted Interval Lists

You are given two lists of closed intervals. Each list is already sorted by start time, and within each list the intervals are pairwise disjoint. Return every intersection between an interval from the first list and an interval from the second list.

Constraints

  • 0 <= len(first_list), len(second_list) <= 10^5
  • -10^9 <= start <= end <= 10^9
  • Each input list is individually sorted and pairwise disjoint
  • Intervals are closed, so touching at one point produces a one-point intersection

Examples

Input: ([[0, 2], [5, 10], [13, 23], [24, 25]], [[1, 5], [8, 12], [15, 24], [25, 26]])

Expected Output: [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]

Explanation: This is the standard example with several overlaps and endpoint-only intersections.

Input: ([], [[1, 3], [5, 9]])

Expected Output: []

Explanation: Edge case: one list is empty.

Input: ([[1, 3], [5, 9]], [[3, 5], [7, 10]])

Expected Output: [[3, 3], [5, 5], [7, 9]]

Explanation: Closed intervals can intersect at a single endpoint.

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

Expected Output: []

Explanation: No overlap exists.

Hints

  1. Use two pointers, one for each list, because both lists are already sorted.
  2. For two current intervals, the overlap is `[max(start1, start2), min(end1, end2)]` if the start is not greater than the end.

Part 3A: Container With Most Water

Given an array of non-negative integers where `heights[i]` is the height of a vertical line at index `i`, choose two lines that together with the x-axis form a container. Return the maximum amount of water the container can hold.

Constraints

  • 0 <= len(heights) <= 10^5
  • 0 <= heights[i] <= 10^4
  • If fewer than two lines are given, the answer is 0

Examples

Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]

Expected Output: 49

Explanation: The best choice is height 8 at index 1 and height 7 at index 8.

Input: [1, 1]

Expected Output: 1

Explanation: Only one pair exists.

Input: [4]

Expected Output: 0

Explanation: Edge case: fewer than two lines.

Input: [0, 2, 0, 3, 1]

Expected Output: 4

Explanation: The best container uses heights 2 and 3 with width 2.

Hints

  1. The area formed by indices `l` and `r` is `(r - l) * min(heights[l], heights[r])`.
  2. Start with the widest container. To possibly improve the answer, move the pointer at the shorter line.

Part 3B: Trapping Rain Water

Given an array of non-negative integers representing an elevation map, compute how much rain water can be trapped after raining.

Constraints

  • 0 <= len(heights) <= 2 * 10^5
  • 0 <= heights[i] <= 10^5
  • If the array has fewer than three bars, the answer is 0

Examples

Input: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Expected Output: 6

Explanation: Several small basins together trap 6 units of water.

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

Expected Output: 9

Explanation: A classic example with multiple pits.

Input: []

Expected Output: 0

Explanation: Edge case: empty input.

Input: [5, 0, 5]

Expected Output: 5

Explanation: A simple bowl traps 5 units in the middle.

Hints

  1. Water above an index depends on the tallest bar to its left and the tallest bar to its right.
  2. You can solve this in O(n) time and O(1) extra space with two pointers and running left/right maximums.
Last updated: Jun 6, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,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

  • Implement Datacenter Router Commands - Amazon (hard)
  • Replace Delimited Tokens in a String - Amazon (medium)
  • Minimize Circular Redistribution Cost - Amazon (medium)
  • Find the Most Common Visit Pattern - Amazon (hard)
  • Maximize Value Under a Budget - Amazon (medium)