Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,230 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Google:
Dec 5, 2011
1 of
1 people found this helpful
Write a program to compute if one string is a rotation of another.
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (6)
1 of 1 people found this helpful
Jan 17, 2012
Does not look correct to me. Consider "123" and "321".
Helpful Answer?
Yes |
No
Inappropriate?
Jan 20, 2012
yes, you are right, the code above is only for checking if it's a regular permutation.
here is the correct code, although it O(n^2) complexity, and I could nit think of a more efficient solution, any ideas?
public static void main(String[] args) {
String str1 = "1111111111111111111112";
String str2 = "1111111111111111111121";
char[] char1 = str1.toCharArray();
char[] char2 = str2.toCharArray();
int i=0;
int j=0;
for (int start = 0; start < char2.length; ++start){
while (true && i<char1.length){
if (char1[i] == char2[(start+j)%(char2.length)]){
++i;
++j;
}
else{
j=0;
i=0;
break;
}
}
}
if (i == char2.length){
System.out.println("shifted correct!");
}
else{
System.out.println("shifted not correct!");
}
}
here is the correct code, although it O(n^2) complexity, and I could nit think of a more efficient solution, any ideas?
public static void main(String[] args) {
String str1 = "1111111111111111111112";
String str2 = "1111111111111111111121";
char[] char1 = str1.toCharArray();
char[] char2 = str2.toCharArray();
int i=0;
int j=0;
for (int start = 0; start < char2.length; ++start){
while (true && i<char1.length){
if (char1[i] == char2[(start+j)%(char2.length)]){
++i;
++j;
}
else{
j=0;
i=0;
break;
}
}
}
if (i == char2.length){
System.out.println("shifted correct!");
}
else{
System.out.println("shifted not correct!");
}
}
Helpful Answer?
Yes |
No
Inappropriate?
7 of 8 people found this helpful
Feb 11, 2012
Simplest way is to concatenate the rotated array after itself and then see if the original array is a sub-string of that!
bool checkStrings (string s1, string s2){
s1+=s1;
if(s1.find(s2)<s1.length())
return true;
else return false;
}
bool checkStrings (string s1, string s2){
s1+=s1;
if(s1.find(s2)<s1.length())
return true;
else return false;
}
Helpful Answer?
Yes |
No
Inappropriate?
Apr 25, 2012
Answer by Yash is incorrect, the input:
11121, 111211
Is incorrect, but would return True. Correct answer is:
def check_strings(str1, str2):
return len(str1) == len(str2) and 0 <= (str1*2).find(str2) < len(str1)
11121, 111211
Is incorrect, but would return True. Correct answer is:
def check_strings(str1, str2):
return len(str1) == len(str2) and 0 <= (str1*2).find(str2) < len(str1)
Helpful Answer?
Yes |
No
Inappropriate?
May 2, 2012
public class TwoTimesACharm {
public static void main(String[] args)
{
String[] test1 = {"1234", "4123", "3412", "2341", "1212", "12345678"};
String original = "1234";
TwoTimesACharm aCharm = new TwoTimesACharm();
for(String s:test1)
{
System.out.println("It is " + aCharm.isRotation(original, s) + " that " + s + " is a rotation of " + original);
}
System.out.println("\n Second method test. the first method implementation doesnt show any skills");
for(String s:test1)
{
System.out.println("It is " + aCharm.isRotation2(original, s) + " that " + s + " is a rotation of " + original);
}
}
//so the reason that we repeat the original string twice is because the rotation would be in the string.
//for example string "1234" possible rotations are
//shift right 4123, 3412, 2341
//shift left 2341, 3412, 4123
// repeat original string "12341234" we will see those rotations are present in there.
private boolean isRotation(String originalString, String rotateString)
{
String repeatTwice = originalString+originalString;
return (repeatTwice.indexOf(rotateString) > -1 ? true:false);
}
private boolean isRotation2(String originalString, String rotateString)
{
//before going any further make sure they are the same length.
if(originalString.length() != rotateString.length())
return false;
//make sure that the inputs aren't the same.
if(originalString.equals(rotateString))
return true;
//I would use StringBuilder for efficiency but for simplicity I used a string
String repeatTwice = originalString+originalString;
int i = 0;
// we do the length of the string because the start of i in the repeatTwice string shouldn't be
//pass the end of the original string or else we will get array out of bounds.
while(i <= originalString.length())
{
//so basically we are iterating through the repeat string until we find a match.
if(rotateString.equals(repeatTwice.substring(i, i+originalString.length())))
return true;
else
i++;
}
return false;
}
}
public static void main(String[] args)
{
String[] test1 = {"1234", "4123", "3412", "2341", "1212", "12345678"};
String original = "1234";
TwoTimesACharm aCharm = new TwoTimesACharm();
for(String s:test1)
{
System.out.println("It is " + aCharm.isRotation(original, s) + " that " + s + " is a rotation of " + original);
}
System.out.println("\n Second method test. the first method implementation doesnt show any skills");
for(String s:test1)
{
System.out.println("It is " + aCharm.isRotation2(original, s) + " that " + s + " is a rotation of " + original);
}
}
//so the reason that we repeat the original string twice is because the rotation would be in the string.
//for example string "1234" possible rotations are
//shift right 4123, 3412, 2341
//shift left 2341, 3412, 4123
// repeat original string "12341234" we will see those rotations are present in there.
private boolean isRotation(String originalString, String rotateString)
{
String repeatTwice = originalString+originalString;
return (repeatTwice.indexOf(rotateString) > -1 ? true:false);
}
private boolean isRotation2(String originalString, String rotateString)
{
//before going any further make sure they are the same length.
if(originalString.length() != rotateString.length())
return false;
//make sure that the inputs aren't the same.
if(originalString.equals(rotateString))
return true;
//I would use StringBuilder for efficiency but for simplicity I used a string
String repeatTwice = originalString+originalString;
int i = 0;
// we do the length of the string because the start of i in the repeatTwice string shouldn't be
//pass the end of the original string or else we will get array out of bounds.
while(i <= originalString.length())
{
//so basically we are iterating through the repeat string until we find a match.
if(rotateString.equals(repeatTwice.substring(i, i+originalString.length())))
return true;
else
i++;
}
return false;
}
}
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
0 of 0 people found this helpful
by Liron:
String str2 = "1111111111111111111121";
if (str1.length() != str2.length()){
return false;
}
char[] char1 = str1.toCharArray();
List<Character> list1 = new ArrayList<Character>();
for (int i=0; i<char1.length; ++i){
list1.add(char1[i]);
}
char[] char2 = str2.toCharArray();
List<Character> list2 = new ArrayList<Character>();
for (int i=0; i<char2.length; ++i){
list2.add(char2[i]);
}
Collections.sort(list1);
Collections.sort(list2);
for (int i=0; i<list1.size(); ++i){
if (!list1.get(i).equals(list2.get(i))){
return false;
}
}
return true;
}
the complexity is O(nlogn)