Linkedin Interview Question for Software Developers

• 16

Team: Not known
Country: India
Interview Type: Phone Interview

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

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());

}

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

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

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

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).

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

@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)

Comment hidden because of low score. Click to expand.
-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;
}
}
return res;
}

Comment hidden because of low score. Click to expand.
0

Compexity is actually

O(n * m)

where n is length of original string, and m is length of substring

Comment hidden because of low score. Click to expand.
0

Compexity is

O(n * m) where n is length of original string, m is length of sub string

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

thanks all for the discussion, that's correct, I forgot about function call.
actually, worst case is m*n.

Comment hidden because of low score. Click to expand.
0

This program throws exception StringIndexOutOfBoundsException

Comment hidden because of low score. Click to expand.
0

var sub = str.Substring( i, n ); should be var sub = str.Substring( i, i+n );

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

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;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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());

}

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ 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()); } }
Comment hidden because of low score. Click to expand.
0
of 0 vote

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());
}

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

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());

}

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

def substrCount(st, k):

length = len(st)
subs = {}

for i in range(length- k +1):
temp = st[i : i+k]

if temp in subs:
subs[temp] += 1

else:
subs[temp] = 1

return subs

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

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)

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.

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.