Algorithms

Question 1

What is an algorithm?

Answer 1

A process or set of steps to accomplish a certain task.

Question 2

Why do I need to know algorithms?

Answer 2

It is the foundation for being a successful problem solver and developer.

Question 3

What are the 5 steps to take to best solve a problem?

Answer 3

1. Understand the problem
2. Explore concrete examples
3. Break it down
4. Solve/Simplify
5. Look back and refactor

Question 4

When solving a problem, what are the 5 steps/questions that can help to better understand the problem?

Answer 4

1. Can I restate the problem in my own words?
2. What are the inputs that go into the problem?
3. What are the outputs that should come from the solution of the problem?
4. Can the outputs be determined from the inputs of the problem. or do I have enough information to solve the problem?
5. How should I label the important pieces of data that are part of the problem?

Question 5

When solving a problem, what are the 4 steps to take when exploring examples?

Answer 5

1. Start with simple examples 2. Progress with more complex examples 3. Explore examples with empty inputs 4. Explore examples with invalid inputs

Question 6

When solving a problem, how do you break down the problem? And why would you break it down?

Answer 6

By explicitly writing out the steps you need to take, in pseudocode or comments. It forces you to think about your approach and the code you are going to write before you write it, and helps you catch any lingering conceptual issues or misunderstandings before you dive in and have to worry about details (e.g. language syntax) as well.

Question 7

When solving a problem and getting stuck, what are the 4 steps to take to simplify the problem?

Answer 7

1. Find the core difficulty in what you are trying to do 2. Temporarily ignore that difficulty 3. Write a simplified solution 4. Then incorporate that difficulty back in

Question 8

When solving a problem, what are the 5 ‘look back and refactor’ questions to ask yourself?

Answer 8

1. Can I check the result? 2. Can I understand it at a glance? 3. Can I improve the performance of the solution? 4. Can I derive the result differently? 5. Can I think of other ways to refactor?

Question 9

In JavaScript, how to use a regular expression to check if a character is an alphanumeric character?

Answer 9

/[a-zA-Z0-9]/.test(character)

Returns true if it finds a match, otherwise it returns false Note: Regular expressions do not have the best performance; checking ASCI character code value (using string.charCodeAt(index)) could be about 50% faster.

Question 10

Name 7 of the most commonly used problem solving ideas or patterns.

Answer 10

1. Frequency Counter
2. Multiple Pointers
3. Sliding Window
4. Divide and Conquer
5. Dynamic Programming
6. Greedy Algorithms
7. Backtracking

Question 11

What is the idea behind Frequency Counters,, and how do they improve performance?

Answer 11

The Frequency Counters pattern uses an object or set to collect values/frequencies of values.

They often avoids the need for nested loops or O(n^2) operations with arrays/strings.

Question 12

What is the idea behind the Multiple Pointers pattern, and how do they improve performance?

Answer 12

The Multiple Pointers pattern creates values (pointers) that correspond to an index or position, and move towards the beginning, end or middle based on a certain condition.

This pattern is very efficient for solving problems with minimal space complexity.

Question 13

What is the idea behind the Sliding Window pattern, and what is it useful for?

Answer 13

The Sliding Window pattern involves creating a window which can eiter be an array or number from one position to another. Depending on a certain condition, the window either increases or closes (and a new window is created).

The Sliding Window pattern is useful for keeping track of a subset of data in an array/string etc.

Question 14

What is the idea behind the Divide and Conquer pattern, and what is its biggest advantage?

Answer 14

The Divide and Conquer pattern involves dividing a data set into smaller chunks and then repeating a process with a subset of data.

The Divide and Conquer pattern can tremendously decrease time complexitiy.

Question 15

What is a recursive function, and how does it affect the call stack?

Answer 15

A recursive function is a function that keeps calling itself until it reaches a base case. A recursive function keeps pushing new functions onto the call stack.

Question 16

Explain the use of the call stack in regards to functions?

Answer 16

• Any time a function is invoked it is placed (pushed) on the top of the call stack.
• When the compiler sees the return keyword or when the function ends, the compiler will remove (pop) the function from (the top of) the stack.

Question 17

What are three essential parts of a recursive function?

Answer 17

