Square/Block Software Engineer Onsite Coding Questions

LeetCode #300: Longest Increasing Subsequence. Difficulty: Medium. Topics: Array, Binary Search, Dynamic Programming. Asked at Square in the last 6 months.

code for prime number with out using any count variable i forgot the square root and took time to optimise the code, later got the hit from interviwer and optimised it. further...

Question : - you are given a n x m matrix with all +ve values in it . You are give a value k , find whether any square submatrix...

Tom is very fond of cube and square numbers, i.e. numbers like 1, 4, 8, 9\u2026 Given an integer N, count the number of integers from 1 to N that Tom...

There is a square field which is full of trees planted in a grid. Each tree takes up one position and has a height between 0and 10. You are tasked with...

Given a n x m matrix consisting on only non negative integers and another non negative integer k. Check if there exists any square submatrix whose sum = k. Required Time...

"Design a Rubik\'s Cube then write a method that solves it, printing each step of the process" I was recently asked this in a virtual onsite for an HFT firm. I\'m...

Post is slightly long. sorry for that, I have included every possible detail I could. ### 1 ) Walls Problem Description - A company manufactures walls which can be directly implanted at the...

## Problem Given a broken calculator that can only double or decrement, find the minimum number of operations to reach a target from a starting value. ## Likely LeetCode equivalent LeetCode 991 - Broken Calculator. ## Tags math, greedy

## Problem Implement a basic calculator supporting +, -, *, / with parentheses using a stack-based approach. ## Likely LeetCode equivalent LeetCode 224 - Basic Calculator. ## Tags stack, strings, math

## Problem You manage a farm with `n` plots. Each plot can grow one crop per season. You are given a list of crops with `(name, cost_per_plot, revenue_per_plot, seasons_to_mature)`. You have a budget `B` and `S` seasons. Maximize total profit over `S` seasons. Assume: once a crop is planted it occupies the plot until harvested; replanting is allowed immediately after harvest. ```python def max_profit( plots: int, budget: int, seasons: int, crops: list[dict] # {name, cost, revenue, maturity} ) -> int: pass ``` **Example:** ``` crops = [{"name":"wheat", "cost":2, "revenue":5, "maturity":1}, {"name":"corn", "cost":5, "revenue":15, "maturity":2}] plots=3, budget=12, seasons=4 output -> (best allocation across seasons) ``` ## Follow-ups 1. What is the subproblem structure for a DP approach here? 2. If crops have weather risk (probability of failure), how do you model expected profit? 3. Some plots have soil bonuses for specific crops. How does that change the assignment? 4. How would you present this optimization to a non-technical farmer -- what are the key levers?

## Problem You are given a list of `n` motorcycles, each with a base speed `v` and a pit-stop time `p` (seconds lost). The track is `L` km long. A faster motorcycle overtakes a slower one instantly when it catches up. Motorcycles pit exactly once at the halfway mark. Return the final finishing order (by finish time ascending). ```python def race_results( riders: list[dict], # {name, speed_kmh, pit_stop_sec} track_km: float ) -> list[str]: pass ``` **Example:** ``` riders = [ {"name": "Alpha", "speed_kmh": 100, "pit_stop_sec": 30}, {"name": "Beta", "speed_kmh": 120, "pit_stop_sec": 60}, ] track_km = 200 # Alpha: 200/100*3600 + 30 = 7230 s # Beta: 200/120*3600 + 60 = 6060 s output -> ["Beta", "Alpha"] ``` ## Follow-ups 1. How does the overtaking rule affect your model if speeds are very close? Does it change the final order? 2. Add tire degradation: speed decreases by 5% for every 50 km without a pit stop. Recompute finish times. 3. There are multiple pit-stop windows. How do you optimize each rider's pit strategy to minimize finish time? 4. Race results are needed in real time as riders cross the line. What data structure supports live standings updates efficiently?

