Citigroup Interview Question
Java DevelopersCountry: India
Very nice solution, but probably not as space efficient as the solution above, that is you have to create three strings (one each for the two substrings and one for the concat). The solution above is in - place and requires no extra storage.
public class MoveChar{
public String move(String input) {
char[] arr = input.toCharArray();
swap(arr, 0, arr.length-1);
int i = arr.length - 1;
while(i > 1) {
swap(arr, i, i-1);
i--;
}
return new String(arr);
}
private void swap(char[] arr, int x, int y) {
char c = arr[x];
arr[x] = arr[y];
arr[y] = c;
}
}
swap the first and last char
then continue swapping neighbors till the second element in the char array
Hmm.. ok.
Best done if underlying data structure is a pointer linked data structure with a head and tail pointer available.
Then a rotate by 1 char is O(1).
If you want to go with an array,
temp=a[0];
for(int i=0; i<N-2; i++) a[i]=a[i+1];
a[N-1] = temp;
In Java,
public class JavaStringShift {
public static void main(String[] args) {
String str = "abcde";
System.out.println("Input : " + str);
str = strShift(str);
System.out.println("Output : " + str);
}
public static String strShift(String str) {
char[] chars = new char[str.length()];
str.getChars(str.length()-1, str.length(), chars, 0);
str.getChars(0, str.length()-1, chars, 1);
return new String(chars);
}
}
Input : abcde
Output : eabcd
static String shiftString(String str) {
int length = str.length();
char[] chars = new char[length];
chars[0] = str.charAt(length-1);
//a-0,b-1,c-2,d-3,e-4
//e-0,a-1,b-2,c-3,d-4
for (int i = 0, j = i + 1; i < length - 1; i++,j++) {
chars[j] = str.charAt(i);
}
return String.valueOf(chars);
}
Would this be efficient w.r.t space requirement?
public class moveChar {
public static void main(String[] args){
String str = "abcde";
System.out.println("Input: " + str);
String out = move(str);
System.out.println("Output: " + out);
}
public static String move(String str){
char[] s = str.toCharArray();
StringBuilder strB = new StringBuilder();
strB.append(s[s.length-1]);
for (int i=0; i<s.length-1; i++)
{
strB.append(s[i]);
}
return (strB.toString());
}
}
public class Oness {
public static void main(String[] args) {
String s1="abcde";
String s2="eabcd";
System.out.println("1 st Approach ");
for(int i=0;i<s1.length();i++)
{
String s=s1.substring(0,1);
s1=s1.substring(1, s1.length());
s1=s1+s;
if(s1.equals(s2))
{
System.out.println("found at position "+(i+1));
break;
}
}
System.out.println("2nd Approach");
String s5="abcde";
String temp=s5.substring(s5.length()-1,s5.length());
s5=s5.substring(0,s5.length()-1);
s5=temp+s5;
System.out.println(s5);
}
}
OutPut :
1 st Approach
found at position 4
2nd Approach
eabcd
public class Oness {
public static void main(String[] args) {
String s1="abcde";
String s2="eabcd";
System.out.println("1 st Approach ");
for(int i=0;i<s1.length();i++)
{
String s=s1.substring(0,1);
s1=s1.substring(1, s1.length());
s1=s1+s;
if(s1.equals(s2))
{
System.out.println("found at position "+(i+1));
break;
}
}
System.out.println("2nd Approach");
String s5="abcde";
String temp=s5.substring(s5.length()-1,s5.length());
s5=s5.substring(0,s5.length()-1);
s5=temp+s5;
System.out.println(s5);
}
}
OutPut :
1 st Approach
found at position 4
2nd Approach
eabcd
public class MoveStringChar {
static String moveChars(String input){
char[] output = input.toCharArray();
for(int i=0; i<input.length();i++){
if(i==0){
output[i]= input.charAt(input.length()-1);
}
else{
output[i] = input.charAt(i-1);
}
}
return String.valueOf(output);
}
public static void main(String[] args){
System.out.println(moveChars("abcde"));
}
}
public class CharMoveTest {
public static void main(String[] args) {
String str = "abcdef";
char[] elements = str.toCharArray();
char lastElement = elements[elements.length-1];
for(int i=elements.length-1;i>0;i--){
elements[i] = elements[i-1];
}
elements[0] = lastElement;
System.out.println(elements);
}
}
How about this one
- Amruta October 21, 2013