DEV Community: yuliakononchuk

8.9 Parens

yuliakononchuk — Tue, 05 Nov 2019 21:47:53 +0000

NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n pairs of parentheses.
EXAMPLE
Input: 3
Output: ((())), (()()), (())(), ()(()), ()()()

To be honest, I've spent some time trying to find a right algorithm here. Initially I assumed there must be a way to get from printParens(n) to printParens(n+1) by adding () in some places (my idea was: from middle until the end for each element of printParens(n)). I couldn't make it work without duplicates 🤷‍♀️, so I started searching for a different algorithm.

I decided to look into the rules that make adding a new paren valid or invalid. For instance, when we look at ()() - how do we figure out that the last paren has to be ) - as we can clearly see that ()() is valid and ()(( is not ?

First of all, the number of right parens and left parens has to match (and be equal to our argument n). Secondly, the number of left parens (() at any index has to always be bigger or equal than the number of right parens - we can't close a paren before opening it. And that is actually it! 🙌 On the next step I tried to build recursion out of this logic.

I've created a helper function getParens, which would take 2 arguments: left and right, which would stand for the number of left and right parens that we can use. Let's say we want to get all pairs of parent for n = 3 - that would mean that we start with left = 3 and right = 3. With every step we would subtract 1 either from first or from second argument - depending on what type of paren - left or right - we're adding.

Note that for recursion we will be going backwards - so, we would need to invert the logical rules described above . So, to get from the string ()( to ()() (but not to ()(() we need to take into account that a left paren (() can be added to existing string ()( only if there was a matching right paren already added to the string at the previous recursion steps. Or, in other words, if the number of right parens that are still in store is smaller than the number of left parens - as we know that we're always starting with an equal number.

On each step of the recursion we can add either ) or ( to each of the combinations that we had on the previous step. Using the rule from above, we can add ( only in case left > right - otherwise we would add an opening paren before we have any closing ones. And we can always add ')' to the existing combination - unless we've run out of parens to use.

If both left and right parens in store are on 0, that means that we've found our valid combination and can start adding brackets to the empty string. Otherwise, if number of left or right brackets goes to below 0, we just want to return an empty array (so that we would map over nothing on the next steps).

And this is how it looks in JS:

function printParens(number) {
  function getParens(left, right){
    if (left < 0 || right < 0) { return []; }
    if (left === 0 && right === 0) { return ['']; }

    const withRight = getParens(left, right-1).map(elem => elem + ')');

    if (left > right) { 
      const withLeft = getParens(left-1, right).map(elem => elem + '(');
      return [...withRight, ...withLeft]
    } 
    return withRight;
  }
  return getParens(number, number)
}

8.7 Permutations Without Dups

yuliakononchuk — Fri, 01 Nov 2019 08:31:38 +0000

NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

Write a method to compute all permutations of a string of unique characters.

I've approached this one by taking a specific example: finding all permutations of 123. Permutations are all the possible combinations of elements, so from 123 we need to get the following ones: 123, 132, 213, 231, 312, 321 - 6 in total. Let's say we knew all permutations of a string of 12, could we then somehow get the permutations of 123? Sure! See the drawing:

We know that permutations of 12 are 12 and 21 - and it looks like we just need to add 3 to every possible position for each of those arrays in order to get out result 🎉(result should be all arrays in the pink circle). The transition from 1 to 12 works in a similar way: to get all permutations of 12 we just need to put 2 in all possible indices in the string of 1 - either before 1 (21) or after (12).

In Javascript this logic can be reflected by the following code:

function getPermutations(str) {
  const lastIndex = str.length - 1;
  const lastChar = str[lastIndex];
  if (lastIndex === 0) { return [str]; }
  const prev = getPermutations(str.slice(0, lastIndex));
  return prev.flatMap(elem => {
    const result = [];
    for (let i = 0; i <= lastIndex; i ++) {
      const newElem = elem.slice(0, i) + lastChar + elem.slice(i);
      result.push(newElem);
    }
    return result;            
  });
}

With getPermutations(str.slice(0, lastIndex)) we're calculating the permutations of a shorter string (string without the last character), and then mapping over the array of these permutations. Each element in the map is then looped over, so that we could create a set of new strings with added last character. This way, for an element 12, we would be able to return [312, 132, 123]. Finally, flatMap allows to return the result as one array - [312, 132, 123, 321, 232, 213] instead of [[312, 132, 123], [321, 232, 213]] - which is convenient for the next iteration of the recursion

8.5 Recursive Multiply

yuliakononchuk — Wed, 23 Oct 2019 16:58:12 +0000

NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

Write a recursive function to multiply two positive integers without using the * operator.You can use addition, subtraction, and bit shifting, but you should minimize the number of those operations.

The easiest approach is to add each number one by one. We can choose the smallest number out of 2 arguments - and add the other number to it, one number at a time:

function multiply(a,b) {
  const max = Math.max(a,b);
  const min = Math.min(a,b);
  function recursiveMultiply(number, multiplier) {
    return (
      multiplier === 1 ? 
      number : 
      number + recursiveMultiply(number, multiplier - 1)
    )
  }
  return recursiveMultiply(max, min);
}

This algorithm uses addition n times, where n is the smallest of 2 arguments of multiplication function. Also the time complexity of this algorithm is O(n): we need to do something n times. Can we do better than that? The task requires to use the minimal amount of additions - and the time complexity can probably be improved as well 🤔

The second approach that I took seems to be a bit more optimal indeed. Similarly as in the previous case, I consider the bigger argument to be multiplicand (let's call it m), and the smaller one - multiplier (n). But in addition to this, I also create an array of pre-calculated values, in which I fill in only the indices that represent the power of 2. For instance, for m = 9 and n = 7 the array will look like this:

Each index in this array actually equals a multiplier of m: eg a number at index 4 would actually be m * 4 (or, in other words, (m + m) + (m + m)). We can do that with log2n operations: each time we will be doubling the array length and the max number.

Note that we're stopping when the index * 2 <= n, and there's a reason for that. The sum of (some of the) numbers in this array will be used to get to the final result (9 * 7, in our example). We're stopping at the index 4, which means the max number we'll calculate for the array would be 9 * 4. If we would go on and calculate the next number as well, the next number would be 9 * 4 + 9 * 4 = 9 * 8 - which would exceed the 9 * 7 that we need to calculate at the end (9 * 8 can not one of the numbers that sum up to 9 * 7).

The next thing to do is to actually (recursively) use these pre-calculated numbers, and that is what recursiveMultiply() function does in the code below:

function multiply(a,b) {
  const max = Math.max(a,b);
  const min = Math.min(a,b);
  let values = [, max]
  let index = 1;

  //Fill in array of values for all indices = 2^n 
  while (index * 2 <= min) {
    const newIndex = index * 2;  
    values[newIndex] = values[index] + values[index];
    index = newIndex;
  } 

  // Recursively add the numbers from the array of values
  function recursiveMultiply(number, multiplier, valuesArray){
    if (multiplier === 0) { return 0; }
    const multLog = Math.log2(multiplier);
    const closestMaxIndex = Math.pow(2, Math.floor(multLog));
    const rest = recursiveMultiply(number, multiplier - closestMaxIndex, valuesArray);
    return valuesArray[closestMaxIndex] + rest;
  }

  return recursiveMultiply(max, min, values);
}

For 9 * 7, we would start with index 7 (the value of n) and search for the closest number that would be a power of 2 (smaller or equal to 7). 7 is not a power of 2, so we need to go down until 4. This chunk does exactly that:

const factorLog = Math.log2(factor);
const closestMaxIndex = Math.pow(2, Math.floor(factorLog));

Finally, we take the number from the pre-calculated array that is stored under closestMaxIndex index (index 4 in this case) - and sum up this number with the rest that still needs to be calculated. So, if we needed to calculate 9 * 7, and 9 * 4 is already known, the rest to be calculated is 9 * 3 : index 3 will be an argument of next iteration of recursiveMultiply. With the next recursive steps we will get 9 * 2 and 9 * 1 - and those numbers will sum up exactly to the result that we need to reach: (9 * 4) + (9 * 2) + (9 * 1) = 9 * 7.

When looking at complexity, this alternative solution uses only 2 * log2n sums - and has a O(log2n) time complexity 🙌 The bigger the argument get, the more benefit will this approach bring.

8.4 Power Set

yuliakononchuk — Sun, 20 Oct 2019 10:41:54 +0000

NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

Write a method to return all subsets of a set.

So, what exactly is meant under all subsets of a set? According to Wikipedia's definition of the power set, given an array [1,2,3], the method should return an array of all the possible combinations of the elements of that array + an empty array: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]. After drawing it on the paper, I observe a certain pattern for adding each next number:

Basically, with every next element n of the given array we need to add to the resulting array a copy of all already stored combinations with n added to each. We can turn this logic into the code:

function allSubsets(arr){
  const maxIndex = arr.length - 1; 
  let result = [ [] ];
  arr.forEach(el => {
   result.forEach(subset => {
     result.push([...subset, el]);
   })
  })
  return result;
}

An alternative recursive solution using the same logic will look like:

function allSubsets(arr) {
  if (arr.length === 0) { return [ [] ]; }
  const prev = allSubsets(arr.slice(1));
  const next = prev.map(el => [...el, arr[0]]);
  return [...prev, ...next];
}

So, to get all subsets of array [n...k] (where n and k are min and max index), we will need to:

1) calculate all subsets of array [n+1...k]
2) create a copy of 1)
3) Add n to each subset of a copy
4) Merge 1) and 3)

8.3 Magic Index

yuliakononchuk — Fri, 18 Oct 2019 12:28:03 +0000

NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

Magic Index: A magic index in an array A[ 0 … n-1] is defined to be an index such that A[ i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.

FOLLOW UP: What if the values are not distinct?

The description of this exercise is suspiciously similar to the binary search: we need to find some value in the sorted array. So, can we tell with 100% confidence looking at a random number in the array whether the magic index is on the left or on the right side of it? Then we would be able to apply the binary search algorithm. It actually looks like yes 🙌

Let's take a random array that satisfies the condition of being distinct & sorted (see an example below), and look at one of the numbers in it- for instance, 1. We know that all numbers before one are smaller than 1, and all numbers after one are bigger than 1 (array is sorted!). In this example, 1 is smaller than its index (it is 4th element => has an index of 3).

Given that the numbers before one are all distinct, the number with the index 2 will be less than 1 (or ≤ 0) - remember that array is sorted. Consequently, number at index 1 will be ≤ -1 - continuing the pattern of each next number being at least (previous number-1) . The indices are also decreasing by one, and thus in the best case scenario both indices and numbers in the array will decrease by one with every step, keeping the relation between 1 and its index: that number is less than the index. Thus, for the numbers before 1 index will never equal the number.

As a result, we should be fine cutting the part before 1 off - and continuing searching for the magic index in the part of the array to the right of 1. The same logic can be applied to the opposite situation: if the number is bigger than its index, the numbers to the right of it will always be bigger then their indices, so we can continue with just the left part. Below you can find the code that summarizes this logic:

function giveMeMagic(sortedArr) {
  const endArray = sortedArr.length - 1;
  function findMagic(arr, minIndex, maxIndex) {
    const middleIndex = Math.ceil((minIndex + maxIndex) / 2);
    const middleValue = arr[middleIndex];

    if (middleValue === middleIndex) { return middleIndex; }
    if (minIndex > maxIndex) { return -1; }
    if (middleValue > middleIndex) {
      return findMagic(arr, 0, middleIndex - 1)
    }
    if (middleValue < middleIndex) {
      return findMagic(arr, middleIndex + 1, maxIndex)
    }
  }
  return findMagic(sortedArr, 0, endArray)
}

Using the binary search approach, we'll always cut the array into 2 halves and check the middle number: if this number equals its index, we've found our magic number! If the number is bigger than its index, we'll continue with the left part - else we'll continue with the right part.

One more thing to mention is the stop condition: in the chunk of code above we're stopping when minIndex becomes bigger than maxIndex, why is that? From the code you can see that we're recalculating maxIndex every time we go for the left part, and minIndex when we go for the right one. If the magic index is not found, we'll always reach the step when maxIndex equals minIndex. The next step after that will either decrease maxIndex (if going to the left) or increase minIndex (if going to the right) - satisfying the minIndex > maxIndex condition. The sketch below should make it a bit more explicit (circled are the middle values on each step):

For the follow-up question, however, the right/left logic does not apply anymore. In the array below the numbers are still sorted, but 1 is duplicated. If we split an array at a circled 1 (the middle index), we can find now the Magic Index both lo the left (underscored 1) and to the right side of it (4) - although the middle value is smaller than the middle index.

So, the first thing that comes to mind is just using the brute force approach and check every number one by one. But can we maybe optimize it somehow?

We know that the middle number (1) is lower that its index (3). Can the number next to it to the right be equal to the next index (4)? Yes, there are no reasons for this not to work, and actually this is exactly the case that we can see in the example above.

However, can the same happen to the number to the left of middle 1? We know that the numbers are sorted, and the next index to the left is 2. Can the number at index 2 equal 2? No, because it has to be smaller or equal to 1 (numbers are sorted!). That means that the first possible index to the left that can have the magic number in it is the index 1. Following this logic, we can skip all indices that are bigger than the middle number (if the middle number is smaller than its index) and skip all indices that are smaller than the middle number (if the middle number is bigger than its index). I've implemented this in JS in the following way:

function giveMeMagic(sortedArr) {
  const endArray = sortedArr.length - 1;
  function findMagic(arr, minIndex, maxIndex) {
    const middleIndex = Math.ceil((minIndex + maxIndex) / 2);
    const middleValue = arr[middleIndex];

    if (middleValue === middleIndex) { return middleIndex; }
    if (minIndex > maxIndex) { return -1; }

    const maxIndexLeft = middleValue < middleIndex ? middleValue : middleIndex - 1;
    const left = findMagic(arr, 0, maxIndexLeft);

    if (left >= 0) { return left; }

    const minIndexRight = middleValue > middleIndex ? middleValue : middleIndex + 1;
    const right = findMagic(arr, minIndexRight, maxIndex);

    return right;

  }
  return findMagic(sortedArr, 0, endArray)
}

One important thing to notice here: on every step of recursion we're calculating and returning left side before doing any recursion for the right side. And only if left returns -1, we proceed with calculating right. This way if the Magic index is found on the left side, we can spare the right side calculations.

8.1 Triple Step

yuliakononchuk — Fri, 18 Oct 2019 12:14:46 +0000

NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

Hmm, this sounds a lot like a recursive algorithm 🤔To me the easiest way to think about it is to start backwards. Imagine that we have 5 steps and need to calculate all combinations of hops that can cover these 5 steps. We know that the child can hop either one step, 2 steps, or 3 steps at once - which means that she got to step 5 from either from step 4, or step 3, or step 2. In other words, if n equals 5, then the number of different ways to get to n is a number of ways to get to (n-1) + ways to get to (n-2) + ways to get to (n-3). Let's call the function that would calculate the number of all possible ways to get to step x getStaircaseCombinations(x).

But how did the child get to step 4 (the n-1 from above)? She must have been either on step 3, step 2, or step 1 before, and you can observe the same pattern all over again. In other words, for each step k we would need to return getStaircaseCombinations(k-1) + getStaircaseCombinations(k-2) + getStaircaseCombinations(k-3).

At which point do we stop? We know that the combination is correct if the sum of steps a child has made equals exactly to 5. We're going backwards, subtracting from 5 - which means that the correct combination should bring us to 0. So, when we're reaching 0 the combination must be valid and we should return 1. The alternative scenario is that we're ending up with a number less than 0: for instance, a child may have jumped to step 5 from step 2 (n-3) and to step 2 from step -1 (yet again, n-3). However, step -1 does not exist, a child would always start with step 0 - which means our combination does not work. So, for the cases resulting in a negative number we would return 0 and not count such combinations in.

This logic results in:

function getStaircaseCombinations(stairs) {
  if (stairs < 0) { return 0; }
  if (stairs === 0) { return 1; }
  return (
    getStaircaseCombinations(stairs - 1) +
    getStaircaseCombinations(stairs - 2) + 
    getStaircaseCombinations(stairs - 3)
  )
};

Finally, you can notice that in the code above we're calculating the same path several times. For instance, for n=5 you would need to calculate the number of step combinations for 'how to reach step 3' twice: for the case of (n-2) and the case of ((n-1)–1) - and the bigger n gets, the more double-work this code will be doing.

In order to avoid this, we can use memoization technique. The logic is as follows:

✔️start with the empty array of results
✔️if array of results doesn't contain yet the number of combinations for x (and only then!), calculate it and store it in the array as results[x]
✔️return the number of combinations for x stored in the array

The slightly adjusted code that allows for memoization will look like:

function getStaircaseCombinations(stairs) {
  let combinations = [];
  function calculateCombinations(n) {
    if (n < 0) { return 0; }
    if (n === 0) { return 1; }
    if (combinations[n] === undefined) {
      combinations[n] = 
        calculateCombinations(n - 1) + 
        calculateCombinations(n - 2) + 
        calculateCombinations(n - 3);
    }
    return combinations[n];
  };
  calculateCombinations(stairs);
  return combinations[stairs];
}