How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at eBay.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at eBay during technical interviews.

Implement bitmap-based block allocator

Quick Overview

The bitmap-based block allocator evaluates understanding of data structures, contiguous allocation algorithms, and low-level state management; it is commonly asked to assess efficiency, correctness under constraints and API design in the Coding & Algorithms domain and focuses on practical application of algorithms and system-level implementation.

Company: eBay

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem 1: Bitmap-based block allocator (OOD/coding) You are implementing a simple block allocator backed by a bitmap. - There are `M` blocks, indexed `0..M-1`. - `bitmap[i] = 0` means the block is **free**; `bitmap[i] = 1` means **allocated**. Design a class `BitmapBlock` with at least the following methods: 1. **Constructor** - Initializes the allocator for `M` blocks (all free initially), or takes an initial bitmap state. 2. **`indexFind(start, n)`** - Finds the **leftmost** index `i >= start` such that blocks `[i, i+n-1]` are all free. - Returns that index `i`, or `-1` if no such contiguous range exists. 3. **`allocateFrom(start, n)`** - Allocates `n` **contiguous** free blocks, with the search beginning at `start`. - Uses `indexFind(start, n)` to locate a placement. - If allocation succeeds, marks those blocks as allocated and returns the starting index. - If allocation fails, returns `-1` and does not modify state. 4. **`countHoles()`** - Returns the number of **holes**, where a *hole* is a maximal contiguous run of free blocks (a maximal segment of 0s). - Example: `bitmap = 001110011000` has holes `00`, `00`, `000` → returns `3`. ### Constraints (reasonable interview assumptions) - `1 <= M <= 10^6` - `0 <= start < M` - `1 <= n <= M` ### Part B Write a small `main()` (or test harness) that constructs a `BitmapBlock`, calls the methods above, and prints results for a few cases. --- ## Problem 2: Validate US phone numbers with a regex (coding) Write a regular expression (or a function using a regex) that validates **US 10-digit phone numbers** with flexible formatting. Assume the phone number contains exactly 10 digits total, but may include formatting characters: - The 3-digit area code may optionally be wrapped in parentheses: `(123)` or `123`. - Separators between groups may be optional and may include spaces and/or hyphens (e.g., `-`, ` `, or no separator). - No other characters are allowed. ### Examples (you may define the exact accepted set as part of the problem statement) - Valid examples could include: `1234567890`, `123-456-7890`, `(123)456-7890`, `(123) 456 7890`. - Invalid examples include: wrong digit count, letters, or misplaced parentheses. Produce a regex that matches all valid forms and rejects invalid ones.

Quick Answer: The bitmap-based block allocator evaluates understanding of data structures, contiguous allocation algorithms, and low-level state management; it is commonly asked to assess efficiency, correctness under constraints and API design in the Coding & Algorithms domain and focuses on practical application of algorithms and system-level implementation.

Part 1: Simulate a Bitmap-Based Block Allocator

Implement a bitmap-backed block allocator. There are M blocks indexed 0..M-1. A bit value of 0 means the block is free, and 1 means allocated. Write a function that creates an allocator from either an all-free state or an initial bitmap, then processes operations in order. Supported operations: - ('indexFind', start, n): return the leftmost index i >= start such that blocks [i, i+n-1] are all free, or -1 if no such range exists. - ('allocateFrom', start, n): use indexFind(start, n), mark those n blocks allocated if found, and return the starting index; otherwise return -1 without changing state. - ('countHoles',): return the number of holes, where a hole is a maximal contiguous run of free blocks. Return a list containing the result of each operation in order.

Constraints

1 <= m <= 10^6
bitmap is either None or has length exactly m
0 <= start < m for every operation that uses start
1 <= n <= m for every operation that uses n
Operations are only 'indexFind', 'allocateFrom', or 'countHoles'

Examples

Input: (8, None, [('indexFind', 0, 3), ('allocateFrom', 0, 3), ('indexFind', 0, 3), ('countHoles',), ('allocateFrom', 3, 3), ('countHoles',)])

Expected Output: [0, 0, 3, 1, 3, 1]

Explanation: Start with 00000000. After allocating 3 blocks from index 0, the next free run of length 3 starts at 3. Hole counts are computed after each state change.

Input: (12, '001110011000', [('countHoles',), ('indexFind', 0, 3), ('allocateFrom', 0, 3), ('indexFind', 0, 2), ('countHoles',)])

Expected Output: [3, 9, 9, 0, 2]

Explanation: Initial holes are '00', '00', and '000'. The only free run of length 3 starts at index 9.

Input: (1, None, [('indexFind', 0, 1), ('allocateFrom', 0, 1), ('countHoles',), ('allocateFrom', 0, 1)])

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

Explanation: Edge case with a single block. Once allocated, there are no holes and no further allocation is possible.

Input: (6, '110011', [('indexFind', 2, 2), ('allocateFrom', 2, 2), ('countHoles',), ('indexFind', 0, 1)])

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

Explanation: The free run at indices 2..3 can be found and allocated. After that, all blocks are allocated.

Hints

For indexFind, scan from left to right while tracking the current length of the free run.
For countHoles, count how many times you enter a free segment from the left.

Part 2: Validate US Phone Numbers with a Regex

Write a function that returns True if a string is a valid US 10-digit phone number and False otherwise. Accepted format rules for this problem: - The phone number must contain exactly 10 digits total. - The area code is either exactly 3 digits, like '123', or those 3 digits wrapped in parentheses, like '(123)'. - Between the 3-digit area code, the next 3 digits, and the final 4 digits, you may have zero or more separator characters. - A separator character may only be a space or a hyphen. - No other characters are allowed. - Parentheses are only allowed around the area code and must be properly matched. Examples of valid forms under these rules include '1234567890', '123-456-7890', '(123)456-7890', and '(123) 456 7890'.

Constraints

0 <= len(phone_number) <= 50
Only ASCII input needs to be considered
The validation must reject letters, misplaced parentheses, and wrong digit counts

Examples

Input: ('1234567890',)

Expected Output: True

Explanation: Ten digits with no separators is valid.

Input: ('(123) 456-7890',)

Expected Output: True

Explanation: Parenthesized area code with spaces and hyphens is valid.

Input: ('123-45-7890',)

Expected Output: False

Explanation: The middle group has only 2 digits, so the total digit grouping is invalid.

Input: ('123) 456-7890',)

Expected Output: False

Explanation: Parentheses are misplaced and not balanced around the area code.

Input: ('',)

Expected Output: False

Explanation: Edge case: an empty string is not a valid phone number.

Hints

Use re.fullmatch so the entire string must match, not just a prefix.
Treat the area code as two alternatives: either '\\d{3}' or '\\(\\d{3}\\)'.

Quick Overview