Longest Absolute Path in File System Representation
Find the length of the longest absolute path to a file within the abstracted file system. The length is measured in characters.
Efficient Order Log Storage
You manage an e-commerce website and need to keep track of the last N order IDs in a log. Design a data structure that supports the following operations efficiently:
February 6, 2025 | Data Structure, dsa, Twitter | No comments
Select a Random Element from a Stream
You are given a stream of elements that is too large to fit into memory. Write an algorithm to select a random element from the stream with equal probability
Estimate π Using Monte Carlo Method
The formula for the area of a circle is given by πr². Use the Monte Carlo method to approximate the value of π to three decimal places.
Longest Substring with K Distinct Characters
Given an integer k and a string s, write a function to determine the length of the longest substring in s that contains at most k distinct characters.
Staircase Climbing Ways
There is a staircase with N steps, and you can ascend either 1 step or 2 steps at a time. Write a function to calculate the number of unique ways to climb the staircase. The sequence of steps matters.
January 11, 2025 | Amazon, Data Structure, dsa | No comments
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:
January 6, 2025 | Binary Tree, dsa, DSA Sheet, Google | No comments