LinkedIn Interview Question: Given a large document and a ... | Glassdoor

Interview Question

Principal Software Engineer Interview

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

Interview Answer

3 Answers

0

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 set = new HashSet();
        for(int i = 0; i map = new HashMap();
        for(head = 0; head 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
0

Could you please explain this??

Anonymous on Apr 26, 2012
2

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.