Figma Software Engineer Phone Screen Questions

## Problem You are given a list of axis-aligned rectangles representing UI elements on a canvas, each defined as `(x1, y1, x2, y2)` where `(x1,y1)` is the top-left corner. Implement: 1. `find_intersecting_pairs()` — return all pairs of rectangles that overlap. 2. `intersection_area(r1, r2)` — return the area of the overlapping region (0 if they don't intersect). 3. `total_covered_area()` — return the total area of canvas covered by at least one rectangle (no double-counting). ```python def intersection_area(r1: tuple, r2: tuple) -> int: x1 = max(r1[0], r2[0]); x2 = min(r1[2], r2[2]) y1 = max(r1[1], r2[1]); y2 = min(r1[3], r2[3]) return max(0, x2-x1) * max(0, y2-y1) ``` ``` Rects: [(0,0,4,4), (2,2,6,6), (10,10,12,12)] Intersecting pairs: [(0,0,4,4) & (2,2,6,6)] Intersection area: (2,2,4,4) -> 4 Total covered area: 16 + 16 - 4 + 4 = 32 ``` ## Follow-ups 1. `find_intersecting_pairs` is O(n^2). Describe a sweep-line algorithm that improves this. 2. How does `total_covered_area` change for 1000 rectangles? Is inclusion-exclusion still feasible? 3. What if rectangles can be rotated (not axis-aligned)? What algorithm handles this case? 4. In a real UI system, overlapping elements affect z-order rendering. How would you sort overlapping elements for correct paint order?

## Problem Given a text string and a list of keywords, return the text with each keyword occurrence wrapped in `<mark>` tags. Keywords are case-insensitive. If two keyword matches overlap, merge them into a single `<mark>` span covering both. ```python def highlight_keywords(text: str, keywords: list[str]) -> str: ... ``` ``` text = "The quick brown fox jumps over the lazy dog" keywords = ["quick brown", "brown fox"] Matches: "quick brown" -> [4, 14] "brown fox" -> [10, 18] Merged span: [4, 18] -> "quick brown fox" Output: "The <mark>quick brown fox</mark> jumps over the lazy dog" --- keywords = ["the", "lazy"] Output: "<mark>The</mark> quick brown fox jumps over <mark>the</mark> <mark>lazy</mark> dog" ``` ## Follow-ups 1. How do you handle overlapping matches efficiently using an interval merge step? 2. What if keywords include regex special characters — how do you escape them before building your search pattern? 3. Your output uses raw HTML. What XSS risk exists if `text` comes from user input, and how do you mitigate it? 4. Extend to support highlighting in a rich-text document (nested HTML). Why is string replacement no longer sufficient?

## Problem Implement a Markdown-to-HTML parser supporting: headings (`#`, `##`, `###`), bold (`**text**`), italic (`*text*`), inline code (`` `code` ``), and unordered lists (`- item`). Input is a multi-line string; output is an HTML string. ```python def parse_markdown(md: str) -> str: ... ``` ``` Input: # Hello World This is **bold** and *italic* text. - Item one - Item two Use `code()` inline. Output: <h1>Hello World</h1> <p>This is <strong>bold</strong> and <em>italic</em> text.</p> <ul><li>Item one</li><li>Item two</li></ul> <p>Use <code>code()</code> inline.</p> ``` ## Follow-ups 1. Your inline parser must handle nested or adjacent markers (`***bold italic***`). How do you approach this? 2. A line can be both a list item continuation and contain inline elements. How does your parser track state across lines? 3. What happens with unclosed markers (e.g., `**bold without closing`)? How do you handle error recovery? 4. How would you extend the parser to support tables? Describe the grammar change needed.

## Problem Implement a minimal string template engine. Templates may contain: - Variable substitution: `{{variable_name}}` - Conditionals: `{{#if condition}}...{{/if}}` - Loops: `{{#each items}}...{{item}}...{{/each}}` ```python def render_template(template: str, context: dict) -> str: ... ``` ``` Template: "Hello {{name}}! {{#if premium}}You have pro access.{{/if}}" "Items: {{#each cart}}{{item.name}} (${{item.price}}) {{/each}}" Context: {"name": "Alice", "premium": True, "cart": [{"name": "Book", "price": 10}]} Output: "Hello Alice! You have pro access." "Items: Book ($10) " ``` ## Follow-ups 1. How do you handle nested `{{#if}}` inside `{{#each}}`? Describe your parsing approach (recursive descent vs regex). 2. What happens if `context` is missing a key referenced in the template? Silent empty string or error? 3. Sanitize output against XSS: if `name = "<script>alert(1)</script>"`, what should your renderer do? 4. Your engine currently runs in O(n) per render. If the same template is rendered 10,000 times, how do you precompile it for speed?

