Facebook Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

What am I missing about example number 2 in the question:

S = "xxxxxx", n = 1, then P = "x"

This doesn't seem consistent with the other examples.
In the first example, if n=3 and P=ab, then 3ab => ababab, that makes sense.
In the third example, if n = 2 and P=aabba, then 2aabba => aabbaaabba, that make sense.

But for exmple 2, if n=1 and P=x, then 1x should be x, not xxxxxx. I feel that in this case, if the P is x, then n should be 6, because 6x => xxxxxx

What am I missing? Am I fundamentally misunderstanding the problem here?

- Imposter June 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think it should be n=1, P='xxxxxx'

- joe February 28, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is incorrect. It could be one of the two options - n = 6 and P = "x", or if you are looking for the longest repeat then n=2 and P="xxx".

- Nick July 28, 2022 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

boolean isPeriod(String s) {
        StringBuilder str = new StringBuilder(s   s);
        str.deleteCharAt(0);
        str.deleteCharAt(str.length() - 1);
        return strStr(str.toString(), s); //KMP strStr(T, S) to find if T has S in it.
    }

    //Solution to follow-up
    //This method looks for the repeating pattern in string
    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
    }

Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

Taught by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greed and other advanced algo problems),
and mock interviews.

Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.

Welcome to email us with any questions. Thanks for reading.

- acoding167 June 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

def factors(n):
    f=[]
    for i in range(1,n):
        if n%i==0:
            f.append(i)
    return f
            
        
def periodic(s):
    
    f=factors(len(s))
    for i in f:
        m=len(s)/i
        #return s[:i]*3
        if s[:i]*int(m)==s:
            return True
    return False
    
print(periodic('abcabc'))                 
        def factors(n):
    f=[]
    for i in range(1,n):
        if n%i==0:
            f.append(i)
    return f
            
        
def periodic(s):
    
    f=factors(len(s))
    for i in f:
        m=len(s)/i
        #return s[:i]*3
        if s[:i]*int(m)==s:
            return True
    return False

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

def periodic (my_str = "aaaaabbbbb"):
    str_len = len(my_str)
    period_sizes = []
    reaps = []
    for i in range(1, int(str_len/2)+1):
        if str_len%i == 0:
            period_sizes.append(i)

    for period_size in period_sizes:
        reaps.append(my_str.count(my_str[:period_size]))

    for i in range (0,len(period_sizes)):
        if period_sizes[i] * reaps [i] == str_len:
            return True
    return (False)

- Leah Bor August 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def factors(n):
    f=[]
    for i in range(1,n):
        if n%i==0:
            f.append(i)
    return f
            
        
def periodic(s):
    
    f=factors(len(s))
    for i in f:
        m=len(s)/i
        #return s[:i]*3
        if s[:i]*int(m)==s:
            return True
    return False

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

a slightly improved version

#!/usr/bin/env python3
"""
  Find whether string S is periodic. Periodic indicates S = nP. e.g.
  if S = abcabc, then n = 3, and P = abc
  if S = xxxx, n = 1, and P = x
  follow up, given string S, find out repetitive pattern of P
"""
def factors(n):
    f = []
    for i in range(1, n):
        if n % i == 0:
            f.append(i)
    return f
def periodic(s):
    f = factors(len(s))
    for i in f:
        m = len(s)/i
        if s[:i] * int(m) == s:
            print(i, s[:i], s)
            return True
    return False
# driver
if __name__ == "__main__":
  assert True == periodic('abcabc')
  assert False == periodic('abcabcd')

- KB2 June 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pattern = []
string = "sarojasaroja"
if len(set(string)) ==1:
print(string[0])
else:
for outer in range(2,int(len(string)/2)+1):
listt = []
if len(string)%outer == 0:
for inner in range(outer):
for innermost in range(inner,int(len(string)/outer)):
if(string[innermost+inner] != string[innermost + outer]):
break
else :
listt.append(string[inner])
if len(listt) == int(len(string)/outer) :
pattern.append(string[inner])
if len(pattern) == outer :
break
print (pattern)

- saroja kumar pradhan(kumar.saroja5@gmail.com) June 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pattern = []
string = "sarojasaroja"
if len(set(string)) ==1:
    print(string[0])
