Ivycomptech Interview Question
Country: India
Interview Type: In-Person
def isPattern(input_string) :
pattern_length = 1
while (pattern_length <= len(input_string)):
if(len(input_string) % pattern_length == 0) : # if pattern_length divides input_string check
# else increase pattern by one character
pattern = input_string[0:pattern_length] # create pattern as substring of input_string
placeholder = pattern_length
while( pattern == input_string[placeholder : pattern_length + placeholder]) :
if placeholder == int(len(input_string) - pattern_length):
return {True : pattern}
else :
placeholder = placeholder + pattern_length
pattern_length = pattern_length + 1
return False
# Test
print(isPattern('abcabcabc')) # {True: 'abc'}
print(isPattern('abcdabababab')) # False
I am interpreting this problem as: "Given a string s, check whether it is made of one or more repetitions of the same substring"
Here is a simple solution in java.
public static boolean hasRepeated(String input) {
assert(input.length() > 0);
char start = input.charAt(0);
for (int i = 1; i < input.length(); i++) {
char current = input.charAt(i);
if (current != start) {
continue;
}
if (matchesRepeated(input.substring(0, i), input.substring(i, input.length()))) {
return true;
}
}
return false;
}
public static boolean matchesRepeated(String pattern, String input) {
if (input.length() % pattern.length() != 0) {
return false;
}
for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) != pattern.charAt(i % pattern.length())) {
return false;
}
}
return true;
}
For c++ code...complexity O(n)
bool repeatedSubstr(std::string data, std::string& pattern){
std::vector<std::string> subs;
std::string temp = "";
for (auto each : data){
if (each == data[0]){
subs.push_back(data[0] + temp);
temp = "";
}
else
temp += each;
}
subs.push_back(data[0] + temp);
if (subs.size() <= 2){
pattern = "";
return false;
}else{
pattern = subs[1];
for (int i = 2; i < (int)subs.size(); i++)
if (subs[i] != pattern){
pattern = "";
return false;
}
return true;
}
}
For python code...complexity O(n)
def repeatedSubstring(data):
subs = data.split(data[0])[1::]
pattern = subs[0]
if len(subs) == 1:
return False
for each in subs:
if each != pattern:
return False
return data[0] + pattern
Update even better solution without vector in c++...complexity O(n)
bool repeatedSubstring(std::string data, std::string& pattern){
std::string temp = "";
pattern = "";
for(int i = 1; i < (int)data.size(); i++){
if (data[i] != data[0]){
temp += data[i];
}else{
if (pattern == "")
pattern = data[0] + temp;
else if (pattern != (data[0] + temp)){
pattern = "";
return false;
}
temp = "";
}
}
temp = data[0] + temp;
if (temp != pattern)
pattern = "";
return (pattern == temp);
}
Update:: Even better answer without vector
bool repeatedSubstring(std::string data, std::string& pattern){
std::string temp = "";
pattern = "";
for(int i = 1; i < (int)data.size(); i++){
if (data[i] != data[0]){
temp += data[i];
}else{
if (pattern == "")
pattern = data[0] + temp;
else if (pattern != (data[0] + temp)){
pattern = "";
return false;
}
temp = "";
}
}
temp = data[0] + temp;
if (temp != pattern)
pattern = "";
return (pattern == temp);
}
bool repeatedSubstr(std::string data, std::string& pattern){
std::vector<std::string> subs;
std::string temp = "";
for (auto each : data){
if (each == data[0]){
subs.push_back(data[0] + temp);
temp = "";
}
else
temp += each;
}
subs.push_back(data[0] + temp);
if (subs.size() <= 2){
pattern = "";
return false;
}else{
pattern = subs[1];
for (int i = 2; i < (int)subs.size(); i++)
if (subs[i] != pattern){
pattern = "";
return false;
}
return true;
}
}
{bool repeatedSubstr(std::string data, std::string& pattern){
std::vector<std::string> subs;
std::string temp = "";
for (auto each : data){
if (each == data[0]){
subs.push_back(data[0] + temp);
temp = "";
}
else
temp += each;
}
subs.push_back(data[0] + temp);
if (subs.size() <= 2){
pattern = "";
return false;
}else{
pattern = subs[1];
for (int i = 2; i < (int)subs.size(); i++)
if (subs[i] != pattern){
pattern = "";
return false;
}
return true;
}
}
- NoOne October 06, 2016