CareerCup

Algorithm:

1> Reverse the string
2> Reverse each word in the reversed string

Had Answer this Algo long time Back .. Responding again.

1> Read each word and put into the stack. use recursion for efficiency.
2> Read the Stack till get empty.

#include <stdlib.h>
#include <stdio.h>

void reverse(char*, char*);

int main() {
    char str[] = "The cat in the hat";
    char *pHead, *pTail, *pEnd, *temp;
    
    //First reverse the whole string
    pHead = pTail = str;
    while(*pTail != '\0')
        ++pTail;
    pEnd = pTail--;
    reverse(pHead, pTail);
    
    //Reverse the (reversed) string word by word
    temp = str;
    while(temp < pEnd) {
        pHead = pTail = temp;
        while(*pTail != ' ' && *pTail != '\0')
            ++pTail;
        temp = pTail--;
        ++temp;
        reverse(pHead, pTail);
    }
    printf("%s\n",str);
    
    return 0;
}

//Reverses the string provided the head & tail of the string
void reverse(char *pHead, char *pTail) {
    char ch;
    
    while(pTail >= pHead) {
        ch = *pTail;
        *pTail-- = *pHead;
        *pHead++ = ch;
    }
}

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

char str[80];

void rev(int l, int r)
{
    char temp;
    while(l<r)
    {
        temp = str[l];
        str[l] = str[r];
        str[r] = temp;
        l++,r--;
    }
}

void fun()
{
    int start = 0, last = strlen(str)-1;
    rev(start, last);
    last = 0;
    while(start < strlen(str))
    {
        while(str[last] != ' ' && str[last] != '\0')
            last++;

              rev(start, last-1);

        while(str[last] == ' ' && str[last] != '\0')
            last++;
        start = last;
    }
}

int main()
{
    cout<<"Enter the string : ";
    gets(str);
    fun();
    cout<<"Output : ";
    puts(str);
    return 0;
}

string str = "This is a cat";
string[] ch=str.Split(' ');

for (int i = ch.Length-1; i >= 0; i--) {

Console.Write(ch[i]+' ');
}

"Spaces between words may not be consistent."

Evan:
Can you advise how inconcistent the spaces might be in between words.

void Reverse(char* ptr1, char* ptr2)
{
	while(ptr1<ptr2)
	{
		char ch=*ptr1;
		*(ptr1)=*(ptr2);
		*ptr2=ch;

		ptr1++;
		ptr2--;
	}
}

void ReverseWordsInSentence(char *input)
{
	char *ptr1 = input, *ptr2 = input;

	while(*ptr2)
		ptr2++;
	ptr2--;

	Reverse(ptr1, ptr2);

	cout<<input;

	ptr1=ptr2=input;

	while(*ptr1 && *ptr2)
	{
		while(*ptr1==' ' && *ptr1)
			ptr1++;

		ptr2=ptr1;
		while(*ptr2!=' ' && *ptr2)
			ptr2++;
		char* temp=ptr2;

		ptr2--;

		Reverse(ptr1, ptr2);
		ptr1=temp;
	}
}

Read the character by character in string ,store the index of the first letter, if the character is empty space then do the reverse word from the starting index to current position-1 finally read the string from last character to first character

Read the character and put into the stack if a empty space occures pop up all the character from stack add to output string. if space comes add directly to out put string keep on doing till it gets end of the string. finally read the string from back words

