LinkedIn
4.5 of 5 789 reviews
www.linkedin.com Mountain View, CA 5000+ Employees

LinkedIn Principal Software Engineer Interview Question

"Given a large document and a short pattern consisting of a few words (eg. W1 W2 W3), find the shortest string that has all the words in any order (for eg. W2 foo bar dog W1 cat W3 -- is a valid pattern)"
Add Tags [?]
Answer Flag Question

Part of a Principal Software Engineer Interview Review - one of 461 LinkedIn Interview Reviews

Answers & Comments

0
of 0
votes
import java.util.*;

class Untitled {
    public static void main(String[] args) {
        String[] strs = {"a","b","d","e","x","b","z","s","x","c","e","c","d","b"};
        String[] pattern = {"b","z","x"};

        getMin(strs, pattern);
    }

    private static void getMin(String[] strs, String[] pattern){

        //initialize the set
        HashSet<String> set = new HashSet<String>();
        for(int i = 0; i < pattern.length; i++){
            set.add(pattern[i]);
        }

        int tail = 0;
        int head = 0;
        int min = Integer.MAX_VALUE;
        int min_tail, min_head;
        //initialize map
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(head = 0; head < strs.length && map.size() < pattern.length; head++){
            if(!set.contains(strs[head])) continue;
            if(map.containsKey(strs[head])){
                map.put(strs[head], map.get(strs[head])+1);
            }else{
                map.put(strs[head], 1);
            }
        }

        if(map.size() < pattern.length){
            System.out.println("No such pattern!");
            return;
        }

        min = head - tail;
        min_tail = tail;
        min_head = head;

        //find the min seq
        while(head < strs.length || canTailMove(map, strs, tail)){
            if(canTailMove(map, strs, tail)) {
                if(map.containsKey(strs[tail])){
                    map.put(strs[tail], map.get(strs[tail])-1);
                }
                tail++;
                if((head - tail) < min){
                    min = head - tail;
                    min_tail = tail;
                    min_head = head;
                }
            }else{
                if(map.containsKey(strs[head])){
                map.put(strs[head], map.get(strs[head])+1);
                }
                head++;
            }
        }

        for(int i = min_tail; i < min_head; i++){
            System.out.print(strs[i]+"\t");
        }
        System.out.println("\n"+min_tail+"\t"+(min_head-1));

    }

    private static boolean canTailMove(HashMap<String, Integer> map, String[] strs, int position){
        if (!map.containsKey(strs[position])) return true;
        if (map.get(strs[position]) <= 1) return false;
        return true;
    }

}
- clouder on Feb 22, 2012 Flag Response
0
of 0
votes
Could you please explain this??
- Anonymous on Apr 26, 2012 Flag Response
1
of 1
vote
This is a classic minimal window problem described in detail here - http://www.leetcode.com/2010/11/finding-minimum-window-in-s-which.html.
- foobar on Jun 21, 2012 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at LinkedIn interview questions and advice. All interview reviews posted anonymously by LinkedIn employees and interview candidates.