Popular Interview Questions on Time and Space Complexity

1. Fibonacci sequence:

function fibonacci(n) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2); //function recursively calls itself twice for each value of n.
  }
}

Time complexity: O(2^n), since the function recursively calls itself twice for each value of n.
Space complexity: O(n), each recursive call requires memory to store its state on the call stack.

2. Reverse a string

function reverseString(str) {
  return str.split('').reverse().join(''); // t(n) = O(n)+O(n)+O(n)
}

Time complexity: O(n), since the function has to iterate through each character in the string. The split function splits the string into an array of individual characters, which takes O(n) time. The reverse function then reverses the order of the characters in the array, which also takes O(n) time. Finally, the join function joins the reversed array back into a string, which takes O(n) time.
Space complexity: O(n), since the function creates an array with n elements.

3. Bubble sort:

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

Time complexity: O(n²), since the function iterates through each pair of elements in the array.
Space complexity: O(1), since the function sorts the array in place.

4. Binary search: It is a commonly used algorithm for searching a sorted array for a specific value.

function binarySearch(arr, val) {
  let start = 0;
  let end = arr.length - 1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] === val) {
      return mid;
    } else if (arr[mid] < val) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return -1;
}

Time complexity:
- Worst-case: O(log n)
- Best-case: O(1)
- Average-case: O(log n)
In the worst-case scenario, binary search requires O(log n) comparisons to find the target element, where n is the number of elements in the sorted array. In the best-case scenario, the target element is found in the first comparison, resulting in a time complexity of O(1). However, in the average case, the algorithm requires O(log n) comparisons to find the target element.
Space complexity: O(1), since the function sorts the array in place.

5. Find the length of the longest substring without repeating characters

function lengthOfLongestSubstring(str) {
  let left = 0;
  let maxLength = 0;
  const charSet = new Set();
  
  for (let right = 0; right < str.length; right++) {
    while (charSet.has(str[right])) {
      charSet.delete(str[left]);
      left++;
    }
    charSet.add(str[right]);
    maxLength = Math.max(maxLength, right - left + 1);
  }
  
  return maxLength;
}

Time complexity: O(n), The algorithm iterates over the input string str once, and the time complexity of iterating over the string once is O(n), where n is the length of the string. The while loop inside the for loop will execute at most n times in total, as each character in the string is processed exactly once. Therefore, the total time complexity of the algorithm is O(n).
Space complexity: O(min(k)), The algorithm uses a set charSet to keep track of the unique characters in the current substring. The set can store at most k unique characters at any given time, where k is the length of the longest substring without repeating characters. Therefore, the space complexity of the algorithm is O(k).

Thank you for taking the time to read my article. I hope you found it informative and thought-provoking. If you have any questions or comments, please feel free to leave them below. Your feedback is always appreciated. 😃