1. Base case: the condition when the recursion ends. This is the most important concept to understand.
2. Different input: each time the recursive function is called it must be called with different data.
3. Return: the recursive function should return a value.

Question 18

What is Helper Method Recursion, and when is it commonly used?

Answer 18

A design pattern that uses two functions:

• an outer function that called to invoke the function, and
• an inner function (called helper function) which is a recursive function, and called by the outer function.

It is commonly used when needing to compile an array or a list of data.

Question 19

What is Pure Recursion?

Answer 19

A design pattern where the recursive function is totally self contained; so without the use of a nested or helper function.

Question 20

What is Linear Search?

Answer 20

The simplest way to search for a value; look at every element in an array and check if it’s the wanted value.

Question 21

What search method does JavaScript use on arrays for indexOf, includes, find, findIndex? What is the time complexity?

Answer 21

For these built-in array search methods, JavaScript uses a Linnear Search method. The time complexity is O(n).

Question 22

When can one use Binary Search? What problem solving pattern does it use? What is its time complexity, and what is the advantage vs Linnear Search?

Answer 22

This search method only works on sorted arrays.

It uses the Divide and Conquer problem solving pattern; rather than eliminating one element at a time, it eliminates half of the remaining elements at a time.

It has a time complexity of O(log n) and it is a much faster for of search than for example Linnear Search with time complexity of O(n).

Question 23

What are the 3 more elementary (simpler) and less efficient sorting algorithms? Why are they also known as quadratic algorithms?

Answer 23

These sorting algorithms are:

• Bubble Sort
• Selection Sort
• Insertion Sort

Their Big O time complexity is O(n²).

Question 24

How does Bubble Sort work? What is its time complexity?

Answer 24

Sorting algorithm where on each iteration the larger value of an adjacent pair is swapped to the right, and as a result the largest value is “pushed” to the end of the array.

The array is sorted if no swap was made on an iteration.

The time complexity is: O(n^2)

Question 25

How does Selection Sort work? What is its time complexity?

Answer 25

Sorting algorithm where on each iteration the index of the smallest value is “selected”, and at the end of the iteration swapped to the beginning of the array.

The array is sorted if no swap was made on an iteration.

The time complexity is: O(n^2)

Question 26

How does Insertion Sort work? What is its time complexity?

Answer 26

Sorting algorithm that builds up the sort by gradually creating a larger sorted portion. It takes elements one by one, and inserts them in the right spot in the sorted left portion of the array.

The time complexity is: O(n^2)

Question 27

What are the 3 more intermediate and faster sorting algorithms?

Answer 27

These sorting algorithms are:

• Merge Sort
• Quick Sort
• Radix Sort

Their Big O time complexity is O(n log n).

Question 28

What is the idea behind the Merge Sort algorithm? What is its Big O time complexity and why? What is the space complexity?

Answer 28

This sorting algorithm uses a combination of three things:

• splitting up (into arrays of 0 or 1 elements)
• sorting
• merging (smaller arrays into new sorted array)

The Big O time complexity is O(n log n), space complexity O(n).

Time complexity is O(n log n) because of:

• O(log n) decompositions when splitting
• comparing O(n) items when merging

Question 29

What is Dynamic Programming?

Answer 29

A method of solving a complex problem where the problem is split into simpler problems, and the solutions of the simpler problems are used to find the solution of the original complex problem.

Question 30

What is the best Big O time complexity for data agnostic sorting algorithm?

Answer 30

O(n log n)

Question 31

How does Quicksort work? What is its Big O time complexity and space complexity

Answer 31

This divide-and-conquer sorting algorithm works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Big O time complexity (in worst case) is O(n^2) and space complexity is O(n).

Question 32

What is Dynamic Programming? And what properties should a problem have in order to use it?

Answer 32

A method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of the subproblems just once and storing their solutions.

It only works on problems that have:

• overlapping subproblems; can be broken down into subproblems which are reused several times, and
• an optimal substructure; an optimimal solution can be constructed from optimal solutions of its subproblems.

Question 33

What is Memoization?

Answer 33

Storing the results of expensive function calls and returning the cached results when the same inputs occur again.

Question 34

In Dynamic Programming, what is Tabulation?

Answer 34

It is storing the result of a previous result in a “table” (usually an array). Usually done using iteration. Better space complexity can be achieved using it.