How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Sig.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Sig during technical interviews.

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.

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.

Input: (1, [(1, 5)])

Expected Output: 1

Explanation: Seat 5 reserved kills blocks 2-5 and 4-7; only 6-9 remains.

Input: (1, [(1, 2), (1, 9)])

Expected Output: 1

Explanation: Seat 2 kills 2-5, seat 9 kills 6-9; only 4-7 survives.

Input: (1, [(1, 5), (1, 6)])

Expected Output: 0

Explanation: Seats 5 and 6 together block every candidate block.

Input: (3, [(1, 5), (2, 7), (3, 2)])

Expected Output: 3

Explanation: Row1->only 6-9 (1); Row2->only 2-5 (1); Row3->2-5 dead, 4-7 and 6-9 overlap so 1. Total 3.

Input: (0, [])

Expected Output: 0

Explanation: No rows, no groups.

Input: (1, [(1, 1), (1, 10)])

Expected Output: 2

Explanation: Seats 1 and 10 are outside every block, so 2-5 and 6-9 still fit: 2 groups.

Hints

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.
Rows are independent, so solve each row separately and sum the results.
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.

Input: ("Pineapple sales drop", {"AAPL": ["apple"]})

Expected Output: []

Explanation: 'apple' inside 'pineapple' is a substring, not a whole word, so no match.

Input: ("APPLE INC announces record quarter", {"AAPL": ["apple inc", "apple"]})

Expected Output: ["AAPL"]

Explanation: Case-insensitive; longest phrase 'apple inc' wins, ticker listed once.

Input: ("No tickers here at all", {"AAPL": ["apple"], "TSLA": ["tesla"]})

Expected Output: []

Explanation: No alias appears.

Input: ("", {"AAPL": ["apple"]})

Expected Output: []

Explanation: Empty headline yields no matches.

Input: ("Microsoft, Google, and Amazon report earnings", {"MSFT": ["microsoft"], "GOOGL": ["google", "alphabet"], "AMZN": ["amazon"]})

Expected Output: ["MSFT", "GOOGL", "AMZN"]

Explanation: Three single-word matches in appearance order; punctuation ignored.

Input: ("Meta Platforms shares the spotlight with Meta", {"META": ["meta", "meta platforms"]})

Expected Output: ["META"]

Explanation: Longest phrase 'meta platforms' consumes both words at the start; the trailing 'meta' is a duplicate.

Hints

Tokenize both the headline and every alias into lowercase alphanumeric words so punctuation and case stop mattering and whole-word matching is automatic.
Index aliases by their tuple of words pointing to a ticker; track the longest alias length so you know how far ahead to look.
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.

Quick Overview