Read the string put it in a array print it backwards

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class StringReversal {

	public static void main(String arg[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("Enter the string to reverse :");
		String str = br.readLine();
		char c, temp[] = str.toCharArray();
		for (int i = 0; i < (str.length() / 2); i++) {
			c = temp[i];
			temp[i] = temp[str.length() - 1 - i];
			temp[str.length() - 1 - i] = c;
		}
		System.out.print("Reversed string is : " + String.valueOf(temp));

		String words[] = String.valueOf(temp).split(" ");
		str = "";

		for (int i = 0; i < words.length; i++) {
			// System.out.print(words[i]);
			temp = words[i].toCharArray();
			int length = temp.length;
			for (int j = 0; j < (length / 2); j++) {
				c = temp[j];
				temp[j] = temp[length - 1 - j];
				temp[length - 1 - j] = c;
			}
			str += String.valueOf(temp)+" ";
		}
		System.out.println("Reversed word order is  : " + str);

	}
}

#include<stdio.h>

#define TRUE 1
#define FALSE 0

int main()
{
    char inp[100];
    int flag1=FALSE,flag2=FALSE,i=0,j=0,k=0,len;
    char c='\0';
    printf("Enter the input string = ");
    gets(inp);
    len = strlen(inp);
    for(i=0;i<=len;i++)
    {
          if((inp[i] == ' ') || (inp[i] == '\0'))
          {
                  if(flag1)
                  {
                         //reverse(inp,j,k);
                         //printf("\n%d\t%d\t%s",j,k,inp+j);
                         k--; //This is needed as for 'hello' k=5 but we need it to k=4;
                         while(j<k)
                         {
                               c=inp[j];
                               inp[j]=inp[k];
                               inp[k]=c;
                               j++;
                               k--;
                          }                                   

                         flag1 = FALSE;
                  }
                  flag2 = TRUE;

          }                              
          else
          {
                  if(flag2)
                  {
                       j = i;
                       k = i;
                       flag2 = FALSE;
                  } 
                  flag1 = TRUE;
                  k++;
          }                  
    }          
    printf("\nThe reversed string = %s",inp);
    getch();
    return 0;
}

static void Main(string[] args)
        {
            string s = "This is Test";
            string[] str = s.Split(' ');
            int t = str.Length;            

            string[] strr = new string[t];
            
            foreach (string st in str)
            {
                strr[t-1] = st;                
                
                t--;                
            }

            foreach (string a in strr)
            {
                Console.WriteLine(a);
            }
            
            Console.ReadLine();
        }

#include<iostream.h>
#include<string>
using namespace std;
int main()
{
	int i=0,j=0,k=-1;
	string s1="this is a cat";
	string s[20];
	for(k=0;k<s1.length();k++)
	{
		if(s1[k]==' ')
		{
			j++;
			continue;
		}
		else if(s1[k-1]==' '&&s1[k]==' ')
		continue;
		else
		{
			s[j]+=s1[k];
			continue;
		}
	}
	while(j>=0)
	{
		cout<<" "<<s[j];
		j--;
	}
	
	return 0;
}

its just a pseudo code

function(String str)
{
while(str[i]!=NULL)
{
if(str[i]!=' ')
push(str[i] ) ///in stack
else
{
while(stack is not empty)
pop and store in some string

}
}

while(stack is not empty)
pop and store in some string

reverse the some string and print it.


}

#include<stdio.h>
void reverse(char *);
void main()
{
int i;
char *s="sur is a good boy";
char *p;
reverse(s);
p=strtok(s," ");
while(p)
{
reverse(p);
printf("%s ",p);
p=strtok(NULL," ");
}

}
void reverse(char *org)
{
char *s,temp;
s=org+strlen(org)-1;
while(*org && org<s)
{
temp=*s;
*s=*org;
*org=temp;
org++;
*s--;
}
}

This is one of the interview question I met before. The interviewer needs me to implement an algo with O(1) space complexity. I think my solution is O(1) now; Yet it seems the time complexity is O(N).

public class ReverseWord {

	public static void reverseWords(char[] words) {
		int head = 0;
		int tail = 0;
		while (tail < words.length) {
			while (tail<words.length && words[tail] != ' ') {
				tail++;
			}
			reverseWord(words,head,tail-1);
			tail++;
			head = tail;
		}
	}

	private static void reverseWord(char[] words,int head,int tail) {
		if (words == null || words.length == 0) {
			return;
		}
		while(head < tail){
			char tmp = words[head];
			words[head++] = words[tail];
			words[tail--] = tmp;
		}
	}

	public static void main(String[] args) {
		reverseWords("This is a cat".toCharArray());
	}

}

I write this in Java. Plz feel free to comment.

public static String reverseWord(String s)
	{
		String result = "";
		String word = "";
		for (int i=s.length()-1; i>=0; i--)
		{
			if ((s.charAt(i)>='a' && s.charAt(i)<='z') || (s.charAt(i)>='A' && s.charAt(i)<='T'))
				word = s.charAt(i) + word;
			else
			{
				result += word + " ";
				word = "";
			}
		}
		result += word; // easy to forget this one!
		
		return result;
	}