Linkedin Interview Question for Software Developers


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

}

- Rajnish Kumar December 09, 2015 | Flag Reply
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

- sanchay101 March 03, 2016 | Flag Reply
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).

- zr.roman December 08, 2015 | Flag Reply
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)

- softwaregeek December 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

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

- zr.roman December 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Compexity is actually

O(n * m)

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

- Nenad December 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Compexity is

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

- africa1001 December 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- africa1001 December 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zr.roman December 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This program throws exception StringIndexOutOfBoundsException

- jj January 28, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- jj January 28, 2016 | Flag
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;
}

- kyduke December 08, 2015 | Flag Reply
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());

}

- Rajnish Kumar December 09, 2015 | Flag
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()); } } - rajnish December 09, 2015 | Flag Reply
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());
}

- sentha December 17, 2015 | Flag Reply
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());

}

- sentha December 17, 2015 | Flag Reply
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

- kwest December 17, 2015 | Flag Reply
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)

- Sunny January 17, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More