Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
#include <stdio.h>
int main()
{
//unsigned char String[] = "xxxxxxxxx";
//unsigned char String[] = "abababababab";
unsigned char String[] = "aabbaaabba";
unsigned char *Pattern;
unsigned int Index = 0, pLength = 0, i, count = 1;
Pattern = &String[0];
pLength = 1;
for ( Index = 1; Index < sizeof(String)-1; )
{
for ( i = 0; i < pLength; i++ )
{
if ( Pattern[i] == String[Index])
Index++;
else
{
pLength++;
if ( pLength > (sizeof(String) / 2) )
pLength = sizeof(String);
Index = pLength;
count = 0;
break;
}
}
count++;
}
return 0;
}
My solution in C++
#include <iostream>
#include <string>
bool isPeriodic(const std::string& str) {
std::string test = str.substr(1) + str.substr(0, str.length() / 2);
return test.find(str) != test.npos;
}
auto findPeriod(const std::string& str) {
auto len = 0;
std::string test = str.substr(1) + str.substr(0, str.length() / 2);
while (test.find(str) != test.npos) {
++len;
test.erase(test.length() - 1);
}
if (!len)
return std::string();
return str.substr(0, 1 + str.length() / 2 - len);
}
Alternative solution for findPeriod in C++
auto findPeriod(const std::string& str) {
auto len = 1;
std::string test = str.substr(1) + str[0];
for (; len <= str.length() / 2 && test.find(str) == test.npos; ++len) {
test += str[len];
}
if (len > str.length() / 2)
return std::string();
return str.substr(0, len);
}
public static String getPeriod(String str) {
if (str == null || str.length() <= 1) return null;
int len = str.length();
int[] lps = new int[len];
int prev = 0;
for (int i = 1; i < len; i++) {
char ch = str.charAt(i);
char prevChar = str.charAt(prev);
if (ch == prevChar) {
prev++;
lps[i] = prev;
} else {
if (prev == 0) {
lps[i] = 0;
} else {
prev = lps[prev-1];
i--;
}
}
}
int lpsLength = lps[len-1];
int leftLen = len - lpsLength;
if (len % leftLen == 0) return str.substring(0, leftLen);
return null;
}
Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
- aonecoding January 20, 2018