Phone Screen @Uber Oct. 26th, 2015

Given a pattern and an input string, check if the input string matches the pattern.

Eg.
pattern: abab
input: howwhathowwhat
mapping: a => how, b => what
so match(abab, howwhathowwhat) -> true
match(abab, whathowhowwhat) -> false
match(“”, “”) -> true
match(“a”, “a”) -> true
match(“ab”, “abab”) -> true
match(“aaaa”, “howwhatwhathow”) -> false
match(“aaaa”, “whatwhatwhatwhat”) -> true

Each char in pattern string can match 1-n chars in input string. Same char can only match same string. Different chars can match same strings.

class Solution {
    public boolean match(String pattern, String input) {
        if (pattern == null || input == null || input.length() < pattern.length()) {
            return false;
        }
        Map<Character, String> map = new HashMap<>();
        return matchHelper(pattern, 0, input, 0, map);
    }

    public boolean matchHelper(String pattern, int index, String input, int inputIndex, Map<Character, String> map) {
        if (index == pattern.length()) {
            if (inputIndex == input.length()) {
                return true;
            }
            return false;
        }
        char c = pattern.charAt(index);

        if (map.containsKey(c)) {
            String val = map.get(c);
            if (inputIndex + val.length() <= input.length() && val.equals(input.substring(inputIndex, inputIndex + val.length()))) {
                return matchHelper(pattern, index + 1, input, inputIndex + val.length(), map);
            }
        } else {
            for (int i = inputIndex; i < input.length(); i++) {
                String val = input.substring(inputIndex, i + 1);
                map.put(c, val);
                if (matchHelper(pattern, index + 1, input, i + 1, map)) {
                    return true;
                }
                map.remove(c);
            }
        }
        return false;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.match("", "")); //true
        System.out.println(s.match("a", "a")); //true
        System.out.println(s.match("ab", "abab")); //true
        System.out.println(s.match("abab", "howwhathowwhat")); //true
        System.out.println(s.match("abab", "howwhatwhathow")); //false
        System.out.println(s.match("aaaa", "howwhatwhathow")); //false
        System.out.println(s.match("aaaa", "whatwhatwhatwhat")); //true
    }
}
FacebookTwitterGoogle+Share

Phone Screen @AppDynamics

Position: Software Engineer (Data Platform)

  1. Questions about resume
  2. Technical Questions
    Similar to Wildcard Matching but difference is follows:
    Implement wildcard pattern matching with support for '.' and '*'.

    • '.' Matches any single character.
    • '*' Matches zero or more of the preceding character.

    The matching should cover the entire input string (not partial).

     Example
    isMatch("aa","a") → false
    isMatch("aa","aa") → true
    isMatch("a","*") → false //since there is no preceding char of *isMatch("aa","**") → false //* can not be preceding char of another *
    isMatch("aa",".*") → true
    isMatch("aaa","aa") → false
    isMatch("aa", "a*") → true
    isMatch("a", ".*") → true
    isMatch("aab", "c*a*b") → true

Solution:

 

Phone Screen @Box

Position: Software Engineer, Full Stack/Developer Experience

  1. Introduce what they are working on
  2. Technical Questions
    1. Merge two sorted array: just describe the algorithm and time complexity
    2. Merge K sorted array: write the code.
    3. Two Sum: an sorted array, find if there is at least a pair of two elements which the sum equals 0. Just describe the algorithm and time complexity.
      I gave him two approaches: using HashMap and two pointers.
      Then he asked me to write the code with two pointers.
    4. Three Sum: just describe the algorithm and time complexity.