X Coding Interview Questions

Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Flatten Nested List Iterator

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an...

Design Twitter

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the 10 most recent tweets in the user's new...

Implement Trie (Prefix Tree)

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various appl...

Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cove...

Tweet Counts Per Frequency

A social media company is trying to monitor activity on their site by analyzing the number of tweets that occur in select periods of time. These periods can be...

Investments in 2016

Table: Insurance

LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Permutation Sequence

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Regular Expression Matching

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '' where:

Remove All Occurrences of a Substring

Given two strings s and part, perform the following operation on s until all occurrences of the substring part are removed:

Trapping Rain Water II

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

Number of Black Blocks

You are given two integers m and n representing the dimensions of a 0-indexed m x n grid.

Max Points on a Line

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Validate IP Address

Given a string queryIP, return "IPv4" if IP is a valid IPv4 address, "IPv6" if IP is a valid IPv6 address or "Neither" if IP is not a correct IP of any type.

The Skyline Problem

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of...

Design Authentication Manager

There is an authentication system that works with authentication tokens. For each session, the user will receive a new authentication token that will expire tim...

Word Break II

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possi...

Minimum Number of Steps to Make Two Strings Anagram

You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character.

Count Sub Islands

You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connec...

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

Time Needed to Buy Tickets

There are n people in a line queuing to buy tickets, where the 0th person is at the front of the line and the (n - 1)th person is at the back of the line.

Process Tasks Using Servers

You are given two 0-indexed integer arrays servers and tasks of lengths n​​​​​​ and m​​​​​​ respectively. servers[i] is the weight of the i​​​​​​th​​​​ server,...

Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.

Design Skiplist

Design a Skiplist without using any built-in libraries.

Finding the Users Active Minutes

You are given the logs for users' actions on LeetCode, and an integer k. The logs are represented by a 2D integer array logs where each logs[i] = [IDi, timei] i...

Happy Number

Write an algorithm to determine if a number n is happy.

Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal's triangle.

Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Integer to Roman

Seven different symbols represent Roman numerals with the following values:

Invalid Tweets

Table: Tweets

Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '' where:

Masking Personal Information

You are given a personal information string s, representing either an email address or a phone number. Return the masked personal information using the below ru...

Minimum Elements to Add to Form a Given Sum

You are given an integer array nums and two integers limit and goal. The array nums has an interesting property that abs(nums[i]) <= limit.

Binary Gap

Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1'...

Customer Placing the Largest Number of Orders

Table: Orders

Minimum Genetic Mutation

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Tree Node

Table: Tree

Random Pick with Weight

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.

Rotting Oranges

You are given an m x n grid where each cell can have one of three values:

Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.