xiaoyunyang / Coding Challenges
Programming Languages
Projects that are alternatives of or similar to Coding Challenges
Coding Challenges Collection
Solutions to coding challenges and algorithm and data structure building blocks
Data Structures
- Linked List
- Queue
- Dequeue
- MinHeap
- Union Find
- Binary Search Tree
- Trie
Nodes
- Singly Node - use to implement Linked List
- Doubly Node - use to implement a Queue
- Graph Node - use in Graph problems
- BST Node - use in Binary Search Tree problems
- Tree Node - use in Tree problems
LeetCode
TOC
1 - Two Sum
- problem
- solution
- repl
- O(N) solution using one pass hash table storing the index of the complement number Complement is defined as
target - nums[i].
3 - Longest Substring Without Repeating Characters
- problem
- solution
- repl
- O(N) solution using dynamic programming (kadane's algorithm). Keep track of the last time you saw the character in a hash table.
20 - Valid Parentheses
- problem
- solution
- repl
- O(N) solution using a stack to make sure every type of open bracket is immediately followed by a close bracket of the same type.
39 - Combination Sum
40 - Combination Sum II
41 - First Missing Positive
42 - Trapping Rain Water
43 - Multiply Strings
129 - Sum Root to Leaf Numbers
135 - Candy
- problem
- solution
- repl
- O(N) Solution using Greedy algorithm. Evaluate left2right and right2left, then combine solution via max of the two.
300 - Longest Increasing Subsequence
- problem
- solution
- repl
- O(N^2) solution using LIS dynamic programming or O(N logN) solution greedy algorithm.
347 - Top K Frequent Elements
594 - Longest Harmonious Subsequence
- problem
- solution
- repl
- O(N) Solution by creating a frequency table and updating a global maximum subsequence length in the loop.
690 - Employee Importance
- problem
- solution
- repl
- O(V*E) Solution by first creating a hash table for easy indexing of nodes in a graph, then traverse that graph via BFS.
721 - Accounts Merge
- problem
- solution
- repl
- Solution using graph search. emails are the vertices. create bi-directional edges from first email to every other email of each account
820 - Short Encoding of Words
- problem
- solution
- repl
- whiteboarding
- Solution using trie of the reversed strings
945 - Minimum Increments to Make Array Unique
953 - Verifying An Alien Dictionary
- problem
- solution
- repl
- O(N) solution using hash map to translate from alien alphabet to normal alphabet, then do a simple comparison in a loop to verify ascending order.
1138 - Alphabet Board Path
1276 - Number of Burgers With No Waste Of Ingredients
- problem
- solution
- repl
- whiteboarding
- Solution by solving a system of equations
1386 - Cinema Seat Allocation
1464 - Maximum Product of Two Elements in an Array
1465 - Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
- problem
- solution
- repl
- O(N+M) solution by keeping track of the maximum gaps made by the horizontal and vertical cuts. Then multiple these max gaps.
1470 - Shuffle the Array
1471 - The k Strongest Values in an Array
- problem
- solution
- repl
- O(N logN) solution by pre-sorting the array and using a while-loop and two pointers.
1472 - Design Browser History
Leetcode 2020 04 Challenge
136 - Single Number
- problem
- solution
- repl
- O(N) solution and O(N) space using a set. O(N) solution and O(1) space using XOR and reduce.
202 - Happy Number
53 - Maximum Subarray
283 - Move Zeroes
122 - Best Time to Buy and Sell Stock II
- problem
- solution
- repl
- O(N) solution by adding to result if current price is greater than previous price.
Leetcode 2020 05 Challenge
278 - First Bad Version
771 - Jewels And Stones
383 - Ransom Note
476 - Number Complement
- problem
- solution
- repl
- O(k) Solution using while loop and xor to toggle bits. k is the most significant bit that's a one.
387 - First Unique Character
- problem
- solution
- repl
- O(N) solution using JS built-in array methods
indexOfandlastIndexOfto find if char is unique. Use Set to store the duplicates.
169 - Majority Element
993 - Cousins in Binary Tree
1232 - Check If It Is a Straight Line
367 - Valid Perfect Square
- problem
- solution
- repl
- O(log N) solution using binary search. Conditional guard return true if input is 0 and 1.
997 - Find the Town Judge
733 - Flood Fill
540 - Single Element in a Sorted Array
402 - Remove K-Digit
208 - Implement Trie (Prefix Tree)
- problem
- solution
- repl
- Each node is an object with key being the letter and value being a node or
endboolean, marking where that this is the end of a word.
918 - Maximum Sum Circular Subarray
328 - Odd Even Linked List
- problem
- solution
- repl
- O(N) solution using by maintaining a pointer to the end of the odd list and the beginning of the even list.
438 - Find All Anagrams in a String
- problem
- solution
- repl
- O(N) solution using the sliding window technique to update a 26-length array to keep track of the character frequency.
567 - Permutation In String
- problem
- solution
- repl
- O(N) solution using the sliding window technique to update a 26-length array to keep track of the character frequency.
901 - Online Stock Span
- problem
- solution
- repl
- O(N) solution using two stacks to keep track of the prices and the previous results of next. The top of the prices stack is always the minimum price seen so far.
94 - Kth Smallest Element in a BST
1277 - Count Square Submatrices with All Ones
- problem
- solution
- repl
- O(N * M) solution using dynamic programming. Create a sum matrix to keep track of number of ones seen in a row from top, left, and left diagonal
451 - Sort Characters By Frequency
986 - Interval List Intersections
1008 - Construct Binary Search Tree from Preorder Traversal
- problem
- solution
- repl
- O(N) solution by recursively building the sub-tree if the sub-tree falls within a range.
1035 - Uncrossed Lines
- problem
- solution
- repl
- O(A * B) solution using dynamic programming. Create a sub-problem solution matrix to keep track of the max uncrossed lines for the sub-arrays. The sub-problem is whether to include the current two items from A and B in the solution or not.
525 - Contiguous Array
- problem
- solution
- repl
- O(N) dynamic programming solution using a variation of Kadane's algorithm and a hash table.
886 - Possible Bipartition
338 - Counting Bits
207 - Course Schedule
973 - K Closest Points to Origin
973 - K Closest Points to Origin
Leetcode 2020 06 Challenge
520 - Detect Capital
237 - Delete Node in a Linked List
1029 - Two City Costs
- problem
- solution
- repl
- whiteboarding
- Solution using a while loop with two pointers to go through a sorted list of cost difference between the cities
344 - Reverse String
- problem
- solution
- O(N) solution using two pointers and a while loop to swap front and back elements of the array.
528 - Random Pick with Weights
406 - Queue Reconstruction by Height
- problem
- solution
- repl
- O(N logN) solution by pre-sorting the array by descending height and ascending K, then repeatedly update the result array.
231 - Power of Two
392 - is Subsequence
- problem
- solution
- repl
- O(N) solution by traversing all the characters of the longer string once and deleting the head character of the shorter string whenever it matches a character from teh longer string.
35 - Search Insert Position
75 - Sort Colors
- problem
- solution
- repl
- Dutch national flag problem. Solution using two pointers to keep track of the boundaries of the outer colors.
380 - Insert Delete GetRandom O(1)
- problem
- solution
- repl
- Solution using a map and an array in the datastructure to achieve O(1) delete and getRandom, respectively.
787 - Cheapest Flight with K Stops
700 - Search in a Binary Tree
468 - Valid IP Address
130 - Surrounded Regions
- problem
- solution
- repl
- Solution using BFS and a set for keeping track of Os connected to any O on the edge.
275 - H-Index II
137 - Single Number II
Leetcode 2020 07 Challenge
441 - Arranging Coins
107 - Binary Tree Level Order Traversal II
- problem
- solution
- repl
- O(N) solution using tree traversal while incrementing level and reverse the result array in a post-processing step.
66 - Plus One
- problem
- solution
- repl
- O(N) solution using
unshiftto add new digit to the front of the array and use carry. Need to have a post processing step to add the extra one to the front as necessary.
Leetcode 2020 08 Challenge
226 - Invert Binary Tree
705 - Design HashSet
125 - Valid Palindrome
342 - Power of Four
- problem
- solution
- repl
- O(log_4 N) solution by recursively dividing the number by 4 until the number is equal to 1.
442 - Find All Duplicates in an Array
- problem
- solution
- O(N) solution using the repeated array update strategy. As we loop, we can negate the elements at index
jwherej=Math.abs(nums[i])-1. This works because the constraint:1 ≤ a[i] ≤ n (n = size of array). If anytime we detect that element at indexjis negative, that means the current element is a duplicate.
Leetcode 2020 09 Challenge
949 - Largest Time for Given Digits
- problem
- solution
- repl
- Solution using one loop and process of elimination. Pro-tip: Make A lot of helper functions.
220 - Contains Duplicate III
- problem
- solution
- repl
- O(N logN) solution by sorting the array first and using two pointers and one while loop.
459 - Repeated Substring Pattern
1305 - All Elements in Two Binary Search Trees
- problem
- solution
- repl
- Solution using two in-order traversals (time complexity O(N)) to create two sorted arrays from the BSTs, then loop through both arrays at the same time in one while-loop (time complexity O(N)) to merge the two sorted arrays, similar to the merge step of merge sort.
290 - Word Pattern
1022 - Sum of Root To Leaf Binary Numbers
- problem
- solution
- repl
- O(logN) solution using binary tree traversal and helper function to convert binary to a decimal number.
165 - Compare Version Numbers
299 - Bulls and Cows
152 - Maximum Product Subarray
- problem
- solution
- repl
- O(N) solution using Kadane's algorithm and tracking both minimum and maximum local solutions.
216 - Combination Sum III
57 - Insert Interval
198 - House Robber
58 - Length of Last Word
421 - Maximum XOR of Two Numbers in an Array
1041 - Robot Bounded in Circle
- problem
- solution
- repl
- O(N) solution which stepping through the entire array of moves to calculate the robot's final direction and location.
121 - Best Time to Buy and Sell Stocks
- problem
- solution
- repl
- O(N) solution by updating the min, max, and maxProfit as you step through the array.
1291 - Sequential Digit
- problem
- solution
- repl
- O(N) solution by setting the limits of loops to min number of digits to max number of digits.
Leetcode 2020 11 Challenge
1290 - Convert Binary Number in a Linked List to Integer
1446 - Consecutive Characters
1217 - Minimum Cost to Move Chips to The Same Position
- problem
- solution
- repl
- O(N) solution. Keep track of the parity of each number as you loop through the array.
1283 - Find the Smallest Divisor Given a Threshold
445 - Add Two Numbers II
563 - Binary Tree Tilt
1026 - Maximum Difference Between Node and Ancestor
- problem
- solution
- O(logN) solution by tree traversal. The solution is the max of the left subtree solution and right subtree solution.
832 - Flipping an Image
- problem
- solution
- repl
- O(N * M) solution by traversing the matrix. Use two pointers in a while loop method for optimization.
593 - Valid Square
- problem
- solution
- repl
- Solution using the geometric property of a square: find distances between all the points and check that there exists two unique non-zero distances. Optimization using a set (cleaner code).
47 - Permutations II
- problem
- solution
- repl
- Solution using recursion (dfs). Keep track of nodes we have visited. Sort the
numsto make sure we skip the same value. When the current value is equal to the previous value, we only use this value if the previous is used.
116 - Populating Next Right Pointers in Each Node
- problem
- solution
- repl
- O(N) solution using BFS. The trick is to recognize the number of nodes to at each level doubles.
845 - Longest Mountain in Array
858 - Mirror Reflection
56 - Merge Intervals
394 - Decode String
804 - Unique Morse Code Words
337 - House Robber III
239 - Sliding Window Maximum
- problem
- solution
- repl
- O(N) solution using Dequeue. Keep track of indices in dequeue. Prune the dequeue of out of range indices and indices whose associated number is less than the current num.
1306 - Jump Game III
Leetcode 2020 12 Challenge
104 - Maximum Depth of Binary Tree
605 - Can Place Flowers
- problem
- solution
- repl
- O(N) solution by counting zeros and using a function to map number of zeros to number of flowers that can be planted. Alternatively, use greedy algorithm.
117 - Populating Next Right Pointers in Each Node II
59 - Spiral Matrix II
1010 - Pairs of Songs With Total Durations Divisible by 60
- problem
- solution
- repl
- O(N) solution and constant space complexity algorithm using hash table to count the frequency of the complements of each time.
941 - Valid Mountain Array
- problem
- solution
- repl
- O(N) solution using two while loops to walk the array once from left to right in two phases.
80 - Remove Duplicates from Sorted Array II
- problem
- solution
- repl
- O(N) solution using a while-loop,
spliceto modify the array in place, and no data-structure (taking advantage of the fact that the array of nums is sorted in ascending order).
865 - Smallest Subtree with all the Deepest Nodes
312 - Burst Balloons
- problem
- solution
- repl
- O(N^2) solution using DP table. Each entry of the DP table stores the max coins we get from bursting bubbles between
leftandright.
977 - Squares of a Sorted Array
- problem
- solution
- repl
- O(N) solution using a stack to keep track of the squares of the negative numbers and perform a merge operation similar to merge sort.
98 - Validate Binary Search Tree
334 - Increasing Triplet Subsequence
880 - Decoded String At Index
110 - Balanced Binary Tree
24 - Swap Nodes in Pairs
Leetcode 2021 01 Challenge
1640 - Check Array Formation Through Concatenation
1379 - Find a Corresponding Node of a Binary Tree in a Clone of That Tree
21 - Merge Two Sorted Lists
- problem
- solution
- repl
- O(N) solution using while-loop to only increment one list node at a time. For the interim data structure for merged list, use array instead of linked list for better space performance
88 - Merge Sorted Array
2 - Add Two Numbers
- problem
- solution
- O(N) solution using while-loop, carry, and keeping track of the tail of the result linked list.
Cracking the Coding Interview
Arrays and Strings
1.1 - isUnique
- Problem: Determine if string contains unique characters. What if you cannot use additional data structures?
- solution
- repl
- O(N) solution with hash table or O(NlogN) with sorting.
1.2 - checkPermutation
- Problem: given two strings, determine if the second string is a permutation (anagram) of the first string.
- solution
- repl
- O(N) solution with hash table or O(NlogN) with sorting. Optimization up-front: if lengths of the strings are different, return false immediately.
1.3 - URLify
- Problem: given a string, replace all the whitespaces with "%20".
- solution
- repl
- O(N) solution. Use regex
/^\s$to test each character to see if it is a whitespace. Need to handle edge cases such as if there are mutiple whitespaces in a row or whitespaces at the end of the string.
1.4 - Palindrome Permutation
- Problem: Given a string, determine if the string is a permutation of a palindrome.
- solution
- repl
- O(N) solution using a hash table. Use
str.replace(/\s/g, '')to get the string without whitespaces.
1.5 - One Away
- Problem: Given s1 and s2, determine if s1 and s2 differ by one edit away. Define edit as inserting a char, deleting a char, or replacing a char.
- solution
- repl
- O(N) solution. Modularize the solution by writing helper functions.
1.6 - String Compression
- Problem: Given a string with a number of characters in a row, compress the string by replacing the repeated characters with the character, followed by the number of occurrences. For example, aabcccccaaa becomes a2b1c5a3. If the compressed string would not be smaller than the original string, the function shall return the original string.
- solution
- repl
- O(N) solution. Make sure to check edge cases. There is an optimization we could do to break from the loop operation when a condition is met.
Linked List
See JavaScript Implementations of LinkedList (also available in repl).
2.1 - Remove Dups
- Problem: Remove duplicates from an unsorted linked list. How would you solve this problem if a temporary buffer is not allowed?
- solution
- repl
- O(N) solution using a hash table and using the
currandprevpointers. With no buffers, we use the "runner technique" where we iterate through the linked list usingcurrpointer while we have another pointer calledrunnerthat goes through the rest of the list which comes aftercurrto check and remove any duplicates.
Stacks and Queues
See JavaScript Implementations of Queue using Doubly Linked List (also available in repl).
Graph
4.1 - Route Between Nodes
- Problem: Given a Directed Graph, design an algorithm to find out whether there is a route between two nodes.
- solution
- repl
- We can use either BFS or DFS for this problem. BFS is more efficient. Make sure we set graph node state to
UNVISITED,VISITED,VISITINGas we traverse through the graph.
4.2 - Minimal Tree
- Problem: Given a sorted (increasing order) array with unique elements, write an algorithm to create a Binary Search Tree (BST) with minimal height.
- solution
- repl
Math and Logic Puzzles
6.1 - The Heavy Pill
- Problem: You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of weight 1.1 grams. Given a scale that provides an exact measurement, how would you find the heavy bottle? You can only use the scale once.
- solution
- repl
Moderate Problems
16.10 - Living People
- Problem: Given a list of people with their birth and death years, implement a method to compute the year with the most number of people alive.
- solution
- repl
16.20 - Phoney Words
-
Problem: On old cellphones,users typed on a numeric keypad and the phone would provide a list of words that matched these numbers. Each digit mapped to a set of 0 - 4 letters. Implement an algorithm to return a list of matching words, given a sequence of digits representing a phone number. You are provided a list of valid words (provided in whatever data structure you'd like).
1 2 3 ABC DEF 4 5 6 GHI JKL MNO 7 8 9 TUV WXYZ PQRS 0 -
Note: O(M * N) where M is number of valid words in the dictionary and N is the length of the phone number. Because N is a small number (phone numbers are usually length 10), we can treat this as a constant. Therefore, the runtime is O(M).
16.21 - Sum Swap
- Problem: Given two arrays of integers, find a pair of values (one value from each array) that you can swap to give the two arrays the same sum
- solution
- repl
Hard Problems
17.26 - Sparse Similarity
-
Problem: Print out the documents IDs and their similarity score iff the similarity score is greater than 0. We define similarity score as the result of dividing the number of intersections with the number of unions. For example:
Input:
const input = { 13: [14,15,100,9,3], 16: [32, 1, 9, 3, 5], 19: [15, 29, 2, 6, 8, 7], 24: [7, 10] }
Output:
13,16 : 0.25 19,24 : 0.14285714285714285 13,19 : 0.1 -
My solution involves building two hash tables.
Misc
Flood Fill
-
Problem:
Given grid and point:
let grid = [ // grid could be any size ['blue', 'blue', 'red', 'red', 'red'], ['pink', 'pink', 'red', 'red', 'red'], ['red', 'pink', 'green', 'green', 'red'], ['red', 'red', 'green', 'red', 'green'], ['red', 'green', 'red', 'red', 'red'], ] let p = [4,2] // a valid location in the grid
find all the locations which has the same color as the given location return the location (indices) in ascending order. For example, given the grid and point above, you should return:
[ [ 3, 3 ], [ 4, 2 ], [ 4, 3 ], [ 4, 4 ] ]
-
The key to solving this problem is you can use depth-first-search (DFS) or breadth-first-search (BFS) and maintain a list of explored nodes. I solved the problem using both DFS with recursion and BFS using queue + while loop. Both provide the same result. For printing out the list of points in ascending order, I had a separate function that sorted the result using JavaScript's built-in sort (quicksort), which has O(NlogN) runtime. A potential optimization for the overall algorithm is to maintain the result as a heap rather than an array. Using an array, insert is O(1) as we use the
Array.prototype.pushmethod; however, the tradeoff is we need to run the O(N logN) algorithm at the end. However, if we use a min heap, inserting into a min heap is O(logN). The advantage is we don't have to sort afterwards, rather, we extract the min from the min heap (runtime O(1)) until the heap is empty. In a min heap, the parent is guaranteed to be smaller than its children so we could recursively extract elements in increasing order from the min heap starting from the root of the heap and working our way down the children. -
The recursion approach is also called the implicit stack-based approach because we are creating call stacks when we recurse. This is less memory efficient than a real stack.
-
For more on the flood fill problem, read the wiki article
Deserialize-1
-
Problem:
Given:
const locations = [ {"id": 1, "name": "San Francisco Bay Area", "parent_id": null}, {"id": 2, "name": "San Jose", "parent_id": 3}, {"id": 3, "name": "South Bay", "parent_id": 1}, {"id": 4, "name": "San Francisco", "parent_id": 1}, {"id": 5, "name": "Manhattan", "parent_id": 6}, {"id": 6, "name": "New York", "parent_id": null}, {"id": 7, "name": "Menlo Park", "parent_id": 1}, {"id": 8, "name": "Brooklyn", "parent_id": 6}, {"id": 9, "name": "Alphabet City", "parent_id": 10}, {"id": 10, "name": "East Village", "parent_id": 13}, {"id": 11, "name": "Greenpoint", "parent_id": 8}, {"id": 12, "name": "Williamsburg", "parent_id": 8}, {"id": 13, "name": "Lower Manhattan", "parent_id": 5}, {"id": 14, "name": "Soho", "parent_id": 13}, {"id": 15, "name": "Financial District", "parent_id": 13} ]
Print out:
New York -Brooklyn --Greenpoint --Williamsburg -Manhattan --Lower Manhattan ---East Village ----Alphabet City ---Financial District ---Soho San Francisco Bay Area -Menlo Park -San Francisco -South Bay --San JoseRules: (1) Child locations should be immediately after their parent, with an extra dash prepended. (2) Locations of the same level of depth should be alphabetically sorted. (3) Assume that the actual list of location will be longer (up to 100 locations), and have max up to 5 levels of depth
-
My solution involves recursively building a tree where each node is a general TreeNode and nodes are inserted into an ordered array of children using a
insertIntoSortedArrfunction.
Shuffle
- Problem: Shuffle an array.
- solution
- repl
- Note: Use the Knuth Shuffle (aka Fisher-Yates shuffle)
Sort 2D Array
- Problem: Sort a 2D array of pairs. The rule is we want to sort by the first elem, then the second elem.
- solution
- repl
- Note: Write custom
comparefunction to pass intoArray.sort.
Array
Least Frequent Array Elements
-
Problem: Given an array of integers, return an array containing the integer that occurs the least number of times. If there are multiple answers, return all possibilities within the resulting array sorted in ascending order. When no solution can be deduced, return an empty array.
Example Input: [10, 941, 13, 13, 13, 941] Output: [10]