Interview Questions.

sentenceReverse.md

Sentence Reverse

You are given an array of characters arr that consists of sequences of characters separated by space characters. Each space-delimited sequence of characters defines a word.

Implement a function reverseWords that reverses the order of the words in the array in the most efficient manner.

Explain your solution and analyze its time and space complexities.

Example:

input:  arr = [ 'p', 'e', 'r', 'f', 'e', 'c', 't', '  ',
                'm', 'a', 'k', 'e', 's', '  ',
                'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' ]

output: [ 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e', '  ',
          'm', 'a', 'k', 'e', 's', '  ',
          'p', 'e', 'r', 'f', 'e', 'c', 't' ]

Constraints:

• [time limit] 5000ms

• [input] array.character arr

  • 0 ≤ arr.length ≤ 100

• [output] array.character

First Solution

function reverseWords(arr) {
  const str = arr.join('').replace(',',''); //Convert arry to string to split
  const input = str.split(' '); // Split into words
  const ans =  input.reduceRight((a,b)=> a.concat((b+" ").split('')), []); //reverse words, add space back
  return ans.slice(0,-1); //trim last space.
}

Second Solution (does this help or hurt readability?)

function reverseWords(arr) {
  const wordsArray = arr.join('').replace(',','').split(' '); //Split array into words
  return wordsArray.reduceRight((a,b)=> [...a, ...b, " "],[]).slice(0,-1); // Reverse words, break into chars & trim last space
}

Second Solution with different spacing

function reverseWords(arr) {
 // Combine characters then split on spaces into words
  const wordsArray = arr.join('')
                    .replace(',','')
                    .split(' ');
                    
  // Reverse words, break into chars & trim last space
  return wordsArray.reduceRight((a,b)=> {
                                  return [...a, ...b, " "];
                                  },[]).slice(0,-1); 
}

Third Solution

function reverseWords(arr, ans=[], start=0) {
  //If this is the first time called reverse the entire array
  if (start === 0) arr.reverse(); 
  
  //Find the next space that delimits a word
  let end = (arr.includes(' ', start)) ? arr.indexOf(' ', start): arr.length;
  
  //Reverse the word and add it to the ans array
  ans = [...ans, ...arr.slice(start, end).reverse(), " "];
  
  //If we haven't reached the end of the array repeat with new starting point
  return (end++ < arr.length)? reverseWords(arr, ans, end++): ans.slice(0,-1);
}

Results

	Time:	Tests Passed:	Failed:	O()
Solution 1	547 ms	6	0	O(n)
Solution 2	458 ms	6	0	O(n)
Solution 3	441 ms	6	0	O(n)

Test Case #1 ✅

Input: [" "," "]

Expected: [" "," "]

Actual: [ ' ', ' ' ]

Test Case #2 ✅

Input: ["a"," "," ","b"]

Expected: ["b"," "," ","a"]

Actual: [ 'b', ' ', ' ', 'a' ]

Test Case #3 ✅

Input: ["h","e","l","l","o"]

Expected: ["h","e","l","l","o"]

Actual: [ 'h', 'e', 'l', 'l', 'o' ]

Test Case #4 ✅

Input: ["p","e","r","f","e","c","t"," ","m","a","k","e","s"," ","p","r","a","c","t","i","c","e"]

Expected: ["p","r","a","c","t","i","c","e"," ","m","a","k","e","s"," ","p","e","r","f","e","c","t"]

Actual:[ 'p',
'r',
  'a',
  'c',
  't',
  'i',
  'c',
  'e',
  ' ',
  'm',
  'a',
  'k',
  'e',
  's',
  ' ',
  'p',
  'e',
  'r',
  'f',
  'e',
  'c',
  't' ]

Test Case #5 ✅

Input: ["y","o","u"," ","w","i","t","h"," ","b","e"," ","f","o","r","c","e"," ","t","h","e"," ","m","a","y"]

Expected: ["m","a","y"," ","t","h","e"," ","f","o","r","c","e"," ","b","e"," ","w","i","t","h"," ","y","o","u"]

Actual:[ 'm',
'a',
  'y',
  ' ',
  't',
  'h',
  'e',
  ' ',
  'f',
  'o',
  'r',
  'c',
  'e',
  ' ',
  'b',
  'e',
  ' ',
  'w',
  'i',
  't',
  'h',
  ' ',
  'y',
  'o',
  'u' ]

Test Case #6 ✅

Input: ["g","r","e","a","t","e","s","t"," ","n","a","m","e"," ","f","i","r","s","t"," ","e","v","e","r"," ","n","a","m","e"," ","l","a","s","t"]

Expected: ["l","a","s","t"," ","n","a","m","e"," ","e","v","e","r"," ","f","i","r","s","t"," ","n","a","m","e"," ","g","r","e","a","t","e","s","t"]

Actual: [ 'l',
'a',
  's',
  't',
  ' ',
  'n',
  'a',
  'm',
  'e',
  ' ',
  'e',
  'v',
  'e',
  'r',
  ' ',
  'f',
  'i',
  'r',
  's',
  't',
  ' ',
  'n',
  'a',
  'm',
  'e',
  ' ',
  'g',
  'r',
  'e',
  'a',
  't',
  'e',
  's',
  't' ]