InterviewCake

Question 1

What is the greedy approach

Answer 1

An algorithm that builds up a solution by choosing the option that looks the best at every step.

Question 2

Simple greedy example

Answer 2

Say you’re a cashier and need to give someone 67 cents (US) using as few coins as possible. How would you do it?

Whenever picking which coin to use, you’d take the highest-value coin you could. A quarter, another quarter, then a dime, a nickel, and finally two pennies. That’s a greedy algorithm, because you’re always greedily choosing the coin that covers the biggest portion of the remaining amount.

Question 3

Other greedy examples

Answer 3

Looking for a minimum spanning tree in a graph? At each step, greedily pick the cheapest edge that reaches a new vertex.
Trying to fit as many overlapping meetings as possible in a conference room? At each step, schedule the meeting that ends earliest.

Question 4

Binary Search

Answer 4

Start in the middle: is it bigger or smaller than the target. Repeat until the target is found. Only works with an ordered list

Question 5

Triangular series

Answer 5

A series of numbers where each number could be the row of an equilateral triangle. Always starts with 1 and increases by 1 with each number. Pairs of numbers on each side will always add up to the same value (1 mores than the series’s n.)

Question 6

Total Sum of triangular series

Answer 6

(n^2 + n)/2 1+2+3 = 6 (9 + 3)/2 = 6

Question 7

Memoization

Answer 7

ensures that a function doesn’t run for the same inputs more than once by keeping a record of the results for the given inputs (usually in an object).

Question 8

Bottom up

Answer 8

a bottom-up algorithm “starts from the beginning,” while a recursive algorithm often “starts from the end and works backwards.”

Question 9

Filter

Answer 9

var words = [‘spray’, ‘limit’, ‘elite’, ‘exuberant’, ‘destruction’, ‘present’];

const result = words.filter(word => word.length > 6);

console.log(result);
// expected output: Array ["exuberant", "destruction", "present"]