Elements of Programming Interviews

Adnan Aziz, Tsung-Hsien Lee, Amit Prakash

Adnan Aziz is a Research Scientist at Facebook. Previously, he was a professor at the Department of Electrical and Computer Engineering at The University of Texas at Austin, where he conducted research and taught classes in applied algorithms. He received his Ph.D. from The University of California at Berkeley; his undergraduate degree is from Indian Institutes of Technology Kanpur. He has worked at Google, Qualcomm, IBM, and several software startups. When not designing algorithms, he plays with his children, Laila, Imran, and Omar.

Tsung-Hsien Lee is a Senior Software Engineer at Uber. Previously, he worked as a Software Engineer at Google and as Software Engineer Intern at Facebook. He received both his M.S. and undergraduate degrees from National Tsing Hua University. He has a passion for designing and implementing algorithms. He likes to apply algorithms to every aspect of his life. He takes special pride in helping to organize Google Code Jam 2014 and 2015.

Amit Prakash is a co-founder and CTO of ThoughtSpot, a Silicon Valley startup. Previously, he was a Member of the Technical Staff at Google, where he worked primarily on machine learning problems that arise in the context of online advertising. Before that he worked at Microsoft in the web search team. He received his Ph.D. from The University of Texas at Austin; his undergraduate degree is from Indian Institutes of Technology Kanpur. When he is not improving business intelligence, he indulges in his passion for puzzles, movies, travel, and adventures with Nidhi and Aanya.

LeetCode Problems

Elements of Programming Interviews

Help us improve! If you notice any incorrectly assigned exercises or if you know of any that are currently unassigned, please report it or submit a pull request on GitHub.

