Solving Array question from blind 75 list.

Solving Array question from blind 75 list.

3 years ago, this question was asked to me, in 1st round of interview at Microsoft to me and i was not able to solve. In this post we will see how we can solve it.

Two sum:

Give an array of integers like [2, 7, 11, 17] and a target 9, return the indices of two numbers in the array that add up to the target.

The most important part, why should i learn this question any way?

1. Ecommerce:
2. Product Bundling; Find pairs of products that together meet a certain price point for promotions or bundle deals
3. Logistics:
4. Finding pairs of items that can be packed together to optimize space usage.

FANG:

1. Amazon:
2. Finding pairs that customer frequently buy together
3. Pairing items for efficient picking and packaging.
4. Apple:
5. Icloud: Identifying pair of files that could be combined or compressed to save space
6. Netflix:
7. Suggesting pairs of movies that together satisfy different aspects of user's preferences.
8. Pairing high and low bandwidth content to balance network load.
9. Google:
10. Finding pairs of web pages that together best answer a complex query
11. Adwords: Matching pairs of keyword that together meet and advertise's budget and targeting criteria.

Little more about Two Sum problem.

• It shows an act in balancing time and space complexity for different scenarios.
• Shows understanding of data structures and their performance implications.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.You can return the answer in any order.

1. Optimising time using more space:

1. we will use obj to trade storage to optimize time
2.   iterate over the numbers array
3.   if the current num is already in the obj 
4. we return the current index and savedIndex
5. else we update our obj

function twoSumUsingMoreSpace(nums, target){

  let mapobj = {}

  for(let i = 0; i < nums.length; i++){

    let currentNumber = nums[i]

    if(mapobj[currentNumber] >=0 ){

      return [i, mapobj[currentNumber]]

    }else{

      let desiredNumber = target - currentNumber

      mapobj[desiredNumber] = i

    }

  }

}

notes:

in the iteration,

• we define currentNumber
• we check currentNumber is already exist
• if yes then we use it to return index
• else we define numberLooking for
• we set desiredNumber to it's index

2. Optimising space using more time:

we will use pointers

1.  leftPointer and rightPointer to compare two numbers to target, 
2. leftPointer will start from 0
3. rightPointer from 1
4. both moves from left to right comparing different numbers in the integer array
5. when moving if value @ leftPointer + value @ rightPointer equal to target
6. we will return the [lefPointer, rightPointer]
7. . if not we will keep on moving.
8. rightPointer keeps on moving right every iteration
9. if rightPointer reaches maxPointer meaning at the end of the array
10. leftPointer moves 1 right
11. rightPointer reset to leftPointer + 1

function twoSumSpaceOptimize(nums, target){

        let 

        leftPointer = 0,

        rightPointer = leftPointer + 1,

        maxPointer = nums.length;

        while(leftPointer < maxPointer){

          let 

          leftvalue = nums[leftPointer],

          rightvalue = nums[rightPointer]

          if(leftvalue + rightvalue === target){

            return [leftPointer, rightPointer]

          }

          if(rightPointer === maxPointer){

            leftPointer ++

            rightPointer = leftPointer + 1

          }

          rightPointer++

        }

}

So this is why and how two sum leet code problem is solved.

#leetcode #computerscience #faang #problemsolving