Linkedin Interview Question
Software Engineer / DevelopersCountry: United States
You can create a suffix tree for any given string and print any path with the length > 1 or you can also use suffix array.
This should work too?
if (inputString.isEmpty() || sequenceLength <= 0 || sequenceLength >= inputString.length()) {
System.out.println("Invalid input");
} else {
int i = 0;
int j = i + sequenceLength;
Set<String> tempSet = new HashSet<>();
Set<String> repeatingSequences = new TreeSet<>();
while (j <= inputString.length()) {
if (!tempSet.add(inputString.substring(i, j))) {
repeatingSequences.add(inputString.substring(i, j));
}
i++;
j = i + sequenceLength;
}
for (String str : repeatingSequences) {
System.out.println(str);
}
}
github.com/techpanja/interviewproblems/blob/master/src/strings/repeatingstringsofspecifiedlength/RepeatingStringOfSpecificLength.java
It works. Just append https : // in the beginning. complete links are not allowed in comments.
@techpanja : Good but deceptive solution. On the face of it, it looks like it is O(n) in time, where n = length of input string. However, it is really O(n*k) in time, where k = number of characters required. This is because the ".substring(int beginIdx, int endIdx)" function doesn't come with O(1) but with O(endIdx - beginIdx) which is O(k) here. Interesting solution none-the-less!
# include <iostream>
# include <string>
# define MAX(a,b) a>b?a:b
using namespace std;
int substring(string s, string sub)
{
int m[50][50]; //Some random number for quick prototype...
int slen = s.length()+1;
int sublen = sub.length()+1;
for(int i=0;i<s.length(); i++)
for(int j=0;j<s.length();j++)
m[i][j] = 0;
//For LCS problem start the matrix from 1 so that the logic m[i-1][j-1] does not go out of bounds.
for(int i=1;i<s.length(); i++)
for(int j=1;j<sub.length();j++)
{
if(s[i] == sub[i])
m[i][j] = 1 + m[i-1][j];
else
m[i][j] = MAX(m[i-1][j],m[i][j-1]);
}
/*
for(int i=0;i<s.length(); i++)
{
cout<<endl;
for(int j=0;j<sub.length();j++)
cout<<m[i][j]<<" ";
}
*/
return m[s.length()-1][sub.length()-1];
}
string LCS(string s, int n)
{
int max = 0;
int result=0;
string ressubstring ;
for(int i=0;i<s.length()-1; i++)
{
string sub =s.substr(i,n);
if((sub.length() == n) && (s.length() >= n))
result = substring(s,sub);
if(result > max )
{
max = result;
ressubstring = sub;
}
}
return ressubstring;
}
int main()
{
string s = "ABCACBABC";
cout<<endl<<"LCS :"<<LCS(s,3)<<endl;
return 0;
}
Simple code
ublic static void main(String[] args) {
String test = "ABCACBABC";
int step = 1;
Set<String> nonReaptingSeq = new TreeSet<>();
Set<String> reaptingSeq = new TreeSet<>();
for (int i = 0; (i < test.length() && (i + step) <= test.length()); i++) {
String sub = test.substring(i, i + step);
System.out.println(sub);
if (!nonReaptingSeq.add(sub)) {
reaptingSeq.add(sub);
}
}
System.out.println(reaptingSeq);
}
public static void main(String[] args) {
String test = "ABCACBABC";
int step = 2;
Set<String> nonReaptingSeq = new TreeSet<>();
Set<String> reaptingSeq = new TreeSet<>();
for (int i = 0; (i < test.length() && (i + step) <= test.length()); i++) {
String sub = test.substring(i, i + step);
System.out.println(sub);
if (!nonReaptingSeq.add(sub)) {
reaptingSeq.add(sub);
}
}
System.out.println(reaptingSeq);
}
Output
[AB, BC]
public static main(String[] args) {
String input = "ABCABCA";
int k=2;
int len = input.length();
//Finally ans will hold the answer strings, if any.
Array<String> ans = new ArrayList<String>();
for(int i=0; i<len-k; i++) {
String temp = input.length(i, i+k);
if (ans.contains(temp)) {
continue;
}
if (input.replaceAll(temp).length() < len-k) {
ans.add(temp);
}
}
This is a much more complex code.
The logic discussed above makes a lot of sense.
But they would be interested in knowing the space complexity, which is quite high when one used the hash-table.
What is needed in O(N) time complexity and space complexity as minimum as possible.
Hope I get some brain-storming examples.
Working code in C++. Not optimized. As mentioned above, I'm still looking for a O(n) time and/or space complexity
#include <iostream>
#include <tr1/unordered_map>
#include <vector>
using namespace std;
using namespace tr1;
void findRepeatSubStr(string s, int req_size){
if(s.size() < 2*req_size){
cout << "string is not long enough" << endl;
return;
}
int i = 0;
string t;
unordered_map<string, bool>m;
int max_itr = s.size() - req_size;
vector <string> v (1);
unordered_map<string, bool>m1;
for(i=0; i <= max_itr; i++){
//cout << "start idx: "<< i << endl;
//cout << "end idx: "<< i+req_size-1 << endl;
t = s.substr(i, req_size);
cout << "t: " << t << endl;
if(m[t] != true){
//unique entry
m[t] = true;
}
else{
//dup entry
if (m1[t] != true){
//not added to v, add
v.push_back(t);
m1[t] = true;
}
}
}
for(i=0; i<v.size(); i++){
cout << v[i] << endl;
}
return;
}
int main(){
string s = "abcabcabc";
findRepeatSubStr(s, 3);
return 0;
}
public Set<String> findRepeatedSubString(String s,int length){
if(s==null||s.length()==0) return null;
Set<String> checkSet = new HashSet<String>();
Set<String> result = new TreeSet<String>();
for(int i=0;i<s.length()-length+1;i++){
if(!checkSet.contains(s.substring(i,i+length)))
checkSet.add(s.substring(i,i+length));
else
result.add(s.substring(i,i+length));
}
if(result.size()==0) return null;
return result;
}
public Set<String> findRepeatedSubString(String s,int length){
if(s==null||s.length()==0) return null;
Set<String> checkSet = new HashSet<String>();
Set<String> result = new TreeSet<String>();
for(int i=0;i<s.length()-length+1;i++){
if(!checkSet.contains(s.substring(i,i+length)))
checkSet.add(s.substring(i,i+length));
else
result.add(s.substring(i,i+length));
}
if(result.size()==0) return null;
return result;
}
public static void main(String... args) {
String s = "ABCABCA";
int k = 2;
final Map<String, Integer> map = new HashMap<>();
for (int i = 0; i+k <= s.length(); ++i) {
String key = s.substring(i, i+k);
System.out.println(key);
Integer value = map.get(key);
if (value == null)
map.put(key, 1);
else
map.put(key, value+1);
}
List<String> list = Lists.newArrayList(map.keySet());
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String first, String second) {
return map.get(second).compareTo(map.get(first));
}
});
System.out.println(list);
System.out.println(map);
}
package linkedin;
import org.junit.Test;
import java.util.*;
import static org.junit.Assert.assertEquals;
public class RepeatedSubstrings {
@Test
public void test() {
assertEquals(new TreeSet<>(Arrays.asList("AB", "BC", "CA")), repeatedSubstrings("ABCABCA", 2));
}
private Set<String> repeatedSubstrings(String input, int len) {
if (input == null) throw new IllegalArgumentException();
if (input.length() < len * 2) return new TreeSet<>();
int lastIdx = input.length() - len;
Set<String> unique = new HashSet<>();
Set<String> res = new TreeSet<>();
for (int i = 0; i <= lastIdx; i++) {
String substr = input.substring(i, i + len);
if (!unique.add(substr)) {
res.add(substr);
}
}
return res;
}
}
Time complexity O(n), space complexity O(n), n is the length of big string. The hash table needs to store all segments with length m.
In Scala
import java.util.TreeMap
object RepeatingSub extends App {
import scala.collection.JavaConverters._
def repeatingSub(str:String, length:Int):Iterable[String] = {
var map = new TreeMap[String, Int]()
require(str.length>length, s"Invalid string $str, too short")
for (i<-0 to str.length-length) {
val sub = str.substring(i, i+length)
if (map.containsKey(sub)) map.put(sub, map.get(sub)+1)
else map.put(sub, 1)
}
map.asScala.filter{case (k,v)=>v>1}.map(_._1)
}
println(repeatingSub("ABCACBABC", 3))
println(repeatingSub("ABCABCA", 2))
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class RepeatingString {public static void main(String... args) {
String s = "ABCABC";
int k = 3;
final Map<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i+k <= s.length(); ++i) {
String key = s.substring(i, i+k);
// System.out.println(key);
Integer value = map.get(key);
if (value == null)
map.put(key, 1);
else
map.put(key, value+1);
}
List<String> list = new ArrayList<String>(map.keySet());
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String first, String second) {
return map.get(second).compareTo(map.get(first));
}
});
// System.out.println(list);
Iterator<Map.Entry<String, Integer>> itr = map.entrySet().iterator();
while(itr.hasNext()){
Map.Entry<String, Integer> entry = itr.next();
if(entry.getValue()==1){
itr.remove();
}
}
if(map.size()==0){
System.out.println("No pattern is getting repeated");
}
else
System.out.println(map);
}}
How about you iterate over the given string character by character and have an inner loop which runs from current index to the string length you are interested in finding out ( say 3) ( constant work) . Put each string of length 3 in a hashmap<Word, WordFrequencey> and update the frequency if the same string occurs again. At the end just iterate over the hashmap and return all those keys which have values > 1.
Time Complexity - O(n) , Space Complexity - No of words in the hashmap *( 2 bytes * (length of each word))
import java.util.TreeMap;
public class RepeatedSubStringsOfMlength {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input1 = "ABCACBABC";
String input2 = "CABCAABC";
System.out.println(findRepeatedSubStr(input1, 3));
System.out.println(findRepeatedSubStr(input2, 2));
}
private static String findRepeatedSubStr(String input1, int m) {
// TODO Auto-generated method stub
if (input1 == null)
return null;
StringBuilder output = new StringBuilder();
TreeMap<String, Integer> stringMap = new TreeMap<String, Integer>();
for (int i = 0; i <= input1.length() - m; i++) {
if (stringMap.containsKey(input1.substring(i, i + m))) {
stringMap.put(input1.substring(i, i + m),
stringMap.get(input1.substring(i, i + m)) + 1);
} else
stringMap.put(input1.substring(i, i + m), 1);
}
for (String str : stringMap.keySet()) {
if (stringMap.get(str) > 1) {
output.append(str);
output.append(" ");
}
}
return output.toString();
}
}
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <unordered_set>
using namespace std;
vector<string> getRepeated(string s, int l) {
int n = s.size();
vector<string> result;
if (n < 2 || n < l) {
return result;
}
unordered_set<long long> done_set;
unordered_set<long long> seen_set;
long long val = 0;
for (int i =0; i < n; ++i) {
if (i < l) {
val = val + pow(7,l-i-1)*(long)s[i];
} else {
cout << "val : " << val << "\tat " << i << "\n";
if (seen_set.find(val) == seen_set.end()) {
seen_set.insert(val);
} else if (done_set.find(val) == done_set.end()) {
result.push_back(string(s,i-l,l));
done_set.insert(val);
}
val = val*7 - pow(7,l)*(long long)s[i-l] + (long long)s[i];
}
}
//check for the last char
if (seen_set.find(val) != seen_set.end() && done_set.find(val) == done_set.end()) {
result.push_back(string(s,n-l,l));
}
return result;
}
void printVec(vector<string>& a) {
for (int i = 0; i < a.size(); ++i) {
cout << a[i] << "\t";
}
cout << "\n**************\n";
}
int main() {
vector<string> res;
res = getRepeated("ABCBCAABC",3);
printVec(res);
res = getRepeated("ABCBAABC",2);
printVec(res);
res = getRepeated("ACC",1);
printVec(res);
res = getRepeated("ACC",3);
printVec(res);
res = getRepeated("ACCDC",3);
printVec(res);
res = getRepeated("ACCCACCCC",4);
printVec(res);
res = getRepeated("ACCCACCCCA",4);
printVec(res);
}
public class RepeatedSubSequence {
public static void main(String args[]) {
String repeatedSubsequence1 = "ABCACBABC";
List<String> output1 = repeatedSubsequence(repeatedSubsequence1, 3);
for(final String value : output1) {
System.out.println(value);
}
String repeatedSubsequence2 = "ABCABCA";
List<String> output2 = repeatedSubsequence(repeatedSubsequence2, 2);
for(final String value : output2) {
System.out.println(value);
}
}
public static List<String> repeatedSubsequence(final String input, int repeatedLength) {
List<String> repeatedSequence = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
if (i + repeatedLength > input.length()) {
break;
}
String substring = input.substring(i, i + repeatedLength);
for(int j = i+1; j< input.length(); j++) {
if(j+repeatedLength > input.length()) {
break;
}
String sequence = input.substring(j,j+repeatedLength);
if(substring.equals(sequence)) {
if(!repeatedSequence.contains(sequence)) {
repeatedSequence.add(sequence);
}
}
}
}
return repeatedSequence;
}
}
public class RepeatedSubSequence {
public static void main(String args[]) {
String repeatedSubsequence1 = "ABCACBABC";
List<String> output1 = repeatedSubsequence(repeatedSubsequence1, 3);
for(final String value : output1) {
System.out.println(value);
}
String repeatedSubsequence2 = "ABCABCA";
List<String> output2 = repeatedSubsequence(repeatedSubsequence2, 2);
for(final String value : output2) {
System.out.println(value);
}
}
public static List<String> repeatedSubsequence(final String input, int repeatedLength) {
List<String> repeatedSequence = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
if (i + repeatedLength > input.length()) {
break;
}
String substring = input.substring(i, i + repeatedLength);
for(int j = i+1; j< input.length(); j++) {
if(j+repeatedLength > input.length()) {
break;
}
String sequence = input.substring(j,j+repeatedLength);
if(substring.equals(sequence)) {
if(!repeatedSequence.contains(sequence)) {
repeatedSequence.add(sequence);
}
}
}
}
return repeatedSequence;
}
}
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.TreeMap;
public class RepeatSubString {
public static List<String> repeatSubString(String s, int n) {
TreeMap<String,Integer> repSubMap = new TreeMap<>();
for (int i=0; i+n-1<s.length(); ++i) {
String sub = s.substring(i,i+n);
if (repSubMap.containsKey(sub)) {
int count = repSubMap.get(sub);
count++;
repSubMap.put(sub, count);
} else {
repSubMap.put(sub,1);
}
}
List<String> list = new LinkedList<>();
for (Entry<String,Integer> kv : repSubMap.entrySet()) {
if (kv.getValue() > 1) {
list.add(kv.getKey());
}
}
return list;
}
public static void main(String[] args) {
System.out.println(repeatSubString("ABCACBABC", 3));
System.out.println(repeatSubString("ABCABCA", 2));
}
}
My solution in ruby.
- jiasilu1987 January 26, 2014