# 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
}
}```
Share

# Phone Screen @AppDynamics

Position: Software Engineer (Data Platform)

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.