Expedia Tech Interview

Expedia Software Engineer Interview

Given a list of words initially, write a method that takes in a word, and returns all known anagrams.
Two words are anagrams if they have the same characters, but not necessarily in the same order.
You can do whatever setup you want in order to make the method fast.
ex:
known words: {cat, dog, bird, act, god}
input: tca
output: {cat, act}

We learn Fundamental Theorem of Arithmetic in Linear Algebra class, but we hardly use the Theorem in real life.
Here is real life application for Fundamental Theorem of Arithmetic, you can impress you friends or co-workers

Use Prime Number to Solve anagram problem [ Fundamental Theorem of Arithmetic ]

1. Map each prime to each alphabet and compute the product
dog = $7 \times 53 \times 17 = 6307$
god = $17 \times 53 \times 7 = 6307$

2. Map each product to list of words
$6307 \rightarrow \{dog, god\}$

public static Map<String, Integer> primeMap() {
        List<Integer> list = getPrime(26);
        Map<String, Integer> map = new HashMap<String, Integer>();
        char ch = 'a';
        for(Integer p : list) {
            map.put(ch + "", p);
            ch += 1;
        }
        return map;
    }

    public static Integer getProduct(String str) {
        Map<String, Integer> map = primeMap();
        int p = 1;
        for(int i=0; i<str.length(); i++) {
            p *= map.get((str.charAt(i) + "").toLowerCase());
        }
        return p;
    }

    public static List<String> anagrams(List<String> list, String str) {
        Map<Integer, List<String> > map = new HashMap<Integer, List<String>>();

        for(String s : list) {
            List<String> l = map.get(getProduct(s));
            if(l != null) {
                l.add(s);
                map.put(getProduct(s), l);
            } else {
                List<String> ll = new ArrayList<String>();
                ll.add(s);
                map.put(getProduct(s), ll);
            }
        }
        return map.get(getProduct(str));
    }

Source Code

Expedia Software Engineer Interview

Given a list of list Integer, find the intersection of all the lists
Input:
list0 = [0] = {2, 1, 1}
list1 = [1] = {7, 5, 1}
list2 = [2] = {4, 5, 5, 1}

Return:
retList = {5, 1}

Algorithm and Data Structure to Solve it

We can map each Integer in a list to Index of the list
e.g.
$2 \rightarrow \{0\}$
2 is the element of list0
0 is the index of list0
$7 \rightarrow \{1\}$
7 is the element of list1
1 is the index of list1

process list0
$2 \rightarrow \{0\}$
$1 \rightarrow \{0\}$

process list1
$7 \rightarrow \{1\}$
$5 \rightarrow \{1\}$
$1 \rightarrow \{0, 1\}$

process list2
$4 \rightarrow \{2\}$
$5 \rightarrow \{1, 2\}$
$1 \rightarrow \{0, 1, 2\}$

Only 1 map to three indices. {0, 1, 2} so 1 is the intersection of three lists

public static List<Integer> intersection(List<List<Integer>> lists) {
        List<Integer> retList = new ArrayList<Integer>();
        if(lists != null) {
            Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();

            for (int i = 0; i < lists.size(); i++) {
                List<Integer> list = lists.get(i);

                for (Integer n : list) {
                    Set<Integer> set = map.get(n);
                    if (set != null) {
                        set.add(i);
                        map.put(n, set);
                    } else {
                        Set<Integer> nSet = new HashSet<Integer>();
                        nSet.add(i);
                        map.put(n, nSet);
                    }
                }
            }
            for (Map.Entry<Integer, Set<Integer>> entry : map.entrySet()) {
                Integer n = entry.getKey();
                Set<Integer> set = map.get(n);
                if (set.size() == lists.size())
                    retList.add(n);
            }
        }
        return retList;
    }

Source Code

Use sort technic to solve anagram problem

//================================================================================ 
    // java anagram 
    // Use sort technic to solve anagrams problem 
    // Use sorted str as key
    // {dog, god}
    // dgo->{dog, god}
    // -------------------------------------------------------------------------------- 
    static String sortStr(String s) {
        char[] clist = s.toCharArray();
        Arrays.sort(clist);
        return String.valueOf(clist);
    }
    static List<String> anagrams(List<String> list, String input) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();

        if(list != null && input != null) {

            for(String str : list) {
                String key = sortStr(str);
                List<String> l = map.get(key);
                if(l != null) {
                    l.add(str);
                    map.put(key, l);
                } else {
                    List<String> ll = new ArrayList<String>();
                    ll.add(str);
                    map.put(key, ll);
                }
            }
        }
        return map.get(sortStr(input));
    }

Source Code