Introducing QuickCode 75 - a companion app for Grind 75
Problem Statement
Letโs face it, algorithm questions are still important in job interviews, so we practice on LeetCode.
We donโt have time to crack all the problems so Grind 75 is the list of questions we wanna focus on. But still it requires a lot of time to practice. After we are done with the list, we are probabally starting to forget, at least for me.
Solution - QuickCode 75
QuickCode 75 allows us to quickly go through the 75 questions and check our understanding.
For each question, we can think for a few moments and choose the best approach, then compare against the best answer. If we can solve each question under 40 seconds, the whole check will be done in less than an hour.
Letโs try it out.
QuickCode 75 based on Grind 75
What are your best approaches regarding time complexity?
1. Two Sum
Given an integer array, find the pair that sum to target number.
N - length of array
2. Valid Parentheses
Given an string which might contain parentheses & brackets like '()abc{]}123'
, check if their pairings are valid.
N - length of string
4. Best Time to Buy and Sell Stock
Given an array of prices on each day, return best profit by choosing a day to buy and a day after it to sell.
N - length of array
5. Valid Palindrome
Check if a string is identical if reversed, ignore cases and non-alphanumeric characters.
N - length of string
6. Invert Binary Tree
For all the nodes on a binary tree, swap their left and right.
N - count of nodes.
7. Valid Anagram
Given 2 strings containing letters, check if one can be transformed to the other by rearranging the letters.
N - suppose 2 strings have same length of N for cost analysis
8. Binary Search
Given a sorted array of numbers and a target number, return its position.
N - length of array
9. Flood Fill
Given a matrix of colors, target color and a cells, switch all the connected cells to with same origin color to target color
N - number of cells
10. Lowest Common Ancestor of a Binary Search Tree
Given a Bineary Search Tree and two nodes, find the lowest common ancestor
N - number of nodes
11. Balanced Binary Tree
Check if a binary tree is balanced - meaning for each node, the difference of left/right subtree heights is <= 1
N - number of nodes
13. Implement Queue using Stacks
Per title.
suppose we enqueue and dequeue N times for cost analaysis
enqueue():
dequeue():
14. First Bad Version
For a sequence of 0s followed by 1s, find the first 1.
N - length of sequence
15. Ransom Note
Given two strings of letters, check if the 1st string could be constructed by the letters from 2nd string.
N - for cost analysis, let's use N to stand string length for bot strings
17. Longest Palindrome
Given a bunch of letters, rearrange however as you want, what would be length of longest palindrome?
N - length of string
19. Majority Element
An array of numbers, find the number that has occurance over half of the length
N - length of array
20. Add Binary
Given two binary strings, add them up
N - use N for length of both strings for cost analysis
21. Diameter of Binary Tree
Find the longest path between two nodes on a binary tree
N - node count
24. Contains Duplicate
Given an array of numbers, check if there is any number with occurance > 1
N - length of array
25. Maximum Subarray
Given an array of numbers, return the largest sum of subarray
N - length of array
26. Insert Interval
Given a list of non-overalpping intervals [start, end]
, sorted by start, insert & merge a new interval
27. 01 Matrix
Given a matrix of 0 and 1, return a matrix of distance to nearest 0 for each cell
28. K Closest Points to Origin
Given a list of points, return the K closest points to origin (0,0)
N - length of list
30. 3Sum
Given an integer array, find all combinations of 3 numbers that add up to 0
N - length of array
34. Course Schedule
Given some courses and the dependencies among them, check if there is a circle inside.
N - count of courses
35. Implement Trie (Prefix Tree)
Per title, implement trie.insert(), trie.search(), trie.startWith().
N - length of the argument string. The space to hold the edges are necessary, do not count them in space cost.
36. Coin Change
Given a few types of coins, return the fewest number of coin to sum up to target amount. Each coin could be used infinite times.
C - types of coins, T - target amount
38. Min Stack
Creat a Stack data structure that could also output min element at O(1)
N - count of elements pushed for analysis purpose
40. Number of Islands
For a matrix of 0s and 1s, connected 1s are counted as one islands, return the count of islands.
N - count of cells
41. Rotting Oranges
For a matrix of oranges. 0 - empty, 1 - fresh orange, 2 - rotten orange. Each day fresh orange becomes rotten if adjacent to a rotten orange. How many days before all oranges become orange?
N - count of cells
42. Search in Rotated Sorted Array
An sorted array of unique numbers is possibly rotated at unknow position, search a target number
N - length of array
43. Combination Sum
An array of unique positive integers, find all the combinations of elements that add up to target integer. Each element could be used infinitely.
The time & space cost for the question is unusual, so please choose it if you know. N - length of array, T - target, M - min value in the array
45. Merge Intervals
Merge a list of intervals which might have overlapping elements.
N - length of list
47. Time Based Key-Value Store
Create a key-value Map that allows storing multiple values for same key, differentiated by timestamp, set(key, value, timestamp)
, get(key, timestamp)
N - suppose there are N entries on the same key for analysis purpose.
48. Accounts Merge
An account could have multiple email, we treat two accounts identical if they have one same email. Now merge the given list of account. Emails in an account should be sorted
N - suppose there are N emails in total for analysis purpose
49. Sort Colors
Sort an array of colors in place so that same colors are next to each other, there are maxium 3 kinds of colors.
N - length of array
50. Word Break
Given a string and a word list, check if the string could be constructed with one ore more words from the list. Each word could be used for infinite times.
N - length of string
51. Partition Equal Subset Sum
Given an array of integers, check if we can separate them into 2 buckets that sum of numbers in each bucket are the same.
N - length of array, T - sum
52. String to Integer
Given a string, converts it into an integer, considering edge cases.
N - length of string
53. Spiral Matrix
Given a matrix, traverse in spiral order, meaning go from outer layer to inner layer, clockwise
N - count of cells
55. Binary Tree Right Side View
Given a binary tree, return the right most element on each layer
N - node count
56. Longest Palindromic Substring
Find the longest palindromic substring from given string.
N - length of string
57. Unique Paths
Given a grid, how many paths are there to move from top-left to bottom-right, if can only move right or down.(No pure math solution).
N - suppose grid is N x N for analysis purpose.
59. Container With Most Water
Given an array of integers, each integer means the height of container border. Find 2 borders that could hold most water.
N - length of array
60. Letter Combinations of a Phone Number
Remember the old phone keyboard, each digit key is mapped to several letters. Now given a string containing digits, return the possible words made from the digits
N - length of string
61. Word Search
Given a matrix of letters, check if a target word could be made from adjacent cells, each cell can be used only once.
M - number of cells, N - length of the word
62. Find All Anagrams in a String
Given two strings m and n, try to find all the anagrams of n in the m.
M - length of m, N - length of n
63. Minimum Height Trees
A connected graph without circle could be a tree if we put one of the nodes as root. Now given a such graph, find the tree with least height
N - node count
64. Task Scheduler
Given some tasks represented by letters and a cooldown time, arrange them so that there are no same tasks run within the cooldown.
N - task count
65. LRU Cache
Create a key-value cache with capacity that it evicts the least used keys when needed. put()
get()
must be in ๐(1)
N - capacity
66. Kth Smallest Element in a BST
Given a BST and value k, find the k-th smallest value.
N - node count, treat k as const during cost analysis
67. Minimum Window Substring
Given two string s and t containg letters, find the shortest substring of s that t could be constructed from.
N - suppose s and t both are at length N for easier cost analysis
68. Serialize and Deserialize Binary Tree
Per title, serialize a binary tree and then deserialize from the the result.
N - node count
69. Trapping Rain Water
Similar to the question of Container With Most Water, if we use all the borders, how much water can we trap?
N - border count
70. Find Median from Data Stream
Create a data structure that easily provides median while accepting new numbers.
N - count of numbers inputed
71. Word Ladder
Words can be transformed to another if there is maximumn 1 letter difference. Given two words and a word list, all of same length. Check if two words can be transformed to each other, by using word list in between and return the shortest path length.
N - length of word, M - word count
72. Basic Calculator
Calculate an input string containing digits, + - * / and ()
N - length of input string
73. Maximum Profit in Job Scheduling
Given some jobs, each job has time interval and profit. Try to earn max profit without time overlapping.
N - job count