Alogrithms

Question 1

What is the condition to use binary search?

Answer 1

array must be sorted

Question 2

What is an inplace sorting alogrithm?

Answer 2

An in-place algorithm is an algorithm which transforms input using no auxiliary data structure.

Question 3

Write the selection sort formula

Answer 3

const array = [1,4,5,3,2]

function selectionSort(array){

 for(let i = 0; i < array.length-1; i++){
    let min = i; 
    for(let j = i+1; j < array.length; j++){
      console.log(array[j])
      if(array[j] < array[min] ){
         min = j; 
      }
    }
   if(min !== i){
     let temp = array[i];
     array[i] = array[min];
     array[min] = temp; 
   } 
  }
  return array; 
}

console.log(selectionSort(array))

Question 4

What does selection sort do?

Answer 4

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning

Question 5

What is bubble sort?

Answer 5

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Question 6

What is time complexity fo selection sort?

Answer 6

O of n squared

Question 7

What is the time complexity of bubble sort

Answer 7

O of n squared

Question 8

Write the algorithm for bubble sort

Answer 8

const array = [1,4,5,3,2]
const array2 = [1,2,3,4,5]

function bubbleSort(array){
for(let i = 0; i < array.length-1; i++){
  // let flag = 0;
  for(let j = 0; j < array.length; j++){
  if(array[j]>array[j+1]){
    let temp = array[j];
    array[j] = array[j+1];
    array[j+1] = temp; 
    flag++
    }
  }
  if(flag===0) return array; 
}

return array;

}

console.log(bubbleSort(array2))

Question 9

What is insertion sort?

Answer 9

Switch current element with all previous elements that are larger.

Question 10

Write the insertion sort algorithm

Answer 10

const array = [1,4,5,3,2]
const array2 = [1,2,3,4,5]

function insertionSort(array){
  for(let i = 1; i < array.length; i++){
    let value = array[i];
    let currIdx = i; 
    while(currIdx > 0 &amp;&amp; value < array[currIdx-1]){
      array[currIdx] = array[currIdx-1];
      array[currIdx-1] = value; 
      currIdx-- 
    }
  }
  return array; 
}

console.log(insertionSort(array))

Question 11

What is the time complexity of insertion sort?

Answer 11

O of n squared

Question 12

Write the algorithm for merge sort

Answer 12

//Merge Sort

const array = [1,4,5,3,2]
const array2 = [1,2,3,4,5]

function mergeSort(array){
  if(array.length < 2) return array

  let mid = Math.floor(array.length/2);
  let left = array.slice(0,mid);
  let right = array.slice(mid); 

return merge(
mergeSort(left),
mergeSort(right)
)

}

function merge (left, right) {
  let result = []
  let indexLeft = 0
  let indexRight = 0

  while (indexLeft < left.length &amp;&amp; indexRight < right.length) {
    if (left[indexLeft] < right[indexRight]) {
      result.push(left[indexLeft])
      indexLeft++
    } else {
      result.push(right[indexRight])
      indexRight++
    }
  }

return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight))
}

console.log(mergeSort(array))

Question 13

What is a stack

Answer 13

A data structure that serves as a collection of elements, with two principle operations: push and pop. Push adds an element to the collection. Pop removes the last element that was added. This data structure follows the “Last In, First Out” principle (LIFO), where the elements that were most recently pushed (added) to the stack, are popped off (removed) first.

Think of a stack of pancakes - you add pancakes to the top of the stack and eat them from top to bottom.

Question 14

What is a queue

Answer 14

A data strucure that serves as a collection of elements that preserves the order at which the elements are inserted. The principle operations are enqueue, which adds an element to the collection, and dequeue, which removes the element that was added the earliest. This data structure follows the “First In, First Out” principle (FIFO), where elements that are enqueued (added) into the queue first, are dequeue (removed) first.

Think of a line for a roller coaster - the people that enter the line first, are the ones that get on the ride first.

Question 15

What is a linked list?

Answer 15

A data structure that serves as a collection of elements. Data is stored in nodes, and each node has a reference to the next node. In order to access elements from a linked list, the first node (or head) is checked. If the element is not present in the first node, then the node that is referenced by the head (the second node) is checked. This action is repeated until the entire list is inspected. The two principle operations are push (or add) and contains. Push creates a new node and adds
it to the end of the list. Contains checks the entire list and determines if the element is present in any of the nodes.

Question 16

What is big O

Answer 16

Upper bound, slowest time

Question 17

How do you calculate add vs multiply N in O of N notation?

Answer 17

-If your algorithm is in the form “do this, then, when you’re all done, do that”then you add the runtimes.
Ex: 2 for loops
However it is still O(n) because it is still a linear algorithm rather than quadratic

If your algorithm is in the form “do this for each time you do that”then you multiply the runtimes.
Ex: nested loop

Question 18

What is O of n of binary search?

Answer 18

O(log N)

Question 19

What kinds of problems run in O(log N)?

Answer 19

This is a good takeaway for you to have. When you see a problem where the number of elements in the
problem space gets halved each time, that will likely be a 0(log N)runtime.
This is the same reason why finding an element in a balanced binary search tree isO(log N). With each comparison, we go either left or right. Half the nodes are on each side, so we cut the problem space in half each time.

Question 20

What type of algorithm would be classified O(2^n)?

Answer 20

Algorithms with 2 recursive calls.

Question 21

Write a fibininaci sequence recursively

Answer 21

function fib(n){
if(n===0) return 0;
else if (n===1) return 1;
else return fib(n-1)+fib(n-2);

Question 22

What is mergesort

Answer 22

An example of merge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.