InterviewDB Question

Set Game: Implement the Card-Matching Logic for the Set Card Game

phone
Sign in to bookmark

Question Details

Round 1 Coding / OOD

Problem

In the card game Set, each card has 4 attributes: number (1/2/3), color (red/green/purple), shading (solid/striped/open), and shape (diamond/squiggle/oval). Three cards form a valid Set if for each attribute, the values across the three cards are either all the same or all different.

python
from dataclasses import dataclass

@dataclass
class Card:
    number: int        # 1, 2, or 3
    color: str
    shading: str
    shape: str

def is_valid_set(c1: Card, c2: Card, c3: Card) -> bool:
    ...

def find_all_sets(cards: list[Card]) -> list[tuple[Card, Card, Card]]:
    ...

Example

c1 = Card(1, "red",    "solid",   "diamond")
c2 = Card(2, "green",  "striped", "squiggle")
c3 = Card(3, "purple", "open",    "oval")
is_valid_set(c1, c2, c3)  -> True   # all different on every attribute

c4 = Card(1, "red",   "solid",   "oval")
c5 = Card(2, "green", "striped", "oval")
c6 = Card(3, "red",   "open",    "oval")  # color: red/green/red -> invalid
is_valid_set(c4, c5, c6)  -> False

Follow-ups

  1. What is the time complexity of find_all_sets for a board of N cards? Can you do better than O(N^3)?
  2. How do you generate all 81 unique cards in the standard deck?
  3. How would you detect when no valid Set exists on the current board (signaling the need to deal more cards)?
  4. How would you design a solver that finds a Set in the minimum number of steps for a given board state?

Full Details

Round 1 Coding / OOD

Problem

In the card game Set, each card has 4 attributes: number (1/2/3), color (red/green/purple), shading (solid/striped/open), and shape (diamond/squiggle/oval). Three cards form a valid Set if for each attribute, the values across the three cards are either all the same or all different.

python
from dataclasses import dataclass

@dataclass
class Card:
    number: int        # 1, 2, or 3
    color: str
    shading: str
    shape: str

def is_valid_set(c1: Card, c2: Card, c3: Card) -> bool:
    ...

def find_all_sets(cards: list[Card]) -> list[tuple[Card, Card, Card]]:
    ...

Example

c1 = Card(1, "red",    "solid",   "diamond")
c2 = Card(2, "green",  "striped", "squiggle")
c3 = Card(3, "purple", "open",    "oval")
is_valid_set(c1, c2, c3)  -> True   # all different on every attribute

c4 = Card(1, "red",   "solid",   "oval")
c5 = Card(2, "green", "striped", "oval")
c6 = Card(3, "red",   "open",    "oval")  # color: red/green/red -> invalid
is_valid_set(c4, c5, c6)  -> False

Follow-ups

  1. What is the time complexity of find_all_sets for a board of N cards? Can you do better than O(N^3)?
  2. How do you generate all 81 unique cards in the standard deck?
  3. How would you detect when no valid Set exists on the current board (signaling the need to deal more cards)?
  4. How would you design a solver that finds a Set in the minimum number of steps for a given board state?
Free preview. Unlock all Samsara questions →

About This Question

This is a reported interview question from a samsara interview during the phone round.

It covers the following topics: Oop, Coding, Ood, Phone .

Topics

Oop Coding Ood Phone

More Samsara Interview Questions

InterviewDB Samsara SWE Phone - Axis Permutation InterviewDB Command Parser: Parse and Dispatch Shell-Like Commands from User Input InterviewDB Samsara SWE Phone - Concurrent Meetings InterviewDB Engine States: Model a Vehicle Engine Using a Finite State Machine InterviewDB Engine Utilization: Compute and Report Resource Utilization Across Processing Engines
← All Samsara questions Samsara Software Engineer Questions → All Coding Other Questions →