## Problem You have `2n` people. Each pair `(i, j)` has a compatibility score `score[i][j]`. Pair all people into `n` non-overlapping pairs to maximize the total compatibility score. ```python def pair_people(scores: list[list[int]]) -> tuple[int, list[tuple[int,int]]]: # Returns (max_score, list_of_pairs) pass ``` **Example:** ``` scores (4 people) = [[0, 6, 2, 4], [6, 0, 3, 5], [2, 3, 0, 7], [4, 5, 7, 0]] Best pairing: (0,1) score=6, (2,3) score=7 -> total 13 output -> (13, [(0,1),(2,3)]) ``` ## Approach Bitmask DP: `dp[mask]` = max score when people in `mask` are already paired. Transition: take the lowest unmatched person, try pairing with every other unmatched person. O(n * 2^(2n)). ## Follow-ups 1. For `2n = 20`, bitmask DP is feasible. What about `2n = 1000`? Discuss approximation algorithms. 2. Some pairs are incompatible (score = -inf). How does that affect your bitmask transitions? 3. This is equivalent to maximum weight matching in a general graph. Name the classical algorithm that solves it in polynomial time. 4. If scores are symmetric and all positive, does greedy (always pick the highest remaining score) give the optimal answer? Provide a counterexample if not.

## Problem You are given `2^k` teams in a single-elimination tournament. Each match is won by the team with the higher strength value (ties go to lower seed number). Simulate the entire bracket and return the winner plus the full round-by-round match results. ```python def simulate_tournament( teams: list[dict] # [{"name": str, "strength": int, "seed": int}] ) -> dict: # Returns {"winner": str, "rounds": [[{"match": [t1,t2], "winner": t}]]} pass ``` **Example:** ``` teams = [{"name":"A","strength":90,"seed":1},{"name":"B","strength":80,"seed":2}, {"name":"C","strength":85,"seed":3},{"name":"D","strength":70,"seed":4}] Round 1: A beats B (90>80), C beats D (85>70) Final: A beats C (90>85) output -> {"winner":"A", ...} ``` ## Follow-ups 1. What if the number of teams is not a power of 2? How do you assign byes? 2. Add upsets: with probability `p`, the weaker team wins. Run `n` simulations and return win probabilities. 3. Design the bracket seeding so the two strongest teams can only meet in the final. 4. How would you store and display this bracket as a tree structure in a database?

## Problem Design an in-memory key-value store that supports nested transactions: - `set(key, value)` and `get(key) -> value | None` - `delete(key)` - `begin()` -- start a new transaction (nestable). - `commit()` -- commit the innermost transaction. - `rollback()` -- undo all changes in the innermost transaction. ```python class TransactionalDB: def set(self, key: str, value: str) -> None: ... def get(self, key: str) -> str | None: ... def delete(self, key: str) -> None: ... def begin(self) -> None: ... def commit(self) -> None: ... def rollback(self) -> None: ... ``` **Example:** ``` db.set("x", "1") db.begin() db.set("x", "2") db.get("x") -> "2" db.rollback() db.get("x") -> "1" ``` ## Approach Maintain a stack of transaction layers (each a dict of staged writes). On `get`, search layers top-to-bottom then the base store. On `commit`, merge top layer into the one below. ## Follow-ups 1. How does your rollback implementation handle `delete` -- what sentinel value distinguishes deletion from absence? 2. Implement `count(value) -> int` returning how many keys currently equal a given value, efficiently. 3. How would you add durability (survive process crash) to this store? 4. Discuss isolation levels -- which one does your implementation provide?

## Problem Build a Trie (prefix tree) that supports: - `insert(word)` -- add a word. - `search(word) -> bool` -- return True if the word exists. - `starts_with(prefix) -> bool` -- return True if any word starts with the prefix. - `words_with_prefix(prefix) -> list[str]` -- return all words sharing the prefix. ```python class Trie: def insert(self, word: str) -> None: ... def search(self, word: str) -> bool: ... def starts_with(self, prefix: str) -> bool: ... def words_with_prefix(self, prefix: str) -> list[str]: ... ``` **Example:** ``` t = Trie() t.insert("apple"); t.insert("app"); t.insert("apex") t.search("app") -> True t.starts_with("ap") -> True t.words_with_prefix("ap") -> ["app", "apple", "apex"] ``` ## Follow-ups 1. What is the space complexity of a Trie vs. a sorted list for dictionary lookup? 2. Add `delete(word)` without leaving orphan nodes. What is the tricky case? 3. Implement fuzzy search: return all words within edit distance 1 of a query string using the Trie. 4. The dictionary has 10 million words. What compression scheme (e.g., DAWG, Patricia trie) would you use?