LinkedIn

  www.linkedin.com
  www.linkedin.com

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<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
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 Question, Sign In with Facebook or Sign Up