Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Interview Questions.

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' ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.