Instacart Software Engineer Phone Screen Questions

## Problem You are given a hand of exactly 3 cards, each as `(rank, suit)` where rank is 2-14 (14=Ace) and suit is one of `H/D/C/S`. Evaluate the hand and return its category. Categories in descending order: 1. `STRAIGHT_FLUSH` — three consecutive ranks, same suit 2. `THREE_OF_A_KIND` — all same rank 3. `STRAIGHT` — three consecutive ranks, mixed suits 4. `FLUSH` — same suit, not consecutive 5. `PAIR` — exactly two same rank 6. `HIGH_CARD` — none of the above ```python from typing import NamedTuple class Card(NamedTuple): rank: int # 2-14 suit: str # H/D/C/S def evaluate_hand(cards: list[Card]) -> str: ... ``` ``` Input: [(10,'H'),(11,'H'),(12,'H')] -> "STRAIGHT_FLUSH" Input: [(7,'H'),(7,'D'),(7,'C')] -> "THREE_OF_A_KIND" Input: [(2,'H'),(5,'D'),(3,'C')] -> "STRAIGHT" Input: [(9,'H'),(3,'H'),(6,'H')] -> "FLUSH" Input: [(9,'H'),(9,'D'),(2,'C')] -> "PAIR" Input: [(2,'H'),(7,'D'),(K,'C')] -> "HIGH_CARD" ``` ## Follow-ups 1. Ace can be low (A-2-3) or high (Q-K-A). How do you handle both cases in your straight detection? 2. Given two hands of the same category, how do you compare them to determine a winner (tiebreaker logic)? 3. Extend to 5-card poker hands. How does your architecture change? 4. How would you generate all possible 3-card hands from a standard 52-card deck and count hands per category?

## Problem You have a transit log of tap-in and tap-out events. Each event is `[customer_id, station, timestamp]`. A trip is completed when a customer taps in at station A then taps out at station B. Compute the average travel time for each unique `(start_station, end_station)` pair. ```python def average_travel_time( events: list[tuple[str, str, int]] # (customer_id, station, timestamp) ) -> dict[tuple[str,str], float]: ... ``` ``` Events: ("C1", "A", 100), ("C2", "B", 110), ("C1", "C", 150), ("C2", "D", 200), ("C1", "A", 300), ("C1", "C", 360) Trips: C1: A->C (50), A->C (60) => avg 55.0 C2: B->D (90) => avg 90.0 Output: {("A","C"): 55.0, ("B","D"): 90.0} ``` ## Follow-ups 1. Your implementation must handle events arriving out of chronological order. How does this affect your approach? 2. What happens if a customer taps in twice without tapping out? How do you handle malformed data? 3. The transit authority wants a live dashboard: as events stream in, update averages without recomputing from scratch. How do you maintain a running average? 4. A customer makes 10,000 trips on the same route. How do you keep your running average numerically stable (avoid floating point drift)?

## Problem A password was encoded with the following steps applied in order: 1. Reverse the string. 2. Replace each letter with the letter `k` positions forward in the alphabet (wrapping: z+1=a). `k` is given. 3. Swap each pair of adjacent characters (swap index 0-1, 2-3, etc.; if odd length, last char stays). Given the encoded string and `k`, return the original password. ```python def decode_password(encoded: str, k: int) -> str: ... ``` ``` Original: "hello" Step 1 (reverse): "olleh" Step 2 (shift +2): "qnnhj" Step 3 (swap pairs): "nqnjh" Encoded: "nqnjh" decode_password("nqnjh", 2) -> "hello" ``` ## Follow-ups 1. Walk through each decode step in reverse order. What is the inverse of each operation? 2. What edge cases matter: `k=0`, `k=26`, an empty string, non-letter characters? 3. If the encoding scheme had 10 steps, how would you structure your decoder to make it easy to add/remove steps? 4. This encoding is symmetric for step 3 (swap is its own inverse). How does that simplify your decode logic?

## Problem Evaluate a mathematical or logical expression string, handling operator precedence and parentheses. Classic stack-based parsing problem. ## Likely LeetCode equivalent No direct match. ## Tags stack, strings, parsing, coding

## Problem Given a sequence of integers, determine if it has a repeating pattern of period `p` (for any p from 1 to n/2). If yes, return the shortest repeating unit and the next `k` predicted elements. If no pattern exists, return an empty list. ```python def find_pattern( sequence: list[int], k: int ) -> tuple[list[int], list[int]]: """Returns (pattern_unit, next_k_elements). pattern_unit=[] if none found.""" ... ``` ``` Input: sequence=[1,2,3,1,2,3,1,2,3], k=4 Pattern found: [1,2,3] (period 3) Next 4: [1,2,3,1] Output: ([1,2,3], [1,2,3,1]) Input: sequence=[1,2,3,4], k=2 No repeating pattern. Output: ([], []) Input: sequence=[5,5,5,5], k=3 Pattern: [5] (period 1) Output: ([5], [5,5,5]) ``` ## Follow-ups 1. How do you verify a candidate period `p`? What is the time complexity of checking all periods? 2. What if the sequence is only approximately periodic (some elements differ by at most 1)? How do you define "close enough"? 3. Can you use the KMP failure function to detect periodicity efficiently? Describe how. 4. If the sequence is a time series of stock prices, what limitations does strict periodicity detection have, and what alternatives would you use?

## Problem Implement a key-value store that supports get and set operations with timestamps, returning the value at or before a given time. ## Likely LeetCode equivalent LC 981 - time-based-key-value-store ## Tags hash_table, binary_search, design, coding