Solve theatre seating and ticker extraction
Problem Description
This interview consists of two independent coding tasks designed to assess your algorithmic thinking, data structure knowledge, and ability to handle specific constraints.
Task 1: Allocate Groups in a Movie Theater
You are given an integer n representing the total number of rows in a movie theater. Each row contains 10 seats, numbered 1 through 10. A list of already reserved seats is provided as pairs (row, seat).
A group of 4 people can be seated together only if all 4 seats are in the same row and fit entirely within one of the following predefined seat blocks:
- Seats
2through5 - Seats
4through7 - Seats
6through9
Your goal is to determine and return the maximum number of 4-person groups that can still be seated in the theater, given the current reservations.
Assumptions:
1 <= row <= n- Reserved seats may appear in any order.
- Each seat is reserved at most once.
Task 2: Extract Stock Tickers from a News Headline
You are provided with a news headline string and a dictionary. This dictionary maps each stock ticker (e.g., "AAPL", "TSLA") to one or more company aliases or keyword phrases (e.g., "apple", "apple inc", "tesla").
Your task is to write a function that identifies and returns all unique stock tickers mentioned in the given headline, based on the provided dictionary.
Requirements:
- Matching of aliases in the headline must be case-insensitive.
- Punctuation within the headline should be ignored during matching.
- Matches must correspond to whole words or whole phrases; partial substrings within longer words are not considered valid matches.
- If multiple aliases from the dictionary map to the same ticker and all match within the headline, that ticker should only be included once in the final output.
- The returned list of tickers must maintain the order of their first appearance in the headline.
- In cases where two or more aliases (potentially for different tickers) overlap at the same starting position in the headline, the longer phrase should be preferred as the match.
Example:
Given tickerMap = { "AAPL": ["apple", "apple inc"], "TSLA": ["tesla"] } and headline = "Apple Inc. rises after Tesla delivery report", the function should return ["AAPL", "TSLA"].
AI interview prep
Core dilemma
The central engineering conflict is the candidate's ability to pivot between two distinct problem types (combinatorial optimization/greedy vs. advanced string matching/data structures) within a single interview, demonstrating depth in both algorithmic domains and efficient implementation strategies under varying constraints.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Solve theatre seating and ticker extraction
Problem Description
This interview consists of two independent coding tasks designed to assess your algorithmic thinking, data structure knowledge, and ability to handle specific constraints.
Task 1: Allocate Groups in a Movie Theater
You are given an integer n representing the total number of rows in a movie theater. Each row contains 10 seats, numbered 1 through 10. A list of already reserved seats is provided as pairs (row, seat).
A group of 4 people can be seated together only if all 4 seats are in the same row and fit entirely within one of the following predefined seat blocks:
- Seats
2through5 - Seats
4through7 - Seats
6through9
Your goal is to determine and return the maximum number of 4-person groups that can still be seated in the theater, given the current reservations.
Assumptions:
1 <= row <= n- Reserved seats may appear in any order.
- Each seat is reserved at most once.
Task 2: Extract Stock Tickers from a News Headline
You are provided with a news headline string and a dictionary. This dictionary maps each stock ticker (e.g., "AAPL", "TSLA") to one or more company aliases or keyword phrases (e.g., "apple", "apple inc", "tesla").
Your task is to write a function that identifies and returns all unique stock tickers mentioned in the given headline, based on the provided dictionary.
Requirements:
- Matching of aliases in the headline must be case-insensitive.
- Punctuation within the headline should be ignored during matching.
- Matches must correspond to whole words or whole phrases; partial substrings within longer words are not considered valid matches.
- If multiple aliases from the dictionary map to the same ticker and all match within the headline, that ticker should only be included once in the final output.
- The returned list of tickers must maintain the order of their first appearance in the headline.
- In cases where two or more aliases (potentially for different tickers) overlap at the same starting position in the headline, the longer phrase should be preferred as the match.
Example:
Given tickerMap = { "AAPL": ["apple", "apple inc"], "TSLA": ["tesla"] } and headline = "Apple Inc. rises after Tesla delivery report", the function should return ["AAPL", "TSLA"].