Problem Approach Flashcards
Trapping water
Have two separate arrays for figuring out the maximum heights when you start from the left and if you start from the right.
Now when you iterate through the given array you can find the minimum among the left and right max arrays, say that is X.
X - value of the current index in the given array will give you its capacity.
Add up all the values and thats how many units of water
How do you reverse a string? [sort of a linkedlist o(1) space problem]
Can be done with two pointers at the end and exchange as you iterate
What is the best approach when there are repetitive actions to be done with just a change of parameters?
For instance, to swap adjacent nodes in a linkedList
When there are repetitive actions to be done with just a change of parameters recursion is a good choice
swapNodes(Node s)
{
// since we are passing the node next to the second
first.next = swapNode(second.next);
second.next = first;
// in the end return the second return second; }
How do you reverse a linked list
Recursion can be used since only a change of parameters needs to be done with each call.
Capacity of water
Since the capacity is determined by both width and height, we can start with the largest width and work our way.
so therefore start with the extremes and calculate the capacity and move either pointer only if there is a line greater than it(this means that there is a possibility of higher capacity). At every point you will keep track of the max capacity
Three sum problem
a+b+c =0 given a list of integers
sort the array(nlogn)
then taking one of the elements as a pivot we call twosum method
In this method we calculate the sum of pivot + lo + high
if that sum is > 0 then we need to decrement high
if sum < 0 increment lo
else we have our result
now to avoid having duplicates we can move our lo pointer if two values are repeated (i.e duplicates)
give an array of integers find the product of i = product of values at all other indexes than i
generate two new arrays left and right.
Left array is the product of all elements to the left of an index
Right array is the product of all elements to the right of an index
then multiple the values in both arrays to get the result
Find the median of two sorted arrays
this is like the last step of merge in merge sort. you compare the first elements and add to an auxiliary array . This would take O(m+n)
In order to do this in O(log(m+n)) you can just consider only the left array of the combined array(so only half of the subset) since all elements to the left of median will be less than median.
consider what is the mid point for the combined array that gives number of elements x in left array
Now assuming all x come from the first array. we start from the middle of the first array and compare that value with the mid+1 of the second array. If its more that indicates that we need to consider more elements from the second array. Similar comparison is done for the second array as well. if neither conditions satisfy then we have found the right partition and just need to confirm by comparing both mid’s
Dutch national flag problem. Sort a given array of integers in order where each color represents a number. This must be done in place and going over the array only once
[0,1,0,2]
We use three pointers
one is the current element (curr)
one is the leftmost element ( left)
one is the rightmost element (right)
if the current == 0 we swap curr with left
then we curr++ and left++
if the current == 2 we swap curr with right
then right–;
else we curr++;
all of this is done till curr <= right;
Quick Select
Used in problems where kth frequent, kth largest, kth less frequent
similar to doing quick sort but we can make it more effective by considering only one half
while partitioning consider right most element as pivot
pivot = arr[right]
i= left;
j = left till right
compare if the j <= pivot then swap i with j
once you go through all elements then swap i with pivot and return i;
Then compare i with the kth element position. If it isn’t same then consider which side of the array to perform quick select again
Given a graph, of street view with time to travel between vertices. Given a start and end location find the time taken to travel.
Similar to Dijakstra
What data structure would you use for a LRU Cache(least recently used) that will do insert and delete in constant time and delete the first added value?
There is a structure that combines both hashmap and linked list. in Java LinkedHashMap.
OR
you can use a hashmap of key to value(value: is a doubly linked list so that removal from front is easy)
How would you find the longest palindromic substring
an approach is to try expand as you go through the characters of the string. eventually you will reach a point where a possible palindrome can form as you expand from it
Some operations whose time complexity is often mistaken
- Adding or removing (or even changing) just one character anywhere in a string is O(n)O(n), because strings are immutable. The entire string is rebuilt for every change.
- Adding or removing not from the end of a list, vector, or array is O(n)O(n) because the other items are moved up to make a gap or down to fill in the gap.
- Checking if an item is in a list, because this requires a linear search. Even if you use binary search, it’ll still be O(\log n)
- Recall that checking if an item is in a set is O(1)
Coin change problem
Given coins [1,2,5] what is the minimum coins to make amount =11
Can use dynamic programming
generate a dp array starting from 0 to the amount.
initialize all values to amount+1;
initialize dp[0] = 0 , since in order to generate amount =0 the minimum coins will always be 0.
keep building this dp array utilizing the previous values
the dp[amount] will have the answer. if its value > amount+1 that means there is no solution
How would you return the next lexicographic permutation for a given array of integers
eg: [1,2,3]
the permutations are 123, 132,321 etc
ans: 132
start from the rightmost side and find the first number a[i] < a[i+1]
in this case it is 2
then start again from the right and find the first number > 2, which is 3.
exchange 2 and 3
1 3 2
and reverse all elements after 3
How do you group given strings into groups of anagrams?
Method 1:
for every string
sort the string
put it in a map with key(the sorted string) and value the actual string
this way the map with have a list of strings in its values
return a new ArrayList(map.values())
Method 2:
use an array of 26 letters for EACH string.
populate it with the count of characters in that word
example :raat will have [2,0…….1,…..1] where 2 is the count for ‘a’ and 1 for r and t
generate a unique key using these values(can add # before each count to generate a unique string to be used a hash key of a map or add all the counts )
check if that key exists in the map if it does append the string s to the list of values
else add it to the map
return a new ArrayList(map.values())
Parentheses problem
Stacks and recursion
How to find distinct values in a list
Use one slow pointer and other faster. move the faster pointer till you find a non distinct value and then swap with the value that repeats
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length == 0 || nums.length == 1) return nums.length;
int i =0;
for(int j = 1 ;j< n ;j ++){
if(nums[i] != nums[j]) {
i++;
nums[i] = nums[j];
}
}
return j+1;
}
}
How to find the integer that occurs once in an array of integers in which there are exactly two occurrences of every value except for one?
Example:
Input: [2,2,1]
Output: 1
Hashmap can be using to keep track of counts
Hashset as well
In ONLY this scenario where there are exactly TWO occurrences we can do bit manipulation (XOR)
class Solution {
public int singleNumber(int[] nums) {
int a = 0;
for (int i : nums) {
a ^= i;
}
return a;
}
}
How to find max or min number of items in an array that appear consecutively?
Example:
Input :[1,1,2,2,2]
Output : 3 (2 occurs thrice)
Determine what is the starting point of a window(consecutive items) and then determine how to end that window
Critical connections in a graph
Tarjan’s Algorithm:
We have to find the articulation points(the vertex if removed will cause the graph to be disconnected)
Need to do dfs because we have to go through each edge therefore recursion
maintain visitedTime and lowestTime
Rotten oranges
We need to do bfs since we want the minimum path to make all oranges rotten
We need a queue of a pair in order to keep track of which row and column we are at
this will help us know if we have to continue going through the grid to ensure all oranges are rotten
int freshOranges = 0;
int minutes = -1;
//Put only rotten oranges in a queue so we can pull each one out and reduce freshoranges count by 1 for every neighbor
//This is added to the queue to indicate one level so we will know that a minute is elapsed
queue.offer(new Pair(-1, -1));
//this shows all possible directions from say origin 0,0. It can be used to derive the neighbours for a give row and column
int[][] directions = {{-1,0}, {1,0}, {0,1}, {0,-1}};
while we remove elemnts from queue if the value ==-1 that means we finished a level and can increment minutes else for every direction we set the value to 2(make them rotten) and add them to the q since they are now rotten and also reduce the number of fresh oranges.
in the end if the fresh oranges are 0 we have our answer else there was no way to make all them rotten
Topological sort
Only can be performed on a directed acyclic graph
This means providing the order of vertices such that all edges are directed upwards
Useful for figuring out the precedence (like course schedule)
It uses dfs and a stack. For every node if it isnt visited perform dfs. After all the neighbors are visited , add the node to the stack
return the stack
Krushkal Algorithm
To find the Minimum spanning tree which is the lowest weight tree that connects all vertices
Backtracking algorithm
def backtrack(candidate):
if find_solution(candidate):
output(candidate)
return
# iterate all possible candidates.
for next_candidate in list_of_candidates:
if is_valid(next_candidate):
# try this partial candidate solution
place(next_candidate)
# given the candidate, explore further.
backtrack(next_candidate)
# backtrack
remove(next_candidate)
How is a 2D array stored in reality in memory
So a 2D array is stored as a single one dimensional array.
the memory it is stored at is inumberOfCol +j where i is the row and j is the column.
For example: position arr[2][1] , in a matrix with 4 rows and 3 columns.
the memory location allocated to it is
23 +1 = 7
In order to get the row we will do 7/3 =2
In order to get the column we do 7%3 =1
What are prefix sums
It allows for the fast calculation of sums of
elements in given slice (contiguous segments of array). Its main idea uses prefix sums which
are defined as the consecutive totals of the first 0, 1, 2, . . . , n elements of an array
for an array a,
p0 = 0 p1 = a0 p2 = a0 + a1 and so on
What is the greedy approach?
Pick the locally optimal move at each step, and that will lead to the globally optimal solution.
Two Sum Problem
Given an array return the indices of the two elements whose sum is equal to a given target
Iterate through the array and build a hashmap, key [ = target - current element in array] and value will be the index of the current element. Before doing so also check whether key exists, if so, you found the other index.
Given a small string s and a big string b, we need to find all permutations of the shorter string s in b.
Sliding window solution.
Slide through b using the window size as s.Length and then see if a permutation of s exist in that window
Permutation problems
Start thinking with Recursion.
For instance, find all the permutations for the string “abc”
we can start with permutation of a
a => a
a => insert b in every permutation of a => ab, ba
ab => insert c in every permutation of ab => cab acb abc
ba => insert c in every permutation of ba => cba bca bac
Problem with ordering and finding medians
Start with trees or heaps
Sorted array related problems and to solve it in-place as in without creating a new array
Think of two pointer or 3 pointer approach (whatever is applicable). Also whenever you’re trying to solve an array problem in-place, always consider the possibility of iterating backwards instead of forwards through the array. It can completely change the problem, and make it a lot easier.
Data structure to process elements in order
Queue. For implementing queue there are two pointers head and tail. And you can calc tail using this formula:
tailIndex = (headIndex + count) % size - 1
where count is the number of elements filled and size is the total size of the array.
Moving window average
We need to process elements in order, so Queue will be a perfect data structure for this
IF sorted THEN
(binary search OR two pointer)
IF all permutations/subsets THEN
backtracking
IF tree THEN
(recursion OR two pointer OR obvious recursion)
IF graph THEN
dfs/bfs
IF linkedlist o(1) space THEN
two pointer
IF obvious recursion problem but recursion banned THEN
stack
IF options (+1 or +2) THEN
DP
IF k items THEN
heap
IF common strings THEN
(map OR trie)
Stock buy and sell problems where prices are listed as array
These are considered peak-valley problems, where you want to find the lowest valley and highest peak.
Robot bounded in circle or what are the conditions for limit cycle trajectory
These problems are solved using limit cycle trajectory. A trajectory is considered limit cycle if:
- either we reach at the origin point after one cycle of instructions
- or we end at a different direction after one cycle of instructions, so for instance, started towards north and ended towards west
Limit cycle trajectories are based on the principle that after 4 cycles the robot will reach at the origin
