CS Interview Questions

A set of instructions that can be executed to accomplish a specific task or to produce a result. A process durer for solving a problem is called an algorithm.

Big O Notation is a way to measure an algorithm's efficiency. It measures the time it takes to run your function as the input grows.

In case the list of elements is not sorted, there's no way to use binary search because the median value of the list can be anywhere and when the list is split into two parts, the element that you were searching for could be cut off. This is why binary search is not useful.

Recursion is a process of calling itself. A function that calls itself is called a recursive function. One critical requirement of recursive functions is the termination point or base case. Every recursive program must have a base case to make sure that the function will terminate. Missing base case results in unexpected behavior.

function sum(num) {
	if (num == 0) {
		return num
	}
	return num + sum(num - 1)
}

console.log(sum(10)) //55

Sorting is the processing of arranging the data in ascending and descending order. There are several types of sorting in data structures namely – bubble sort, insertion sort, selection sort, bucket sort, quick sort etc.

Ascending order is the arrangement of numbers from the smallest to the largest. For example, the following numbers are in ascending order: 3, 15, 28, 49. Descending order is an arrangement of numbers from the largest to the smallest. For example, the numbers 45, 32, 26, 12 are arranged in descending order.

Ascending

• 1
• 2
• 3
• 4
• 5

Descending

• 5
• 4
• 3
• 2
• 1

Sorting can often reduce the complexity of a problem, it is an important algorithm in Computer Science. These algorithms have direct applications in searching algorithms, database algorithms, divide and conquer methods, data structure algorithms, and many more.

Linear search is also known as sequential search. It is named as linear because its time complexity is of the order of n O(n).

• Binary search requires that the list be sorted. Linear search does not require that the list be sorted.
• Binary search require comparisons to be made. Linear search does not require comparisons to be made. Linear search require equality comparisons.
• Binary search time complexity is O(log n). Linear search time complexity is O(n).

Example of binary search:

function binarySearch(arr, item) {
  let low = 0
  let high = arr.length - 1
  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    const guess = arr[mid]
    if (guess === item) {
      return true
    }
    if (guess > item) {
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return false
}

Example of linear search

function linearSearch(arr, item) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === item) {
      return true
    }
  }
  return false
}

A linear search is a simple search algorithm that looks at each element in the data set and checks if the element is the one you are looking for. Starting at the beginning of the data set. Once the item is found, the search ends.

function linearSearch(arr, item) {
	for (let i = 0; i < arr.length; i++) {
		if (arr[i] === item) {
			return true
		}
	}
	return false
}

linearSearch([1, 2, 3, 4, 5], 3) // true

Big O Notation The time complexity is O(n) because the algorithm has to look at each element in the data set.

Linear time complexity O(n) means that the algorithms take proportionally longer to complete as the input grows.

Examples of linear time algorithms: Get the max/min value in an array.

function getMax(arr) {
	let max = arr[0]
	for (let i = 1; i < arr.length; i++) {
		if (arr[i] > max) {
			max = arr[i]
		}
	}
	return max
}

function getMin(arr) {
	let min = arr[0]
	for (let i = 1; i < arr.length; i++) {
		if (arr[i] < min) {
			min = arr[i]
		}
	}
	return min
}

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

const max = getMax(arr)
const min = getMin(arr)

In the above example, the algorithm is O(n) because it has to loop through the array once to find the max and once to find the min value. The loop is dependent on the size of the array.

Big O notation is written in the form of O(n) where O stands for “order of magnitude” and n represents what we're comparing the complexity of a task against.

Space complexity is the amount of memory that an algorithm will use. Algorithms are run on a computer It need certain amount of memory space to run. The amount of memory used by an algorithm is called its space complexity.

Example:

function factorial(n) {
	if (n === 0) {
		return 1
	}
	return n * factorial(n - 1)
}

The above algorithm will use O(n) space complexity. This is because it will use n amount of memory to store the result of the factorial function.

Another Example:

function sum(n1, n2) {
	return n1 + n2
}

This algorithm will use O(1) space complexity. This is because it will use only one memory space to store the result of the sum function.

Space complexity types are used to describe the amount of space required to store a given data structure.

Space complexity types#

• O(1): Constant time complexity.
• O(n): Linear time complexity.
• O(log n): Logarithmic time complexity.

The fastest possible running time for any algorithm is O(1), commonly referred to as Constant Running Time. In this case, the algorithm always takes the same amount of time to execute, regardless of the input size.

Example of Constant Running Time:

function constantRunningTime(n) {
	return n
}

constantRunningTime(1) // O(1)

The above algorithm is the fastest possible running time for any algorithm. It always takes the same amount of time to execute, regardless of the input size.

Binary search is a search algorithm that works by comparing the target value to the middle element of the data set. If the target value is less than the middle element, the algorithm repeats the process on the lower half of the data set. If the target value is greater than the middle element, the algorithm repeats the process on the upper half of the data set.

function binarySearch(arr, item) {
 let low = 0
 let high = arr.length - 1

 while (low <= high) {
  const mid = Math.floor((low + high) / 2)
  const guess = arr[mid]

  if (guess === item) {
   return true
  }

  if (guess > item) {
   high = mid - 1
  } else {
   low = mid + 1
  }
 }

 return false
}

binarySearch([1, 2, 3, 4, 5], 3) // true

Note: The above algorithm is O(log n) because it has to divide the data set in half every time it loops.

Binary Search in String

const str = 'abcdefghijklmn'
function bSearch(array, word) {
 let left = 0
 let right = array.length - 1
 while (left <= right) {
  const mid = Math.floor((left + right) / 2)
  const guess = word.localeCompare(array[mid])
  if (0 == guess) {
   return { result: array[mid], index: mid }
  }
  if (guess > 0) {
   left = mid + 1
  } else {
   right = mid - 1
  }
 }
 return -1
}
console.log(bSearch(str.split(''), 'h'))