## Round 1 - Coding (Frontend) ## Problem Implement the selection logic for a spreadsheet grid. Support: - `select_cell(row, col)` — single cell selection, clears previous. - `extend_selection(row, col)` — extend selection from anchor to `(row, col)` (shift+click behavior). - `toggle_cell(row, col)` — add/remove a cell from selection (ctrl+click). - `get_selected_cells() -> set[tuple[int,int]]` — return all currently selected cells. - `get_selection_bounds() -> tuple[int,int,int,int]` — return `(min_row, min_col, max_row, max_col)` of selection. ```python class TableSelection: def select_cell(self, row: int, col: int) -> None: ... def extend_selection(self, row: int, col: int) -> None: ... def toggle_cell(self, row: int, col: int) -> None: ... def get_selected_cells(self) -> set[tuple[int,int]]: ... ``` ``` select_cell(0,0) # selected: {(0,0)}, anchor=(0,0) extend_selection(2,2) # selected: full 3x3 block (0,0)-(2,2) toggle_cell(1,1) # deselect center; selected: 8 border cells get_selection_bounds() # -> (0,0,2,2) ``` ## Follow-ups 1. `extend_selection` fills a rectangular block. How do you enumerate all cells in that block efficiently? 2. How does keyboard navigation (arrow keys + shift) map to your API? 3. What if the grid has 1 million rows? How do you represent a large contiguous selection without storing every cell? 4. Describe how you would serialize the selection state for copy-paste operations.

## Round 1 - Coding ## Problem Implement a 2D canvas abstraction that manages a collection of shapes and handles rendering and hit-testing: - `add_shape(shape)` — add a shape (Circle, Rect, or Line) with id, position, color. - `move_shape(id, dx, dy)` — translate shape by offset. - `hit_test(x, y) -> str | None` — return the id of the topmost shape at point `(x,y)`, or None. - `render() -> list[str]` — return a list of draw commands in z-order (e.g. `["draw_rect(0,0,10,10,red)", ...]`). ```python class Canvas: def add_shape(self, shape: Shape) -> None: ... def move_shape(self, shape_id: str, dx: int, dy: int) -> None: ... def hit_test(self, x: int, y: int) -> str | None: ... def render(self) -> list[str]: ... class Rect(Shape): def contains(self, x, y) -> bool: return self.x <= x <= self.x+self.w and self.y <= y <= self.y+self.h ``` ``` canvas.add_shape(Rect("r1", 0, 0, 10, 10, "red")) canvas.add_shape(Circle("c1", 5, 5, 4, "blue")) # overlaps r1 at center canvas.hit_test(5, 5) -> "c1" # topmost canvas.move_shape("c1", 20, 0) canvas.hit_test(5, 5) -> "r1" ``` ## Follow-ups 1. How do you determine "topmost" — insertion order, z-index property, or both? 2. Your `hit_test` is O(n). For a canvas with 10,000 shapes, how do you speed this up (spatial index)? 3. How would you implement undo/redo for `move_shape` and `add_shape`? 4. Describe how you would serialize the canvas state to JSON and restore it.

## Problem Design a layer system for a graphics application. Each layer has: `id`, `content` (2D pixel grid), `opacity` (0.0-1.0), `blend_mode` ("normal"|"multiply"|"screen"), and `visible` flag. Implement: - `add_layer(layer, position)` — insert layer at given z-position. - `flatten() -> Grid` — composite all visible layers top-to-bottom using their blend modes. - `move_layer(id, new_position)` — reorder layer. - `set_opacity(id, opacity)` — update layer opacity. ```python class LayerSystem: def add_layer(self, layer: Layer, position: int) -> None: ... def flatten(self) -> list[list[tuple[int,int,int]]]: ... def move_layer(self, layer_id: str, new_pos: int) -> None: ... def set_opacity(self, layer_id: str, opacity: float) -> None: ... # Blend formulas (per channel, 0-255): # normal: result = top * opacity + bottom * (1 - opacity) # multiply: result = (top * bottom / 255) * opacity + bottom * (1-opacity) # screen: result = (255 - (255-top)*(255-bottom)/255) * opacity + bottom*(1-opacity) ``` ## Follow-ups 1. `flatten` recomputes from scratch every call. How would you cache intermediate composites and invalidate on change? 2. What data structure best represents the layer stack for efficient reordering? 3. How does the order of compositing (top-to-bottom vs bottom-to-top) affect the blend result? 4. Describe how Photoshop's layer panel maps to your class design.

## Problem You have a permission tree where each node has an `id`, a `parent_id`, and an `access_level` (0=public, 1=restricted, 2=private). A user has a clearance level. A node is accessible if `user_clearance >= node.access_level` AND all ancestors are accessible. Given a target node and a user clearance, find the topmost accessible ancestor — the highest node in the path from root to target that the user can access. If the root itself is accessible, return the root. ```python def topmost_accessible( nodes: dict[str, dict], # id -> {parent_id, access_level} target_id: str, user_clearance: int ) -> str | None: ... ``` ``` Tree: root(0) -> dept(1) -> team(2) -> doc(2) User clearance = 1 Path root->dept->team->doc Accessible: root(ok), dept(ok), team(fail), doc(fail) Topmost accessible = "dept" ``` ## Follow-ups 1. If the root itself is inaccessible, what do you return? 2. How does your solution change if permission inheritance can be broken (a public node under a private one)? 3. For a tree with 1 million nodes, you need to answer 10,000 topmost-accessible queries per second. How do you precompute or cache? 4. Extend to support group-based permissions (user belongs to groups; a node grants access to a group). How does this change the lookup?