Amazon Interview Question: Assume you have a method isSubstring which checks if one word is a substring of another.

Let say you have two string s1 and s2 ,write code to check if s2 is a rotation of s1 using only one call to isSubstring(eg. "WaterBottle" is a rotation of "erbottlewat").

Approach First:

lets take s1 into two parts x and y in rotation.

s1= xy = waterbottle

x= wat

y=erbottle

s2=yx=erbottlewat

Solution:

public boolean isRotation(String s1, String s2)
{
  int len =s1.length();
  if(len == s2.length() && len > 0)
  {
    String s1s1=s1+s1;
    return isSubstring(s1s1,s2);
  }
  return false;
}

Amazon Interview Question............................................... :)

Write a method to perform basic string compression eg. aabcccccaaa.Should become the ouput a2b1c5a3.

Bad Solution:

public String compressBad(String str)
{
  String mystr= "";
  char last=str.charAt(0);
  int count = 1;
  for(int i=1; i< str.length();i++)
  {
    if(str.charAt(i) == last)
    {
      count++;
    
    }
    else
    {
      mystr +=last + "" + count;
      last =str.charAt(i);
      count =1;
    }
  }
  return mystr + last +count ;
}

This code will not be able to handle all the case.Lets take a look at the runtime of this code.

The runtime is o(p+K to the power of 2)

p=size of the original string.

k=number of character sequences.

So if the string is aabccdeea then there are six character sequence  which will be slow the concatenation operates in o(n to the power of 2).

Write a method to replace all spaces with %20 in a String.(Note-Perform in place operation only.)

public void replaceSpaces(Char[] str, int length)

{

  int spaceCount=0;

  int newLength,i;

   for(i=0;i<lenght;i++)

   {

     if(str[i] == ' ')

      {

         spaceCount++;

      }

   }

  newLenght =newLength + spaceCount *2;

 str[newLength] = '\0' ;

 for( i=length -1; i>=0,i--)

 {

   if(str[i] == ' ')

   {

     str[newLength -1] = '0';

    str[newLength -2] = '2';

    str[newLength -3] = '%';

    newLength =newLength - 3 ;

   }

  else

  {

     str[newLength -1] = str[i] ;

     newLength =newLength - 1;

  }

 }

}

 Note: i have implemented this problem using character arrays because java string are immutable.if you will use string directly.this would require a new copy of the string but it would allow us  to implement this in just one pass.

How will you check,given two strings are permutation of the other.

Example:    "god"   permutation will be "dog" 

Solution:

 public String sort(String s)

 {

   char[] content = s.toCharArray();

   java.util.Arrays.sort(content);

   return new String(content);

 }

public boolean permutation(String s ,String t)

{

  if(s.lenght() ! = t.length())

 {

   return false;

 }

 return  sort(s).equals(sort(t));

}

Though this solution is not as optimal in some cases.

Programming Questions on String and its Best Solution with its complexity

Question: Write an algorithm to find if a string has all unique characters.what if you cannot use additional data-structure?.

Solution: i will write only method(Algorithm).

public boolean isUniqueChar(String str)

{

   if(str.lenght() > 256)

    return false;

 boolean[] char_set = new boolean[256];

 for(int a=0; str.length(); a++)

  {

    int val = str.charAt(a);

    if(char_set[val])

    {

       return false;   // because alredy found this char instring

    }

     char_set[val] = true;

  }

  return true;

}

Explanation:

 Time Complexity for this code is o(n) where  n=length of the string.

  Space complexity =o(1)

Again once question here,Can we reduce the space complexity? if yes then how?

Solution: yes we can reduce the space complexity using a bit vector.