Solve theatre seating and ticker extraction
Quick Overview
This question evaluates algorithmic problem-solving skills across two areas: efficient seat-allocation and interval occupancy reasoning for grouping in a constrained seating layout, and robust string processing with phrase-based, case-insensitive matching and mapping to ticker identifiers.
Implement the following two coding tasks.
- Allocate groups in a movie theater
You are given an integer n representing the number of rows in a movie theater. Each row has seats 1 through 10. Some seats are already reserved, represented 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 in one of these seat blocks:
-
seats
2-5 -
seats
4-7 -
seats
6-9
Return the maximum number of 4-person groups that can still be seated.
Assume:
-
1 <= row <= n - reserved seats may appear in any order
- each seat is reserved at most once
- Extract stock tickers from a news headline
You are given:
- a news headline string
- a dictionary mapping each stock ticker to one or more company aliases or keyword phrases
Write a function that returns all tickers mentioned in the headline.
Requirements:
- matching is case-insensitive
- punctuation should be ignored
- matches must be whole words or whole phrases, not substrings inside longer words
- if multiple aliases match the same ticker, include that ticker only once
- return tickers in the order of their first appearance in the headline
- if two aliases overlap at the same starting position, prefer the longer phrase
Example: if AAPL -> ["apple", "apple inc"] and TSLA -> ["tesla"], then the headline "Apple Inc. rises after Tesla delivery report" should return ["AAPL", "TSLA"].