GE (General Electric) Interview Question
Software Engineer / DevelopersHere is the code that I have tested with GCC..it work superb, complexity is O(2n)..
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char * reverse(char *input)
{
char *tmp = input;
int count = 0;
while(tmp && *tmp)
{
if (*tmp == ' ') count++;
tmp++;
}
char *p[++count];
char *new = (char *) malloc((strlen(input)+1)*sizeof(char));
char *output = new;
p[0] = input;
int i=1;
while(input && *input && i<count)
{
if (*input == ' ')
{
p[i++] = ++input;
}
else
{
input++;
}
}
int j;
for(j=count-1;j>=0;j--)
{
while(*p[j] != '\0' && *p[j] != ' ' )
{
*new++ = *p[j]++;
}
*new++ = (j > 0)? ' ':'\0';
}
return output;
}
int main()
{
char y[] = "I am an Indian";
printf("%s\n",y);
char *x = reverse(&y[0]);
while(x && *x)
{
printf("%c",*x);
x++;
}
return 0;
}
Hi codegeek,
THe solution u have provided is fine, but u have to do it without extra space. The sort should be inplace sort
1. Reverse each word - O(n) time, O(1) space
2. Reverse all sentence - O(n) time, O(1) space
Algo:
for the first output push first string in the stack & print rest & then pop the stack.
for the 2nd output push 2 string & print the remaining & likewise for the 3rd output.
java code:
public static void main(String[] args) {
String a = "I am an indian";
Stack<String> stack = new Stack<String>();
String[] temp;
String delimiter = " ";
temp = a.split(delimiter);
for(int i=0;i<temp.length-1;i++){
int k=i;
for(int l = 0;l<=k;l++){
stack.push(temp[l]);
}
for(int j=i+1;j<temp.length;j++){
System.out.print(temp[j]+" ");
}
while(!stack.isEmpty()){
System.out.print(stack.pop()+" ");
}
System.out.println();
}
}
}
Depends on how the string is presented, as an array of characters or as a linkedlist of words..
My best bet would be to convert the given thing into a linked list of words, and then manipulate the string accordingly using 2 pointers, one at the end, i.e. at the word 'indian' and one at the starting of the sentence..
#include <stdio.h>
#include <string.h>
void reverse(char *str)
{
int ii;
char temp;
int len = strlen(str) - 1;
for(ii = 0; ii < len; ii++, len--)
{
temp = str[ii];
str[ii] = str[len];
str[len] = temp;
}
}
int main(int argc, char *argv[])
{
char str[] = "Hi a this is Lakshman";
int len = strlen(str);
reverse(str);
char *token = NULL;
for(token = strtok(str, " "); token != NULL; token = strtok(NULL, " "))
reverse(token);
int ii;
for(ii = 0; ii != len; ii++)
{
if(str[ii] == '\0')
str[ii] = ' ';
}
printf("%s\n", str);
return 0;
}
package demo;
import java.util.Scanner;
public class JavaDemoTwo {
private static String original = "";
public JavaDemoTwo() {
// TODO Auto-generated constructor stub
}
static void readInput(){
Scanner in = new Scanner(System.in);
System.out.print("Enter a string to reverse : ");
original = in.nextLine();
in.close();
}
static void reverseString(){
String reverse = "";
int length = original.length();
for ( int i = length - 1 ; i >= 0 ; i-- )
reverse = reverse + original.charAt(i);
System.out.println("Reverse of entered string is: "+reverse);
}
static String rearrangeStrings(String myString){
int indexOfSpace = myString.indexOf(" ");
String finalString = myString.substring(indexOfSpace + 1)+" "+myString.substring(0, indexOfSpace);
original = finalString;
return original;
}
public static void main(String[] args) {
readInput();
System.out.println("input string : " + original);
reverseString();
for(int i=0;i<original.split(" ").length-1;i++ )
System.out.println(rearrangeStrings(original));
}
}
Algo:
split the input string on space delimiter.
for fisrt output push fisrt string in stack & then print remaining strings & then pop the stack.
for 2nd output push 2 strings in stack & print remaining & then pop both the string from stack & like wise for the 3rd output ,push 3string in stack & print remaining & then pop the stack with all three strings.
Here goes the java code:
public class Stoken{
public static void main(String[] args) {
String a = "I am an indian";
Stack<String> stack = new Stack<String>();
String[] temp;
String delimiter = " ";
// given string will be split by the argument delimiter provided.
temp = a.split(delimiter);
for(int i=0;i<temp.length-1;i++){
int k=i;
for(int l = 0;l<=k;l++){
stack.push(temp[l]);
}
for(int j=i+1;j<temp.length;j++){
System.out.print(temp[j]+" ");
}
while(!stack.isEmpty()){
System.out.print(stack.pop()+" ");
}
System.out.println();
}
}
}
Here is a clean C++ solution. Tested with VS.
#include <iostream>
using namespace std;
int cnt;
void SortWord(char str[], int len)
{
char *temp = new char[len];
memset(temp, 0, len);
for (int i = 0; str[i] != '\0' && cnt > i; i++)
{
if (str[i] == ' ') {
memcpy(temp, &str[i + 1], len - i - 1);
str[i] = '\0';
temp[len - i - 1] = ' ';
memcpy(&temp[len - i], str, i);
temp[len] = '\0';
memcpy(str, temp, len);
cout << str << endl;
cnt = cnt - i - 1;
SortWord(str, len - i - 1);
break;
}
}
}
int main()
{
char input[] = "this is a test";
int len = strlen(input);
cnt = len;
SortWord(input, len);
return 0;
}
the input string can be changed. A sample output of string "this is a test of fun" looks like:
is a test of fun this
a test of fun is this
test of fun a is this
of fun test a is this
fun of test a is this
Hey this can be done in various ways...the best approach is to maintain distinct char pointers to individual words in the sentence and then form new words for specified order by assigning the words pointed by those particular pointers in the new sentence.
- CodeGeek December 30, 2010For example, for sentence char *input = "i am an indian"; there can be 4 char pointers declared, say
char *p1,*p2,*p3,*p4;
then assign pointers such that they should point to individual words, i.e.
p1 = "i" , p2 = "am" , p3 = "an" , p4 = "indian"
and then declare new sentence as follow
char* new = (char *) malloc( (strlen(input)+1)*sizeof(char) );
Note: size is inputstring lenght + 1 to accomodate the null character at the end.
Now, start assigning individual words to this new *empty* string
pointed by char * output.
This is the algorithm..