Implement Calendar, Tokenizer, and Meeting Optimizer
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement the following three coding tasks.
1. **Calendar insertion check**
You are given a list of existing calendar events, where each event is a half-open interval `[start, end)`. The existing calendar is valid, meaning no two existing events overlap. Given one new event `[newStart, newEnd)`, determine whether it can be added without creating any overlap. Return `true` if it can be scheduled and `false` otherwise.
2. **Mixed-delimiter string tokenizer**
Given a string containing lowercase letters, spaces, and the character `*`, tokenize it using these rules:
- If the string contains no `*`, split on one or more spaces and ignore empty tokens.
- If the string contains at least one `*`, split on `*`, discard empty segments created by consecutive `*`, and trim leading and trailing spaces from each remaining segment while preserving spaces inside the segment.
Examples:
- `"a bc d"` -> `["a", "bc", "d"]`
- `"a*a aa*bb"` -> `["a", "a aa", "bb"]`
- `"a *bd**c"` -> `["a", "bd", "c"]`
3. **Investor meeting optimization**
A founder wants to meet investors. There are `n` investors, and investor `i` is available on a subset of days `availability[i]`. The founder can choose at most `k` distinct days on which to schedule meetings. If a day is chosen, the founder can meet every investor who is available on that day, and each investor counts at most once even if they are available on multiple chosen days. Compute the maximum number of distinct investors the founder can meet.
Assume the total number of distinct days is small enough (for example, at most 20) so that a dynamic-programming solution is feasible.
Quick Answer: This question evaluates competencies in interval scheduling and overlap detection, custom string tokenization and parsing rules, and combinatorial optimization using subset/bitmask dynamic programming, reflecting algorithmic problem solving, edge-case handling, and efficient data-structure use.