Bloomberg LP Interview Question
Financial Software DevelopersI would suggest reversing the string as a solution given below:
"I am from Chicago"
Step 1: Read the characters from rear and keep it infront of the String
"o I am from Chicag"
"go I am from Chica"
and soon until
"Chicago I am from "
Step 2: Now reads the space. In this case, locate the position of first " " [space] from Chicago. Now follow the same process as given above in step 1
"Chicago m I am fro"
"Chicago om I am fr"
"Chicago rom I am f"
"Chicago from I am "
Now again space came at rear. Now go to the first space after from and follow the first step.
public static void revOneByte(char arr[]){
int len = arr.length;
char temp;
int l=0;
int t;
while(l<len-1)
{
t=l;
while(arr[len-1]!=' ')
{
temp = arr[len-1];
System.arraycopy(arr,t,arr,t+1,len-(t+1));
arr[t] = temp;
l++;
}
System.arraycopy(arr,l,arr,l+1,len-(l+1));
arr[l]= ' ';
l++;
}
System.out.println(arr);
}
Let me elaborate on what ekapil2 said .
First make a function reverse(char *a,int start,int end)which reverses an array given its start and end .
Second reverse the entire array .
Third make a function that reverses words i.e. it checks for spaces b/w words and asks reverse() to reverse it by sending its start and end .
The first & simplest I can think of is:
Use the temporary byte and do shift right by the size of the array times.
Steps:
eg: "I AM NSK"
0. Given Array: "I AM NSK" Byte: ' '
i. " I AM NS" 'K' (push last char K to the tmp byte.
ii. "KI AM NS" ' ' (push from tmp byte to first byte of Array).
iii." KI AM N" 'S'; "SKI AM N" ' '
iv. " SKI AM " 'N'; "NSKI AM "
v. do this by n time where n is the length of the array. And We have what we wanted.
As you know, first thought is always unamortized, there may be better solutions.
Best storage for this linked list of words where reversing is cheaper(concept of stack or use two pivots).
void chicago(char str[], int,int len);
void chicagoRev(){
char str[] = {"I am from Chicago"};
int len = strlen(str);
chicago(str, 0, len);
int j = 0;
for(int i=0;i< len-1; i++){
if(str[i] == ' '){
chicago(str, j,i);
j = i+1;
}
}
cout << str;
}
void chicago(char str[], int start,int len) {
for(int i=start, j=len-1; i< ((start+len)/2), j>=(start+len)/2; i++, j--)
{
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}
I hope this is the solution.
This code works! However there could be one improvement: if there are multiple blank spaces laying in the middle, say " I am from Chicago". you will make unnecessary calls to chicago().
I think first reverse the string as "ogacihC morf ma I"
- ekapil2 October 11, 2010Now reverse each word to get "chicago from am I"