else:
    for outer in range(2,int(len(string)/2)+1):
        listt = []
        if len(string)%outer == 0:
            for inner in range(outer):
                for innermost in range(inner,int(len(string)/outer)):
                    if(string[innermost+inner] != string[innermost + outer]):
                        break
                    else :
                        listt.append(string[inner])
                if len(listt) == int(len(string)/outer) :
                    pattern.append(string[inner])
            if len(pattern) == outer :
                break
    print (pattern)

- saroja kumar pradhan(kumar.saroja5@gmail.com) June 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pattern = []
string = "sarojasaroja"
if len(set(string)) ==1:
    print(string[0])
else:
    for outer in range(2,int(len(string)/2)+1):
        listt = []
        if len(string)%outer == 0:
            for inner in range(outer):
                for innermost in range(inner,int(len(string)/outer)):
                    if(string[innermost+inner] != string[innermost + outer]):
                        break
                    else :
                        listt.append(string[inner])
                if len(listt) == int(len(string)/outer) :
                    pattern.append(string[inner])
            if len(pattern) == outer :
                break
    print (pattern)

- saroja kumar pradhan(kumar.saroja5@gmail.com) June 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pattern = []
string = "sarojasaroja"
if len(set(string)) ==1:

print(string[0])

else:

for outer in range(2,int(len(string)/2)+1):
        listt = []
        if len(string)%outer == 0:
            for inner in range(outer):
                for innermost in range(inner,int(len(string)/outer)):
                    if(string[innermost+inner] != string[innermost + outer]):
                        break
                    else :
                        listt.append(string[inner])
                if len(listt) == int(len(string)/outer) :
                    pattern.append(string[inner])
            if len(pattern) == outer :
                break
    print (pattern)

