Linkedin Interview Question Software Developers
Team: Not known
Country: India
Interview Type: Phone Interview
This can be done in time complexity O(n) and space cpmplexity O(n).
Data structure trie (or trie like). Each node will have children and can have recursive path to some of the parents. A character will come only once in this trie. Also store a hashmap of the character key and the node as value. Parse the input string once to create trie structure and populate this hashmap. If a path already exists in this trie like structure add 1 to the count. Assuming each path is initialized with 1 value of the count.
For every substring to be checked, check if path exists and if it does, take the minimum value.
If all the possible substrings of a particular length are to be found, traverse this trie and find substrings with that length
Quite straightforward.
For storage use hashtable: key - substring, value - count.
In a loop count all occurrences of all substrings of given length.
If substring (key) exists in a hashtable, increment count (value).
Otherwise, insert a new entry in hashtable with value equal to 1.
Time O(n*m).
Space O(n).
@zr.roman your algo cannot be O(n) you are not given the substring rather you have to find all the possible one, the trivial algo you explained comes to about O(n^2)
it's O(n), see the solution (c#):
(upd: actually O(n*m))
static private Hash GetCntOfPossSubstrs( string str, int n ) {
var res = new Hash(); // Hash = Dictionary<string, int>;
for ( int i = 0; i + n <= str.Length; i++ ) {
var sub = str.Substring( i, n );
if ( res.ContainsKey( sub ) ) {
res[ sub ]++;
continue;
}
res.Add( sub, 1 );
}
return res;
}
Compexity is actually
O(n * m)
where n is length of original string, and m is length of substring
substring has linear time complexity.
so if n = 36 and m = 18 then our function is going to be called 19 times and each time it is going to copy 18 elements..
36 * 18 is closer to my value then just n = 36
thanks all for the discussion, that's correct, I forgot about function call.
actually, worst case is m*n.
c++, KMP algorithm, O(n * k)
KMP: O(n), find all substr: O(n * k)
vector< pair<string, int> > substringCountKMP(string str, int k) {
vector< pair<string, int> > ret;
vector<int> fails(str.size() + 1, -1);
vector<int> counts(str.size() + 1, 1);
int i, pos;
for (i = 1; i <= str.size(); i++) {
pos = fails[i - 1];
while (pos != -1 && str[pos] != str[i - 1]) {
pos = fails[pos];
}
fails[i] = pos + 1;
}
for (i = fails.size() - 1; i > 0; i--) {
if (fails[i] >= k) {
counts[ fails[i] ] += counts[i];
counts[i] = 0;
}
}
for (i = k; i < counts.size(); i++) {
if (counts[i] == 0) continue;
ret.push_back(make_pair(str.substr(i - k, k), counts[i]));
}
return ret;
}
java solution
public class SubstrLength2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input="ABCGRETCABCG";
Map<String,Integer> substrMap=new HashMap<String,Integer>();
for(int i=0;i+3<=input.length();i++){
String substr=input.substring(i, i+3);
int frequency=1;
if(substrMap.containsKey(substr)){
frequency=substrMap.get(substr);
frequency++;
}
substrMap.put(substr, frequency);
}
System.out.println(substrMap.toString());
}
String s="ABCGRETCABCG";
HashMap<String,Integer> hm = new HashMap<String,Integer>();
StringBuilder sb = new StringBuilder();
int i=0,
j=0;
int count=0;
while(j<s.length())
{
sb.append(s.charAt(j));
j++;
count++;
if(count==3)
{
i++;
j=i;
count=0;
int frequency = 1;
if(hm.containsKey(sb.toString()))
{
frequency = hm.get(sb.toString());
frequency ++;
}
hm.put(sb.toString(),frequency);
sb = new StringBuilder();
}
}
Set set = hm.entrySet();
Iterator iterator = set.iterator();
while(iterator.hasNext()) {
Map.Entry mentry = (Map.Entry)iterator.next();
System.out.print("key is: "+ mentry.getKey() + " & Value is: ");
System.out.println(mentry.getValue());
}
String s="ABCGRETCABCG";
HashMap<String,Integer> hm = new HashMap<String,Integer>();
StringBuilder sb = new StringBuilder();
int i=0,
j=0;
int count=0;
while(j<s.length())
{
sb.append(s.charAt(j));
j++;
count++;
if(count==3)
{
i++;
j=i;
count=0;
int frequency = 1;
if(hm.containsKey(sb.toString()))
{
frequency = hm.get(sb.toString());
frequency ++;
}
hm.put(sb.toString(),frequency);
sb = new StringBuilder();
}
}
Set set = hm.entrySet();
Iterator iterator = set.iterator();
while(iterator.hasNext()) {
Map.Entry mentry = (Map.Entry)iterator.next();
System.out.print("key is: "+ mentry.getKey() + " & Value is: ");
System.out.println(mentry.getValue());
}
def subStringCount(strVar, l):
if len(strVar) < l:
print "No substring of length %d"%l
else:
subStringCount = dict()
for i in xrange(len(strVar)+1-l):
subStringCount[strVar[i:i+3]] = subStringCount.get(strVar[i:i+3], 0) + 1
print subStringCount
if __name__ == "__main__":
subStringCount("ABCGRETCABCG", 3)
java solution public class SubstrLength2 { public static void main(String[] args) { // TODO Auto-generated method stub String input="ABCGRETCABCG"; Map<String,Integer> substrMap=new HashMap<String,Integer>(); for(int i=0;i+3<=input.length();i++){ String substr=input.substring(i, i+3); int frequency=1; if(substrMap.containsKey(substr)){ frequency=substrMap.get(substr); frequency++; } substrMap.put(substr, frequency); } System.out.println(substrMap.toString());}
- Rajnish Kumar December 09, 2015