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;
}
}
};
