Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
public class ArrayMatch {
public static void main(String[] args) {
String words[] = { "cc", "cb", "bb", "ac" };
char ordering[] = { 'b', 'c', 'a' };
System.out.println(checkIfSortedArray(words, ordering));
}
private static boolean checkIfSortedArray(String[] words, char[] ordering) {
boolean b = true;
int j = 0;
for (int i = 0; i < words.length; i++) {
if (getFirstMismatch(words[i], ordering[j])) {
continue;
} else if (getFirstMismatch(words[i], ordering[++j])) {
continue;
} else {
b = false;
}
}
return b;
}
public static boolean getFirstMismatch(String str1, char ordering) {
return str1.startsWith(String.valueOf(ordering));
}
}
charOrder = []
def inOrder(left,right):
# print left, right, charOrder
i = 0
while (left[i] != '\0' and right[i] != '\0'):
# print left[i],ord(left[i]),'++',right[i],ord(right[i]),i
# print ord(left[i]),charOrder[ord(left[i]) - ord('a')],'--',ord(right[i]),charOrder[ord(right[i]) - ord('a')]
if charOrder[ord(left[i]) - ord('a')] > charOrder[ord(right[i]) - ord('a')]:
return 0
elif charOrder[ord(left[i]) - ord('a')] < charOrder[ord(right[i]) - ord('a')]:
return 1
i = i+1
if left[i] == '\0':
# print 'hello'
return 1
return 0
def recursiveInorder(char_array,left,right):
if left==right:
return 1
mid = (left + right) / 2
# print mid
l = recursiveInorder(char_array,left,mid)
r = recursiveInorder(char_array,mid+1,right)
if l == 0 or r == 0:
return 0
lString = char_array[mid]
rString = char_array[mid + 1]
return inOrder(lString,rString)
char_array = ["cc\0", "cb\0", "bb\0","ac\0"]
order = ['c','b','a']
for i in range(26):
charOrder.append(27)
for i in range(len(order)):
charOrder[ord(order[i]) - ord('a')] = i
print recursiveInorder(char_array,0,len(char_array)-1)
charOrder = []
def inOrder(left,right):
# print left, right, charOrder
i = 0
while (left[i] != '\0' and right[i] != '\0'):
# print left[i],ord(left[i]),'++',right[i],ord(right[i]),i
# print ord(left[i]),charOrder[ord(left[i]) - ord('a')],'--',ord(right[i]),charOrder[ord(right[i]) - ord('a')]
if charOrder[ord(left[i]) - ord('a')] > charOrder[ord(right[i]) - ord('a')]:
return 0
elif charOrder[ord(left[i]) - ord('a')] < charOrder[ord(right[i]) - ord('a')]:
return 1
i = i+1
if left[i] == '\0':
# print 'hello'
return 1
return 0
def recursiveInorder(char_array,left,right):
if left==right:
return 1
mid = (left + right) / 2
# print mid
l = recursiveInorder(char_array,left,mid)
r = recursiveInorder(char_array,mid+1,right)
if l == 0 or r == 0:
return 0
lString = char_array[mid]
rString = char_array[mid + 1]
return inOrder(lString,rString)
char_array = ["cc\0", "cb\0", "bb\0","ac\0"]
order = ['c','b','a']
for i in range(26):
charOrder.append(27)
for i in range(len(order)):
charOrder[ord(order[i]) - ord('a')] = i
print recursiveInorder(char_array,0,len(char_array)-1)
charOrder = []
def inOrder(left,right):
# print left, right, charOrder
i = 0
while (left[i] != '\0' and right[i] != '\0'):
# print left[i],ord(left[i]),'++',right[i],ord(right[i]),i
# print ord(left[i]),charOrder[ord(left[i]) - ord('a')],'--',ord(right[i]),charOrder[ord(right[i]) - ord('a')]
if charOrder[ord(left[i]) - ord('a')] > charOrder[ord(right[i]) - ord('a')]:
return 0
elif charOrder[ord(left[i]) - ord('a')] < charOrder[ord(right[i]) - ord('a')]:
return 1
i = i+1
if left[i] == '\0':
# print 'hello'
return 1
return 0
def recursiveInorder(char_array,left,right):
if left==right:
return 1
mid = (left + right) / 2
# print mid
l = recursiveInorder(char_array,left,mid)
r = recursiveInorder(char_array,mid+1,right)
if l == 0 or r == 0:
return 0
lString = char_array[mid]
rString = char_array[mid + 1]
return inOrder(lString,rString)
char_array = ["cc\0", "cb\0", "bb\0","ac\0"]
order = ['c','b','a']
for i in range(26):
charOrder.append(27)
for i in range(len(order)):
charOrder[ord(order[i]) - ord('a')] = i
print recursiveInorder(char_array,0,len(char_array)-1)
Solution with Time Complexity O(n) and SpaceComplexity O(m) m => number of unique chars n=> number of strings
private bool IsSortedCorrectly()
{
Dictionary<char, int> rank = ConvertToRank(Ordering);
string prev = null;
foreach (var str in Words)
{
if (!IsInCorrectOrder(rank, prev, str))
{
return false;
}
prev = str;
}
return true;
}
bool IsInCorrectOrder(Dictionary<char, int> rank, string prev, string str)
{
if (rank != null && !string.IsNullOrEmpty(prev) && !string.IsNullOrEmpty(str))
{
int len = prev.Length > str.Length ? str.Length : prev.Length;
for (int i = 0; i < len; i++)
{
var prevChar = prev[i];
var currChar = str[i];
if (!rank.ContainsKey(prevChar) || !rank.ContainsKey(currChar))
{
throw new ArgumentException("Key not found!");
}
if (rank[prevChar] < rank[currChar])
{
return true;
}
if (rank[prevChar] > rank[currChar])
{
return false;
}
}
}
return true;
}
Dictionary<char, int> ConvertToRank(char[] ordering)
{
var rank = new Dictionary<char, int>();
int rankValue = 0;
foreach (var c in ordering)
{
if (!rank.ContainsKey(c))
{
rank.Add(c, rankValue++);
}
else
{
throw new ArgumentException("Duplicate Key!");
}
}
return rank;
}
def isSorted(words,order):
''' Returns True if all words in words[] are sorted as per order[] else return False
'''
locations={}
for i,c in enumerate(order):
locations[c]=i
for i in range(len(words)-1):
index = first_mismatch(words[i],words[i+1])
if index==-2 or index!=-1 and locations[words[i][index]]>locations[words[i+1][index]]:
return False
return True
def first_mismatch(a,b):
'''
Compares the two words and returns the first index of non-matching characters.
Returns -1 if words are same or sorted.
'''
for i in range(min(len(a),len(b))):
if a[i]!=b[i]: return i
if len(a)>len(b): return -2 #Not Sorted
return -1
words=['cba','cb','bb','ab']
order=['c','b','a']
print('True') if isSorted(words,order) else print('False')
public void checkOrder(String[] words, char[] ordering) {
List<Character> temp = new ArrayList<>();
for (String word: words) {
for ( char order: ordering) {
if(word.startsWith(String.valueOf(order)) == true && !temp.contains(order)) {
temp.add(order);
}
}
}
int i = 0, count = 0;
for (char order: temp) {
if (order == ordering[i]) {
count++;
}
i++;
}
if (count == ordering.length) {
System.out.println("Order matched");
} else {
System.out.println("No order matched");
}
}
public void checkOrder(String[] words, char[] ordering) {
List<Character> temp = new ArrayList<>();
for (String word: words) {
for ( char order: ordering) {
if(word.startsWith(String.valueOf(order)) == true && !temp.contains(order)) {
temp.add(order);
}
}
}
int i = 0, count = 0;
for (char order: temp) {
if (order == ordering[i]) {
count++;
}
i++;
}
if (count == ordering.length) {
System.out.println("Order matched");
} else {
System.out.println("No order matched");
}
}
def isOrderedArray(array: Vector[String], order: Vector[String]): Boolean = {
def isOrderedArrayImpl(array: Vector[String], order: Vector[String]): Boolean = {
if(array.isEmpty) true
else if(array.nonEmpty && order.isEmpty) false
else {
val currentOrder: String = order.head
val nextLevelVector: Vector[String] = getVectorAfterFirstMismatch(array, currentOrder)
isOrderedArrayImpl(nextLevelVector, order.tail)
}
}
def getVectorAfterFirstMismatch(vector: Vector[String], key: String): Vector[String] = {
if(vector.isEmpty) Vector.empty
else if(!isPrefix(vector.head, key)) vector
else getVectorAfterFirstMismatch(vector.tail, key)
}
def isPrefix(string: String, key: String): Boolean = {
if(string.length < key.length) false
else {
val result = string.take(key.length) == key
result
}
}
isOrderedArrayImpl(array, order)
}
My O(N) solution in js
const isOrdered = (words, order) => {
let orderIndex = 0;
let firstLetter = words[0].charAt(0);
for(let i = 0; i < words.length; i++) {
let prevFirstLetter = firstLetter;
firstLetter = words[i].charAt(0);
if(prevFirstLetter !== firstLetter) {
orderIndex++;
}
if(firstLetter !== order[orderIndex]) {
return false;
}
}
return true;
}
console.log(isOrdered(['cc', 'cb', 'bb', 'ac'], ['c', 'b', 'a']));
console.log(isOrdered(['cc', 'cb', 'bb', 'ac'], ['b', 'c', 'a']));
public static void main(String args[]) throws Exception {
String words[] = { "cc", "cb", "bb", "ac" };
char ordering[] = { 'b', 'c', 'a' };
System.out.println(checkIfSortedArray(words, ordering));
}
public static boolean checkIfSortedArray(String strs[], char orderings[]) {
Map<Character, Integer> map = new HashMap();
for (int i = 0; i < orderings.length; i++) {
map.put(orderings[i], i);
}
for (int i = 1; i < strs.length; i++) {
int mismatch = getFirstMismatch(strs[i - 1], strs[i]);
if (mismatch != -1) {
char from = strs[i - 1].toCharArray()[mismatch];
char to = strs[i].toCharArray()[mismatch];
if (map.get(from) > map.get(to))
return false;
}
}
return true;
}
public static int getFirstMismatch(String str1, String str2) {
char elem[] = str1.toCharArray();
char elem2[] = str2.toCharArray();
return IntStream.range(0, min(elem.length, elem2.length)).filter(temp -> elem[temp] != elem2[temp]).findFirst()
.orElse(-1);
}
- Anonymous June 10, 2018public static boolean isSorted(String[] words, char[] order){ int [] charMap = new int[26]; for(int i = 0; i < order.length; i++){ charMap[order[i] - 'a'] = i+1; } Comparator<String> c = (a, b) -> { for(int i = 0; i < Math.min(a.length(), b.length()); i++){ if(charMap[a.charAt(i) - 'a'] > charMap[b.charAt(i) -'a']){ return 1; } else if(charMap[a.charAt(i) - 'a'] < charMap[b.charAt(i) -'a']){ return -1; } else if(charMap[a.charAt(i) - 'a'] == charMap[b.charAt(i) -'a']){ continue; } } return a.length() - b.length(); }; String[] words2 = Arrays.copyOf(words, words.length); Arrays.sort(words2, c); for(int i = 0 ; i <words.length; i++){ if(!words2[i].equalsIgnoreCase(words[i])){ return false; } } return true; }