Implement bitmap-based block allocator

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.