Number	Question	Leetcode Number	Leetcode Title	Similar Questions	Difficulty	Video
Primitive Types
4.1	Computing the parity of a word	-	-	-	N/A	N/A
4.2	Swap bits	-	-	-	N/A	N/A
4.3	Reverse Bits	190	Reverse Bits	-	Easy
4.4	Find a closest integer with the same weight	-	-	-	N/A	N/A
4.5	Compute XxY without arithmetical operators	-	-	-	N/A	N/A
4.6	Compute x/y	-	-	-	N/A	N/A
4.7	Compute x^y	50	Pow(x, n)	-	Medium
4.8	Reverse digits	-	-	-	N/A	N/A
4.9	Check if a decimal integer is a palindrome	9	Palindrome Number	-	Easy
4.1	Generate uniform random numbers	-	-	470	N/A	N/A
4.11	Rectangle intersection	-	-	836	N/A	N/A
Arrays
5.1	The Dutch national flag problem	75	Sort Colors	-	Medium
5.2	Increment an arbitrary-precision integer	66	Plus One	-	Easy
5.3	Multiply two arbitrary-precision integers	-	-	-	N/A	N/A
5.4	Advancing through an array	55	Jump Game	-	Medium
5.5	Delete duplicates from a sorted array	26	Remove Duplicates from Sorted Array	-	Easy
5.6	Buy and sell a stock once	121	Best Time to Buy and Sell Stock	-	Easy
5.7	Buy and sell a stock twice	123	Best Time to Buy and Sell Stock III	-	Hard
5.8	Computing an altemation	280	Wiggle Sort	-	Medium
5.9	Enumerate all primes to n	-	-	204	N/A	N/A
5.1	Permute the elements of an array	-	-	-	N/A	N/A
5.11	Compute the next permutation	31	Next Permutation	-	Medium
5.12	Sample offline data	-	-	-	N/A	N/A
5.13	Sample online data	-	-	-	N/A	N/A
5.14	Compute a random permutation	384	Shuffle an Array	-	Medium	N/A
5.15	Compute a random subset	-	-	-	N/A	N/A
5.16	Generate nonuniform random numbers	-	-	-	N/A	N/A
5.17	he Sudoku checker problem	36	Valid Sudoku	-	Medium
5.18	Compute the spiral ordering of a2D array	54	Spiral Matrix	-	Medium
5.19	Rotate a 2D array	48	Rotate Image	-	Medium
5.2	Compute rows in Pascal's Triangle	118	Pascal's Triangle	-	Easy
Strings
6.1	Interconvert strings and integers	-	-	8	N/A	N/A
6.2	Base conversion	-	-	-	N/A	N/A
6.3	Compute the spreadsheet column encoding	171	Excel Sheet Column Number	-	Easy	N/A
6.4	Replace and remove	-	-	-	N/A	N/A
6.5	Test palindromicity	125	Valid Palindrome	-	Easy
6.6	Reverse all the words in a sentence	186	Reverse Words in a String II	-	Medium	N/A
6.7	Compute all mnemonics for a phone number	17	Letter Combinations of a Phone Number	-	Medium
6.8	The look-and-say problem	38	Count and Say	-	Medium	N/A
6.9	Convert from Roman to decimal	13	Roman to Integer	-	Easy
6.1	Compute all valid IP addresses	93	Restore IP Addresses	-	Medium
6.11	Write a string sinusoidallY	-	-	-	N/A	N/A
6.12	Implement run-length encoding	443	String Compression	-	Medium	N/A
6.13	Find the first occurrence of a substring	28	Implement strStr()	-	Easy
Linked Lists
7.1	Merge Two Sorted Lists	21	Merge Two Sorted Lists	-	Easy
7.2	Reverse a single sublist	206	Reverse Linked List	-	Easy
7.3	Test for cyclicity	142	Linked List Cycle II	-	Medium	N/A
7.4	Test for overlapping lists-lists are cycle-free	160	Intersection of Two Linked Lists	-	Easy
7.5	Test for overlapping lists-lists may have cycles	-	-	-	N/A	N/A
7.6	Delete a node from a singly linked lis	237	Delete Node in a Linked List	-	Medium	N/A
7.7	Remove the kth last element from a list	19	Remove Nth Node from End of List	-	Medium
7.8	Remove duplicates from a sorted lis	83	Remove Duplicates from Sorted List	-	Easy
7.9	Implement cyclic right shift for singly linked lists	61	Rotate List	-	Medium
7.1	Implement even-odd merge	-	-	328	N/A	N/A
7.11	Test whether a singly linked list is palindromic	234	Palindrome Linked List	-	Easy
7.12	Implement list pivoting	86	Partition List	-	Medium
7.13	Add list-based integers	2	Add Two Numbers	-	Medium
Stacks and Queues
8.1	Implement a stack with max API	-	-	155 , N/A	N/A	N/A
8.2	Evaluate RPN expressions	150	Evaluate Reverse Polish Notation	-	Medium
8.3	Test a string over '{,},(,),[,]' for well-formedness	20	Valid Parenthesis	-	Easy
8.4	Normalize pathnames	71	Simplify Path	-	Medium
8.5	Compute buildings with a sunset view	-	-	-	N/A	N/A
8.6	Compute binary tree nodes in order of increasing depth	102	Binary Tree Level Order Traversal	-	Medium
8.7	Implement a circular queue	622	Design Circular Queue	-	Medium
8.8	Implement a queue using stacks	232	Implement Queue using Stacks	-	Easy
8.9	Implement a queue with max API	-	-	-	N/A	N/A
Binary Trees
9.1	Test if a binary tree is height-balanced	110	Balanced Binary Tree	-	Easy
9.2	Test if a binary tree is symmetric	101	Symmetric Tree	-	Easy
9.3	Compute the lowest common ancestor in a binary tree	236	Lowest Common Ancestor of a Binary Tree	-	Medium
9.4	Compute the LCA when nodes have parent pointers	-	-	-	N/A	N/A
9.5	Sum the root-to-leaf paths in a binary tree	129	Sum Root to Leaf Numbers	-	Medium
9.6	Find a root to leaf path with specified sum	112	Path Sum	-	Easy
9.7	Implement an inorder traversal without recursion	-	-	94	N/A	N/A
9.8	Implement a preorder traversal without recursion	-	-	144	N/A	N/A
9.9	Compute the kth node in an inorder traversal	-	-	-	N/A	N/A
9.1	Compute the successor	-	-	-	N/A	N/A
9.11	Implement an inorder traversal with O(1) space	94	Binary Tree Inorder Traversal	-	Easy
9.12	Reconstruct a binary tree from traversal data	105	Construct Binary Tree from Preorder and Inorder Traversal	-	Medium
9.13	Reconstruct a binary tree from a preorder traversal with markers	1028	Recover a Tree From Preorder Traversal	-	Hard	N/A
9.14	Form a linked list from the leaves of a binary tree	-	-	-	N/A	N/A
9.15	Compute the exterior of a binary tree	545	Boundary of Binary Tree	-	Medium	N/A
9.16	Compute the right sibling tree	-	-	-	N/A	N/A
Heaps
10.1	Merge sorted files	-	-	-	N/A	N/A
10.2	Sort an increasing-decreasing array	-	-	-	N/A	N/A
10.3	Sort an almost-sorted array	-	-	-	N/A	N/A
10.4	Compute the k closest stars	973	K Closest Points to Origin	-	Medium
10.5	Compute the median of online data	295	Find Median from Data Stream	-	Hard
10.6	Compute the k largest elements in a max-heap	-	-	-	N/A	N/A
Searching
11.1	Search a sorted array for first occurrence of k	-	-	-	N/A	N/A
11.2	Search a sorted array for entry equal to its index	-	-	-	N/A	N/A
11.3	Search a cyclically sorted array	33	Search in Rotated Sorted Array	-	Medium
11.4	Compute the integer square root	69	Sqrt(x)	-	Easy
11.5	Compute the real square root	-	-	-	N/A	N/A
11.6	Search in a 2D sorted affay	240	Search a 2D Matrix II	-	Medium	N/A
11.7	Find the min and max simultaneously	-	-	-	N/A	N/A
11.8	Find the kth largest element	215	Kth Largest Element in an Array	-	Medium
11.9	Find the missing IP address	-	-	-	N/A	N/A
11.1	Find the duplicate and missing elements	-	-	-	N/A	N/A
Hash Tables
12.1	Test for palindromic permutations	266	Palindrome Permutation	-	Easy	N/A
12.2	Is an anonymous letter constructible?	383	Ransom Note	-	Easy
12.3	Implement an ISBN cache	-	-	-	N/A	N/A
12.4	Compute the LCA, optimizing for close ancestors	-	-	-	N/A	N/A
12.5	Find the nearest repeated entries in an array	-	-	-	N/A	N/A
12.6	Find the smallest subarray covering all values	-	-	76	N/A	N/A
12.7	Find smallest subarray sequentially covering all values	-	-	727	N/A	N/A
12.8	Find the longest subarray with distinct entries	-	-	-	N/A	N/A
12.9	Find the length of a longest contained interval	-	-	-	N/A	N/A
12.1	Compute all string decompositions	-	-	-	N/A	N/A
12.11	Test the Collatz conjecture	-	-	-	N/A	N/A
12.12	Implement a hash function for chess	-	-	-	N/A	N/A
Sorting
13.1	Compute the intersection of two sorted arrays	-	-	-	N/A	N/A
13.2	Merge two sorted arrays	88	Merge Sorted Array	-	Easy
13.3	H-Index	274	H-Index	-	Medium
13.4	Remove first-name duplicates	-	-	-	N/A	N/A
13.5	Smallest nonconstructiblev alue	-	-	-	N/A	N/A
13.6	Render a calendar	-	-	-	N/A	N/A
13.7	Merging intervals	56	Merge Intervals	-	Medium
13.8	Compute the union of intervals	-	-	-	N/A	N/A
13.9	Partitioning and sorting an affay with many rePeated entries	-	-	-	N/A	N/A
13.1	Team photo day-1	-	-	-	N/A	N/A
13.11	lmplement a fast sorting algorithm for lists	-	-	-	N/A	N/A
13.12	Compute a salary threshold	148	Sort List	-	Medium
Binary Search Trees
14.1	Test if a binary tree satisfies the BST property	98	Validate Binary Search Tree	-	Medium
14.2	Find the first key greater than a given value in a BST	285	Inorder Successor in BST	-	Medium	N/A
14.3	Find the k largest elements in a BST	-	-	-	N/A	N/A
14.4	Compute the LCA in a BST	235	Lowest Common Ancestor of a Binary Search Tree	-	Medium
14.5	Reconstruct a BST from traversal data	-	-	-	N/A	N/A
14.6	Find the closest entries in three sorted arrays	-	-	-	N/A	N/A
14.7	Enumerate numbers of the form a + b*sqrt(2)	-	-	-	N/A	N/A
14.8	Build a minimum height BST from a sorted affay	108	Convert Sorted Array to Binary Search Tree	-	Easy
14.9	Test if three BST nodes are totally ordered	-	-	-	N/A	N/A
14.1	The range lookup problem	-	-	-	N/A	N/A
14.11	Add credits	-	-	-	N/A	N/A
Recursion
15.1	The Towers of Hanoi problem	-	-	-	N/A	N/A
15.2	Generate all nonattacking placements of n-Queens	51	N-Queens	-	Hard
15.3	Generate permutations	46	Permutations	-	Medium
15.4	Generate the power set	78	Subsets	-	Medium
15.5	Generate all subsets of size k	-	-	-	N/A	N/A
15.6	Generate strings of matched parens	22	Generate Parentheses	-	Medium
15.7	Generate palindromic decompositions	131	Palindrome Partitioning	-	Medium
15.8	Generate binary trees	-	-	-	N/A	N/A
15.9	Implement a Sudoku solver	37	Sudoku Solver	-	Hard	N/A
15.1	Compute a Gray code	89	Gray Code	-	Medium	N/A
Dynamic Programming
16.1	Count the number of score combinations	-	-	-	N/A	N/A
16.2	Compute the Levenshtein distance	72	Edit Distance	-	Medium
16.3	Count the number of ways to traverse a 2D array	62	Unique Paths	-	Medium
16.4	Compute the binomial coefficients	-	-	-	N/A	N/A
16.5	Search for a sequence in a 2D array	-	-	-	N/A	N/A
16.6	The knapsack problem	-	-	-	N/A	N/A
16.7	The bedbathandbeyond.com problem	140	Word Break II	-	Hard
16.8	Find the minimum weight path in a triangle	120	Triangle	-	Medium
16.9	Pick up coins for maximum gain	877	Stone Game	-	Medium
16.1	Count the number of moves to climb stairs	70	Climbing Stairs	-	Easy
16.11	The pretty printing problem	-	-	-	N/A	N/A
16.12	Find the longest nondecreasing subsequence	300	Longest Increasing Subsequence	-	Medium
Greedy Algorithms and Invariants
17.1	Compute an optimum assignment of tasks	-	-	-	N/A	N/A
17.2	Schedule to minimize waiting time	-	-	-	N/A	N/A
17.3	The interval covering problem	-	-	-	N/A	N/A
17.4	The 3-sum problem	15	3Sum	-	Medium
17.5	Find the majority element	169	Majority Element	-	Easy
17.6	The gasup problem	134	Gas Station	-	Medium
17.7	Compute the maximum water trapped by a pair of vertical lines	11	Container With Most Water	-	Medium
17.8	Compute the largest rectangle under the skyline	84	Largest Rectangle in Histogram	-	Hard
Graphs
18.1	Search a maze	505	The Maze II	-	Medium	N/A
18.2	Paint a Boolean matrix	733	Flood Fill	-	Easy
18.3	Compute enclosed regions	1020	Number of Enclaves	-	Medium
18.4	Deadlock detection	-	-	-	N/A	N/A
18.5	Clone a graph	-	-	-	N/A	N/A
18.6	Making wired connections	-	-	-	N/A	N/A
18.7	Transform one string to another	-	-	-	N/A	N/A
18.8	Team photo day-2	-	-	-	N/A	N/A
Parallel Computing
19.1	Implement caching for a multithreaded dictionary	-	-	-	N/A	N/A
19.2	Analyze two unsynchronized interleaved threads	-	-	-	N/A	N/A
19.3	Implement synchronization for two interleaving threads	-	-	-	N/A	N/A
19.4	Implement a thread pool	-	-	-	N/A	N/A
19.5	Deadlock	-	-	-	N/A	N/A
19.6	The readers-writers problem	-	-	-	N/A	N/A
19.7	The readers-writers problem with write preference	-	-	-	N/A	N/A
19.8	Implement a Timer class	-	-	-	N/A	N/A
Honors Class
24.1	Compute the greatest common divisor	-	-	-	N/A	N/A
24.2	Find the first missing positive entry	-	-	-	N/A	N/A
24.3	Buy and sell a stock k times	-	-	-	N/A	N/A
24.4	Compute the maximum product of all entries but one	-	-	-	N/A	N/A
24.5	Compute the longest contiguous increasing subarray	-	-	-	N/A	N/A
24.6	Rotate an array	-	-	-	N/A	N/A
24.7	Identify positions attacked by rooks	-	-	-	N/A	N/A
24.8	Justify text	-	-	-	N/A	N/A
24.9	Implement list zipping	-	-	-	N/A	N/A
24.1	Copy a postings list	-	-	-	N/A	N/A
24.11	Compute the longest substring with matching parens	-	-	-	N/A	N/A
24.12	Compute the maximum of a sliding window	-	-	-	N/A	N/A
24.13	Implement a postorder traversal without recursion	-	-	-	N/A	N/A
24.14	Compute fair bonuses	-	-	-	N/A	N/A
24.15	Search a sorted array of unknown length	-	-	-	N/A	N/A
24.16	Search in two sorted arrays	-	-	-	N/A	N/A
24.17	Find the kth largest element-large n, small k	-	-	-	N/A	N/A
24.18	Find an element that appears only once	-	-	-	N/A	N/A
24.19	Find the line through the most points	-	-	-	N/A	N/A
24.2	Convert a sorted doubly linked list into a BST	-	-	-	N/A	N/A
24.21	Convert a BST to a sorted doubly linked list	-	-	-	N/A	N/A
24.22	Merge two BSTs	-	-	-	N/A	N/A
24.23	Implement regular expression matching	-	-	-	N/A	N/A
24.24	Synthesize an expression	-	-	-	N/A	N/A
24.25	Count inversions	-	-	-	N/A	N/A
24.26	Draw the skyline	-	-	-	N/A	N/A
24.27	Measure with defective jugs	-	-	-	N/A	N/A
24.28	Compute the maximum subarray sum in a circular array	-	-	-	N/A	N/A
24.29	Determine the critical height	-	-	-	N/A	N/A
24.3	Find the maximum 2D subarray	-	-	-	N/A	N/A
24.31	Implement Huffman coding	-	-	-	N/A	N/A
24.32	Trapping water	-	-	-	N/A	N/A
24.33	The heavy hitter problem	-	-	-	N/A	N/A
24.34	Find the longest subarray whose sum <= k	-	-	-	N/A	N/A
24.35	Road network	-	-	-	N/A	N/A
24.36	Test if arbitrage is possible	-	-	-	N/A	N/A

All solution videos are from the respective channels of NeetCode, NeetCode.io, Tech Dose, and Greg Hogg. Visit their channels for further explanations and tips for various interviews.