Amazon Interview Question
Quality Assurance EngineersTeam: Kindle
Country: India
Interview Type: Written Test
Youre assuming the direction of rotation is always the same, which wasnt given. This fails if we have for example s="amazon" and s2="onamaz"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
char s1[1000],s2[1000];
int len1, len2,i,j,flag=1;
scanf("%s",s1);
scanf("%s",s2);
len1=strlen(s1);
len2=strlen(s2);
for(i=2;i<len1;i++){
if(s2[i-2]!=s1[i]){
flag=0;
break;
}
}
if(flag){
if(s1[0]!=s2[len2-2])
flag=0;
if(flag){
if(s1[1]!=s2[len2-1])
flag=0;
}
}
if(flag)
printf("True");
else printf("False");
return 0;
}
First, the length of S1 and S2 should equal.
It is ez to solve by duplicate s1 or s2 like s2 = s2+s2:
e.g S1="amazon" S2="azonam"
Assuming we are duplicating S2:
S2="azonamazonam";
Then, we can scan S2, find whether S2 contains S1.
public static boolean isRotated(String s1, String s2) {
if (s1.length()!=s2.length())
return false;
int len = s1.length();
// double String "s2";
s2 = s2+s2;
for (int i=0;i<len;i++) {
if (s2.substring(i,i+len).equals(s1))
return true;
}
return false;
}
The time complexity should be O(n), space complexity O(1);
}
Logic is works well .Adding addtional verification.
if (s1.length()!=s2.length())
return false;
int len = s1.length();
// double String "s2";
s1 = s1+s1;
for (int i=0;i<len;i++) {
if (s1.substring(i,i+len).equals(s2)) {
if (i==2) {
System.out.println("Left Roatation works");
return true;
} else {
i=i+len-1;
String ch = s1.substring(i+1,len*2);
if (ch.length() == 2) {
System.out.println("Right rotation works");
}
}
}
}
return false;
}
bool isSubstr2Places(string s1, string s2){
return (s2 == s.substr(2) + s.substr(0,2)) || (s2 == s.substr(0,2) + s.substr(2) );
}
public static boolean isRotatedByTwoChars(String s1, String s2)
{
String s3 = s1.substring(2, s1.length())+ s1.substring(0,2);
String s4 = s1.substring(0, s1.length()-2) + s1.substring(s1.length()-2, s1.length());
System.out.println(s3);
System.out.println(s4);
if (s2.equals(s3) || s2.equals(s4)) return true;
else return false;
}
private static int myMod(int value, int mod){
if( value >= 0 ){
return value % mod;
}
return mod + value;
}
/**
* Rotate string to the right.
* time: O(N)
* space: O(N)
*/
public static String rotate(String str, int offset){
if( str == null ){
throw new IllegalArgumentException("Can't rotate NULL string");
}
if( offset == 0 ){
return str;
}
char[] arr = str.toCharArray();
BitSet handledPositions = new BitSet(str.length());
for( int i = 0; i < arr.length; i++ ){
int cur = i;
int next = myMod((cur+offset), arr.length);
char temp = arr[cur];
/** not handled yet */
while( ! handledPositions.get(next) ){
char ch = temp;
temp = arr[next];
arr[next] = ch;
cur = next;
next = myMod((next+offset), arr.length);
handledPositions.set(cur);
}
}
return new String(arr);
}
/**
* Check if 'rotated' string is rotation by 2 positions to the left/right of a 'base' string.
* time: O(N)
* space: O(N)
*/
public static boolean isRotateByTwo(String base, String rotated){
if( base == null || rotated == null ){
throw new IllegalArgumentException("NULL 'base' and/or 'rotated' stirng(s) passed");
}
if( base.length() != rotated.length() ){
return false;
}
/**
* 1. shift right by 2 and check;
* 2. shift left by 2 and check.
*/
return rotate(base, 2).equals(rotated) || rotate(base, -2).equals(rotated);
}
int _tmain(int argc, _TCHAR* argv[])
{
char* a = "quality";
char* b = "lityqua";
bool flag = true;
int count = 0;
char* t = a + 2;
char* t2 = b;
while (*t != '\0')
{
if (*t == *t2)
{
++t;
++t2;
}
else
{
flag = false;
break;
}
}
if (flag)
{
t = a;
while (*t2 != '\0')
{
if (*t2 == *t)
{
++t2;
++t;
}
else
{
flag = false;
}
}
}
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
_getch();
return 0;
}
public boolean rotate(String s1, String s2){
if(s1 == null || s2 == null || s1.length() != s2.length()) return false;
if(s1.length() <= 2) return s2.equals(s1);
return s2.equals(s1.substring(2) + s1.substring(0,2))
|| s2.equals(s1.substring(s1.length() - 2) + s1.substring(0, s1.length() - 2));
}
def isSwappable?(str1, str2)
return false if str1 == nil || str2 == nil || str1.length != str2.length
extra_in_string1 = []
extra_in_string2 = []
(1..str1.length).each do |i|
if str1[i] != str2[i]
extra_in_string1 << str1[i]
extra_in_string2 << str2[i]
end
end
extra_in_string1.length == 2 && extra_in_string1.sort == extra_in_string2.sort
end
Test cases:
isSwappable?(nil, nil) # false
isSwappable?(nil, "a") # false
isSwappable?("a", nil) # false
isSwappable?("a", "asd") # false
isSwappable?("asx", "asd") # false
isSwappable?("abc", "acb") # false
isSwappable?("amazon", "azamon") # true
isSwappable?("amazox", "azamon") # false
First, the length of S1 and S2 should equal.
It is ez to solve by duplicate s1 or s2 like s2 = s2+s2:
e.g S1="amazon" S2="azonam"
Assuming we are duplicating S2:
S2="azonamazonam";
Then, we can scan S2, find whether S2 contains S1.
public static boolean isRotated(String s1, String s2) {
if (s1.length()!=s2.length())
return false;
int len = s1.length();
// double String "s2";
s2 = s2+s2;
for (int i=0;i<len;i++) {
if (s2.substring(i,i+len).equals(s1))
return true;
}
return false;
}
The time complexity should be O(n), space complexity O(1);
}
public class StringRotation
{
public static boolean isRotated(String s1, String s2,int rotationCount)
{
if(s1.length()!=s2.length())
{
return false;
}
String s=s1.substring(rotationCount)+s1.substring(0,rotationCount);
if(s.equals(s2))return true;
else
return false;
}
public static void main(String[] args)
{
System.out.println(isRotated("amazon","azonam",2));
}
}
public class StringRotation
{
public static boolean isRotated(String s1, String s2,int rotationCount)
{
if(s1.length()!=s2.length())
{
return false;
}
String s=s1.substring(rotationCount)+s1.substring(0,rotationCount);
if(s.equals(s2))return true;
else
return false;
}
public static void main(String[] args)
{
System.out.println(isRotated("amazon","azonam",2));
}
}
public class RoatingDemo {
public static void main(String[] args) {
TestRoatation("amazon","azonam");
TestRoatation("quality","lityqua");
}
public static void TestRoatation(String actualData, String rotationData)
{
String rotationlogicalData="";
int roation=2;
for(int i=roation;i<actualData.length();i++)
{
rotationlogicalData=rotationlogicalData+actualData.charAt(i);
}
for(int i=0;i<roation;i++)
{
rotationlogicalData=rotationlogicalData+actualData.charAt(i);
}
System.out.println(rotationlogicalData);
if(rotationlogicalData.equals(rotationData))
{
System.out.println("pass");
}
else
{
System.out.println("fail");
}
}
}
ublic class RoatingDemo {
public static void main(String[] args) {
TestRoatation("amazon","azonam");
TestRoatation("quality","lityqua");
}
public static void TestRoatation(String actualData, String rotationData)
{
String rotationlogicalData="";
int roation=2;
for(int i=roation;i<actualData.length();i++)
{
rotationlogicalData=rotationlogicalData+actualData.charAt(i);
}
for(int i=0;i<roation;i++)
{
rotationlogicalData=rotationlogicalData+actualData.charAt(i);
}
System.out.println(rotationlogicalData);
if(rotationlogicalData.equals(rotationData))
{
System.out.println("pass");
}
else
{
System.out.println("fail");
}
}
}
public static void main(String[] args) {
String s1 = "amazon", s2 = "azonam";
boolean matchFound = false;
for(int i=0; i<s2.length(); i++) {
for(int j=0; j<s2.length(); j++) {
if(i!=j) {
String strTemp = "" + s2.charAt(i) + s2.charAt(j) + collectRestOfWords(s2, i, j);
if(strTemp.equals(s1)) {
System.out.println("Word " + strTemp + " matched!");
matchFound = true;
break;
}
}
}
if(matchFound) {
return;
}
}
System.out.println("No match found");
}
public void test(int nRotations){
String s = "quality";
String s2 = "lityqua";
//defining 3 queues for the validations
Queue<Character> q1 = new LinkedList<Character>();
for(char c : s.toCharArray()) q1.add(c);
Queue<Character> q2 = new LinkedList<Character>();
for(char d : s2.toCharArray()) q2.add(d);
//result list
Queue<Character> q3 = new LinkedList<Character>();
for(int i=0; i<q1.size(); i++){
//condt 1 - check if they are not changed
if(q1.peek() == q2.peek()){
//poll the values
q1.poll();
q2.poll();
continue;
}
//condt2 - check if they are changed
q3.add(q1.poll());
}
//now validate the size of q3
if(q3.size() == nRotations){
System.out.println("The rotations matches with the char changes");
}
else System.out.println("The rotations doesn't match "+q3.size());
}
if(s2==( s.substr(2)+s.substr(0,2)))
- Anonymous July 26, 2014return true;
else
return false;