Algs Flashcards
1
Q
anagrams(str1, str2)
A
function anagrams(str1, str2){
const letters = {};
str1.split(“”).forEach(char => {
if(!letters[char]) letters[char] = 0;
letters[char] += 1;
});
str2.split(“”).forEach(char =>{
if (!letters[char]) letters[char] = 0;
letters[char] -= 1;
});
return Object.values(letters).every(letterCount => letterCount === 0);
}
2
Q
base_converter(n, b) // Write a recursive function, `baseConverter(n, b)` that takes in a base 10 // number `n` and converts it to a base `b` number. Assume that `b` will never // be greater than 16. Return the new number as a string. If the number is 0, // your function should return "0" regardless of the base. // // The 'base' of a number refers to the amount of possible digits that can occupy // one of the places in the number. We are used to base 10 numbers, which use // the digits 0-9, however in computer science base 2 (binary) and base 16 (hexadecimal) // numbers are often used. The digits used in base 16 are as follows (from // smallest to largest): // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f]
A
if([0,1].includes(n)) return n.toString()
const digits = [ ‘0’, ‘1’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’];
return baseConverter(Math.floor(n/b), b) + digits[n % b]; }
3
Q
binarySearch(array, target)
A
function binarySearch(array, target){
if (array.length === 0) return -1;
const midpoint = Math.floor(array.length/2);
if(array[midpoint] > target) {
return binarySearch(array.slice(0, midpoint), target);
} else if (array[midpoint] < target) {
const subResult = binarySearch(array.slice(midpoint + 1), target);
return subResult === -1 ? -1 : subResult + midpoint + 1;
} else {
return midpoint;
}
}
4
Q
bubble_sort
// Write an `Array.prototype.bubbleSort(callback)` method, that bubble sorts an array. // It should take an optional callback that compares two elements, returning // -1 if the first element should appear before the second, 0 if they are // equal, and 1 if the first element should appear after the second. Do NOT call // the built-in Array.prototype.sort method in your implementation. Also, do NOT // modify the original array. // // Here's a quick summary of the bubble sort algorithm: // // Iterate over the elements of the array. If the current element is unsorted // with respect to the next element, swap them. If any swaps are made before // reaching the end of the array, repeat the process. Otherwise, return the // sorted array.
A
const defaultCallback = (num1, num2) => {
if (num1 < num2) {
return -1;
} else if (num1 === num2) {
return 0;
} else {
return 1;
}
};
Array.prototype.bubbleSort = function (callback) {
if (typeof callback !== “function”) {
callback = defaultCallback;
}
let resultArr = this.slice();
let sorted = false;
while (!sorted) {
sorted = true;
for (let i = 1, n = resultArr.length; i < n; i++) {
if (callback(resultArr[i - 1], resultArr[i]) === 1) {
sorted = false;
let swap = resultArr[i - 1];
resultArr[i - 1] = resultArr[i];
resultArr[i] = swap;
}
}
}
return resultArr;
};
5
Q
ceasarCipher(str, shift)
// Write a function, `caesarCipher(str, shift)` that will take a message and an // increment amount and outputs the encoded message. Assume lowercase and no // punctuation. Preserve spaces. // // The English alphabet, in order, is 'abcdefghijklmnopqrstuvwxyz' // // Examples: // caesarCipher(“abc”, 2) => “cde” // caesarCipher(“xyz”, 1) => “yza"
A
function ceasarCipher(str, shift){
const alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('');
let encoded = "";
for (let i = 0; i < str.length; i++) {
if (str[i] === ' '){
encoded +- ' ';
continue;
}
const offset = (alphabet.indexOf(str[i]) + shift) % 26;
encoded += alphabet[offset];
}
return encoded;
}
6
Q
deepDup(arr);
// Write a function, `deepDup(arr)`, that will perform a "deep" duplication of // the array and any interior arrays. A deep duplication means that the array // itself, as well as any nested arrays (no matter how deeply nested) are duped // and are completely different objects in memory than those in the original // array.
A
function deepDup(arr){
return arr.map(el => el instanceof Array ? deepDup(el) : el);
}
7
Q
digitalRoot(num)
Write a function, `digitalRoot(num)`. It should sum the digits of a positive // integer. If the result is greater than 9 (i.e. more than one digit), sum the // digits of the resulting number. Keep repeating until there is only one digit // in the result, called the "digital root". // **Do not use string conversion within your method.** // // You may wish to use a helper function, `digitalRootStep(num)` which performs // one step of the process.
A
function digitalRoot(num){
while (num >= 10) {
num = digitalRootStep(num);
}
return num;
}
function digitalRootStep(num) {
let root = 0;
while(num>0) {
root += num % 10;
num = Math.floor(num/10);
}
return root;
}
OR
function digitalRoot(num) {
return num < 10 ? num : digitalRoot(digitalRoot(Math.floor(num / 10)) + (num % 10));
8
Q
doubler(array)
A
function doubler(array){
return array.map(el => el * 2);
}
9
Q
dups
// Write an `Array.prototype.dups` method that will return an object containing
// the indices of all duplicate elements. The keys are the duplicate elements;
// the values are arrays of their indices in ascending order
//
// Example:
// [1, 3, 4, 3, 0, 3, 0].dups => { 3: [1, 3, 5], 0: [4, 6] }
A
Array.prototype.dups = function () {
const count = {};
const dups = {};
this.forEach( (el, idx) => {
count[el] = count[el] || [];
count[el].push(idx);
});
const keys = Object.keys(count).filter(el => count[el].length > 1);
keys.forEach( (key) => {
dups[key] = count[key];
});
return dups;
};
10
Q
function exponent(b, n)
// Write a function, `exponent(b, n)`, that calculates b^n recursively. // Your solution should accept negative values for n. Do NOT use ** or Math.pow
A
function exponent(b, n){
if (n===0) return 1;
if (n > 0) {
return b * exponent(b, n-1);
} else {
return 1/b * exponent(b, n + 1);
}
}
11
Q
factorialsRec(num)
// Write a recursive function, `factorialsRec(num)`, that returns the first // `num` factorial numbers. Note that the 1st factorial number is 0!, which // equals 1. The 2nd factorial is 1!, the 3rd factorial is 2!, etc.
A
function factorialsRec(num){
if(num === 1) return [1];
const facts = factorialsRec(num - 1); facts.push(facts[facts.length - 1] * (num - 1)); return facts; }
12
Q
function factors(num)
hint: THE WEIRD ONE
A
function factors(num){
const facts = Array.from(Array(num)).map((el, idx) => idx + 1);
return facts.filter(el => num % el === 0);
}
13
Q
function fibsSum(n)
// Write a function, `fibsSum(n)`, that finds the sum of the first n // fibonacci numbers recursively. Assume n > 0. // Note that for this problem, the fibonacci sequence starts with [1, 1].
A
function fibSum(n) {
if (n === 1) return 1;
if (n === 2) return 2;
return fibsSum(n - 1) + fibsSum(n - 2) + 1; }
14
Q
function firstEvenNumbersSum(n) / Write a function `firstEvenNumbersSum(n)` that returns the sum of the // first n even numbers recursively. Assume n > 0
A
function firstEvenNumbersSum(n) {
if (n === 1) return 2;
return 2 * n + firstEvenNumbersSum(n - 1);
}
15
Q
inherits
A
Function.prototype.inherits =
function(Parent) {
function Surrogate() {}
Surrogate.prototype = Parent.prototype;
this.prototype = new Surrogate();
this.prototype.constructor = this;
};
16
Q
jumbleSort(str, alphabet = null)
Write a function `jumbleSort(string, alphabet)`.
// Jumble sort takes a string and an alphabet. It returns a copy of the string
// with the letters re-ordered according to their positions in the alphabet. If
// no alphabet is passed in, it defaults to normal alphabetical order (a-z).
//
// The English alphabet, in order, is 'abcdefghijklmnopqrstuvwxyz'
// Example:
// jumbleSort("hello") => "ehllo"
// jumbleSort("hello", ['o', 'l', 'h', 'e']) => 'ollhe'
A
function jumbleSort(str, alphabet = null) {
alphabet = alphabet || 'abcefghijklmnopqrstuvwxyz'.split('');
str = str.split('');
let sorted = false;
while (!sorted) {
sorted = true;
for (let i = 0; i < str.length; i ++) {
if (i === str.length - 1) break;
let current = str[i];
let next = str[i + 1];
if (alphabet.indexOf(current) > alphabet.indexOf(next)) {
str[i] = next;
str[i + 1] = current;
sorted = false;
}
}
}
return str.join('');
}
17
Q
median
// Write an `Array.prototype.median` method that returns the median of elements // in an array. If the length is even, return the average of the middle two // elements.
A
Array.prototype.median = function () {
if (!this.length) return null;
const sorted = this.sort();
const mid =
Math.floor(this.length/ 2);
if (this.length % 2 !== 0) {
return sorted[mid];
} else {
return (sorted[mid] +
sorted[mid - 1]) / 2;
}
};
18
Q
merge_sort
Write an `Array.prototype.mergeSort` method that merge sorts an array. It // should take an optional callback that compares two elements, returning -1 if // the first element should appear before the second, 0 if they are equal, and 1 // if the first element should appear after the second. Define and use a helper // method, `merge(left, right, comparator)`, to merge the halves. // // **IMPORTANT: Make sure to use a function declaration (`function merge`) as // opposed to a function expression (`const merge = function`) for `merge`. Do // NOT use the built-in `Array.prototype.sort` method in your implementation.** // // Here's a summary of the merge sort algorithm: // // Split the array into left and right halves, then merge sort them recursively // until a base case is reached. Use a helper method, merge, to combine the // halves in sorted order, and return the merged array.
A
Array.protype.mergeSort = function (func) {
if (this.length <= 1) return this;
if (!func) func = (left, right) => {
return left < right ? -1 : left > right ? 1 : 0;
};
const midpoint = Math.floor(this.length /2); const sortedLeft = this.slice(0, midpoint).mergeSort(func); const sortedRight = this.slice(midpoint).mergeSort(func); return merge(sortedLeft, sortRight, func); };
function merge(left, right, comparator) {
let merged = [];
while (left.length && right.length) {
switch(comparator(left[0], right[0])) {
case -1:
merged.push(left.shift());
break;
case 0:
merge.push(left.shift());
break;
case 1:
merged.push(right.shift());
break;
}
}
merged = merged.concat(left, right);
return merged;
}
19
Q
my_apply
// Write a `Function.prototype.myApply(context, argsArr)` method that accepts an // object and an array of additional arguments. It should call the function with // the passed-in object as `this`, also passing the arguments array. Do NOT use // the built-in `Function.prototype.apply` or `Function.prototype.call` methods // in your implementation.
A
Function.prototype.myApply = function (context, args =[]) {
return this.bind(context)(…args);
};
OR
Function.prototype.myApply = function (context, args = []){
return this.bind(context, …args)();
};
20
Q
myBind
// Write a `Function.prototype.myBind(context)` method. It should return a copy // of the original function, where `this` is set to `context`. It should allow // arguments to the function to be passed both at bind-time and call-time. // Note that you are NOT allowed to use ES6 arrow syntax for this problem.
A
Function.prototype.myBind = function (context, ...bindArgs){
const that = this;
return function (...callArgs) {
return that.apply(context, bindArgs.concat(callArgs));
};
};
21
Q
myCall
// Write a `Function.prototype.myCall(context)` method, that accepts an object, // and any number of additional arguments. It should call the function with the // passed-in object as `this`, also passing the remaining arguments. Do NOT use // the built-in `Function.prototype.call` or `Function.prototype.apply` methods // in your implementation.
A
Function.prototype.myCall = function (context, …args){
return this.bind(context)(…args);
};
22
Q
my_curry
// Write a `Function.prototype.myCurry(numArgs)` method that collects arguments // until the number of arguments collected is equal to the original `numArgs` // value and then invokes the curried function.
A
Function.prototype.myCurry = function (numArgs) {
let nums = [];
let fcn = this;
return function _myCurry (el) {
nums.push(el);
if (nums.length < numArgs) {
return _myCurry;
} else {
return fcn(...nums);
}
};
};
23
Q
myEach
// Write an `Array.prototype.myEach(callback)` method that invokes a callback // for every element in an array and returns undefined. Do NOT use the built-in // `Array.prototype.forEach`.
A
Array.prototype.myEach = function (func) {
for (let i = 0; i < this.length; i++){
func(this[i]);
}
};
24
Q
myFilter
// Write an `Array.prototype.myFilter(callback)` that takes a callback and // returns a new array which includes every element for which the callback // returned true. Use the `Array.prototype.myEach` method you defined above. Do // NOT call the built-in `Array.prototype.filter` or `Array.prototype.forEach` // methods.
A
Array.prototype.myFilter = function (callback) {
const result = [];
this.myEach((el) => {
if (callback(el)) result.push(el)
});
return result;
};
25
myFind(array, callback)
```
// Write a function `myFind(array, callback)` that returns the first
// element for which the callback returns true. If none is found, the
// function should return `undefined`
// Do not use the built-in `Array.prototype.find` method.
```
```
function myFind(array, callback) {
for (let i = 0; i < array.length; i++) {
if (callback(array[i])){
return array[i];
}
}
}
```
26
myFlattten
```
// Write an `Array.prototype.myFlatten()` method which flattens a
// multi-dimensional array into a one-dimensional array.
// Example:
// [["a"], "b", ["c", "d", ["e"]]].myFlatten() => ["a", "b", "c", "d", "e"]
```
```
Array.prototype.myFlatten = function () {
let flattened = [];
```
```
this.forEach((el) => {
if (el instanceof Array) {
flattened = flattened.concat(el.myFlatten());
} else {
flattened.push(el);
}
});
returned flattened;
};
```
27
myJoin
```
// Write an `Array.prototype.myJoin(separator)` method, which joins the elements
// of an array into a string. If an argument is provided to `myJoin`, use that
// between each element. Otherwise, use an empty string.
// Do NOT call the built-in `Array.prototype.join` method.
// ex.
// [1, 2, 3].myJoin() => '123'
// [1, 2, 3].myJoin('$') => '1$2$3'
```
```
Array.prototype.myJoin = function (seperator = '') {
let newString = "";
```
this.forEach((el, idx) => {
newString += `${el}`;
if (idx < this.length - 1) newString += separator;
});
return newString;
};
28
myReduce
```
// Write an `Array.prototype.myReduce(callback, acc)` method which takes a
// callback and an optional argument of a default accumulator. If myReduce only
// receives one argument, then use the first element of the array as the default
// accumulator. Use the `Array.prototype.myEach` method you defined above. Do
// NOT call in the built-in `Array.prototype.reduce` or `Array.prototype.forEach`
// methods.
```
```
Array.prototype.myReduce = function (callback, acc) {
const array = this.slice();
```
if (typeof acc === 'undefined') {
acc = array.shift();
}
array.myEach(el => {
acc = callback(acc,el);
});
return acc;
};
29
myReject
```
// Write an `Array.prototype.myReject(callback)` method. Return a new array,
// which contains only the elements for which the callback returns false.
// Use the `Array.prototype.myEach` method you defined above. Do NOT call the
// built-in `Array.prototype.filter` or `Array.prototype.forEach` methods.
// ex.
// [1,2,3].myReject( (el) => el > 2 ) => [1, 2]
```
```
Array.prototype.myReject = function (callback) {
const selection = [];
```
```
this.myEach(el => {
if (!callback(el)) {
selection.push(el);
}
});
```
return selection;
};
30
myReverse(array)
```
// Write a function `myReverse(array)` which returns the array in reversed
// order. Do NOT use the built-in `Array.prototype.reverse`.
// ex. myReverse([1,2,3]) => [3,2,1]
```
```
function myReverse(array) {
const result = [];
for (let i = 1; i < array.length + 1; i++) {
result[i - 1] = array[array.length - i];
}
```
return result;
}
31
myRotate
```
// Write an `Array.prototype.myRotate(times)` method which rotates the array by
// the given argument. If no argument is given, rotate the array by one position.
// ex.
// ["a", "b", "c", "d"].myRotate() => ["b", "c", "d", "a"]
// ["a", "b", "c", "d"].myRotate(2) => ["c", "d", "a", "b"]
// ["a", "b", "c", "d"].myRotate(-1) => ["d", "a", "b", "c"]
```
```
Array.protoype.myRotate = function (times = 1) {
let rotations;
const rotated = this.slice(0);
```
if (times < 0) {
rotations = this.length + (times % this.length);
}
```
for (let i = 0; i < rotations; i++) {
rotated.push(rotated.shift());
}
```
return rotated;
};
32
```
mySlice
// Write a `String.prototype.mySlice(startIdx, endIdx)` method. It should take
// a start index and an (optional) end index and return a new string. Do NOT
// use the built-in string methods `slice`, `substr`, or `substring`.
// ex.
// `abcde`.mySlice(2) => `cde`
// `abcde`.mySlice(1, 3) => `bc`
```
```
String.prototype.mySlice = function (start, end) {
let slice = "";
```
if (typeof end === 'undefined') {
end = this.length;
}
```
for (let i = start; i < end && i < this.length; i ++){
slice += this[i];
}
return slice;
};
```
33
mySome
```
// Write an `Array.prototype.mySome(callback)` method which takes a callback
// and returns true if the callback returns true for ANY element in the array.
// Otherwise, return false.
// Use the `Array.prototype.myEach` method you defined above. Do NOT call the
// built-in `Array.prototype.some` or `Array.prototype.forEach` methods.
```
```
Array.prototype.mySome = function (callback) {
let some = false;
```
this.myEach(el => {
if (callback(el)) some = true;
});
return some;
};
34
```
permutations(array)
// Write a recursive function, `permutations(array)`, that returns all of the
// permutations of an array (A permutation is a possible ordering of the
// elements in an array)
// e.g. permutations([1,2]) => [[1,2], [2,1]]
// e.g. permutations([1,2,3]) => [[1,2,3], [1,3,2], [2,1,3],
// [2,3,1], [3,1,2], [3,2,1]]
```
```
function permutations(array) {
if (array.length <= 1) {
return [array];
}
```
```
const result = [];
const first = array.pop();
const prevPerms = permutations(array);
```
```
prevPerms.forEach(perm => {
for (let i = 0; i <= perm.length; i++) {
let nextPerm = perm.slice(0, i).concat([first]).concat(perm.slice(i));
result.push(nextPerm);
}
});
```
return result;
}
35
primeFactorization(num)
```
// Write a recursive function `primeFactorization(num)` that returns the prime
// factorization of a given number. Assume num > 1
//
// primeFactorization(12) => [2,2,3]
```
```
function primeFactorization(num) {
if (num === 1) return [];
```
let i =2;
while (!(isPrime(i) && num % i === 0 )) {
i++;
}
return [i].concat(primeFactorization(num/i));
}
```
function isPrime(num) {
if (num < 2) return false;
let i = 2;
```
while (i < num) {
if (num % i === 0) return false;
i++;
}
return true;
}
36
primes(num)
```
// Write a function `primes(num)`, which returns an array of the first "num" primes.
// You may wish to use an `isPrime(num)` helper function.
```
```
function primes(count) {
const primeNums = [];
let i = 2;
```
while (primeNums.length < count) {
if (isPrime(i)) primeNums.push(i);
i += 1;
}
return primeNums;
}
```
function isPrime(num) {
if (num < 2) return false;
let i = 2;
```
while (i < num) {
if (num % i === 0) return false;
i++;
}
return true;
}
37
quickSort
```
// Write an `Array.prototype.quickSort(callback)` method that quick sorts an array.
// It should take an optional callback that compares two elements, returning -1
// if the first element should appear before the second, 0 if they are equal, and
// 1 if the first element should appear after the second. Do NOT call the
// built-in Array.prototype.sort method in your implementation.
//
// Here's a summary of the quick sort algorithm:
//
// Choose a pivot element, then iterate over the rest of the array, moving the
// remaining elements on to the appropriate side of the pivot. Recursively quick
// sort each side of the array until a base case is reached.
```
quickSort = function (func) {
if (this.length < 2) return this;
```
if (!func) {
func = (x, y) => {
if (x < y) return - 1;
return 1;
};
}
```
```
const pivot = this[0];
let left = this.slice(1).filter((el) => func(el, pivot) === -1);
let right = this.slice(1).filter((el) => func(el, pivot) !== -1);
left = left.quickSort(func);
right = right.quickSort(func);
```
return left.concat([pivot]).concat(right);
};
38
realWordsInString
```
// Write a `String.prototype.realWordsInString(dictionary)` method, that returns
// an array containing the substrings of `string` that appear in `dictionary`.
// sorted alphabetically. This method does NOT return any duplicates.
```
```
String.prototype.realWordsInString = function (dictionary) {
const realWords = [];
```
```
dictionary.forEach((el) => {
if (this.includes(el)) realWords.push(el);
});
return realWords.sort();
};
```
39
recSum(nums)
```
// Write a recursive function `recSum(numArr)` that returns the sum of all
// elements in an array. Assume all elements are numbers.
```
```
function recSum(nums) {
if(!nums.length) return 0;
return nums[0] + recSum(nums.splice(1));
}
```
40
stringIncludeKey(string, key)
```
function stringIncludeKey(string, key) {
if (!key.length) return true;
```
```
let nextKeyChar = key[0];
let keyIndex = string.indexOf(nextKeyChar);
```
```
if (keyIndex < 0) return false;
return stringIncludeKey(string.slice(keyIndex + 1), key.slice(1));
}
```
41
```
subset(arr)
// Write a function `subsets(arr)` that recursively returns all subsets of an
// array. Examples:
// `subsets([1,2])` => [[],[1],[2],[1,2]]
// `subsets([1,2,3])` => [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
```
function subsets(arr) {
```
if (!arr.length) return [[]];
const last = arr[arr.length - 1];
```
const subs = subsets(arr.slice(0, arr.length - 1));
```
return subs.concat(subs.map((el) => {
let newArr = el.slice(0);
newArr.push(last);
return newArr;
}));
}
```
42
symmetricSubstrings
```
String.prototype.symmetricSubstrings = function () {
const symmetric = [];
```
```
for (let i = 0; i < this.length; i++) {
for (let j = 2; j <= this.length - i; j++) {
const subst = this.slice(i, i + j);
const reversed = subst.split('').reverse().join('');
```
if (subst === reversed) symmetric.push(subst);
}
}
return symmetric.sort();
};
43
titleize(title)
```
// Write a function `titleize(str)` that capitalizes each word in a string like
// a book title.
// Do not capitalize the following words (unless they are the first word in the
// string): ["a", "and", "of", "over", "the"]
```
```
function titlelize(title) {
const littleWords = ['a', 'and', 'of', 'over', 'the'];
```
```
const words = title.split(' ');
const titlelizeWords = words.map( (word, idx) => {
if (idx !== 0 && littleWords.indexOf(word) >= 0) {
return word.toLowerCase();
} else {
return word.slice(0, 1).toUpperCase() + word.slice(1);
}
});
return titleizedWords.join(' ');
}
```
44
transpose
```
// Write a function `transpose(arr)` that returns a 2d array transposed.
// e.g. transpose([[1,2],[3,4],[5,6]]) => [[1,3,5],[2,4,6]]
```
```
function transpose(arr) {
const transposedArr = [];
```
```
for (var col = 0; col < arr[0].length; col++) {
const transposedRow = [];
for (var row = 0; row < arr.length; row++) {
transposedRow.push(arr[row][col]);
}
transposedArr.push(transposedRow);
}
return transposedArr;
}
```
45
twoSum
```
Array.prototype.twoSum = function () {
const pairs = [];
for (let i = 0; i < this.length - 1; i++) {
for (let j = 1 + 1; j < this.length; j++) {
if (this[i] + this[j] === 0) pairs.push([i, j]);
}
}
return pairs;
};
```
