## Google Interview Question for Software Engineers

• 2

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

If B matches repeated A that means B can be written as <S><A...><P> where <S> is any suffix of A including empty suffix, <A...> is A repeated some number of times including zero times and <P> is any prefix of A including empty prefix. Let len(A) = N, len(B) = M then ans is 1 (if non-empty S exists) + number of times A is repeated + 1 (if non-empty P exists):

<S> and <P> can be checked to exist in O(N*N) while individual <A> can be checked in N time and there might be at max ceil(M/N) times <A> in B.

If this pattern is not matched, return -1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String[] args) {

String A = "abcd";
String B = "cdabcdabcdabcdab";
String temp = "";

int len = B.length() / A.length();

for(int i=0; i<len; i++) {
temp = temp + A;
}

while(len<=(B.length() / A.length() + 1)) {
if(temp.contains(B)) {
System.out.println(len);
break;
}else {
len++;
temp = temp+A;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````count=0
while True:
count+=1
if B in A*count:
print(count)
break

if count>1000:
print(-1)
break``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

int getCount(String A, String B) {
int startIndex = B.indexOf(A);

int count = B.length() / A.length();
if (startIndex > 0) {
count++;
}
return count;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int getCount(String A, String B) {
int startIndex = B.indexOf(A);

int count = B.length() / A.length();
if (startIndex > 0) {
count++;
}
return count;
}``````

Comment hidden because of low score. Click to expand.
0

This one never returns -1 when not possible. Also, the calculation based on lengths sometimes returns one number higher than it should.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int getCount(String A, String B) {
int startIndex = B.indexOf(A);

int count = B.length() / A.length();
if (startIndex > 0) {
count++;
}
return count;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Runtime O(m+n), Space O(1)

``````public static int NumOfRepeatsToGetSubstring(string i_A, string i_B)
{
int count = 1;
int a = 0, b = 0;

while (b < i_B.Length)
{
if (i_A[a] == i_B[b])
{
++b;
}
else if (count > 1)
{
count = -1;
break;
}

++a;
if (a == i_A.Length)
{
a = 0;
++count;
}
}

return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````The test string never needs to be longer than A + B + A.

function getRepetitions(A, B) {
var test = "", repetitions = 0, max;
if (A.length < B.length)
max = B.length + (A.length * 2);
else
max = A.length * 2;
while (test.length <= max) {
test += A;
repetitions++;
if (test.indexOf(B) != -1) { // I'm not sure if including test.length >= B.length would improve performance here
return repetitions;
}
}
return -1;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note:
The length of A and B will be between 1 and 10000.
*/

console.log(isRepeat('abcd','bcdabcdab'));

function isRepeat(seed, target){
let tmp = seed;
let count = 1;
for (; tmp.length < target.length; count++) {
tmp+= seed
}
if (tmp.indexOf(target) !==-1) {
return count;
}
return -1;
}

/*
Complixity is o(n).
you can always use KMP algorithem to implement indexOf which has o(n)

*/``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity: O(n) where n is the length of aString

``````def repeatingStringCheck(aString, bString):
try:
n = aString.index(bString)
except ValueError:
return False
while len(aString) < len(bString) + n:
aString += aString
return bString in aString``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think we can use KMP algorithm to solve it, and it takes linear time to solve it.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static void main(String[] args) {

String A = "abcd";
String B = "cdabcdab";
String temp = "";

int len = B.length() / A.length();

for(int i=0; i<len; i++) {
temp = temp + A;
}

while(true) {
if(temp.contains(B)) {
System.out.println(len);
break;
}else {
len++;
temp = temp+A;
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static void main(String[] args) {

String A = "abcd";
String B = "cdabcdab";
String temp = "";

int len = B.length() / A.length();

for(int i=0; i<len; i++) {
temp = temp + A;
}

while(true) {
if(temp.contains(B)) {
System.out.println(len);
break;
}else {
len++;
temp = temp+A;
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.