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.

Solve theatre seating and ticker extraction

Company: Sig

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement the following two coding tasks. 1. **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 2. **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"]`.

Quick Answer: 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.

Allocate 4-Person Groups in a Movie Theater

You are given an integer `n` representing the number of rows in a movie theater. Each row has seats numbered `1` through `10`. Some seats are already reserved, given as a list of `(row, seat)` pairs. 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 these contiguous seat blocks: - seats `2-5` - seats `4-7` - seats `6-9` Return the **maximum number of 4-person groups** that can still be seated across the whole theater. Notes: - `1 <= row <= n`, seats are `1..10`. - Reserved pairs may appear in any order; each seat is reserved at most once. - A block is usable only if **all four** of its seats are free. - Within a single row the chosen blocks must not share any seat, so a row can yield at most 2 groups (e.g. `2-5` together with `6-9`).

Constraints

  • 1 <= row <= n (n can be 0, meaning no rows)
  • seat values are between 1 and 10
  • each seat is reserved at most once
  • reserved pairs may be given in any order

Examples

Input: (1, [])

Expected Output: 2

Explanation: One empty row: take blocks 2-5 and 6-9 (disjoint) for 2 groups.

Input: (2, [])

Expected Output: 4

Explanation: Two empty rows, 2 groups each = 4.

Hints

  1. Only three candidate 4-seat blocks per row exist (2-5, 4-7, 6-9); a block is usable iff all four of its seats are free.
  2. Rows are independent, so solve each row separately and sum the results.
  3. Within a row, 2-5 and 6-9 are disjoint (giving 2 groups), but 4-7 overlaps both — pick the largest set of non-overlapping usable blocks.

Extract Stock Tickers From a News Headline

You are given a news headline string and a dictionary mapping each stock **ticker** to a list of company **aliases** or keyword phrases. Return all tickers mentioned in the headline. Matching rules: - Matching is **case-insensitive**. - **Punctuation is ignored** (treat the text as a sequence of word tokens). - A match must cover **whole words / whole phrases**, never a substring inside a longer word (so `apple` must not match inside `pineapple`). - If multiple aliases map to the same ticker, include that ticker **only once**. - Return tickers in the order of their **first appearance** in the headline. - If two aliases could begin at the **same starting position**, prefer the **longer** phrase (e.g. match `apple inc` rather than just `apple`). Example: with `AAPL -> ["apple", "apple inc"]` and `TSLA -> ["tesla"]`, the headline `"Apple Inc. rises after Tesla delivery report"` returns `["AAPL", "TSLA"]`.

Constraints

  • matching is case-insensitive and ignores punctuation
  • matches are whole words/phrases, never substrings of a longer word
  • each ticker appears at most once in the output
  • tickers are ordered by first appearance in the headline
  • at the same start position, the longer alias phrase is preferred

Examples

Input: ("Apple Inc. rises after Tesla delivery report", {"AAPL": ["apple", "apple inc"], "TSLA": ["tesla"]})

Expected Output: ["AAPL", "TSLA"]

Explanation: 'apple inc' is matched as the longer phrase at position 0; 'tesla' matched later.

Input: ("Tesla and Apple both gain; Tesla leads", {"AAPL": ["apple"], "TSLA": ["tesla"]})

Expected Output: ["TSLA", "AAPL"]

Explanation: Order follows first appearance; the second 'Tesla' is deduplicated.

Hints

  1. Tokenize both the headline and every alias into lowercase alphanumeric words so punctuation and case stop mattering and whole-word matching is automatic.
  2. Index aliases by their tuple of words pointing to a ticker; track the longest alias length so you know how far ahead to look.
  3. Scan the headline left to right; at each position try the longest phrase first, and on a match advance past the consumed words to honor the longest-match-at-same-start rule.

Loading coding console...