Barclays Capital Interview Question
Senior Software Development EngineersCountry: United States
Read the string starting from the end, storing the characters in a variable. If you encounter a "space" character, print the string held by the variable in reverse and clear the variable. Repeat until you've read the entire string. Should run in O(n) time where n is the length of the string.
class Reverse{
static String input = "I love you";
static char[] in = input.toCharArray();
public static void main(String[] args){
int end=0;
int start=0;
for(int i=0;i<in.length; ){
while(i<in.length && in[i]!=' ')
i++;
end=i-1;
in= reverse(start, end, in);
start=i+1;
i=start;
}
in = reverse(0, in.length-1,in);
for(int i=0;i<in.length;i++){
System.out.print(in[i]);
}
}
public static char[] reverse(int i, int j, char[] word){
if(i==j)
return word;
while(i<j){
char temp = word[i];
word[i]=word[j];
word[j]=temp;
i++;
j--;
}
return word;
}
}
Did you calculate the complexity of you program?? Please think from that point. How about the below code?
import java.util.Arrays;
import java.util.StringTokenizer;
public class Test {
public static void main(String[] args) {
String str = "i love you";
String[] strArray = str.split(" ");
StringBuilder sbuilder = new StringBuilder();
for(int i=strArray.length -1;i>=0; i--){
sbuilder.append(strArray[i]).append(" ");
}
System.out.println(sbuilder.toString());
}
}
I have used only one for loop. complexity O(n).
protected static string ReverseOrderingOfWords(string s)
{
string temp = string.Empty;
string reverse = string.Empty;
int counter = 0;
foreach (char ch in s)
{
counter++;
if (!char.IsWhiteSpace(ch))
{
temp = temp + ch;
}
else
{
reverse = " " + temp + reverse;
temp = string.Empty;
}
if (counter == s.Length)
{
reverse = temp + reverse;
}
}
return reverse;
}
#include <iostream>
using namespace std;
string ReverseWordOrders(string s)
{
int index = s.length() - 1;
string temp,result;
for(int i=0; i<=index; i++)
{
if(s[i] != ' ')
{
temp = temp + s[i];
}
else
{
result = ' ' + temp + result;
temp.clear();
}
if(i == index)
{
result = temp + result;
}
}
return result;
}
int main()
{
string myString;
cout << "Enter any string:";
getline(cin,myString);
myString = ReverseWordOrders(myString);
cout<< "String after reversing word orders:" << myString << endl;
return 0;
}
///public class Split_ILU {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "I love you";
String[] str_arr=str.split(" ");
StringBuilder stb=new StringBuilder();
System.out.println("str_arr.length="+str_arr.length);
for(int i=(str_arr.length-1);i>=0;i--){
stb.append(str_arr[i]);
stb.append(" ");
}
System.out.println("stb="+stb.toString());
}
}
///
private static void reverse(String[] args) {
String [] result = new String [args.length];
int counter =0;
for (int i = args.length -1 ; i >=0 ; i-- )
{
result[counter]= args[i].toString();
counter++;
}
//System.out.println( Arrays.toString( args ) );
//System.out.println( Arrays.toString( result ) );
//0(n) one loop
}
Here's the code in C
It calculates in O(n^2)
#include <stdio.h>
#include <stdlib.h>
int main()
{
char *str="I am Sam but my friend is also Sam";
char *str2=NULL,*str1=str,*str3=NULL;
while(*str1!='\0')
{
str1++;
}
str1--;
str2=str1;
while(*str2!=str[0])
{
while(*str2!=' ')
{
str2--;
}
str3=--str2;
str2++;
while(str2!=str1+1)
{
printf("%c",*str2);
str2++;
}
str1=str3;
str2=str3;
}
if(str[1]==' ')
printf(" %c",str[0]);
else
printf("%c",str[0]);
}
This is my implementation of the program in java. It runs in O(N). Hope it helps.
public static void reverseWords(String str)
{
int end=str.length();
int endIndex;
endIndex=str.length();
StringBuilder sb=new StringBuilder();
while(end!=0)
{
end--;
if(str.charAt(end)!=' ' && end!=0)
continue;
else if(str.charAt(end)==' ')
{
sb.append(str.substring(end+1, endIndex));
sb.append(" ");
endIndex=end;
}
else if(end==0)
sb.append(str.substring(end, endIndex));
}
System.out.println(sb);
}
I have got an easy and basic solution for this.
public static void main(String[] args) {
String s="I Love You and You Love Me";
s=" "+s;
String s1="";
int l=s.length()-1;
int ei=0;
while(l>=0){
if(s.charAt(l)==' '){
s1=s1+s.substring(l+1, ei+l+1)+" ";
l--;
ei=0;
}
else{
l--;
ei++;
}
}
char c ='A';
System.out.println("Output string is "+s1+" and ascii of A is "+(int)c);
}
public class StringTest {
public static void main(String[] args)
{
String s="i love you";
String []ss=s.split(" ");
for(int i=ss.length-1;i>=0;i--)
{
System.out.print(" ");
System.out.print(ss[i]);}// YOU LOVE I
}
}
# include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *ptr = "I LOVE YOU";
char *ptr2 ,*ptr3; //for reversal//
int temstrlen = 0;
char *ptr3;
void main()
{
int len=strlen(ptr);
int len1 =len;
int i=0;
ptr2 = (char *) malloc(len+1);
ptr3=ptr2;
while(len)
{
if ((*(ptr+len-1)) !=' ')
{ temstrlen ++; len --;
if(len !=0) continue;
}
//found blank;
for(i=0;i<temstrlen;i++)
{ *ptr2 = *(ptr+len+i);
ptr2++;
}
if(len!=0) {*ptr2=' '; ptr2++; temstrlen=0; len--;}
} //end of while
*(ptr3+len1) = '\0';
printf("%s \n",ptr3);
}
package com.DataStructure;
public class Reverse {
public static void main(String[] args) {
String str = reverse("IM LOVE MY INDIA");
int i = 0, j = 0;
String str2 = "";
int len = str.length();
while (j < len) {
if (str.charAt(j) == ' ') {
str2 = str2 + reverse(str.substring(i, j)) + " ";
i = j + 1;
j = i;
} else if (j == str.length()-1) {
str2=str2+reverse(str.substring(i, j+1));
i = j + 1;
j = i;
} else {
j++;
}
}
System.out.println(str2);
}
static String reverse(String str) {
String str1 = "";
if (str.length() == 0) {
return str;
} else if (str.length() == 1) {
return str;
} else {
return str1 + str.charAt(str.length() - 1)
+ reverse(str.substring(0, str.length() - 1));
}
}
}
package com.DataStructure;
public class Reverse {
public static void main(String[] args) {
String str = reverse("IM LOVE MY INDIA");
int i = 0, j = 0;
String str2 = "";
int len = str.length();
while (j < len) {
if (str.charAt(j) == ' ') {
str2 = str2 + reverse(str.substring(i, j)) + " ";
i = j + 1;
j = i;
} else if (j == str.length()-1) {
str2=str2+reverse(str.substring(i, j+1));
i = j + 1;
j = i;
} else {
j++;
}
}
System.out.println(str2);
}
static String reverse(String str) {
String str1 = "";
if (str.length() == 0) {
return str;
} else if (str.length() == 1) {
return str;
} else {
return str1 + str.charAt(str.length() - 1)
+ reverse(str.substring(0, str.length() - 1));
}
}
}
package com.DataStructure;
public class Reverse {
public static void main(String[] args) {
String str = reverse("IM LOVE MY INDIA");
int i = 0, j = 0;
String str2 = "";
int len = str.length();
while (j < len) {
if (str.charAt(j) == ' ') {
str2 = str2 + reverse(str.substring(i, j)) + " ";
i = j + 1;
j = i;
} else if (j == str.length()-1) {
str2=str2+reverse(str.substring(i, j+1));
i = j + 1;
j = i;
} else {
j++;
}
}
System.out.println(str2);
}
static String reverse(String str) {
String str1 = "";
if (str.length() == 0) {
return str;
} else if (str.length() == 1) {
return str;
} else {
return str1 + str.charAt(str.length() - 1)
+ reverse(str.substring(0, str.length() - 1));
}
}
}
public class Reverse {
public static void main(String[] args) {
String str = reverse("IM LOVE MY INDIA");
int i = 0, j = 0;
String str2 = "";
int len = str.length();
while (j < len) {
if (str.charAt(j) == ' ') {
str2 = str2 + reverse(str.substring(i, j)) + " ";
i = j + 1;
j = i;
} else if (j == str.length()-1) {
str2=str2+reverse(str.substring(i, j+1));
i = j + 1;
j = i;
} else {
j++;
}
}
System.out.println(str2);
}
static String reverse(String str) {
String str1 = "";
if (str.length() == 0) {
return str;
} else if (str.length() == 1) {
return str;
} else {
return str1 + str.charAt(str.length() - 1)
+ reverse(str.substring(0, str.length() - 1));
}
}
}
- Vir Pratap Uttam May 20, 2015