Coding problems Flashcards
(31 cards)
Find the Maximum Product of Two Integers in an Array
[Arrays]
Iterate through the array and keep track of the maximum and second maximum, as well as the minimum and second minimum numbers. The maximum product will be either max1 * max2 or min1 * min2.
Rotate an Array (k steps)
[Arrays]
There are various ways to do this, but one method is to reverse the entire array, then reverse the first k elements, and finally reverse the last n-k elements, where k is the number of rotations and n is the length of the array.
Maximum Subarray Sum - “Kadane’s Algorithm”
[Arrays]
Initialize two variables, max_current and max_global. Iterate through the array, updating max_current to be the maximum of the current element and the sum of max_current and the current element. Update max_global whenever max_current is greater than max_global.
Remove Duplicates from Sorted Array
[Arrays]
Use two pointers. One pointer iterates through the array, while the other points to the location where the next unique element should go. Swap elements as necessary.
Move All Zeros to the End
[Arrays]
Use a pointer to keep track of the last non-zero element’s index. Iterate through the array and swap the current non-zero element with the zero after last non-zero element.
Two Sum - one array and target, return indices of the two numbers such that they add up to target.
[Arrays]
Use a hash map to store visited numbers and their indices. For each element, check if (target - element) exists in the hash map.
Find the “Kth” Max/Min Element of an Array
[Arrays]
Use QuickSelect, a variation of the QuickSort algorithm, to find the Kth smallest/largest element in expected O(n) time.
Merge Two Sorted Arrays
[Arrays]
Use two pointers, one for each array. Compare the current elements pointed by the two pointers and put the smaller one into the result array, then move the pointer of the smaller element.
Intersection of Two Arrays
[Arrays]
Use two sets to hold the unique elements of each array. Take the intersection of the sets.
Longest Consecutive Sequence
[Arrays]
Put all elements in a hash set for quick look-up. Then, iterate through the array. For each number n, first check if this is the first number of subsequence (by checking for n - 1), and then look for consecutive numbers n+1, n+2, … in the set, keeping track of the longest sequence.
Find the Majority Element
Given an array of integers, find the element that appears more than n/2 times.
(Boyer-Moore Voting Algorithm)
Initialize a candidate and a counter. Iterate through the array, updating the counter if the element is the same +1 or not -1. If the counter goes below 0, then change the candidate.
Verify the candidate by counting its occurrences in a second pass.
Product of Array Except Self
Compute an output array such that output[i] is equal to the product of all elements in the array except arr[i]
First, traverse the array from left-to-right, storing the product of all numbers to the left of each index. Do a second right-to-left traversal to calculate the product of all numbers to the right, and then multiply the two.
Search in Rotated Sorted Array
An array is sorted and then rotated. Find a target value in it.
Use binary search with added conditions to identify which half of the array is still sorted after the rotation. Depending on the sorted half, decide whether to adjust low or high pointers.
Three Sum
Find all unique triplets in the array that sum up to a specific target.
First, sort the array. Then, for each element, use a two-pointer technique to find pairs that sum up to the negation of the current element.
Spiral Order Matrix
Given a matrix, return all elements in spiral order.
Keep track of boundaries (top, bottom, left, right), and iterate through the matrix updating these boundaries as you collect elements in spiral order.
Jump Game
Given an array of non-negative integers, you are initially positioned at the first index. Each element in the array represents your maximum jump length from that position. Determine if you can reach the last index.
Iterate through the array while keeping track of the farthest index you can reach. If you ever reach a point that is beyond the farthest reachable index, return false.
Subarray Sum Equals K
Find the number of continuous subarrays whose sum equals k.
Use a hash map to store the counts of prefix sums. As you iterate through the array, update the current sum and check if current_sum - k exists in the hash map.
Kth Smallest Element in a Sorted Matrix (MxN)
Find the kth smallest element in a row-wise and column-wise sorted matrix.
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/solutions/1322101/c-java-python-maxheap-minheap-binary-search-picture-explain-clean-concise/
- Brute force - add all elements to max heap of size K. Complexity - O(M * N * logK)
- Min heap to keep K smallest elements. Put first element of each row into min heap (put tuple with matrix indeces). Pop smallest element and then push the next one in that row in the heap, do this K times.
Complexity - O(K * logK) - Binary search - start from largest and smallest element, then count how many elements are smaller then mid.
Counting elements need N+M operations - travers from top right to bottom left.
Complexity - O((M+N) * log(max - min) )
Longest Increasing Subsequence
Find the length of the longest increasing subsequence in a given array.
https://leetcode.com/problems/longest-increasing-subsequence/solutions/1326308/c-python-dp-binary-search-bit-segment-tree-solutions-picture-explain-o-nlogn/
- Dynamic Programming - Let dp[i] is the longest increase subsequence of nums[0..i] which has nums[i] as the end element of the subsequence. Complexity - O(N^2)
- Greedy with Binary Search - keep array sub, where sub[i] - has the best subsequence of length i (the best - smallest top of subsequence, thus easier to extend). Complexity - O(N * logN)
Fibonacci Sequence
Find the n-th Fibonacci number.
- Loop
- Recursion like f_helper(n,a,b) - pass two previous numbers
Lowest common ancestor in a tree.
Given a tree (node with array of children), tree root and two elements, find a lowest common ancestor of two elements.
Used DFS, and on each step pass back if the element was found and if the common ancestor was found.
Usually the elements are guaranteed unique, then you can just pass up a count of how many elements were found.
Merge Sort
Sort an array using merge sort.
Divide the array into two halves, sort each half recursively, and then merge them back together. The base case is an array with 0 or 1 elements, which is already sorted.
Gale-Shapley algorithm. Matching interns with teams
You are to match n interns with n teams given the preferences list for each intern and team. Prioritize intern selection first.
Go through all the interns matching them one by one to the best preference, if on the next step the conflict is found (best team for the next intern has already been assigned an intern), use team ranking to choose one of them and push the other intern back into the stack.
Data structures:
1. stack of interns left to match
2. dict with {team: matched intern}, update when needed
3. current best team for each intern start with [0,0, …0] and increment when needed
4. team ranking converted to dicts for each team [{intern: his rank}, …. ]
Union Find - Disjoint Set
Implement effective data structure which represent disjoint sets: elements are unique across all sets (operation add element as a single set), each set has a root element (operation find[x] to return root element of the set with x), and can do union of two sets.
- Data structure is a collection of trees where nodes point up to the parent, represented as a dictionary:
{e1:e1, e2:e1, e3:e3} - two sets {e1, e2} and {e3} - to make union more effective:
a) keep rank dictionary to remember the depth of the trees from each element, union with shorter tree at the bottom
b) When running find[] - flatten tree to keep all elements under root, no need to update rank
