Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
This is how you get N/2 performance where N is a number of words.
String reverseWords(String str) {
String[] tokens = str.split(" ");
for (int first = 0, last = tokens.length - 1; first < last; first++, last--) {
String swapStr = tokens[first];
tokens[first] = tokens[last];
tokens[last] = swapStr;
}
return String.join(" ", tokens);
}
public class ReverseWords {
public static void main(String[] args) {
System.out.println(reverseWords("Man bites dog"));
}
public static String reverseWords(String value) {
if (value == null || value.equals("")) {
return null;
}
String[] words = value.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
sb.append(words[i] + " ");
}
return sb.deleteCharAt(sb.length()-1).toString();
}
}
void reverseStringNotWords(char *string)
{
int length = strlen(string);
int start = 0;
int end = 0;
int mid = 0;
for (int i=0; i<=length; i++) {
if (string[i] == ' ' || string[i] == '\0') {
end = i-1;
mid = (end - start) / 2;
for (int j=0; j<=mid; j++) {
string[start+j]=string[start+j]^string[end-j]^(string[end-j]=string[start+j]);
}
start = i+1;
if (string[i] == '\0')
break;
}
}
mid = length/2;
length--;
for (int j=0; j<mid; j++) {
string[j]=string[j]^string[length-j]^(string[length-j]=string[j]);
}
}
import java.io.*;
class Reverse
{
public static void main(String args[])
{
try
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
String arr[] = str.split(" ");
int len = arr.length;
StringBuffer result = new StringBuffer();
for(int i = len-1 ; i >= 0 ; i--)
{
result = result.append(arr[i]+" ");
}
String res = ""+result;
System.out.println(res);
}
catch(IOException e)
{
System.out.println(e);
}
}
}
// Using string.Split method this requires O(N) space where N = number of words;
public string ReverseWords(string s)
{
if (string.IsNullOrEmpty(s))
return string.Empty;
var arr = s.Split(' ');
var sb = new StringBuilder();
for (int i = arr.Length - 1; i > 0; i--)
sb.Append(arr[i]).Append(" ");
sb.Append(arr[0]);
return sb.ToString();
}
// Implementing my own code to split the words
public string ReverseWords(string s)
{
if (string.IsNullOrEmpty(s))
return string.Empty;
var sb = new StringBuilder();
int i = s.Length - 1;
int end = i;
string word;
while (i > 0)
{
if (s[i] == ' ')
{
word = s.Substring(i + 1, end - i);
sb.Append(word);
sb.Append(" ");
end = i - 1;
}
i--;
}
word = s.Substring(0, end + 1);
sb.Append(word);
return sb.ToString();
}
The best possible recursive solution which i feel is possible .. I tested the same for 1000000 size string
public static String reverseWords(String value){
if(value == null || value.length() == 0)
return "";
int index = value.indexOf(" ");
if(index <= 0)
return value;
return reverseWords(value.substring(index +1))+" "+value.substring(0,index);
}
import java.util.* ;
import java.lang.String;
public class ReverseWords{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
ReverseWords obj = new ReverseWords();
String result = obj.reverseWords(input);
System.out.println(result);
}
String reverseWords(String value){
int strLen = value.length()-1; // 0 index
char[] myChar = value.toCharArray();
int i =0;
int j = strLen;
//First reverse the complete string
while(i<=j){
char temp = myChar[i];
myChar[i] = myChar[j];
myChar[j] = temp;
i++;
j--;
}
int base_index =0;
for(i=0;i<=strLen;i++){
if(myChar[i]==' '){
int a = base_index;
int b = i-1;
while(a<=b){
char temp = myChar[a];
myChar[a] = myChar[b];
myChar[b] = temp;
a++;
b--;
}
base_index = i+1;
}
if(i==strLen){ // reached last character of the string
int a = base_index;
int b = i;
while(a<=b){
char temp = myChar[a];
myChar[a] = myChar[b];
myChar[b] = temp;
a++;
b--;
}
}
}//end of for loop
String result = String.valueOf(myChar);
return result;
}
}
import java.util.* ;
import java.lang.String;
public class ReverseWords{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
ReverseWords obj = new ReverseWords();
String result = obj.reverseWords(input);
System.out.println(result);
}
String reverseWords(String value){
int strLen = value.length()-1; // 0 index
char[] myChar = value.toCharArray();
int i =0;
int j = strLen;
//First reverse the complete string
while(i<=j){
char temp = myChar[i];
myChar[i] = myChar[j];
myChar[j] = temp;
i++;
j--;
}
int base_index =0;
for(i=0;i<=strLen;i++){
if(myChar[i]==' '){
int a = base_index;
int b = i-1;
while(a<=b){
char temp = myChar[a];
myChar[a] = myChar[b];
myChar[b] = temp;
a++;
b--;
}
base_index = i+1;
}
if(i==strLen){ // reached last character of the string
int a = base_index;
int b = i;
while(a<=b){
char temp = myChar[a];
myChar[a] = myChar[b];
myChar[b] = temp;
a++;
b--;
}
}
}//end of for loop
String result = String.valueOf(myChar);
return result;
}
}
{
function reverseWords( str ) {
var revString = ""
var lastIdx = str.lastIndexOf(" ")
var firstIdx = str.indexOf(" ")
var end = str.length
var word = ""
while ( lastIdx >= firstIdx ) {
word = str.slice( lastIdx+1, end)
str = str.slice(0, lastIdx)
revString = revString+word+" "
lastIdx = str.lastIndexOf(" ")
}
revString = revString + str
return revString
}
}
Javascript
{
function reverseWords( str ) {
var revString = ""
var lastIdx = str.lastIndexOf(" ")
var firstIdx = str.indexOf(" ")
var end = str.length
var word = ""
while ( lastIdx >= firstIdx ) {
word = str.slice( lastIdx+1, end)
str = str.slice(0, lastIdx)
revString = revString+word+" "
lastIdx = str.lastIndexOf(" ")
}
revString = revString + str
return revString
}
}
Space complexity O(1) and Time complexity O(n)
class StringReverse {
public static void main(String[] argc) {
StringReverse sr = new StringReverse();
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String reverseStr = sr.reverseWords(str);
System.out.println(reverseStr);
}
public void reverse(StringBuilder str, int i, int j) {
while (i < j) {
char temp = str.charAt(j);
str.setCharAt(j, str.charAt(i));
str.setCharAt(i, temp);
i++;
j--;
}
}
public String reverseWords(String str) {
if (str == null || str.length() == 0) {
return null;
}
final char SPACE = ' ';
int start = 0;
int curr = 0;
StringBuilder sb = new StringBuilder(str);
reverse(sb, 0, sb.length() - 1);
while (curr < sb.length()) {
if (sb.charAt(curr) == SPACE) {
reverse(sb, start, curr-1);
start = curr + 1;
}
curr = curr + 1;
}
reverse(sb, start, curr-1);
return sb.toString();
}
}
static private string ReverseWords(string originalString)
{
Stack<string> myStack = new Stack<string>();
foreach (string subString in originalString.Split(' '))
{
myStack.Push(subString);
}
string reversedString = "";
while (myStack.Count > 0)
{
reversedString += myStack.Pop();
if (myStack.Count > 0)
{
reversedString += " ";
}
}
return reversedString;
}
static private string ReverseWords(string originalString)
{
Stack<string> myStack = new Stack<string>();
foreach (string subString in originalString.Split(' '))
{
myStack.Push(subString);
}
string reversedString = "";
while (myStack.Count > 0)
{
reversedString += myStack.Pop();
if (myStack.Count > 0)
{
reversedString += " ";
}
}
return reversedString;
}
static private string ReverseWords(string originalString)
{
Stack<string> myStack = new Stack<string>();
foreach (string subString in originalString.Split(' '))
{
myStack.Push(subString);
}
string reversedString = "";
while (myStack.Count > 0)
{
reversedString += myStack.Pop();
if (myStack.Count > 0)
{
reversedString += " ";
}
}
return reversedString;
}
import java.util.Stack;
public class ReverseSentence {
public static void main(String[] args) {
String ans = reverseSentence("Man bites dog");
System.out.println(ans);
}
public static String reverseSentence(String s) {
Stack<String> st = new Stack<String>();
String[] words = s.split(" ");
for(String w : words) {
st.push(w);
}
StringBuilder sb = new StringBuilder();
while(!st.empty()) {
sb.append(st.pop());
sb.append(" ");
}
sb.deleteCharAt(sb.length() -1);
return sb.toString();
}
}
For those of you using split, reverse, etc - doesn't performance count for anything these days?
C++ (could easily be C or any language), assuming the answer needs to reside in a copied buffer, and not re-write the original (to re-write, reverse string, for each word, reverse word):
#include <iostream>
#include <string>
using namespace std;
string reverseWords(const char* str){
int len = strlen(str);
// Allocate memory (from stack, for now):
char* buffer = (char*)alloca((len+1)*sizeof(char));
buffer[len-1] = '\0'; // null terminate the string
int end = 0, start = len - 1; // end is the end of the copied buffer, start is the beginning of the word we copy
// Iterate string from end to start
for (int i=len-1;i>=0;--i){
if (str[i] == ' '){ // space?
// copy the word to the new buffer
memcpy(buffer + end,str+i+1,start - i);
// set new start, end
end+=start-i;
start = i - 1;
// add a space and move end of buffer one more notch
buffer[end++] = ' ';
}
}
// copy the last word (first word in the original text)
memcpy(buffer + end, str,start+1);
return buffer;
}
int main(int argc,char* argv[]){
cout << reverseWords("Man bytes dog") << endl;
return 0;
}
Another C version
#include <stdio.h>
char STRING[] = {"dog and cat bites man and woman"};
void
reverse(char *str)
{
char *tStr;
int count = 0;
if (*str == '\0') // end of string; Recursion base case
return;
tStr = str; // make copy of pointer to traverse string
while((*tStr != ' ') && (*tStr != '\0')) {
// traverse till next word or end of the string
tStr++;
count++;
}
tStr++; // Skip pass ' ' [white space]
reverse(tStr); // recursion, repeat same process for rest of the string.
printf("%.*s ", count, str);
#if 0
// Another way to print string
int i = 0;
while (count) {
printf("%c", str[i++]);
count--;
}
printf("%c", ' ');
#endif
}
int
main() {
printf("%s\n", STRING);
reverse(STRING);
printf("\n");
return 0;
}
output
dog and cat bites man and woman
woman and man bites cat and dog
This is an Objective-C solution in O(log n) time and O(i) space
-(NSString *)reverseWords:(NSString *)value{
NSString *result;
NSMutableArray *tempArray = [NSMutableArray arrayWithArray:[value componentsSeparatedByString:@" "]];
for(int i = 0; i < [tempArray count] / 2; i++){
[tempArray exchangeObjectAtIndex:((int)[tempArray count] - i - 1) withObjectAtIndex:i];
}
result = [[tempArray valueForKey:@"description"] componentsJoinedByString:@" "];
return result;
}
void reverse(string &s, int i, int j)
{
int left = i;
int right = j;
while(left< right)
{
int temp;
temp = s[left];
s[left]= s[right];
s[right] = temp;
left++;
right--;
}
}
int main (int argc, char *ARgv[])
{
string input = "Tiger eats boy and space leftover#@# ";
reverse(input, 0,(int)input.size()-1); //master reverse
int lindex = 0;
int rindex = 0;
while(rindex < (int)input.size())
{
while(input[rindex]!= ' ' && rindex < input.size())
rindex++;
reversestring(input, lindex, rindex-1);
rindex++;
while(input[rindex] == ' ' && rindex < input.size())
rindex++;
lindex = rindex;
}
cout << input << endl;
return 0;
}
- tomkowz October 05, 2016func wordsReversed(string: String) -> String { return string.components(separatedBy: " ").reversed().joined(separator: " ") }