Google Interview Question
Data EngineersCountry: United States
const isOrdered = (order, str) => {
const orderRank = order.split("");
let lastSeen = -1;
return str.split("").reduce((accum, val) => {
if (!accum) {
return accum;
}
const lookUp = orderRank.indexOf(val),
isOrdered = (lastSeen <= lookUp) || lookUp === -1;
lastSeen = lookUp;
return isOrdered;
});
};
Have a HashSet that stores the priority (ordering) of the string "abc"
Loop through characters of the given string, for each character check the priority
If the priority is not present OR if priority is same, go to the next character
Else If the priority is greater, increase the current_seen priority and go to the next character
Else return false
If reached end of string, return true
Time complexity: O(n + m)
Space complexity: O(1), assuming both strings are ASCII
public static boolean checkOrder(String pattern, String str) {
int[] label = new int[128];
int order = 1;
for (char c : pattern.toCharArray()) {
label[c] = order;
order++;
}
int lastOrder = -1;
for (char c : str.toCharArray()) {
int currOrder = label[c];
if (currOrder == 0) continue;
if (lastOrder != -1 && currOrder < lastOrder) return false;
lastOrder = currOrder;
}
return true;
}
- Anonymous January 20, 2018