Coded transmissions Coding Interview Question

Coding Interview Question to write a function that decodes Coded Transmissions.

You have given coded transmissions inform of array of characters and you have been asked to write a function reverseWords() that takes a message as an array of characters and reverses the order of the words in place. 

For example:

/**Input: */const message = [ 'c', 'a', 'k', 'e', ' ',
                'p', 'o', 'u', 'n', 'd', ' ',
                's', 't', 'e', 'a', 'l' ];
/**Function */reverseWords(message);

console.log(message.join(''));
/** Output */
// Prints: 'steal pound cake'

Assumption:

When writing your function, assume the message contains only letters and spaces, and all words are separated by one space.

Front-End Engineer Interview Questions.

Breakdown

Let’s start with a simpler problem. What if we wanted to reverse all the characters in the message?

Well, we could swap the first character with the last character, then the second character with the second to last character, and so on, moving towards the middle. Can you implement this in code?

function reverseCharacters(message) {

  let leftIndex = 0;
  let rightIndex = message.length - 1;

  // Walk towards the middle, from both sides
  while (leftIndex < rightIndex) {

    // Swap the left char and right char
    const temp = message[leftIndex];
    message[leftIndex] = message[rightIndex];
    message[rightIndex] = temp;
    leftIndex++;
    rightIndex--;
  }
}

Now we need to figure out few things.

How do we figure out where words begin and end?

Once we know the start and end indices of two words, how do we swap those two words?

What happens when you swap two words that aren’t the same length?

We will now try to solve these questions.

First what happens when we do a character-level reversal.

// input: the eagle has landed
[ 't', 'h', 'e', ' ', 'e', 'a', 'g', 'l', 'e', ' ',
'h', 'a', 's', ' ', 'l', 'a', 'n', 'd', 'e', 'd' ];

// character-reversed: dednal sah elgae eht
[ 'd', 'e', 'd', 'n', 'a', 'l', ' ', 's', 'a', 'h', ' ',
'e', 'l', 'g', 'a', 'e', ' ', 'e', 'h', 't' ];

Now, What if we put it up against the desired output:

// input: the eagle has landed
[ 't', 'h', 'e', ' ', 'e', 'a', 'g', 'l', 'e', ' ',
'h', 'a', 's', ' ', 'l', 'a', 'n', 'd', 'e', 'd' ];

// character-reversed: dednal sah elgae eht
[ 'd', 'e', 'd', 'n', 'a', 'l', ' ', 's', 'a', 'h', ' ',
'e', 'l', 'g', 'a', 'e', ' ', 'e', 'h', 't' ];

// word-reversed (desired output): landed has eagle the
[ 'l', 'a', 'n', 'd', 'e', 'd', ' ', 'h', 'a', 's', ' ',
'e', 'a', 'g', 'l', 'e', ' ', 't', 'h', 'e' ];

The character reversal reverses the words! It’s a great first step. From there, we just have to “unscramble” each word.

Checkout Our video Tutorial on Balanced Parentheses.

More precisely, we just have to re-reverse each word!

Solution

We’ll write a helper function reverseCharacters() that reverses all the characters between a leftIndex and rightIndex.

We use it to: Reverse all the characters in the entire message, giving us the correct word order but with each word backward.

Reverse the characters in each individual word.

function reverseWords(message) {

  // First we reverse all the characters in the entire message
  reverseCharacters(message, 0, message.length - 1);
  // This gives us the right word order
  // but with each word backward

  // Now we'll make the words forward again
  // by reversing each word's characters

  // We hold the index of the *start* of the current word
  // as we look for the *end* of the current word
  let currentWordStartIndex = 0;
  for (let i = 0; i <= message.length; i++) {

    // Found the end of the current word!
    if (i === message.length || message[i] === ' ') {

      // If we haven't exhausted the string our
      // next word's start is one character ahead
      reverseCharacters(message, currentWordStartIndex, i - 1);
      currentWordStartIndex = i + 1;
    }
  }
}


function reverseCharacters(message, leftIndex, rightIndex) {

  // Walk towards the middle, from both sides
  while (leftIndex < rightIndex) {

    // Swap the left char and right char
    const temp = message[leftIndex];
    message[leftIndex] = message[rightIndex];
    message[rightIndex] = temp;
    leftIndex++;
    rightIndex--;
  }
}

Complexity

O(n)O(n) time and O(1)O(1) space!