Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

KMP prefix table algorithm can help

- koustav.adorable March 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

private static String getPeriod(String string) { // O(n * n)
        //for every possible period size i, check if it's valid
        for (int i = 1; i <= string.length() / 2; i++) {
            if (string.length() % i == 0) {
                String period = string.substring(0, i);
                int j = i;
                while(j + i <= string.length()) {
                    if (period.equals(string.substring(j, j + i))) {
                        j = j + i;
                        if(j == string.length()) { //period valid through entire string
                            return period;
                        }
                    } else {
                        break;
                    }
                }
            }

        }
        return null; //string is not periodic
    }

- aonecoding4 March 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 votes

This method will return null every time.

- just a beginner March 09, 2019 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

yep this code doesn't work

- cornolio March 11, 2019 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

yep this code is wrong

- frankTheTANK March 11, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N^3) solution

Boolean isPeriodic(String str) {
	if (isSameCharacters(str)) {
		return true;
	}
	
	int maxLength =. str.length() / 2 
	while (maxLength >= 1) {
		if (isMatch(maxLength, str.length() - maxLength, str.length(),str)) {
			boolean middleSegment = isMatch(maxLength, maxLength, str.length() - maxLength,str)
			if (middleSegment) {
				return true;
			}
		}
		maxLength -= 1;
	}
	return false;
}


Boolean isMatch( int patternEnd, int start, int end, String str) {
	if (start > end) {
		return true;
	}
	int lenRegion = end - start;
	if (patternEnd % lenRegion != 0) {
		return false;
	}

	for (int i = start; i+ patternEnd < end; i += patternEnd) {
		for (int j = 0; j < patternEnd; j++) {
			if (str.charAt(j) != str.charAt(I + j)) {
				return false;

			}
		}
	}
}

- divm01986 March 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String findRepPattern(String str) {
        int len = str.length();
        for(int i = 1; i <= len/2; ++i) {
            if (len % i == 0) {
                String prefix = str.substring(0, i);
                int start = i;
                boolean found = true;

                while (start < len && found) {
                    String lastPrefix = str.substring(start, start + i);
                    if (lastPrefix.equals(prefix)) {
                        start += i;
                    } else {
                        found = false;
                    }
                }

                if (start == len) {
                    System.out.println("pattern: " + prefix + " N = " + (len / prefix.length()));
                    return prefix;
                }
            }
        }
        return null;
    }

- guilhebl March 02, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

string GetPeriodicString(string s)
{
	int length = s.length();
	int* lps = new int[length];
	lps[0] = 0;
	for(int i=1; i<length; i++)
	{
		int len = lps[i-1];
		while(len > 0)
		{
			if(s[i] == s[len])
			{
				lps[i] = len + 1;
				break;
			}
			else
			{
				len = lps[len-1];
			}
		}
		if(len == 0)
		{
			if(s[i] == s[0])
			{
				lps[i] = 1;
			}
			else
			{
				lps[i] = 0;
			}
		}
	}
	int x = length - lps[length-1];
	for(int i=length-x-1; i>=x; i-=x)
	{
		if(i+1-lps[i] != x)
		{
			return s;
		}
	}
	return s.substr(0, x);
}
int main() {
	string s;
	cin>>s;
	cout<<GetPeriodicString(s);
}

- Nishagrawa March 02, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

s = input()
l = len(s)
st = ""
b = 0
for i in range (l):
st+=s[i]
b1 = 1
for j in range(i+1, l, i+1):
if(s[j: j+i+1]!=st):
b1=0
break
if(b1==1):
b=1
break
if(b==1):
print(st)

- snocoder March 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

s = input()
l = len(s)
st = ""
b = 0
for i in range (l):
    st+=s[i]
    b1 = 1
    for j in range(i+1, l, i+1):
        if(s[j: j+i+1]!=st):
            b1=0
            break
    if(b1==1):
        b=1
        break
if(b==1):
    print(st)

- snocoder March 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

