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