05_0_produce_x_output.md

Produce "X" output

Produce "X" message given a string of characters

We have 2 strings:

1. An input string with the characters to use
2. Anoutput string or the string we want to form (or produce) with the previous input

Some constraints:

• We care about symbols including white space ' '
• We care about lower/uppercase (T is not equals to t)
• We care about the chars repetition; so, to produce hello we need to have 2 l on our input string

function generateMessage(input, message) {
  const hs = {}
  
  for (let character of input) {
    if (hs[character] > 0) {
       hs[character] += 1
    }
    else hs[character] = 1
  }
  
  for (let character of message) {
    if (!hs[character]) return false
    else hs[character]--
  }

  return true
}


generateMessage('helo world', 'hello world')
// false

Produce "X" output through basic mathematical operations

We have an array and we want to find 2 numbers which through addition, subtraction, multiplication or division produces x result (aka, number).

Examples:

• [4,1,3,6] and we want to add to 7

  • First combination of 2 numbers respecting order 4,3:
    • Retrieving the numbers: 4,3
    • Retrieving the indexes of those numbers in the array: 0,2
  • All combinations of 2 numbers: 4,3 and 1,6

Sometimes, the request can include sorting. Remember to check our Sorting Section. This could be particularly useful, if the interviewer allows it, to speed your program:

Also, you could receive a string of numbers and have to produce -first- an array. Important: this will work just with single digits.

'347932'.split('')

Output:

["3", "4", "7", "9", "3", "2"]

Find the pair of numbers which add up to a particular result

Solution 1: nested for loops

Constraint: preserve order and traverse from left to right.

• Time complexity: O(n^2) or quadratic
• Space complexity: O(1) or constant

function addUp(arr, target) {

  const result = []
  
	for (let i = 0; i < arr.length; i++) {
		for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === target) result.push([arr[i], arr[j]])
		}
	}
	
	return result
}

addUp([], 5)
addUp([1], 5)
addUp([1,2,6,8], 5)
addUp([1,2,4,3], 5)

Output:

[]
[]
[]
[ [ 1, 4 ], [ 2, 3 ] ]

Solution 2: Sorting and using pointers

• Time complexity: O(nlogn) or logarithmic
• Space complexity: O(1) or constant

function addUp(arr, target) {

  const result = []

  const newArr = [...arr].sort((a, b) => a - b)

  let leftPointer = 0
  let rightPointer = newArr.length - 1

  // while pointers are not overlapping
  while (leftPointer < rightPointer) {
    const sum = newArr[leftPointer] + newArr[rightPointer] 
    
    if (sum === target) {
      result.push([newArr[leftPointer], newArr[rightPointer]])
      leftPointer++
    } else if (sum < target) {
      leftPointer++
    } else if (sum > target) {
      rightPointer--
    }
  }

	return result
}

addUp([], 5)
addUp([1], 5)
addUp([1,2,6,8], 5)
addUp([1,2,4,3], 5)

// Extra tests
addUp([1,2,4,3,1,5], 5)
addUp([1,2,4,3,6,1,8,10,9], 10)

Output:

[]
[]
[]
[ [ 1, 4 ], [ 2, 3 ] ]
[ [ 1, 4 ], [ 1, 4 ], [ 2, 3 ] ]
[ [ 1, 9 ], [ 1, 9 ], [ 2, 8 ], [ 4, 6 ] ]

Solution 3: hash table

• Time complexity: O(n) or linear
• Space complexity: O(n) or linear

This solution is the preferred one and it avoids (also) duplicates in the results: [ [ 6, 4 ], [ 8, 2 ], [ 9, 1 ] ]

function addUp(arr, target) {

  const result = []

  const ht = {}
  
  for (let element of arr) {
    if (ht[target - element]) {
      result.push([element, (target - element)])
    } else ht[element] = true
  }

	return result
}

addUp([], 5)
addUp([1], 5)
addUp([1,2,6,8], 5)
addUp([1,2,4,3], 5)

// Extra tests
addUp([1,2,4,3,1,5], 5)
addUp([1,2,4,3,6,1,8,10,9], 10)

Output:

[]
[]
[]
[ [ 4, 1 ], [ 3, 2 ] ]
[ [ 4, 1 ], [ 3, 2 ] ]
[ [ 6, 4 ], [ 8, 2 ], [ 9, 1 ] ]