Linkedin Interview Question for Software Engineer / Developers


Country: United States




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

My solution in ruby.

def repeatSubstring2(str, len)
  return false if str.length < len or len == 0
  str.downcase!
  subHash = {}
  resultArray = []
  # Add substring to hash
  (0..str.length - len).each do |i|
    subString = str[i..i+len-1]
    if subHash.has_key? subString
      subHash[subString] += 1
      resultArray.push subString
    else
      subHash[subString] = 1
    end
  end
  # Sort resultArray alphabetically
  puts resultArray.sort.join ' '
end

- jiasilu1987 January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- sam January 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The space requirement for a suffix tree is not necessarily less than that of a hash table.

- sabz July 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- techpanja January 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

github.com/techpanja/interviewproblems/blob/master/src/strings/repeatingstringsofspecifiedlength/RepeatingStringOfSpecificLength.java

- techpanja January 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

URL not workin

- juny January 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It works. Just append https : // in the beginning. complete links are not allowed in comments.

- techpanja January 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Killedsteel February 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nishant, In java 6 , substring function on string is constant time :)

- Anon February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anon Java 7 its O(n) time. Post Java 7 update 6.
Also i think we cannot go with evaluating time complexity on the basis of programming language.

- Karthik September 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kirankumarcelestial January 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,
Can you please explain your code ?

- Shekhar February 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

- Nilesh Salpe January 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

- Nilesh Salpe January 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anonymous January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous January 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- puneet.sohi February 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- Jeremy.Shi February 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- jellyenigma February 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Cdr February 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Boris Marchenko July 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sabz July 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- shobhit August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ps August 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sLion August 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- anonymous March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- bruce January 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous January 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

thanks very useful.........

- janagan April 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

    }
}

- pugal January 14, 2018 | 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