Implement bitmap-based block allocator

Q: Implement bitmap-based block allocator

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

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

Q: What role is this question designed for?

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

Question

Loading...

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:

Constructor
- Initializes the allocator for M blocks (all free initially), or takes an initial bitmap state.
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.
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.
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.