[Hard] interview questions #17

[rygh4775]

Multi Search: Given a string b and an array of smaller strings T, design a method to search b for each small string in T.

[tgi01054]

Example

b = "mississippi" T = {"is","ppi","hi","sis","i","ssippi"}

Solution 1

    public static boolean isSubstringAtLocation(String big, String small, int offset) {
        for (int i = 0; i < small.length(); i++) {
            if (big.charAt(offset + i) != small.charAt(i)) {
                return false;
            }
        }
        return true;
    }

    public static ArrayList<Integer> search(String big, String small) {
        ArrayList<Integer> locations = new ArrayList<Integer>();
        for (int i = 0; i < big.length() - small.length() + 1; i++) {
            if (isSubstringAtLocation(big, small, i)) {
                locations.add(i);
            }
        }
        return locations;
    }

    public static HashMapList<String, Integer> searchAll(String big, String[] smalls) {
        HashMapList<String, Integer> lookup = new HashMapList<String, Integer>();
        for (String small : smalls) {
            ArrayList<Integer> locations = search(big, small);
            lookup.put(small, locations);
        }
        return lookup;
    }

    public static void main(String[] args) {
        String big = "mississippi";
        String[] smalls = {"is", "ppi", "hi", "sis", "i", "mississippi"};
        HashMapList<String, Integer> locations = searchAll(big, smalls);
        System.out.println(locations.toString());
    }

Time complexity

O(kbt)

• k: length of the longest string in T
• b: length of the string b
• t: number of smaller strings within T

Solution 2

Example: bibs List of suffix: bibs, ibs, bs, s

Time complexity

O(b^2+kt)

• build trie: O(b^2) Worst case build cost in Trie: O(mn) ** m: longest word n: number of word
• search: O(kt)
• k: length of the longest string in T
• b: length of the string b
• t: number of smaller strings within T

Solution 3

Conclusion

• Solution 1: O(kbt)
• Solution 2: O(b^2+kt) if b is very large, sol 1 is good. if t is very large, sol 2 is good.