algorithms Flashcards
what is the difference between permutations and combinations?
permutation - order matters
combination - order does not matter
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
var permute = function(choices, temp = [], permutations = []) {
if(choices.length === 0){
permutations.push([...temp]);
}
for(let i = 0; i < choices.length; i++){
let newChoices = choices.filter((choice, index) => index !== i)
temp.push(choices[i])
permute(newChoices, temp, permutations)
temp.pop()
}
return permutations };
What is a Bottom-Up approach?
The bottom-up approach is often the most intuitive. We start with knowing how to solve the problem
for a simple case, like a list with only one element. Then we figure out how to solve the problem for two
elements, then for three elements, and so on. The key here is to think about how you can build the solution
for one case off of the previous case (or multiple previous cases).
What is a Top-down approach?
The top-down approach can be more complex since it’s less concrete. But sometimes, it’s the best way to
think about the problem.
In these problems, we think about how we can divide the problem for case N into subproblems.
Be careful of overlap between the cases.
Half-and-Half Approach
In addition to top-down and bottom-up approaches, it’s often effective to divide the data set in half.
For example, binary search works with a “half-and-half” approach. When we look for an element in a sorted
array, we first figure out which half of the array contains the value. Then we recurse and search for it in that
half.
Merge sort is also a “half-and-half” approach. We sort each half of the array and then merge together the
sorted halves.
Dynamic programming
Dynamic programming is mostly just a matter of taking a recursive algorithm and finding the overlapping
subproblems (that is, the repeated calls). You then cache those results for future recursive calls.
How do you find the nth Fibonacci?
- top down
memo = []
function fib(n) {
if (memo[n]) return memo[n]
let f
if(n <=2) f = 1
else f = fib(n-1) + fib(n-2)
memo[n] = f
return f
}
-bottom up
fib = []
function(n){
for(let I = 0; I < = n; I++){
if(I <=2) fib[i] = 1
else fib[I]= fib[I-1] + fib[I-2]
}
return fib[n]
}
What is the benefit of using memoization in a top down approach in recursion
it stores computations in a cache and removes the need of making a computation that we made in a previous tree
5 steps in dynamic programming
- define subproblems
- guess (part of the solution)
- relate subproblem solutions
- recurse & memoize OR use loops bottom up approach
- solve the original problem
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
var subsets = function(nums) {
const subsets = [];
permute(0, nums, [], subsets);
return subsets;
};
function permute(index, nums, current, subsets){
subsets.push(current.slice(0))
for(let i = index; i < nums.length; i++){
current.push(nums[i]);
permute(i+1,nums,current,subsets);
current.pop();
}
}
Implement tower of hanoi
var hanoi = function(disks, source, destination, buffer) {
if(disks === 1){
destination.push(source.pop());
} else {
hanoi(disks-1, source, buffer,destination);
destination.push(source.pop());
hanoi(disks-1, buffer, destination, source);
}
}
Given a string, determine if a permutation of the string could form a palindrome.
var isAnagram = function(s) {
let odds = 0;
const store = {}
for(let i = 0; i < s.length; i++){
store[s[i]] === undefined ? store[s[i]] = 1 : store[s[i]]++
if(store[s[i]] % 2 !== 0) {
odds++
} else {
odds--
}
}
return odds < 2
};
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ],
rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ]
var rotate = function(matrix) {
if(matrix.length === 0 || matrix.length!==matrix[0].length) return false
const len = matrix.length
for(let layer = 0; layer < len/2; layer++){
let first = layer;
let last = len - 1 - layer;
for(let i = first; i < last; i++){
let offset = i - first;
let top = matrix[first][i];
// left -> top
matrix[first][i] = matrix[last-offset][first];
// bottom -> left
matrix[last-offset][first] = matrix[last][last-offset];
//right -> bottom
matrix[last][last-offset] =matrix[i][last];
// top -> right
matrix[i][last] = top; // right
What is an in place algorithm
In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. In-place algorithm updates input sequence only through replacement or swapping of elements
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:
Input: [ [1,1,1], [1,0,1], [1,1,1] ] Output: [ [1,0,1], [0,0,0], [1,0,1] ] Example 2:
Input: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] Output: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]
var setZeroes = function(matrix) {
let isCol = false;
let R = matrix.length;
let C = matrix[0].length;
for (let i = 0; i < R; i++) {
// Since first cell for both first row and first column is the same i.e. matrix[0][0]
// We can use an additional variable for either the first row/column.
// For this solution we are using an additional variable for the first column
// and using matrix[0][0] for the first row.
if (matrix[i][0] == 0) {
isCol = true;
}
for (let j = 1; j < C; j++) {
// If an element is zero, we set the first element of the corresponding row and column to 0
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// Iterate over the array once again and using the first row and first column, update the elements.
for (let i = 1; i < R; i++) {
for (let j = 1; j < C; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// See if the first row needs to be set to zero as well
if (matrix[0][0] == 0) {
for (let j = 0; j < C; j++) {
matrix[0][j] = 0;
}
}
// See if the first column needs to be set to zero as well
if (isCol) {
for (let i = 0; i < R; i++) {
matrix[i][0] = 0;
}
}
};
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: “bb”
var longestPalindrome = function (s) {
if (s===null || s.length < 1) return "";
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
let len1 = expandAroundCenter(s, i, i);
let len2 = expandAroundCenter(s, i, i + 1);
let len = Math.max(len1, len2);
if (len > end - start) {
start = i - Math.floor((len - 1) / 2);
end = i + Math.floor(len / 2);
}
}
return s.substring(start, end + 1);
}
function expandAroundCenter( s, left, right) {
if(s === null || left > right) return 0;
while (left >= 0 && right < s.length && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
var productExceptSelf = function(nums) {
// The length of the input array
let length = nums.length;
// Final answer array to be returned
let answer = [];
// answer[i] contains the product of all the elements to the left
// Note: for the element at index '0', there are no elements to the left,
// so the answer[0] would be 1
answer[0] = 1;
for (let i = 1; i < length; i++) {
// answer[i - 1] already contains the product of elements to the left of 'i - 1'
// Simply multiplying it with nums[i - 1] would give the product of all
// elements to the left of index 'i'
answer[i] = nums[i - 1] * answer[i - 1];
}
// R contains the product of all the elements to the right
// Note: for the element at index 'length - 1', there are no elements to the right,
// so the R would be 1
let R = 1;
for (let i = length - 1; i >= 0; i--) {
// For the index 'i', R would contain the
// product of all elements to the right. We update R accordingly
answer[i] = answer[i] * R;
R *= nums[i];
}
return answer; }
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
var maxProfit = function(prices) {
let min = prices[0]
let output = 0;
for(let i=1; i < prices.length;i++){
const cur = prices[i]
const diff = cur - min
if(cur < min) min = cur
if(diff > output) output = diff
}
return output;
};Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
function maxSubArray(A) {
var prev = 0;
var max = -Number.MAX_VALUE;
for (var i = 0; i < A.length; i++) {
prev = Math.max(prev + A[i], A[i]);
max = Math.max(max, prev);
}
return max;
}
What is the main quality of a greedy algorithm?
Greedy algorithms make the best choice at each decision without looking ahead.
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
var maxProduct = function(nums) {
let currentMax = nums[0];
let currentMin = nums[0];
let finalMax = nums[0];
for(let i = 1; i < nums.length; i++){
let temp = currentMax
currentMax = Math.max(Math.max(currentMax * nums[i], currentMin*nums[i]), nums[i])
currentMin = Math.min(Math.min(temp * nums[i], currentMin*nums[i]), nums[i])
if(currentMax > finalMax){
finalMax = currentMax;
}
}
return finalMax;
};
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
Input: [3,4,5,1,2]
Output: 1
Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0
var findMin = function(nums) {
// If the list has just one element then return that element.
if (nums.length == 1) {
return nums[0];
}
// initializing left and right pointers.
let left = 0, right = nums.length - 1;
// if the last element is greater than the first element then there is no rotation.
// e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
// Hence the smallest element is first element. A[0]
if (nums[right] > nums[0]) {
return nums[0];
}
// Binary search way
while (right >= left) {
// Find the mid element
let mid = left + Math.floor((right - left) / 2);
// if the mid element is greater than its next element then mid+1 element is the smallest
// This point would be the point of change. From higher to lower value.
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1];
}
// if the mid element is lesser than its previous element then mid element is the smallest
if (nums[mid - 1] > nums[mid]) {
return nums[mid];
}
// if the mid elements value is greater than the 0th element this means
// the least value is still somewhere to the right as we are still dealing with elements
// greater than nums[0]
if (nums[mid] > nums[0]) {
left = mid + 1;
} else {
// if nums[0] is greater than the mid value then this means the smallest value is somewhere to
// the left
right = mid - 1;
}
}
return -1;
};
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
function threeSum(nums) {
const results = []
// obviously irrelevant if we don't have at least 3 numbers to play with! if (nums.length < 3) return results
// having the numbers in ascending order will make this problem much easier. // also, knowing the overall problem will take at least O(N^2) time, we can // afford the O(NlogN) sort operation nums = nums.sort((a, b) => a - b)
// if the question asks us for a custom target, we can control it here let target = 0
for (let i = 0; i < nums.length - 2; i++) {
// `i` represents the "left" most number in our sorted set.
// once this number hits 0, there's no need to go further since
// positive numbers cannot sum to a negative number
if (nums[i] > target) break
// we don't want repeats, so skip numbers we've already seen if (i > 0 && nums[i] === nums[i - 1]) continue
// `j` represents the "middle" element between `i` and `k`. // we will increment this up through the array while `i` and `k` // are anchored to their positions. we will decrement `k` for // for each pass through the array, and finally increment `i` // once `j` and `k` meet. let j = i + 1
// `k` represents the "right" most element let k = nums.length - 1
// to summarize our setup, we have `i` that starts at the beginning, // `k` that starts at the end, and `j` that races in between the two. // // note that `i` is controlled by our outer for-loop and will move the slowest. // in the meantime, `j` and `k` will take turns inching towards each other depending // on some logic we'll set up below. once they collide, `i` will be incremented up // and we'll repeat the process.
while (j < k) {
let sum = nums[i] + nums[j] + nums[k]
// if we find the target sum, increment `j` and decrement `k` for
// other potential combos where `i` is the anchor
if (sum === target) {
// store the valid threesum
results.push([nums[i], nums[j], nums[k]])
// this is important! we need to continue to increment `j` and decrement `k` // as long as those values are duplicated. in other words, we wanna skip values // we've already seen. otherwise, an input array of [-2,0,0,2,2] would result in // [[-2,0,2], [-2,0,2]]. // // (i'm not a fan of this part because we're doing a while loop as we're // already inside of another while loop...) while (nums[j] === nums[j + 1]) j++ while (nums[k] === nums[k - 1]) k--
// finally, we need to actually move `j` forward and `k` backward to the // next unique elements. the previous while loops will not handle this. j++ k--
// if the sum is too small, increment `j` to get closer to the target
} else if (sum < target) {
j++
// if the sum is too large, decrement `k` to get closer to the target
} else { // (sum > target)
k--
}
}
}
return results };
Implement an isAnagram method in java
static boolean isAnagram(String a, String b) {
if(a.length() != b.length()) return false;
int c[] = new int[26], d[] = new int[26] ;
a = a.toUpperCase();
b = b.toUpperCase();
for(int i=0; i
