Amazon Interview Question Software Engineer / Developers
code in java:
public class StringReverse {
public static String strRev(String s)
{
String reversedString="";
for(int i=(s.length()-1);i>=0;i--)
{
reversedString+=s.charAt(i);
}
return reversedString;
}
public static void reverseWordByWord(String s)
{
String wordFormed="";
String requiredString="";
for(int i=0;i<=s.length();i++)
{
if(i==s.length() || s.charAt(i)==' ')
{
wordFormed=strRev(wordFormed);
requiredString+=wordFormed+" ";
System.out.println(requiredString);
wordFormed="";
}
else
wordFormed+=s.charAt(i);
}
System.out.println(requiredString);
}
public static void main(String[] args)
{
String s="What is this";
String reversedString=strRev(s);
reverseWordByWord(reversedString);
}
}
Gayle -- How about using a HashTable? You will need to make just one pass over the string.
Here arent we assuming that words are separated by spaces. What if some of the words are separated by '-' or any such character?Or there is something like "coca - cola". In fact I was asked this very question in an interview.This was a follow up question to reverse words.Any ideas?
If extra space is allowed, there can be various solutions and still none of them can improve the runtime better than O(n).
Since we've an O(n) solution without extra space (1st sol) - I feel we should stick to that.
Ravas - In the first solution, we can use a list of word delimiters like white space, comma, period, dash etc and still the algorithm won't be much complicated.
Is there a constraint that we cannot use another temp string.
Why cant we directly start from the end of the original string, move bakwards and add a word at a time. Each character would be traversed twice, once while moving backwards to see if its the start of a word and again while copying to the output string.
Complexity would still be O(n)
char* reversestr(char st[])
{
char* rev = (char*)malloc(strlen(st));
int pos = 0,prevpos,revpos=0;
int len = strlen(st);
pos += len-1;
cout<<"last word:"<<st[pos];
while(pos > -1)
{
while(st[pos] != ' ' && pos > -1) {pos--; }
prevpos=pos;
pos++;
while(st[pos] != ' ' && st[pos] != '\0')
{
rev[revpos++] = st[pos++];
cout<<"\nlast char added:"<<rev[revpos-1];
}
rev[revpos++] = ' ';
pos=prevpos-1;
}
rev[len] = '\0';
cout<<"\nreversed string :"<<rev;
return rev;
}
two solutions
1.recursion
2.iteration
Strategy >
first reverse the whole string
then reverse it word by word.
1.recursion:
#include<stdio.h>
char s[100]="Madan Mohan Malviya";
void reverse(char a[]);//to reverse string.
void revword(char a[]);//to reverse word.
void main(){
reverse(s);
revword(s);
printf("%s",s);
}
void reverse(char a[]){
static int i=0;
char x=a[0];
if(x == NULL)
return;
reverse(&a[1]);
s[i++]=x;
}
void revword(char a[]){
static int i=0;
char x=a[0];
if(x == ' '|| x == NULL)
return;
revword(&a[1]);
s[i++]=x;
if(s[i]==' '){
i++;
revword(&s[i]); //called when next word appears.
}
}
2nd solution
Using Iteratin:
#include<stdio.h>
char s[100]="Madan Mohan Malviya";
void main(){
char temp;
int i=0,len=0;
//reversing the whole string
while(s[len])
len+=1;
len =len-1;
while(len>i){
temp=s[i];
s[i++]=s[len];
s[len--]=temp;
}
//reversing words
int base=0,j;
while(1){
i=0;
while((s[base+i] != ' ') && (s[base+i] != NULL))
i++;
len=i;
i--;
j=0;
while(i>j){
temp = s[base+i];
s[base+i]=s[base+j];
s[base+j]=temp;
i--;
j++;
}
base=base+len;
if(s[base] == NULL)
break;
base=base+1;
}
printf("\n\n%s\n\n",s);
}
#include <iostream>
using namespace std;
class sample {
char *s;
public:
sample(char *p) {
s=new char[strlen(p) +1];
s=strcpy(s,p);
}
char* reverse();
};
char *sample::reverse() {
char *temp, *temp1, *temp2;
int check = 0;
temp = new char[strlen(s) + 1];
temp1 = new char[strlen(s) + 1];
*temp1='\0';
temp2 = temp;
while(*s != '\0') {
if (*s != ' ') {
*temp = *s;
temp++;
} else {
if(check == 1) {
*temp = ' ';
temp++;
} else {
check = 1;
}
*temp = '\0';
strcat(temp2,temp1);
strcpy(temp1,temp2);
temp = temp2;
}
s++;
}
*temp = ' ';
*++temp = '\0';
strcat(temp2,temp1);
return temp2;
}
main() {
sample samp("test the program");
cout << samp.reverse();
}
usually they were expecting your lower level skill of programming. So, they prefer you not use any library nor and string object (not even swap() nor strcpy() ). Ravi and vel provided the good solution of skill sets that the candidate knows pointers and low level primitive memory allocation like char and char* For the ones who only know how to use libraries or stack.. what so ever.. tough luck..
my solution is different. I use an array of pointers to separate only the "head" and ignore the "tail" .For example, a string "reverse this sentence" ...
the pointers will be
ptr1->"reverse this sentence"
ptr2->"this sentence"
ptr3->"sentence"
So.. just get only the first word each of the above pointers(from the last ptr to the first ptr), wala.. u got the reversed words.
For eg, "sentence" from ptr3, "this" from ptr2, "reverse" from ptr1.
Note: this is better than the first solution because pointers are cheap. Whereas the first solution requires a lot of CPU time to reverse each char then reverse each word again....(imagine if the string has hundred of words, would you rather just use pointers or the first solution?)
Here is my code...
/* If the string is
My name is Gaurav
it should give
Gaurav is name my
ym eman si varuag
*/
#include<stdio.h>
void reverse(char *, int, int);
void main()
{
char buf[100];
int start_index, end_index = 0, i, len=0, nlen = 0;
char *s;
char temp;
printf("Please enter the string \n");
s = gets(buf);
i=0;
while(s[i++] != '\0')
continue;
len = i-1;
nlen = len;
start_index = 0, i =0;
while(len)
{
if(s[i++] != ' ')
end_index++;
else
{
reverse(buf, start_index,end_index-1);
start_index = end_index + 1;
end_index = start_index;
}
len--;
}
reverse(buf, start_index,end_index-1);
printf("The new string is %s\n", buf);
s = buf;
i = 0;
while(i<nlen)
{
temp = s[i];
s[i++] = s[--nlen];
s[nlen] = temp;
}
printf("Another new string is %s\n", buf);
}
void reverse(char * s, int start, int end)
{
char temp;
while(start < end)
{
temp = s[start];
s[start++] = s[end];
s[end--] = temp;
}
}
Java code ;
public class ReverseWordInAString {
/**
* @param args
*/
public static void main(String[] args) {
doReverse("the quick brown fox");
}
// No EXTRA SPACE && o(n) solution
public static void doReverse(String input){
int j,i;
int l =input.length();
int end=l-1;
for(i=l-1;i>=0;i--){
if(input.charAt(i)!=' ')
continue;
else{
j=i+1;
while(j<=end){
System.out.print(input.charAt(j));
j++;
}
end=i-1;
System.out.print(" ");
}
}
i=0;
while(i<=end){
System.out.print(input.charAt(i));
i++;
}
}
}
import java.io.*;
public class RevSentence {
public static void main(String args[]) throws IOException
{
String s= new String();
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
s=br.readLine();
char a[]=s.toCharArray();
int len=a.length;
// Reverse whole array
int j=len-1;
for(int i=0;i<=(len-1)/2;i++)
{
char temp=a[i];
a[i]=a[j];
a[j]=temp;
j--;
}
int start=0,end=0;
for(int i=0;i<a.length;i++)
{ // Reverse array word by word
if( a[i]==' ' || i==a.length-1)
{
end=i-1;
if( i==a.length-1) // to handle last word
{
end=a.length-1;
}
int k=end;
for(j=start;j<=(start+end)/2;j++)
{
char temp=a[j];
a[j]=a[k];
a[k]=temp;
k--;
}
start=end+2; // start of next word
}
}
String b=new String(a);
System.out.println(b);
}
}
/*
Output:
welcome to hell
hell to welcome
*/
Time complexity :- O(n)
just put each word in a stack... and pop
- vikas gupta April 17, 2006