- saroja kumar pradhan(kumar.saroja5@gmail.com) June 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{pattern = [] string = "sarojasaroja" if len(set(string)) ==1: {{{ print(string[0])}}} else: {{{for outer in range(2,int(len(string)/2)+1):}}} {{{ listt = []}}} {{{if len(string)%outer == 0:}}} {{{ for inner in range(outer):}}} {{{ for innermost in range(inner,int(len(string)/outer)):}}} {{{if(string[innermost+inner] != string[innermost + outer]):}}} {{{ break}}} {{{else :}}} {{{ listt.append(string[inner])}}} {{{if len(listt) == int(len(string)/outer) :}}} {{{pattern.append(string[inner])}}} {{{ if len(pattern) == outer :}}} {{{break}}} {{{print (pattern)}}} - saroja kumar pradhan(kumar.saroja5@gmail.com) June 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- test June 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- test June 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def isPeriodic(input, start, end=1):

    if end-start > len(input) - end:
        return False

    did_match = True
    for x in range(start, end):
        #print (" check " + str(x) + " " + str(start) + " " + str(end) + " => " + str(len(input)))
        if input[x] != input[end - start + x]:
            did_match = False
            break

    if did_match:
        delta = end - start
        start2 = end

        if end + delta == len(input):
            return True

        did_match = isPeriodic(input, end, end + delta)

    if not did_match:
        return isPeriodic(input, start, end+1)

    return did_match


if __name__ == "__main__":
    S = "ababab"
    print(S + " => " + str(isPeriodic(S, 0)))
    S = "xxxxxx"
    print(S + " => " + str(isPeriodic(S, 0)))
    S = "aabbaaabba"
    print(S + " => " + str(isPeriodic(S, 0)))
    S = "aabbaabbaabb"
    print(S + " => " + str(isPeriodic(S, 0)))
    S = "abcd"
    print(S + " => " + str(isPeriodic(S, 0)))
    S = "abbaabbaabba"
    print(S + " => " + str(isPeriodic(S,

- Recursive June 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static boolean isPeriodic(String s) {
		for(int i=s.length(); i>1; i--) {
			int length = s.length();
			String p = s.substring(0, length / i);
			if (isSubstring(s, p)) {
				System.out.println(p);
				return true;
			}
		}
		return false;
	}

	static boolean isSubstring(String s, String p) {
		for (int i=0; i<s.length(); i+=p.length()) {
			if (!s.substring(i, i+p.length()).equals(p)) return false;
		}
		return true;
	}

- Oleg June 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static boolean isPeriodic(String s) {
		for(int i=s.length(); i>1; i--) {
			int length = s.length();
			String p = s.substring(0, length / i);
			if (isSubstring(s, p)) {
				System.out.println(p);
				return true;
			}
		}
		return false;
	}

	static boolean isSubstring(String s, String p) {
		for (int i=0; i<s.length(); i+=p.length()) {
			if (!s.substring(i, i+p.length()).equals(p)) return false;
		}
		return true;
	}

- omikheev June 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Optional;

class Main {
  public static void main(String[] args) {
    System.out.print("String: " + args[0]);
    Optional<String> patOp = findPattern(args[0]);
    if (patOp.isPresent()) {
      System.out.println(" Pattern: " + patOp.get());
    } else {
      System.out.println(" No pattern found.");
    }
  }

  // The algorithm is to concatenate the string to itself, take the result without
  // the first and the last characters and look for the string inside this result.
  // If present - the string is periodic.
  // To find the pattern, take the index of the string in the result, cut the result
  // up until this index and add the first character of the original string in 
  // the beginning.
  // Example:   
  //   original: aabbaaabba                    
  //   result to look in:            [a]abbaaabbaaabbaaabb[a]
  //   found the original at index 4:   0123|--------|  
  //   prefix: abba, add back the first character -> aabba
  public static Optional<String> findPattern(String str) {
    String test = str + str;
    String sub = test.substring(1, test.length() - 1);
    int index = sub.indexOf(str);
    if (index < 0) {
      return Optional.empty();
    }
    return Optional.of(str.charAt(0) + sub.substring(0, index));
  }
}

- vladiu June 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function printIsPeriodAndCount(str) {

    for (let i = 1; i < str.length; i++) {

        let splitFactor = str.substr(0, i);

        let parts = str.split(splitFactor);

        if (splitFactor !== str && parts.length > 1 && !parts.find(s=>s !== '')) {
            console.log(true);
            console.log(parts.length - 1);
        }

    }

}

- yakir.rotem July 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const isPeriodic = (str) => {

    let currStr = str.charAt(0);
    let n = 1;
    let i = 1;

    while (i < str.length) {

        if (currStr.charAt(0) === str.charAt(i)) {
            if (currStr === str.substring(i, i + currStr.length)) {
                n++;
            } else {
                currStr += str.substring(i, i + currStr.length);
            }
            
            i += currStr.length - 1;
        } else {
            let newStr = "";
            while (n >= 1) {
                newStr += currStr;
                n--;
            }
            n = 1;
            newStr += str.charAt(i);
            currStr = newStr;
        }

        i++;

    }

    console.log(`n: ${n}, p: ${currStr}`);
};

- Jonathan Mor July 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const isPeriodic = (str) => {

    let currStr = str.charAt(0);
    let n = 1;
    let i = 1;

    while (i < str.length) {

        if (currStr.charAt(0) === str.charAt(i)) {
            if (currStr === str.substring(i, i + currStr.length)) {
                n++;
            } else {
                currStr += str.substring(i, i + currStr.length);
            }
            
            i += currStr.length - 1;
        } else {
            let newStr = "";
            while (n >= 1) {
                newStr += currStr;
                n--;
            }
            n = 1;
            newStr += str.charAt(i);
            currStr = newStr;
        }

        i++;

    }

    console.log(`n: ${n}, p: ${currStr}`);
};

- Jonathan Mor July 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class PeriodicStringTest {
    
    public static void main(String[] args) {
        findRepetitivePattern("aabbaaabba");
        findRepetitivePattern("xxxxxxxxxx");
        findRepetitivePattern("ababab");
        findRepetitivePattern("aa");
        findRepetitivePattern("aaabaa");
    }
    
    public static void findRepetitivePattern(String str) {
        if (str.length() <= 1) {
            System.out.println("String '" + str + "' is not periodic.");
            return;
        }
        String repititivePattern = null;
        boolean periodic = false;
        for (int i = 0; i < str.length() - 1; i++) {
            repititivePattern = str.substring(0, i+1);
            String splits[] = str.split(repititivePattern, -1);
            for (String split : splits) {
                if (split.equals("")) {
                    periodic = true;
                } else {
                    periodic = false;
                    break;
                }
            }
            if (periodic) {
                System.out.println("String '" + str + "' ===> P = " + repititivePattern + ", n = " + (splits.length-1));
                return;
            }
        }
        System.out.println("String '" + str + "' is not periodic.");
    }

}

Output:
String 'aabbaaabba' ===> P = aabba, n = 2
String 'xxxxxxxxxx' ===> P = x, n = 10
String 'ababab' ===> P = ab, n = 3
String 'aa' ===> P = a, n = 2
String 'aaabaa' is not periodic.

- Samrat July 08, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class PeriodicStringTest {
    
    public static void main(String[] args) {
        findRepetitivePattern("aabbaaabba");
        findRepetitivePattern("xxxxxxxxxx");
        findRepetitivePattern("ababab");
        findRepetitivePattern("aa");
        findRepetitivePattern("aaabaa");
    }
    
    public static void findRepetitivePattern(String str) {
        if (str.length() <= 1) {
            System.out.println("String '" + str + "' is not periodic.");
            return;
        }
        String repititivePattern = null;
        boolean periodic = false;
        for (int i = 0; i < str.length() - 1; i++) {
            repititivePattern = str.substring(0, i+1);
            String splits[] = str.split(repititivePattern, -1);
            for (String split : splits) {
                if (split.equals("")) {
                    periodic = true;
                } else {
                    periodic = false;
                    break;
                }
            }
            if (periodic) {
                System.out.println("String '" + str + "' ===> P = " + repititivePattern + ", n = " + (splits.length-1));
                return;
            }
        }
        System.out.println("String '" + str + "' is not periodic.");
    }

}

- samband14 July 08, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def period_string(string):
    k = len(string)
    for i in range (k, 0, -1):
        if not k%i:
            if string[:k//i] == string[k//i:2*k//i]:
                return (k//(k//i), string[:k//i])   
    return "non periodic string"

- Alexey Gorovoy July 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def period_string(string):
    k = len(string)
    for i in range (k, 0, -1):
        if not k%i:
            if string[:k//i] == string[k//i:2*k//i]:
                return (k//(k//i), string[:k//i])   
    return "non periodic string"

- Alexey Gorovoy July 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
 * T: O(n^2)
 * S: O(n)
 * */
public class PeriodicPattern{
    static boolean ans = false;
    public static void main(String[] args){
        String str = "aabbaaabba";
        for(int i=0; i<str.length()/2+1; i++){
            String s = str.substring(0, i+1);
            dfs(str, s.length(), s);
        }
        System.out.println(ans);
    }

    public static void dfs(String str, int start, String p){
        if(start == str.length()){
            ans = true;
            System.out.println(p);
            return;
        }

        if(str.indexOf(p, start) == start)
            dfs(str, start+p.length(), p);
    }
}

- xzhan211@binghamton.edu July 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

S = nP
based on the definition, any string is always periodic.
because "anystring" = 1 * "anystring".

So "n must be more than 1" should be a part of the definition. Otherwise its

def isPeriodic
return true
end

- michael July 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

S = nP
based on the definition, any string is always periodic.
because "anystring" = 1 * "anystring".

So "n must be more than 1" should be a part of the definition. Otherwise its

def isPeriodic
return true
end

- michael July 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def periodic (my_str):
str_len = len(my_str)
period_sizes = []
reaps = []
for i in range(1, int(str_len/2)+1):
if str_len%i == 0:
period_sizes.append(i)

for period_size in period_sizes:
reaps.append(my_str.count(my_str[:period_size]))

for i in range (0,len(period_sizes)):
if period_sizes[i] * reaps [i] == str_len:
return True
return (False)

- Leah Bor August 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static string FindPeriodicPattern(string s)
        {
            StringBuilder currPatt = new StringBuilder();
            int n = 1, i = 0, innerI = 0;

            bool isCurrMatch = false;

            while (i < s.Length)
            {
                innerI = i;
                foreach (var ch in currPatt.ToString())
                {
                    if (s[innerI] == ch)
                    {
                        isCurrMatch = true;
                        innerI++;
                        continue;
                    }
                    else
                    {
                        isCurrMatch = false;
                        currPatt.Append(s[i]);
                        break;
                    }
                }

                if (isCurrMatch)
                {
                    i = innerI;
                    n++;
                }
                else
                {
                    if(string.IsNullOrEmpty(currPatt.ToString()))
                        currPatt.Append(s[i]);
                    i++;
                }

            }

            return n > 1 ? currPatt.ToString() : null;
        }

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

import textwrap
for i in range(2, len(S)):
    if len(S)%i ==0:
        if len(set(textwrap.wrap(S,i)))==0:
        	print(i, textwrap.wrap(S,i)[0])
            print("True")
            break

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

// S = "ababab", then n=3, P= "ab"
// S = "xxxxxx", then n = 1, and P = "x"
// S = "aabbaaabba", then n = 2, and P = "aabba"

function findPattern(str) {
  var pattern = '';
  var n = 1;
  
  for (var i = 0; i < str.length;) {
    var step = pattern.length > 0 ? pattern.length : 1;
    var test = str.substr(i, step);
        
    if (test == pattern) {
      // Possible a pattern
      i += step;
      n += 1;
    } else {
      i += 1;
      pattern = str.substr(0, i);
      n = 1;
    }
  }
  
  return {n, pattern};
}

console.log("ababab => " + JSON.stringify(findPattern("ababab")))
console.log("xxxxxx => " + JSON.stringify(findPattern("xxxxxx")))
console.log("aabbaaabba => " + JSON.stringify(findPattern("aabbaaabba")))

- sheng August 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main( string [] args )
        {
            string s = "ababab";
            int Period = 0;
            string szRepeatString = "";
            int l = s.Length;
            for ( int subLen = 1 ; subLen <= l / 2 ; subLen++ )
            {
                if ( l % subLen != 0 ) continue;
                string szStub = s.Substring( 0, subLen );
                int nCopies = l / subLen;
                int n;
                for ( n = 1 ; n < nCopies ; n++ )
                {
                    if( s.Substring( n * subLen, subLen ) != szStub )
                    {
                        break;
                    }
                }
                if ( n == nCopies )
                {
                    szRepeatString = szStub;
                    Period = subLen;
                    break;
                }
            }

            Console.WriteLine( "string = " + s + ", period = " + Period + ", sub string = " + szRepeatString );
        }

- Eric H Frazer October 09, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{def periodic_scan(S):
s = S
cnt = 1
i = 1
comp = s[:i]
s = s[i:]
while len(s) > 0:
if i > len(S)//2:
return "None"
elif comp == s[:i]:
s = s[i:]
cnt += 1
else:
i += 1
s = S
cnt = 1
comp = s[:i]
s = s[i:]
return comp,cnt

# implement
print(periodic_scan("ababab"))
print(periodic_scan("xxxxxx"))
print(periodic_scan("aabbaaabba"))
print(periodic_scan("abcdefg"))
print(periodic_scan("abcdefghijklmnopabcdefghijklmnopabcdefghijklmnop"))}}

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

def periodic_scan(S):
	s = S
	cnt = 1
	i = 1
	comp = s[:i]
	s = s[i:]
	while len(s) > 0:
		if i > len(S)//2:
			return "None"
		elif comp == s[:i]:
			s = s[i:]
			cnt += 1
		else:
			i += 1
			s = S
			cnt = 1
			comp = s[:i]
			s = s[i:]
	return comp,cnt
	
# implement
print(periodic_scan("ababab"))
print(periodic_scan("xxxxxx"))
print(periodic_scan("aabbaaabba"))
print(periodic_scan("abcdefg"))
print(periodic_scan("abcdefghijklmnopabcdefghijklmnopabcdefghijklmnop"))

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

A more pythonic solution:

def smallest_period(s):
    n = len(s)
    i = 0
    while i < n/2:
        i += 1
        if n % i == 0 :
            p = s[:i]
            comp = [ s[next:next+i] == p for next in range(i,n,i)]
            if all(comp):
                return (p,n//i)
    return (s,1)            
        

s = 'ababab'
exp = ('ab',3)
actual = smallest_period(s)
assert actual == exp, actual

s = 'xxxxxx'
exp = ('x',6)
actual = smallest_period(s)
assert actual == exp, actual

s = 'aabbaaabba'
exp = ('aabba',2)
actual = smallest_period(s)
assert actual == exp, actual

s = 'abcdefa'
exp = ('abcdefa',1)
actual = smallest_period(s)
assert actual == exp, actual

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

C++ program

#include <iostream>
#include <set>
#include <iterator>


// Some properties
// 1. Pattern should contain atleast one distinct character that is present in the string.
// 2. Size of the string should be multiple of the pattern size.
//
// Steps:
// A. Find the substring to start with that satisfies #1.
// B. See if that satisfies #2.
// C. If so check if that is a correct pattern.
// D. If B or C failed, traverse the string for the next pattern that satisfies A to C.


bool IsValidPattern(std::string s, std::string pattern)
{
    // Property 2.
    if (s.length() % pattern.length() == 0)
    {
        bool fValid = true;
        for (int i = 0; i < s.length(); i+=pattern.length())
        {
            if (s.compare(i, pattern.length(), pattern) != 0)
            {
                fValid = false;
                break;
            }
        }
        if (fValid) return true;
    }

    return false;
}
void CheckPeriodic(std::string s, int nExepected, std::string expectedPattern)
{
    // Unique letters
    std::set<char> letters(s.begin(), s.end());

    std::string::iterator it = s.begin();

    int iIndex = 0;
    // Property 1.
    while ( iIndex <= s.length() / 2)
    {
        letters.erase(s[iIndex++]);
        if (letters.size() == 0) break;
    };

    while (iIndex <= s.length() / 2)
    {
        std::string pattern = s.substr(0, iIndex);

        if (IsValidPattern(s, pattern))
        {
            std::cout << s << " -> " << s.length() / pattern.length() << pattern;

            if (nExepected == s.length() / pattern.length() && pattern == expectedPattern)
            {
                std::cout << " -> PASS" << std::endl;
            }
            else
            {
                std::cout << " -> failed, expected " << nExepected << expectedPattern << std::endl;
            }
            return;
        }
        iIndex++;
    };

    if (nExepected == 0)
    {
        std::cout << s << " -> PASS  -> not periodic" << std::endl;
    }
    else
    {
        std::cout << s << " -> FAIL, expected " << nExepected << expectedPattern << std::endl;
    }

}

int main()
{
    CheckPeriodic("ababab", 3, "ab");
    CheckPeriodic("abababababab", 6, "ab");
    CheckPeriodic("xxxxxx", 6, "x");
    CheckPeriodic("abcdafabcdafabcdaf", 3, "abcdaf");
    CheckPeriodic("aabbaaabba", 2, "aabba");
    CheckPeriodic("abcdeabcde", 2, "abcde");
    CheckPeriodic("abc", 0, "");
    CheckPeriodic("", 0, "");

    return 0;
}


Output:

ababab -> 3ab -> PASS
abababababab -> 6ab -> PASS
xxxxxx -> 6x -> PASS
abcdafabcdafabcdaf -> 3abcdaf -> PASS
aabbaaabba -> 2aabba -> PASS
abcdeabcde -> 2abcde -> PASS
abc -> PASS  -> not periodic
 -> PASS  -> not periodic

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

function isPeriodic(str) {
    f: for (let i = 0; i <= str.length / 2; i += 1) {
    window.P = str.substring(0, i);
    if (!window.P) {
        continue;
    }
    for (let x = 0; x < str.length; x += window.P.length) {
        const currentPattern = str.substr(x, window.P.length);
        if (currentPattern !== window.P) {
            break;
        } else if (x + window.P.length === str.length) {
            console.log('RESULT', window.P, str.length / window.P.length);
            break f;
        }
    }
}
}

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

Best Case is n;
Worst Case is n power 2

function getrepetitionPattern($str){
		$arr = str_split($str);
		$len = count($arr);
		$pattern[0] = $arr[0];

		$i = 0; //pattern index
		$r = 1; //array init index
		$j = 1; //array pointer

		$n = 1;

		while($j < $len){
			if($arr[$j] == $pattern[$i]){ 
				$j++; $i++;
				if(count($pattern) == $i ) {
					$i = 0; 
					$n++; //increase patter count
				}
			}else{ 
				$pattern[] = $arr[$r];
				$r ++; $j = $r;
				$i = 0;
				$n = 1;
			}
		}

		print $n."".implode("",$pattern)."<br/><br/>"; 

	}

	$str1 = "abababab";
	$str2 = "xxxxxxxk";
	$str3 = "aabbaaabbaa";

	getrepetitionPattern($str1);
	echo '<br/>';
	getrepetitionPattern($str2);
	echo '<br/>';
	getrepetitionPattern($str3);

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

def verify_p(s, p):
    if len(s)%len(p) != 0:
        return False

    for i in range(len(p), len(s)):
        mod = i%len(p)
        if s[i] != p[mod]:
            return False
    return True

def find_p(s):
    p = ''
    k = 0
    while k < len(s)-1:
        p += s[k]
        k += 1
        ret = verify_p(s, p)
        if ret:
            print('found P:', s, p)
            return


if __name__ == '__main__':
    find_p('ababab')
    find_p('abaabaabaaba')

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

private boolean checkIfPeriodic(String str) {
          int dist = 1, prev = 0, next = 1;
        boolean lastMatch = false;
        while (next + dist <= str.length()) {
            if (str.substring(prev, dist + prev).equals(str.substring(next, next + dist))) {
                //Match found
                prev = next;
                next = next + dist;
                lastMatch = true;
            } else {
                //Not matched
                if(lastMatch){
                    prev=0;
                }
                dist++;
                next = dist + prev;
                lastMatch = false;

            }
        }
        return lastMatch;
    }

- RV March 24, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

term = 'aabbaaabba'
rep_term = ''
is_periodic = False

for i, char in enumerate(term):
    rep_term += char
    if i + 1 > len(term) / 2:
        break 
        
    if len(term.replace(rep_term, '')) > 0:
        continue
    else:
        is_periodic = True
        break
        
print(is_periodic)

- ES April 20, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const isPeriodic = function(str, substr = null) {
const toMatch = substr ? substr : str.charAt(0)
const matchRx = new RegExp(toMatch, 'gi')
const match = str.match(matchRx)

if (match.length * toMatch.length === str.length) {
return { P: match[0], n: match.length }
}

return isPeriodic(str, str.slice(0, toMatch.length + 1))
}

- BenjaminWFox August 12, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const isPeriodic = function(str, substr = null) {
  const toMatch = substr ? substr : str.charAt(0)  
  const matchRx = new RegExp(toMatch, 'gi')
  const match = str.match(matchRx)
  
  if (match.length * toMatch.length === str.length) {
     return { P: match[0], n: match.length }
  }
  
  return isPeriodic(str, str.slice(0, toMatch.length + 1))
}

- BenjaminWFox August 12, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

javascript implementation

function findPattenForS(S) {
    let output = {
        S: S,
        n: 0,
        P: ''
    }
    let tempPatten = S[0];
    let tempMeetPatten = true, meetPatten = false;
    let steps = 1;
    for (steps = 1; steps<=S.length; steps++) {
        tempPatten = S.substr(0, steps);
        for (let i=0; i<S.length; i = i+steps) {
            if (tempPatten !== S.substr(i, steps)) {
                tempMeetPatten = false;
                break;
            }
        }
        if(tempMeetPatten) {
            meetPatten = true;
            break;
        }
        tempMeetPatten = true;
    }
    if (meetPatten) {
        output.n = steps;
        output.P = tempPatten;
    }
    return output;
}

console.log(findPattenForS("abababab"));
console.log(findPattenForS("xxxxxxxxx"));
console.log(findPattenForS("abcabcabc"));
console.log(findPattenForS("abababac"));

output:
{ S: 'abababab', n: 2, P: 'ab' }
{ S: 'xxxxxxxxx', n: 1, P: 'x' }
{ S: 'abcabcabc', n: 3, P: 'abc' }
{ S: 'abababac', n: 8, P: 'abababac' }

- Yolanda September 01, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def isPeriodic(str1):
    
    # is string is periodic n has to be 2, 3......n/2 at max
    # brute force
    n = int(len(str1)/2) 
    
    for i in range(1, n+1):
        # i simply means the pattern length
        
        #print(i)
        
        temp = str1[0:i]
        #print(i,temp)
        found = None
        for j in range(i,len(str1), i):
            
            temp1 = str1[j:j+i]
            #print(i, j,temp,temp1)
            if temp == temp1:
                continue
            else:
                found = False
                break
        if found is None:
            return i, True
                
            
            #print(temp1)
    
    return -1,False

- satyans24 September 19, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void CountSubstring(string s)
{
string substring = "";
bool isLoop = true;
int numberOfSubstrings = 0;

for (int i = 1; i < s.Length/2+1; i++)
{
isLoop = true;
substring = s.Substring(0, i);

if(s.Length%substring.Length == 0)
{
numberOfSubstrings = s.Length / substring.Length;
for (int j = 0; j < numberOfSubstrings; j++)
{
if(!s.Substring(j* substring.Length, substring.Length).Equals(substring))
{
isLoop = false;
break;
}
}
}

else
{
isLoop = false;
}

if (isLoop)
{
Console.WriteLine(string.Format("n={0},P={1}", numberOfSubstrings, substring));
return;
}
}
Console.WriteLine("Not a loop");

}

- tal December 28, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Periodic {

    public static boolean isPeriodic(String s, int repeat){
        int charsNo = s.length()/repeat;
        String p = null;
        for(int i=0;i<s.length();){
            int j = i+charsNo-1;
            String st = s.substring(i,j);
            if(p==null)p = st;
            else{
                if(!p.equals(st)){
                    return false;
                }
            }
            i = j+1;
        }
        return true;

    }
    public static void main(String[] args) {
        String s = "ababab";
        int n = 3;
        System.out.println(isPeriodic(s,n));

         s = "aabbaaabba";
         n = 2;
        System.out.println(isPeriodic(s,n));

        s = "xxxxxxxx";
        n = 8;
        System.out.println(isPeriodic(s,n));
    }
}

- Sougata January 18, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Python:

def isPeriodic(s):
    p=[]
    for i in range(len(s)-1):
        newss = s[:i+1]
        p.append(newss)
        new_p = []
        print(p)
        for ss in p:
            if mayBePeriod(ss, newss):
                new_p.append(ss)
        p = new_p
    
    for ss in p:
        if isPeriod(ss, s):
            print(ss)
            return True
    return False
    
def mayBePeriod(substr, word_t):
    while True:
        if word_t.startswith(substr):
            word_t = word_t.partition(substr)[2]
        else: 
            break
        
    if word_t == "" or substr.startswith(word_t):
        return True
    else:
        return False
                
def isPeriod(substr, word_t):
    
    repeated = 0
    while True:
        if word_t.startswith(substr):
            word_t = word_t.partition(substr)[2]
            repeated += 1
        else:
            break
    
    if repeated > 1 and word_t == "":
        return True
    
    return False

- Daemon Groznny September 12, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function isStrPeriodic(str) {
  const strArr = Array.from(str);
  let i = 0;
  let pattern = '';
  let count = 0;
  
  while (i < strArr.length) {
    if (i === 0 && pattern === '') {
      pattern = strArr[i];
      console.log('before continue')
      
      i++;
      continue;
    }
    
    const patternLength = pattern.length;
    const wordArr = strArr.slice(i + 1, i + patternLength);
    const wordStr = wordArr.join('');
    
    const foundPatternArr = [];
    const remainingLetters = strArr.slice(i);
    
    for (let j = 0; j < remainingLetters.length; j += patternLength) {
      foundPatternArr.push(remainingLetters.slice(j, j + patternLength).join(''))
    }

    const nonPatternFound = foundPatternArr.find(e => e !== pattern);
    
    if (nonPatternFound) {
      pattern += strArr[i];

      i++;
      continue;
    }
    
    // PATTERN FOUND
    
    count = foundPatternArr.length + 1;
    
    break;
    
    i++;
  }
  
  return { pattern, count }
}

const { pattern, count } = isStrPeriodic('aabbaaabbaaabbax')

console.log('pattern:', pattern)
console.log('count:', count)

- Hasan February 14, 2022 | 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