s=str(input())
n=len(s)
for i in range(1,n+1):
    if n%i==0:
        x=s[:i]
        if x*(n//i) == s:
            print(x, n//i)
            break

- albdiystuff March 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the for loop just need to go from 1 to n and not n+1

- Sandhya March 04, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static boolean isPeriodic(String S) {
        int n = S.length();
        for(int i=1 ; i < n ; ++i ) {
            String p = S.substring(0, i);
            String[] parts = S.split(p);
            if( parts.length == 0 ) {
                System.out.println(p);
                return true;
            }
        }
        return false;
    }

- DevilDeepu March 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class GNPString {

public static boolean verify(int n, String pattern, String input)
{
int m = 0;
for(int i = 0; i < input.length(); i += pattern.length())
{
if(input.substring(i, i + pattern.length()).compareTo(pattern) == 0)
{
++m;
}
else
{
return false;
}
}


return m == (input.length()/n);
}

public static int GetN(char[] input)
{
int j = input.length-1;
int k = input.length-1;
char[] pattern = new char[input.length];
int len = 0;

String in = new String(input);

while(j > 0)
{
++len;

if(verify(len, new String(input, j, len), in))
{
return (input.length/len);
}

--j;
}

return 0;
}

public static void main(String[] args)
{
System.out.println(GetN(new String("abababab").toCharArray()));

System.out.println(GetN(new String("aabaab").toCharArray()));

System.out.println(GetN(new String("aaaa").toCharArray()));

System.out.println(GetN(new String("aabaaaba").toCharArray()));

System.out.println(GetN(new String("axbayb").toCharArray()));
}

}

- Anonymous March 06, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class GNPString {

	public static boolean verify(int n, String pattern, String input)
	{
		int m = 0;
		for(int i = 0; i < input.length(); i += pattern.length())
		{
			if(input.substring(i, i + pattern.length()).compareTo(pattern) == 0)
			{
				++m;
			}
			else
			{
				return false;
			}
		}
		
		
		return m == (input.length()/n);
	}
	
    public static int GetN(char[] input)
    {
    	int j = input.length-1;
    	int k = input.length-1;
    	char[] pattern = new char[input.length];
    	int len = 0;
    	
    	String in = new String(input);
    	
    	while(j > 0)
    	{
    		++len;
    		
    		if(verify(len, new String(input, j, len), in))
    		{
    				return (input.length/len);
    		}
   		
    		--j;
    	}
    	
    	return 0;
    }
    
    public static void main(String[] args)
    {
    	System.out.println(GetN(new String("abababab").toCharArray()));
    	
    	System.out.println(GetN(new String("aabaab").toCharArray()));
    	
    	System.out.println(GetN(new String("aaaa").toCharArray()));
    	
    	System.out.println(GetN(new String("aabaaaba").toCharArray()));
    	
    	System.out.println(GetN(new String("axbayb").toCharArray()));
    }

}

- guru March 06, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def string_period(msg):
    for k in range(1, len(msg)):
        if msg == (msg[k:] + msg[:k]):
            break
    return msg[:k]

- autoboli March 06, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean repeatedSubstringPattern(String s) {
		int prefixTable[] = new int[s.length()];
		int i = 0;
		int j = 1;
		while (j < s.length()) {
			if (s.charAt(i) == s.charAt(j))
				prefixTable[j++] = ++i;
			else if (i > 0)
				i = prefixTable[i - 1];
			else
				j++;
		}
		return prefixTable[s.length() - 1] > 0 && s.length() % (s.length() - prefixTable[s.length() - 1]) == 0;
	}

- koustav.adorable March 06, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function findPeriod(s) {
  for (var i = 1; i <= s.length / 2; ++i) {
    if (s.length % i === 0) {
      const n = s.length / i;
      const c = s.substring(0, i);
      if (c.repeat(n) === s) return [n, c];
    }
  }

  return null;
}

- Aleksey March 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * A class for checking periodicity of a string.
 */
public class PeriodicString {
    /**
     * Recursively check for periodic.
     * @param rest Rest of the string to be checked.
     * @param current The substring for which we are checking periodicity.
     * @param ocr Number of occurrence.
     * @return true when periodic or check for the rest string.
     */
    private static boolean isPeriodicStringWith(String rest, String current, int ocr) {
        if (ocr > 1 && rest.isEmpty()) {
            return true;
        }
        if (!rest.startsWith(current)) {
            return false;
        }
        return isPeriodicStringWith(rest.substring(current.length()), current, ocr + 1);
    }

    /**
     * Checking if a string is periodic.
     * @param input The input string.
     * @return true when the whole string is periodic.
     */
    public static boolean isPeriodic(String input) {
        if (input != null) {
            for (int i = 1; i <= input.length() / 2; i++) {
                if (isPeriodicStringWith(input.substring(i), input.substring(0, i), 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Run sample test cases.
     * @param args command line arguments. Not required.
     */
    public static void main(String[] args) {
        System.out.println(isPeriodic("xxxxx"));
        System.out.println(isPeriodic("ababababab"));
        System.out.println(isPeriodic("ababaababa"));
        System.out.println(isPeriodic("ababaabab"));
        System.out.println(isPeriodic("a"));
        System.out.println(isPeriodic(""));
        System.out.println(isPeriodic(null));
    }
}

- m3ghd007 March 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def checkPattern(selection, mainstring):
    lengthOfPattern=len(selection)
    n = 0
    for i in range(len(mainstring)):
        if mainstring[i] == selection[i%len(selection)]:
            lengthOfPattern-=1
        else:
            return -1
        if lengthOfPattern == 0:
            lengthOfPattern=len(selection)
            n+=1
    if lengthOfPattern != len(selection) or n == 0:
        return -1
    return n

def findPattern(mainstring):
    selection=''
    for i in range(len(mainstring)):
        selection+=mainstring[i]
        n = checkPattern(selection,mainstring[i+1:])
        if n != -1:
            break
    if n == -1:
        print 'No pattern'
    else:
        print 'n =',n,'Pattern=',selection
    return

findPattern('xdxdxdxd')

- Anonymous March 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def checkPattern(selection, mainstring):
    lengthOfPattern=len(selection)
    n = 0
    for i in range(len(mainstring)):
        if mainstring[i] == selection[i%len(selection)]:
            lengthOfPattern-=1
        else:
            return -1
        if lengthOfPattern == 0:
            lengthOfPattern=len(selection)
            n+=1
    if lengthOfPattern != len(selection) or n == 0:
        return -1
    return n

def findPattern(mainstring):
    selection=''
    for i in range(len(mainstring)):
        selection+=mainstring[i]
        n = checkPattern(selection,mainstring[i+1:])
        if n != -1:
            break
    if n == -1:
        print 'No pattern'
    else:
        print 'n =',n,'Pattern=',selection
    return

findPattern('xdxdxdxd')

- helloWorld March 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def checkPattern(selection, mainstring):
lengthOfPattern=len(selection)
n = 0
for i in range(len(mainstring)):
if mainstring[i] == selection[i%len(selection)]:
lengthOfPattern-=1
else:
return -1
if lengthOfPattern == 0:
lengthOfPattern=len(selection)
n+=1
if lengthOfPattern != len(selection) or n == 0:
return -1
return n

def findPattern(mainstring):
selection=''
for i in range(len(mainstring)):
selection+=mainstring[i]
n = checkPattern(selection,mainstring[i+1:])
if n != -1:
break
if n == -1:
print 'No pattern'
else:
print 'n =',n+1,'Pattern=',selection
return

if __name__ == "__main__":
test_cases = [
'aaaaaaa',
'bbb',
'asdasdasdsadsadsadsad',
'ab'*50,
'asd'*20
]

for each in test_cases:
findPattern(each)

- Anonymous March 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def checkPattern(selection, mainstring):
    lengthOfPattern=len(selection)
    n = 0
    for i in range(len(mainstring)):
        if mainstring[i] == selection[i%len(selection)]:
            lengthOfPattern-=1
        else:
            return -1
        if lengthOfPattern == 0:
            lengthOfPattern=len(selection)
            n+=1
    if lengthOfPattern != len(selection) or n == 0:
        return -1
    return n

def findPattern(mainstring):
    selection=''
    for i in range(len(mainstring)):
        selection+=mainstring[i]
        n = checkPattern(selection,mainstring[i+1:])
        if n != -1:
            break
    if n == -1:
        print 'No pattern'
    else:
        print 'n =',n+1,'Pattern=',selection
    return

if __name__ == "__main__":
    test_cases = [
        'aaaaaaa',
        'bbb',
        'asdasdasdsadsadsadsad',
        'ab'*50,
        'asd'*20
    ]

    for each in test_cases:
        findPattern(each)

- helloNano March 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is how I'd do it, inspiration leetcode 459

private static String FindPattern(String input) throws NoSuchObjectException {
    int repeatPos=(input+input).indexOf(input,1);
    if (repeatPos==-1) 
        throw new NoSuchObjectException("Pattern not found!!!");
    else 
        return input.substring(0,repeatPos);
}

- PeyarTheriyaa March 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def isPeriodic(input):
	if not input or input is None:
		return None

	return helper(0, input)

def helper(idx, substring):
	char = substring[:idx]
	if len(substring.replace(char, '')) == 0:
		return (char, substring.count(char))

	return helper(idx + 1, substring)

- frankTheTANK March 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var input = "abababab";

var isPeriodic = false;

var midPoint = Math.ceil(input.length / 2);

// We split the string in half... the max length of a pattern cannot be more
// than half the length of the string
var left = input.substring(0, midPoint);

for (var i = left.length; i > 0; i--) {
  var newPattern = left.substring(0, i);
  // Want to check if repeating newPattern results in the input string
  var j = 1;
  do {
    var someString = newPattern.repeat(j);
    if (someString === input) {
      isPeriodic = true;
      console.log("String is periodic: n = " + j + ", P = " + newPattern);
      break;
    } else j++;
  } while (someString.length <= input.length);
}

if (!isPeriodic) {
  console.log("Not a periodic string.")

}

- Kalyan Chatterjee March 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var input = "abababab";

var isPeriodic = false;

var midPoint = Math.ceil(input.length / 2);

// We split the string in half... the max length of a pattern cannot be more
// than half the length of the string
var left = input.substring(0, midPoint);

for (var i = left.length; i > 0; i--) {
  var newPattern = left.substring(0, i);
  // Want to check if repeating newPattern results in the input string
  var j = 1;
  do {
    var someString = newPattern.repeat(j);
    if (someString === input) {
      isPeriodic = true;
      console.log("String is periodic: n = " + j + ", P = " + newPattern);
      break;
    } else j++;
  } while (someString.length <= input.length);
}

if (!isPeriodic) {
  console.log("Not a periodic string.")
}

- Kalyan Chatterjee March 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var input = "abababab";

var isPeriodic = false;

var midPoint = Math.ceil(input.length / 2);

// We split the string in half... the max length of a pattern cannot be more
// than half the length of the string
var left = input.substring(0, midPoint);

for (var i = left.length; i > 0; i--) {
var newPattern = left.substring(0, i);
// Want to check if repeating newPattern results in the input string
var j = 1;
do {
var someString = newPattern.repeat(j);
if (someString === input) {
isPeriodic = true;
console.log("String is periodic: n = " + j + ", P = " + newPattern);
break;
} else j++;
} while (someString.length <= input.length);
}

if (!isPeriodic) {
console.log("Not a periodic string.")
}

- Kalyan Chatterjee March 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
- aonecoding4 March 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{public String findSubstring(String str)
{
if(str==null || str.length()==1)
return null;
//aaabcaaabc
int p1=0;
int p2=1;
while(p2<=str.length()/2){

while(str.charAt(p2)!=str.charAt(p1))
{
if(p2 >str.length()/2)
return null;
p2++;
if(p2>str.length()/2)return null;
}
boolean check = findSubstringHelper(str.substring(p1, p2),str.substring(p2));
if(check) return str.substring(p1, p2);
p2++;
}

return null;
}

public boolean findSubstringHelper(String substr,String str)
{
int start=0;
int end=substr.length();
while( end<=str.length())
{
if(!str.substring(start, end).equalsIgnoreCase(substr)) return false;
start=end;
end=start+substr.length();

}
if(start<str.length() && end>str.length()) return false;
return true;
}}}

- Nimmi March 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String findSubstring(String str)
	{
		if(str==null || str.length()==1)
			return null;
		//aaabcaaabc
		int p1=0;
		int p2=1;
		while(p2<=str.length()/2){

			while(str.charAt(p2)!=str.charAt(p1))
			{
				if(p2 >str.length()/2)
					return null;
				p2++;			
				if(p2>str.length()/2)return null;
			}
			boolean check = findSubstringHelper(str.substring(p1, p2),str.substring(p2));
			if(check) return str.substring(p1, p2);
			p2++;
		}
			
		return null;
	}
	
	public boolean findSubstringHelper(String substr,String str)
	{
		int start=0;
		int end=substr.length();
		while( end<=str.length())
		{
			if(!str.substring(start, end).equalsIgnoreCase(substr)) return false;
			start=end;
			end=start+substr.length();
			
		}
		if(start<str.length() && end>str.length()) return false;
		return true;
	}

- Nimmi March 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def nPattern(String):
if(len(String)==0):
return "",0
pattern = ""
patternCounter = 1
patternCheckStart = 0
patternEndCheck = 0
for i in range(0,len(String)):
if(patternCheckStart==len(String)):
break
if(pattern == ""):
pattern = String[i]
if(len(String)%len(pattern)==0):
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

while(patternCheckStart < len(String)):
if(pattern==String[patternCheckStart:patternEndCheck]):
patternCheckStart = patternEndCheck
patternEndCheck = patternCheckStart+len(pattern)
patternCounter = patternCounter+1
else:
pattern = String[0:patternCheckStart+1]
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

return pattern,patternCounter

- Ptatik Agrawal March 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def nPattern(String):
pattern = ""
patternCounter = 1
patternCheckStart = 0
patternEndCheck = 0
for i in range(0,len(String)):
if(patternCheckStart==len(String)):
break
if(pattern == ""):
pattern = String[i]
if(len(String)%len(pattern)==0):
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

while(patternCheckStart < len(String)):
if(pattern==String[patternCheckStart:patternEndCheck]):
patternCheckStart = patternEndCheck
patternEndCheck = patternCheckStart+len(pattern)
patternCounter = patternCounter+1
else:
pattern = String[0:patternCheckStart+1]
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

return pattern,patternCounter

print(nPattern("bdsxmgh"))

- Anonymous March 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def nPattern(String):
pattern = ""
patternCounter = 1
patternCheckStart = 0
patternEndCheck = 0
for i in range(0,len(String)):
if(patternCheckStart==len(String)):
break
if(pattern == ""):
pattern = String[i]
if(len(String)%len(pattern)==0):
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

while(patternCheckStart < len(String)):
if(pattern==String[patternCheckStart:patternEndCheck]):
patternCheckStart = patternEndCheck
patternEndCheck = patternCheckStart+len(pattern)
patternCounter = patternCounter+1
else:
pattern = String[0:patternCheckStart+1]
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

return pattern,patternCounter

- Pratik Agrawal March 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
def nPattern(String):
pattern = ""
patternCounter = 1
patternCheckStart = 0
patternEndCheck = 0
for i in range(0,len(String)):
if(patternCheckStart==len(String)):
break
if(pattern == ""):
pattern = String[i]
if(len(String)%len(pattern)==0):
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

while(patternCheckStart < len(String)):
if(pattern==String[patternCheckStart:patternEndCheck]):
patternCheckStart = patternEndCheck
patternEndCheck = patternCheckStart+len(pattern)
patternCounter = patternCounter+1
else:
pattern = String[0:patternCheckStart+1]
patternCheckStart = len(pattern)
patternEndCheck = patternCheckStart+len(pattern)

return pattern,patternCounter
}

- Pratik Agrawal March 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.company;

import java.lang.Math;

public class Main {

    //this can be done in O(n^(3/2)) complexity.
    static String isPeriodic(String S){

        int len_of_s = S.length();
        int len_of_p = len_of_s + 1;
        int sq_len = (int)Math.sqrt(len_of_s);
        // this loop is run √ length(s) time and in each iteration isPossible is called whose complexity is O(length(S))
        // hence overall complexity is length(S)^(3/2)
        for(int i = 1; i < sq_len; i++){
            if(len_of_s%i == 0){
                int x = i;
                int y = len_of_s/i;
                if(isPossible(S,x)){
                    len_of_p = Math.min(len_of_p,x);
                }
                else if(isPossible(S,y)){
                    len_of_p = Math.min(len_of_p,y);
                }
            }
        }
        String res = "Not periodic";
        if(len_of_p != len_of_s+1){
            res = S.substring(0,len_of_p);
        }
        return res;
    }
    static boolean isPossible(String S, int len_of_expected_p){
        String p = S.substring(0,len_of_expected_p);
        for(int i = 0; i < S.length(); i += len_of_expected_p){
            if(!p.equals(S.substring(i,i+len_of_expected_p))){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        /*
        * Find whether string S is periodic.
            Periodic indicates S = nP.
            e.g.
            S = "ababab", then n = 3, and P = "ab"
            S = "xxxxxx", then n = 1, and P = "x"
            S = "aabbaaabba", then n = 2, and P = "aabba"
            Given string S, find out the P (repetitive pattern) of S.
        * */
        System.out.println(isPeriodic("aabbaaabba"));
    }
}

- Avneesh March 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def is_periodic(input_string, is_return_first=True):
    input_length = len(input_string)  
    result = (False, 0, '')  
    pattern_length = 1  
    while pattern_length <= int(input_length / 2):  
        if input_length % pattern_length == 0:  
            is_pattern_equal = True
            pattern_string = input_string[:pattern_length]
            pattern_multiplier = int(input_length / pattern_length)
            j = 0
            while (j < pattern_length) and is_pattern_equal:
                for k in range(1, pattern_multiplier):
                    if input_string[j] != input_string[k * pattern_length + j]:
                        is_pattern_equal = False
                        break
                j += 1
            if is_pattern_equal:
                result = (True, pattern_multiplier, pattern_string)
                if is_return_first:
                    return result
        pattern_length += 1
    return result

print(is_periodic('abababababababababababab'))
print(is_periodic('xxxxxx', False))
print(is_periodic('aabbaaabba'))

- MKisunko March 16, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int i,j,k=0;
string s,d,c;
cin>>s;
int count[s.length()];
for (i=0; i<s.length(); i++)
{
count[i]=1;
k++;
d=s.substr(0,i+1);
for (j=i+1; j<s.length(); j+=k)
{
c=s.substr(j,k);
if (d==c)
{
count[i]++;
continue;
}
break;
}
}
//cout<<count<<endl;
sort(count,count+s.length());
for (i=s.length()-1; i>=0; i--)
{
if (count[i]>1 && s.length()%count[i]==0)
{
cout<<"periodic"<<" "<<(s.length()/count[i]) <<endl;
return 0;
}
else if (count[i]==1)
{
cout << "not periodic" << endl;
return 0;
}
}
return 0;
}

- bsse1118@iit.du.ac.bd March 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    int i,j,k=0;
    string s,d,c;
    cin>>s;
    int count[s.length()];
    for (i=0; i<s.length(); i++)
    {
        count[i]=1;
        k++;
        d=s.substr(0,i+1);
        for (j=i+1; j<s.length(); j+=k)
        {
            c=s.substr(j,k);
            if (d==c)
            {
                count[i]++;
                continue;
            }
            break;
        }
    }
    //cout<<count<<endl;
    sort(count,count+s.length());
    for (i=s.length()-1; i>=0; i--)
    {
        if (count[i]>1 && s.length()%count[i]==0)
        {
            cout<<"periodic"<<"    "<<(s.length()/count[i]) <<endl;
            return 0;
        }
        else if (count[i]==1)
        {
            cout << "not periodic" << endl;
            return 0;
        }
    }
    return 0;
}

- bsse1118@iit.du.ac.bd March 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the most important thing is to get the set of lengths.
The available length is a prime of string length and all length are combination of the primes.
If you find a prime up to square root of the string length, you can find another prime.
Then, the time complexity to get the set of lengths is O(square root of N), N is the string length.
The maximum number of the set of length is 2 X square root of N.

Therefore, the total time complexity is O(square root of N)

bool isPeriodic(const string& str, int len)
{
	for (int i = len, last = str.size() - len -1; i < last; i += len)
	{
		for (int k = 0; k < len; k++) {
			if (str[k] != str[i + k])
				return false;
		}
	}
	return true;
}

string findPeriodic(const string& str)
{
	int size = str.size();
	list<int> lengths = { 1 };
	for (int len = 2, max_len = sqrt(size); len <= max_len; len++)
	{
		if (size % len == 0) {
			lengths.push_back(len);
			lengths.push_back(size/len);
		}
	}

	for (int len : lengths)
	{
		if (isPeriodic(str, len))
			return str.substr(0, len);
	}
	return str;
}

int main()
{
	string s[] = { "ababab", "xxxxxx", "aabbaaabba" };
	for (int i = 0; i < _countof(s); i++)
		cout << findPeriodic(s[i]) << endl;

	return 0;
}

- lesit.jae March 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;


string find(string str)
{
int i=0,j=1,l=1;
int len=str.length();
for(int k=1;k<len;k++)
{
if(str.at(k)==str.at(i))
{
i++;
}
else
{
k=l;
l++;
i=0;
// cout<<l<<endl;

}
if(l==i)
{
i=0;
}

}
if(len%l!=0) l=len;
return str.substr(0,l);
}

int main()
{
string str="abaababa";
cout<<find(str);

return 0;
}

- Anonymous March 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;


string find(string str)
{
int i=0,j=1,l=1;
int len=str.length();
for(int k=1;k<len;k++)
{
if(str.at(k)==str.at(i))
{
i++;
}
else
{
k=l;
l++;
i=0;
// cout<<l<<endl;

}
if(l==i)
{
i=0;
}

}
if(len%l!=0) l=len;
return str.substr(0,l);
}

int main()
{
string str="abaababa";
cout<<find(str);

return 0;
}

- Tanim March 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;


string find(string str)
{
int i=0,j=1,l=1;
int len=str.length();
for(int k=1;k<len;k++)
{
if(str.at(k)==str.at(i))
{
i++;
}
else
{
k=l;
l++;
i=0;
// cout<<l<<endl;

}
if(l==i)
{
i=0;
}

}
if(len%l!=0) l=len;
return str.substr(0,l);
}

int main()
{
string str="abaababa";
cout<<find(str);

return 0;
}

- tanim1505039 March 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
public:
    int solve(string s) {

        string tmps = s + s;

        int n = 0;
        int i = 0;
        string pattern;
        while (i < s.length()) {
            int d = tmps.find(s, i+1);
            if (d < s.length() && pattern.empty())
                pattern = tmps.substr(i, d-i);
            i = d;
            n++;
        }
        cout<<"pattern=["<<pattern<<"]["<<n<<"]"<<endl;
        return pattern;
    }
};

int main(int argc, char* argv[]) {
    Solution s;

    s.solve("ababab");

    cout<<"-------------------------"<<endl;
    s.solve("xxxxxx");
    cout<<"-------------------------"<<endl;
    s.solve("aabbaaabba");
}

- Anonymous March 19, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
public:
    int solve(string s) {

        string tmps = s + s;

        int n = 0;
        int i = 0;
        string pattern;
        while (i < s.length()) {
            int d = tmps.find(s, i+1);
            if (d < s.length() && pattern.empty())
                pattern = tmps.substr(i, d-i);
            i = d;
            n++;
        }
        cout<<"pattern=["<<pattern<<"]["<<n<<"]"<<endl;
        return pattern;
    }
};

int main(int argc, char* argv[]) {
    Solution s;

    s.solve("ababab");

    cout<<"-------------------------"<<endl;
    s.solve("xxxxxx");
    cout<<"-------------------------"<<endl;
    s.solve("aabbaaabba");
}

- Willy March 19, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 5 vote

LeetCode 459. Repeated Substring Pattern

- Sithis March 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/// The question is wrong, should return 6x in the example xxxxxx
       static String getPeriodic(String input) {
		int length = input.length();
		String subString = "";
		String expanded = "";
		for(int i =0;  i<length/2; i++)
		{
			expanded = "";
			subString = "";
			if(length%(i+1)==0)
			{
			  subString = input.substring(0,i+1); 
			  for (int j=0; j< length/(i+1); j++) {
				  expanded = expanded + subString ;
			  }
			 if (input.equals(expanded))
			 {
				 return (length/subString.length()+subString);
			 }
			}
		}
		return "";

}

- Feng Zhang March 02, 2019 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More