Amazon Interview Question
Software Engineer / DevelopersSay given string is: "My name is Anurag Singh"
1. reverse given string: "hgniS garunA si eman yM"
2. Now reverse each word: "Singh Anurag is name My"
#include <stdio.h>
#include <string.h>
void reverseString(char *s,int start, int end);
int main(int argc, char *argv[])
{
char *s="My name is Anurag Singh";
printf("%s\n",s);
int len=strlen(s);
reverseString(s,0,len-1);
printf("reverse by charater: %s\n",s);
int i=0,start=0;
while(i<=len)
{
if(s[i] && s[i] != ' ')
i++;
else
{
reverseString(s,start,i-1);
start=++i;
}
}
printf("Reverse by Word: %s\n",s);
return 0;
}
void reverseString(char *s,int start, int end)
{
int i=0,j=0;
char c;
for(i=start,j=end;i<j;i++,j--)
{
c=s[i];
s[i]=s[j];
s[j]=c;
}
}
Good. However, in reverseString function, when you try to make s[i]=s[j], the compiler got "access violation error". Who can correct it? Thanks.
char *s="My name is Anurag Singh";
This should be corrected to
char s[]="My name is Anurag Singh";
We can split the string into tokens and reverse append, like below:
public class StringReverse {
public static void main(String[] args) {
String testStr = "Java is platform neutral language";
System.out.println("input=" + testStr);
System.out.println("output=" + reverseString(testStr));
}
public static String reverseString(String s) {
if (s != null && s.trim().length() != 0) {
String[] tokens = s.split("\\s");
System.out.println("tokens=" + Arrays.asList(tokens));
StringBuffer sb = new StringBuffer();
for (int i=tokens.length-1; i>=0; i--) {
sb.append(tokens[i]).append(' ');
}
return sb.toString();
} else {
return null;
}
}
}
OUTPUT:
input=Java is platform neutral language
tokens=[Java, is, platform, neutral, language]
output=language neutral platform is Java
using regular expression is the best choice if allowed, no matter what kind of empty symbols(\t, \n, \r) between words.
String reverseString(String s){
Pattern p = Pattern.compile("\\w+");
Matcher m = p.matcher(s);
String reverse = null;
while(m.find())
if(reverse == null) reverse = m.group();
else reverse = m.group()+" "+reverse;
return reverse;
}
//Reverese a string: (courtesy: crack the interview)
void Reverse(char *str, int start, int end)
{
if(start >= end) return;
else
{
char temp = *(str+start);
*(str+start) = *(str+end);
*(str+end) = temp
Reverse(str,++start,--end);
}
}
//Reverese a words in the sentence:
void WordReverese_Sentence(char *str)
{
int len = strlen(str);
if(len == 0 || len == 1) return;
int i = 0, j =0;
//precondition : i is always = j
//Logic : in the loop j will first find the end of the current word
Then, it will find the next possible spot for i
while(j<len)
{
while(j<len && str[j] != 32)
{
j++;
}
if((j-1) < len) Reverse(str,i,j-1);
while(j<len && str[j] == 32)
{
j++;
}
if(j<len) i=j;
}
}
Works well for
1. empty string
2. one character
3. one word
4. multiple words seperated by single spaces
5. multiple words seperated by multiple spaces
void ReverseWordsInString(char *str)
{
int l = 0;
if(!str)
{
printf("NULL String");
return;
}
l = strlen(str);// O(N)
int s = 0; //Starting index of string
inr e = l-1; //End index of string
char t_ch;
//I: the bus
while(s<e) //Reverse String // O(N)
{
//Swap Sring charcter
t_ch = *(str + s);
*(str + s) = *(str + e);
*(str + e) = t_ch;
s++;
e--;
}
//O: sub eht
// bus the
//Reverse words of string
int space = 1;
int i = 0;
s = 0; e = 0;
int t_s, t_e;
for(i=0; i<l; i++) // O(N)
{
if(str[i] == ' ')//Check for while space
{
if(!space)//Check for eleminating multiple spaces
{
e = i-1;
t_s = s;
t_e = e;
while(t_s<t_e)//reverse word
{
t_ch = *(str + s_t);
*(str + s_t) = *(str + e_t);
*(str + e_t) = t_ch;
t_s++;
t_e--;
}
space = 1;
}
s = i+1;
}
else
{
space = 0;
}
}
printf("String after word reverse: %s", str);
return;
}
#define MAX_LEN 256
char *word_reverse(char *str) {
int i = 0;
char *p;
p = (char *)malloc(sizeof(char) * MAX_LEN);
while(*str != ' ' || *str != '\0') {
p[i++] = *str;
str++;
}
if (*str == ' ') {
str++;
str = word_reverse(str);
strcat(str, p);
strcpy(p, "");
strcpy(p, str);
}
return p;
}
It can also be done using array of strings...
void reverse_by_words(char *src)
{
char *dest,*ptr, **reverse;
int len=0;
dest=malloc(sizeof(char)*strlen(src));
strcpy(dest,src);
ptr=strtok(dest, " ");
while (ptr != NULL) {
reverse[len]=malloc(strlen(ptr)*sizeof(char));
strncpy(reverse[len],ptr,strlen(ptr));
ptr = strtok(NULL, " ");
len++;
}
while (len--!=0) {
printf("%s ",reverse[len]);
}
printf("\n");
}
Use two stacks, A and B. Push in A till space is encountered. Then push in B till next space is encountered..pop from B and push in A till B is empty..continue the loop till all words are pushed..then just pop A till empty (apply suitable error checks)
I don't think you should "Push in A till space is encountered."...
When "push in B till next space is encountered..pop from B and push in A till B is empty..continue the loop till all words are pushed..", you end up with A which has all the individual words reversed *except the first one because you didn't make it go though B!*
At the end when you "then just pop A till empty", you basically reverse the whole string and in combination with the above effort, you get the right outcome...
static string ReverseString(char[] str)
{
Reverse(str, 0, str.Length - 1);
//reverse each word
int startWord = 0;
for (int i = 0; i < str.Length; i++)
{
if (str.Contains(' '))
{
if (str[i] == ' ' || str[i] == '\0')
{
Reverse(str, startWord, i - 1);
startWord = i + 1;
}
else if ((i + 1) == str.Length)
{
Reverse(str, startWord, i);
}
}
else
break;
}
Console.WriteLine(str);
return str.ToString();
}
static void Reverse(char[] str, int beginindex, int endindex)
{
while (beginindex < endindex)
{
char temp = str[beginindex];
str[beginindex] = str[endindex];
str[endindex] = temp;
beginindex++;
endindex--;
}
}
<pre lang="" line="1" title="CodeMonkey20762" class="run-this">void ReverseString(char* str)
{
int i = strlen(str) - 1;
int spaces1 = 0;
char* new_string = (char*)malloc(strlen(str)*sizeof(char));
while(i >= 0)
{
spaces1 = i;
while(str[i] != ' ')
{
i--;
if(i == 0)
{
break;
}
}
if(i != 0)
{
memcpy((char*)new_string + strlen(str) - spaces1 - 1, (char*)str + i + 1, spaces1 - i);
new_string[strlen(str) - i - 1] = ' ';
}
else
{
memcpy((char*)new_string + strlen(str) - spaces1 - 1, (char*)str + i, spaces1 - i + 1);
memset((char*)new_string + strlen(str), NULL, 1);
}
i--;
}
}
</pre><pre title="CodeMonkey20762" input="yes">
</pre>
#include <stdio.h>
#include <conio.h>
void main()
{
char str [] = "I am good boy";
char *ptr1 , *ptr2 ,*start;
ptr1=str;
while (*ptr1!='\0'){
ptr1++;
}
start=str;
while(start<=ptr1){
if(*ptr1==' ')
{
*ptr1 = '\0';
ptr1++;
ptr2=ptr1;
printf("%s",ptr2);
printf(" ");
}
if(ptr1 == start){
printf("%s",start);}
ptr1--;
}
getch();
}
Try this code!!
Separate each word and put them into stack and call popup.
- Sanjay Kumar (Inventwheel.com) February 07, 2011