{{ message }}

Instantly share code, notes, and snippets.

# carl-parrish/sentenceReverse.md

Last active Dec 25, 2017
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' ]
``````