Autocomplete System Implementation
Build an autocomplete system that, given a query string s and a set of possible query strings returns all strings from the set that start with s as a prefix.
Job Scheduler Implementation
Design a job scheduler that accepts a function f and an integer n. The scheduler should execute the function f after a delay of n milliseconds.
Largest Sum of Non-Adjacent Numbers
Problem Statement (Asked By Airbnb) Given a list of integers, write a function to compute the largest sum of numbers such that no two numbers are adjacent in the list. The input may contain zero or negative values. For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we […]
Count Unival Subtrees in a Binary Tree
A unival tree (short for "universal value tree") is a tree in which all nodes have the same value.
Given the root of a binary tree, determine how many unival subtrees it contains.
For example, the following tree has 5 unival subtrees:
Count Decoding Ways for Encoded Messages
Problem Statement (Asked By Facebook) Given the mapping a = 1, b = 2, …, z = 26, and an encoded message, count the number of possible ways to decode it. For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'. You can assume that the messages […]
Implement an XOR Linked List
An XOR-linked list is a memory-efficient version of a doubly linked list. Instead of each node storing separate next and prev pointers, each node contains a single field called both, which stores the result of the XOR operation on the memory addresses of the next and previous nodes.
Construct and Deconstruct a Pair
Problem Statement (Asked By Jane Street) The function cons(a, b) creates a pair of two elements. Implement two functions: For instance: Below is the implementation of cons: Your task is to define the car and cdr functions. Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and […]
Find the Smallest Missing Positive Integer
Problem Statement (Asked By Stripe) You are given an array of integers. Your task is to find the smallest missing positive integer in O(N) time using O(1) additional space. In other words, identify the smallest positive number that is not present in the array. The array may include: You are allowed to modify the input […]
Serialize and Deserialize a Binary Tree
Given the root of a binary tree, create two functions:
serialize(root) - Converts the binary tree into a string representation.
deserialize(s) - Reconstructs the binary tree from its string representation.
Product of Array Except Self
Problem Statement (Asked By Uber) Given a list of integers, return a new list such that each element at index i of the new list is the product of all the elements in the original list except the one at i. For instance, if the input is [1, 2, 3, 4, 5], the expected output […]
