Algorithms are part of our everyday lives as software engineers, whether you work ( to want work)  at Facebook,  Google,  Amazon, Netflix, or a small startup in your city. Getting a job in software development is becoming more and more difficult due raising of solving algorithmic questions during job interviews. In this blog, we are going to solve some basic algorithm questions.

 

1. Two Number Sum 

Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array, in any order. If no two numbers sum up to the target sum, the function should return an empty array.  Note that the target sum has to be obtained by summing two different integers in the array; you can't add a single integer to itself in order to obtain the target sum.

 

array  = [3, 5, -4, 8, 11, 1, -1, 20]
targetSum  = 9

 

function twoNumberSum(array, targetSum) {
  const diff = {}

  for (const i of array){
    
      const change =   targetSum -i
      if(diff?.[change.toString()]){
        
      return [i, change]
    }else{
      diff[i] =  true
    }
    
  }

  return []
}

 

In our solution above, we are using a hash map (a javascript object) to store the items in the array while we loop over it.  But on each loop iteration, we calculated the difference between the targetSum and the current item and check if the difference exists in the diff object as a key, if it does we return the current item and difference and terminate the loop. If no two sum for the target sum is not found we return an empty array. Our solution will have time complexity of O(n) and space complexity O(n).

 

2. Sorted Squared Array

Write a function that takes in a non-empty array of integers that are sorted  in ascending order and returns a new array of the same length with the squares of the original integers also sorted in ascending order.

 

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

output = [1, 4, 9, 16, 25, 36]

 

function sortedSquaredArray(array) {

  const cArray =  array.sort((a, b) => a - b)
  const newArray = new Array(array.length)
  let start = 0;
  let end  = array.length -1;
  let lastIdx =  array.length -1;

  while (start <= end) {
    if(Math.abs(cArray[start]) >  Math.abs(cArray[end])){
        newArray[lastIdx]  = cArray[start] * cArray[start];
        start ++;
    }else{
          newArray[lastIdx] = cArray[end] * cArray[end];
        end--
    }
      lastIdx--;
  }
  
  return newArray;
}

 

In our solution above we first sort the array (assuming we are using a quick sort or merge sort algorithm which gives a time complexity of O(nlogn)). After that, we loop through the array and square it accordingly. There can be the possibility of a high negative value and a square of it will result in a high value so we use a two pointer loop to sort the squares. This will give a time complexity of O(n) and a space complexity of O(n).

 

3. Validate a subsequence
 Given two non-empty arrays of integers, write a function that determines  whether the second array is a subsequence of the first one. A subsequence of an array is a set of numbers that aren't necessarily adjacent in the array but that are in the same order as they appear in the array. For instance, the numbers [1,2,3]  from subsequence of the array [1,2,3,4], and so do the number [2,4].

 

array = [2,3,4,53,5,7,2,6,7]
sequence = [4,7,7]

 

function isValidSubsequence(array, sequence) {
 
  let idx = -1;
  
  for(const i of array){
    if(i == sequence[idx+1]){ 
      idx++;
    }
    if(idx == sequence.length-1){
      return true
    }
  }

    return false
}

 

In our solution above, we use idx to keep track of the subsequence we come across whiles we loop over the array. Our time complexity will be O(n) and the space complexity will be O(1).

In this tutorial, we have learnt about some basic algorithm algorithms that we can meet in an interview. If you want to see more of these blogs, please consider subscribing to my profile for more updates. Cheers 🫡.