Facebook Interview Question Software Engineers
Country: United States
function isOrdered(words, ordering) {
let oIdx = 0
let oIdxCount = 0
for (let i = 0; i < words.length; i++) {
const first = words[i].charAt(0)
if (first === ordering[oIdx]) {
oIdxCount++
}
else if (first !== ordering[oIdx] && oIdxCount > 0 && first === ordering[oIdx+1]) {
oIdx++
oIdxCount = 1
}
else {
return false
}
}
return oIdx == ordering.length-1
}
console.log(isOrdered(['cc', 'cb', 'bb', 'ac'], ['c', 'b', 'a']))
console.log(isOrdered(['cc', 'cb', 'bb', 'ac'], ['b', 'c', 'a']))
#include <iostream>
int charOrder[ 26 ];
int isInOrder( char *left, char *right )
{
int i = 0;
while( right[ i ] != '\0' && left[ i ] != '\0')
{
if( charOrder[ left[ i ] - 'a'] > charOrder[ right[i] - 'a'] )
{
return 0;
}
else if( charOrder[ left[ i ] - 'a'] < charOrder[ right[i] - 'a'])
return 1;
i++;
}
if( left[ i ] == '\0')
{
return 1;
}
return 0;
}
int recursiveInOrder( char array[][4], int left, int right )
{
char *lString, *rString;
int mid;
if( left == right )
return 1;
mid = (left + right) / 2;
int l = recursiveInOrder( array, left, mid);
int r = recursiveInOrder(array, mid+1, right);
if( l == 0 || r == 0 )
return 0;
lString = array[ mid ];
rString = array[ mid + 1];
return isInOrder( lString, rString );
}
int main(int argc, const char * argv[]) {
char array[][4] = {"cc", "cb", "bb","ac"};
char order[]={'b','c','a'};
int i = 0;
for( i = 0; i < 26; i++ )
{
charOrder[ i ] = 27;
}
for( i = 0; i < 3; i++ )
{
charOrder[ order[ i ] - 'a' ] = i;
}
std::cout << recursiveInOrder( array, 0, 3);
return 0;
}
#include <iostream>
int charOrder[ 26 ];
int isInOrder( char *left, char *right )
{
int i = 0;
while( right[ i ] != '\0' && left[ i ] != '\0')
{
if( charOrder[ left[ i ] - 'a'] > charOrder[ right[i] - 'a'] )
{
return 0;
}
else if( charOrder[ left[ i ] - 'a'] < charOrder[ right[i] - 'a'])
return 1;
i++;
}
if( left[ i ] == '\0')
{
return 1;
}
return 0;
}
int recursiveInOrder( char array[][4], int left, int right )
{
char *lString, *rString;
int mid;
if( left == right )
return 1;
mid = (left + right) / 2;
int l = recursiveInOrder( array, left, mid);
int r = recursiveInOrder(array, mid+1, right);
if( l == 0 || r == 0 )
return 0;
lString = array[ mid ];
rString = array[ mid + 1];
return isInOrder( lString, rString );
}
int main(int argc, const char * argv[]) {
char array[][4] = {"cc", "cb", "bb","ac"};
char order[]={'b','c','a'};
int i = 0;
for( i = 0; i < 26; i++ )
{
charOrder[ i ] = 27;
}
for( i = 0; i < 3; i++ )
{
charOrder[ order[ i ] - 'a' ] = i;
}
std::cout << recursiveInOrder( array, 0, 3);
return 0;
}
if( process.argv.length<4 ) {
console.log("USAGE: %s words_separated_by_comma orderding_separated_by_comma",process.argv[1]);
}
else {
const ordering = {};
process.argv[3].split(',').forEach(function(letter,ndx) {
ordering[letter[0]] = ndx;
});
//console.log(ordering);
let previous_value = Math.NEGATIVE_INFINITY;
// Among the words, find the first one that is "less" than the previoud
if( process.argv[2].split(',').find(function(word) {
let current_value = 0;
for( let n=0; n<word.length; n++ ) {
if( !ordering.hasOwnProperty(word[n]) ) {
console.log("Found letter '%s' that does not have an order",word[n]);
process.exit(-1);
}
current_value = (current_value*256)+ordering[word[n]];
}
//console.log("Value of %s is %d, previous_value is %d",word,current_value,previous_value);
if( current_value<previous_value )
return true;
previous_value = current_value;
return false;
}) ) {
// This means that we found the element that is "less" then the previous one
// This means that the words are not "ordered"
console.log("False");
}
else {
console.log("True");
}
}
I present two solutions here.
One is the brute force solution which basically involves comparing every word with every letter to see if the words are ordered. This takes O(M*N) where M is the number of the words and N is the number of letters.
The more optimized way which can be done is O(M) time is where you have two pointers which point to the words list and the letters list respectively. As soon as you encounter the first mismatch, return False immediately. Else, if the traversal through the entire list is successful, then return True.
def isOrderedBruteForce(words, ordering):
letter_index = 0
word_index = 0
while letter_index < len(ordering):
cur_word = words[word_index]
cur_letter = ordering[letter_index]
while cur_word.startswith(cur_letter):
word_index += 1 # Move to the next word
if word_index == len(words):
return True
cur_word = words[word_index]
letter_index += 1
if letter_index < len(ordering) and not words[word_index].startswith(ordering[letter_index]):
return False
return False
def isOrderedOptimized(words, ordering):
letter_index = 0
for word_index, word in enumerate(words):
if word.startswith(ordering[letter_index]):
continue
elif letter_index+1 < len(ordering) and word.startswith(ordering[letter_index+1]):
letter_index += 1
continue
else:
return False
return True
print(isOrderedBruteForce(['cc','cb','bb','ac'], ['c','b','a'])) # True
print(isOrderedBruteForce(['cc','cb','bb','ac'], ['b','c','a'])) # False
print(isOrderedBruteForce(['cc','cb','bb','ac','cat', 'aab'], ['c','b','a'])) # False
print('-' * 15)
print(isOrderedOptimized(['cc','cb','bb','ac'], ['c','b','a'])) # True
print(isOrderedOptimized(['cc','cb','bb','ac'], ['b','c','a'])) # False
print(isOrderedOptimized(['cc','cb','bb','ac','cat', 'aab'], ['c','b','a'])) # False
// let's assume only 26 characters, all lower case
// a >= b
bool is_greater_or_equal(const string& a, const string& b, const vector<int>& rank) {
size_t l = min(a.size(), b.size());
for (size_t i = 0; i < l; ++i) {
int ao = rank[a[i] - 'a'];
int bo = rank[b[i] - 'a'];
if (ao != bo) return ao > bo;
}
return a.size() >= b.size();
}
int main()
{
vector<string> words{"cc", "cb", "bb", "ac" };
vector<char> ordering{ 'c', 'b', 'a' };
vector<int> rank(26, -1);
int i = 0;
for (char c : ordering) rank[c - 'a'] = i++;
for (size_t i = 1; i < words.size(); ++i) {
if (!is_greater_or_equal(words[i], words[i - 1], rank)) {
cout << "not ordered";
return 1;
}
}
cout << "ordered";
return 0;
private Dictionary<char, int> orderRank;
public static bool CheckOrder(string [] words, char[] order)
if(order.Length == 0 || words.Length <= 1) return true;
orderRank = buildRanking(order); // O(m)
for(int i = 1; i < words.Length; i++){ // n
string previous = words[i - 1]; // k
string current = words[i];
for(int k = 0; k < current.Length && k < previous.Length; k++){
if(orderRank[current[k]] > orderRank[previous[k]]){
break;
}else if(orderRank[current[k]] == orderRank[previous[k]]){
continue;
}else{
return false;
}
}
}
return true;
}
private void buildRanking(char[] order){
for(int i =0; i < order.Length; i++){
if(!orderRank.ContainsKey(order[i)){
orderRank.Add(order[i], i+1);
}else{
// no duplicates
}
}
}
def check_order(words, ordering):
order_dict = dict((ordering[i], i) for i in range(0, len(ordering)))
max_len = _get_max_len(words)
return _is_in_order([_convert(word, order_dict, max_len) for word in words])
def _convert(word, order_dict, max_digit):
cur_digit = max_digit
result = 0
for c in word:
result += order_dict[c] * 26 * cur_digit
cur_digit -= 1
return result
def _get_max_len(words):
result = 0
for word in words:
if len(word) > result:
result = len(word)
return result
def _is_in_order(converted):
prev = 0
for i in converted:
if i < prev:
return False
prev = i
return True
print check_order(['cc', 'cb', 'bb', 'ac'], ['c', 'b', 'a']) # True
print check_order(['cc', 'cb', 'bb', 'ac'], ['b', 'c', 'a']) # False
O(N) solution
def check_order(words, ordering):
order_dict = dict((ordering[i], i) for i in range(0, len(ordering)))
max_len = _get_max_len(words)
return _is_in_order([_convert(word, order_dict, max_len) for word in words])
def _convert(word, order_dict, max_digit):
cur_digit = max_digit
result = 0
for c in word:
result += order_dict[c] * 26 * cur_digit
cur_digit -= 1
return result
def _get_max_len(words):
result = 0
for word in words:
if len(word) > result:
result = len(word)
return result
def _is_in_order(converted):
prev = 0
for i in converted:
if i < prev:
return False
prev = i
return True
print check_order(['cc', 'cb', 'bb', 'ac'], ['c', 'b', 'a']) # True
print check_order(['cc', 'cb', 'bb', 'ac'], ['b', 'c', 'a']) # False
import java.util.HashMap;
public class CheckOrdering {
public boolean run(String[] input, String[] order){
HashMap<Character, Integer> orderValues = new HashMap<Character, Integer>();
fillHashMap(order, orderValues);
int prevOrderValue = 0;
for(int i = 0; i < input.length; ++i)
{
String toCheck = input[i];
int orderValue = 0;
for(int j = 0; j < toCheck.length(); ++j){
char charToCheck = toCheck.charAt(j);
if(orderValues.containsKey(charToCheck)) {
int value = orderValues.get(charToCheck);
orderValue *= 10;
orderValue += value;
}
else return false;
}
if(prevOrderValue > orderValue) return false;
prevOrderValue = orderValue;
}
return true;
}
private void fillHashMap(String[] order, HashMap<Character, Integer> orderValues){
for(int i = 0; i < order.length; ++i)
{
if(!orderValues.containsKey(order[i])){
orderValues.put(order[i].charAt(0), i);
}
}
}
CheckOrdering checkOrdering = new CheckOrdering();
String[] words = new String[] { "cc", "cb", "bb", "ac"};
String[] order = new String[] { "c", "b", "a"};
boolean result = checkOrdering.run(words, order);
System.out.println("result = " + result);
order = new String[] { "b", "c", "a"};
result = checkOrdering.run(words, order);
System.out.println("result = " + result);
This is my solution in swift 4
class wordsChecker{
private var hash = [Character:Int]()
private var currentState = [Int]()
func checkOrder(order:[Character], strings:[String]) -> Bool{
for index in 0..<order.count{
hash[order[index]] = index
}
for word in strings{
if (checkString(word) == false){
return false
}
}
return true
}
private func checkString(_ word:String,_ index:Int = 0) -> Bool{
if (index >= word.count){
//complete currentState with Zeros
completeWithZeros(FromIndex: index)
return true
}
if (index >= currentState.count){
currentState.append(0)
}
let currentChar = word[word.index(word.startIndex, offsetBy: index)]
if (hash[currentChar] != nil){
let currentLetterValue = currentState[index]
guard let currentNewValue = hash[currentChar] else {
return false
}
if (currentLetterValue == currentNewValue){
return checkString(word, index+1)
} else if (currentLetterValue < currentNewValue) {
currentState[index] = currentNewValue
if index+1 < currentState.count{
currentState.removeSubrange(index+1..<currentState.count)
}
return checkString(word, index+1)
} else {
return false
}
} else {
//not know character
return false
}
}
private func completeWithZeros(FromIndex index:Int){
if index <= currentState.count{
for currentIndex in index..<currentState.count{
currentState[currentIndex] = 0
}
}
}
}
This is my solution with Swift 4
class wordsChecker{
private var hash = [Character:Int]()
private var currentState = [Int]()
func checkOrder(order:[Character], strings:[String]) -> Bool{
for index in 0..<order.count{
hash[order[index]] = index
}
for word in strings{
if (checkString(word) == false){
return false
}
}
return true
}
private func checkString(_ word:String,_ index:Int = 0) -> Bool{
if (index >= word.count){
//complete currentState with Zeros
completeWithZeros(FromIndex: index)
return true
}
if (index >= currentState.count){
currentState.append(0)
}
let currentChar = word[word.index(word.startIndex, offsetBy: index)]
if (hash[currentChar] != nil){
let currentLetterValue = currentState[index]
guard let currentNewValue = hash[currentChar] else {
return false
}
if (currentLetterValue == currentNewValue){
return checkString(word, index+1)
} else if (currentLetterValue < currentNewValue) {
currentState[index] = currentNewValue
if index+1 < currentState.count{
currentState.removeSubrange(index+1..<currentState.count)
}
return checkString(word, index+1)
} else {
return false
}
} else {
//not know character
return false
}
}
private func completeWithZeros(FromIndex index:Int){
if index <= currentState.count{
for currentIndex in index..<currentState.count{
currentState[currentIndex] = 0
}
}
}
}
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 static boolean checkOrder(String[] strs, Character[] order) {
HashMap<Character, Double> orderMap = new HashMap<Character, Double>();
Double[] ordering = new Double[strs.length];
for (int i = 0; i < order.length; i++) {
orderMap.put(order[i], new Double(i));
}
for (int i = 0; i < strs.length; i++) {
String currStr = strs[i];
Double sum = 0.0;
for (int j = 0; j < currStr.length(); j++) {
sum += orderMap.get(currStr.charAt(j)) * (1.0 / (j + 1.0));
}
ordering[i] = sum;
}
for (int i = 1; i < ordering.length; i++) {
if (ordering[i] < ordering[i - 1])
return false;
}
return true;
My solution essentially turns the string into Double values, as well as the alphabet. So "c, b, a" would actually be like "0, 1, 2", then I turn the string into a sum so like cc would be 0, cb (the second letter is only matter if the first letter matches, so for the first letter it'd be the value itself, the second letter would be value/2, 3rd letter would be value/3, and etc) would be 0.5, and bb would be 1.5... etc. After turning the string array into a Double Array, then just check if the order is ascending value and you'd know if it is sorted. This is only (M being the number of total chars in the string array, N is the length of the alphabet) O(M + N + M) so pretty much O(M + N).
public static boolean checkOrder(String[] strs, Character[] order) {
HashMap<Character, Double> orderMap = new HashMap<Character, Double>();
Double[] ordering = new Double[strs.length];
for (int i = 0; i < order.length; i++) {
orderMap.put(order[i], new Double(i));
}
for (int i = 0; i < strs.length; i++) {
String currStr = strs[i];
Double sum = 0.0;
for (int j = 0; j < currStr.length(); j++) {
sum += orderMap.get(currStr.charAt(j)) * (1.0 / (j + 1.0));
}
ordering[i] = sum;
}
for (int i = 1; i < ordering.length; i++) {
if (ordering[i] < ordering[i - 1])
return false;
}
return true;
}
Similar Java solution:
private static boolean isSorted(ArrayList<String> words, String order) {
ArrayList<String> sortedWords = new ArrayList<>();
sortedWords.addAll(words);
Collections.sort(words, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
int pos1 = 0;
int pos2 = 0;
for (int i = 0; i < Math.min(o1.length(), o2.length()) && pos1 == pos2; i++) {
pos1 = order.indexOf(o1.charAt(i));
pos2 = order.indexOf(o2.charAt(i));
}
if (pos1 == pos2 && o1.length() != o2.length()) {
return o1.length() - o2.length();
}
return pos1 - pos2;
}
});
return words.toString().contentEquals(sortedWords.toString());
}
public static bool checkInorder(string[] words, char[] ordering)
{
int currentIndex = 0;
Hashtable ord = new Hashtable();
for(int i = 0; i< ordering.Length; i++)
{
if (!ord.Contains(ordering[i]))
{
ord.Add(ordering[i], i + 1);
}
}
for(int x = 0; x < words.Length; x++)
{
if (ord[words[x][0]] == null)
{
return false;
}
if((int)ord[words[x][0]] == currentIndex ||(int) ord[words[x][0]] == currentIndex + 1)
{
currentIndex = (int)ord[words[x][0]];
}
else
{
return false;
}
}
return true;
}
public static bool checkInorder(string[] words, char[] ordering)
{
int currentIndex = 0;
Hashtable ord = new Hashtable();
for(int i = 0; i< ordering.Length; i++)
{
if (!ord.Contains(ordering[i]))
{
ord.Add(ordering[i], i + 1);
}
}
for(int x = 0; x < words.Length; x++)
{
if (ord[words[x][0]] == null)
{
return false;
}
if((int)ord[words[x][0]] == currentIndex ||(int) ord[words[x][0]] == currentIndex + 1)
{
currentIndex = (int)ord[words[x][0]];
}
else
{
return false;
}
}
return true;
}
public static bool checkInorder(string[] words, char[] ordering)
{
int currentIndex = 0;
Hashtable ord = new Hashtable();
for(int i = 0; i< ordering.Length; i++)
{
if (!ord.Contains(ordering[i]))
{
ord.Add(ordering[i], i + 1);
}
}
for(int x = 0; x < words.Length; x++)
{
if (ord[words[x][0]] == null)
{
return false;
}
if((int)ord[words[x][0]] == currentIndex ||(int) ord[words[x][0]] == currentIndex + 1)
{
currentIndex = (int)ord[words[x][0]];
}
else
{
return false;
}
}
return true;
}
public static boolean isOrdered(String[] words, char[] ordering) {
if(words == null || ordering == null) {
throw new IllegalArgumentException("Invalid input!");
}
Map<Integer, Character> ranking = new HashMap<>();
for(int i = 0; i < ordering.length; i++) {
ranking.put(i, ordering[i]);
}
int rank = 0;
int charWordRank = 0;
for(String word: words) {
char c = ranking.get(rank);
if(word.contains(c+"")) {
if(rank < charWordRank) {
return false;
}
rank++;
}
charWordRank++;
}
return true;
}
public static boolean isOrdered(String[] words, char[] ordering) {
if(words == null || ordering == null) {
throw new IllegalArgumentException("Invalid input!");
}
Map<Integer, Character> ranking = new HashMap<>();
for(int i = 0; i < ordering.length; i++) {
ranking.put(i, ordering[i]);
}
int rank = 0;
int charWordRank = 0;
for(String word: words) {
char c = ranking.get(rank);
if(word.contains(c+"")) {
if(rank < charWordRank) {
return false;
}
rank++;
}
charWordRank++;
}
return true;
}
public static boolean isOrdered(String[] words, char[] ordering) {
if(words == null || ordering == null) {
throw new IllegalArgumentException("Invalid input!");
}
Map<Integer, Character> ranking = new HashMap<>();
for(int i = 0; i < ordering.length; i++) {
ranking.put(i, ordering[i]);
}
int rank = 0;
int charWordRank = 0;
for(String word: words) {
char c = ranking.get(rank);
if(word.contains(c+"")) {
if(rank < charWordRank) {
return false;
}
rank++;
}
charWordRank++;
}
return true;
}
public static boolean isOrdered(String[] words, char[] ordering) {
if(words == null || ordering == null) {
throw new IllegalArgumentException("Invalid input!");
}
Map<Integer, Character> ranking = new HashMap<>();
for(int i = 0; i < ordering.length; i++) {
ranking.put(i, ordering[i]);
}
int rank = 0;
int charWordRank = 0;
for(String word: words) {
char c = ranking.get(rank);
if(word.contains(c+"")) {
if(rank < charWordRank) {
return false;
}
rank++;
}
charWordRank++;
}
return true;
}
def is_sorted(array, ordering):
INDEX = {}
for index, char in enumerate(ordering):
INDEX[char] = index
for i in range(len(array) - 1):
word1 = array[i]
word2 = array[i + 1]
index = 0
while index < len(word1) and index < len(word2):
if INDEX[word1[index]] < INDEX[word2[index]]:
break
elif INDEX[word1[index]] > INDEX[word2[index]]:
return False
else:
index += 1
else:
if len(word1) > len(word2):
return False
return True
if __name__ == '__main__':
print is_sorted(['cc', 'cb', 'bb', 'ac'], ['c', 'b', 'a'])
print is_sorted(['cc', 'cb', 'bb', 'ac'], ['b', 'c', 'a'])
print is_sorted(['ccc', 'ccc', 'aaab', 'aaa'], ['b', 'c', 'a'])
print is_sorted(['ccc', 'ccc', 'aaa', 'aaab'], ['b', 'c', 'a'])
def is_sorted(array, ordering):
INDEX = {}
for index, char in enumerate(ordering):
INDEX[char] = index
BASE = len(ordering) # Base of the number system !
previous_score = 0
for word in array:
score = 0
for char in word:
score = score * BASE + INDEX[char]
if score < previous_score:
return False
else:
previous_score = score
return True
function isOrdered(words, ordering) {
let oIdx = 0
let oIdxCount = 0
for (let i = 0; i < words.length; i++) {
const first = words[i].charAt(0)
if (first === ordering[oIdx]) {
oIdxCount++
}
else if (first !== ordering[oIdx] && oIdxCount > 0 && first === ordering[oIdx+1]) {
oIdx++
oIdxCount = 1
}
else {
return false
}
}
return oIdx == ordering.length-1
}
console.log(isOrdered(['cc', 'cb', 'bb', 'ac'], ['c', 'b', 'a']))
console.log(isOrdered(['cc', 'cb', 'bb', 'ac'], ['b', 'c', 'a']))
function isOrdered(words, ordering) {
let oIdx = 0
let oIdxCount = 0
for (let i = 0; i < words.length; i++) {
const first = words[i].charAt(0)
if (first === ordering[oIdx]) {
oIdxCount++
}
else if (first !== ordering[oIdx] && oIdxCount > 0 && first === ordering[oIdx+1]) {
oIdx++
oIdxCount = 1
}
else {
return false
}
}
return oIdx == ordering.length-1
}
console.log(isOrdered(['cc', 'cb', 'bb', 'ac'], ['c', 'b', 'a']))
console.log(isOrdered(['cc', 'cb', 'bb', 'ac'], ['b', 'c', 'a']))
public boolean isWordSorted(List<String> words, List<Character> ordering) {
List<Character> nonDuplicateChars = createNonDuplicateChars(words);
for (int i=0;i<ordering.size();i++) {
if (ordering.get(i) != nonDuplicateChars.get(i)) {
return false;
}
}
return true;
}
private List<Character> createNonDuplicateChars(List<String> words) {
char lastChar = 0;
List<Character> nonDuplicateChars = new ArrayList<>();
for (String word : words) {
char[] wordChars = word.toCharArray();
for (char wordChar : wordChars) {
if (wordChar != lastChar) {
nonDuplicateChars.add(wordChar);
lastChar = wordChar;
}
}
}
return nonDuplicateChars;
}
public boolean isWordSorted(List<String> words, List<Character> ordering) {
List<Character> nonDuplicateChars = createNonDuplicateChars(words);
for (int i=0;i<ordering.size();i++) {
if (ordering.get(i) != nonDuplicateChars.get(i)) {
return false;
}
}
return true;
}
private List<Character> createNonDuplicateChars(List<String> words) {
char lastChar = 0;
List<Character> nonDuplicateChars = new ArrayList<>();
for (String word : words) {
char[] wordChars = word.toCharArray();
for (char wordChar : wordChars) {
if (wordChar != lastChar) {
nonDuplicateChars.add(wordChar);
lastChar = wordChar;
}
}
}
return nonDuplicateChars;
}
object checkSort {
private def findChange(in: Array[String], maxsize: Int): Array[Char] = {
in.map(_.charAt(0)).foldLeft(Array[Char]())({
case (array, char) if array.isEmpty || array.size <= maxsize || array.last != char => array(array.size - 1) = char; array
case (array, _) => array
})
}
def check(in: Array[String], sort: Array[Char]): Boolean = {
val subOrder = findChange(in, sort.size)
val subSortSet = subOrder.toSet
sort.filter(subSortSet(_)).sameElements(subOrder)
}
def main(args: Array[String]): Unit = {
//new CountGraph( new mutable.MultiMap[MyNode,MyNode]())
}
}
public class OrderingArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] words = new String[] {"cc","cb","bb","ac"};
Character[] ordering = new Character[] {'b','c','a'};
int ordering_index = 0;
boolean matching = true;
for (int i = 0; i < words.length; i++) {
char firstLetter = words[i].charAt(0);
if(firstLetter != ordering[ordering_index]) {
if (firstLetter == ordering[ordering_index +1]) {
ordering_index +=1;
} else {
matching = false;
break;
}
}
}
System.out.println(matching);
}
}
public class OrderingArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] words = new String[] {"cc","cb","bb","ac"};
Character[] ordering = new Character[] {'b','c','a'};
int ordering_index = 0;
boolean matching = true;
for (int i = 0; i < words.length; i++) {
char firstLetter = words[i].charAt(0);
if(firstLetter != ordering[ordering_index]) {
if (firstLetter == ordering[ordering_index +1]) {
ordering_index +=1;
} else {
matching = false;
break;
}
}
}
System.out.println(matching);
}
}
#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include<cmath>
#include <unordered_map>
#include<memory>
#include<algorithm>
#include<assert.h>
#include <sstream>
using namespace std;
bool issorted(vector<string> words, string ordering)
{
vector<int> alpha(26, 0);
int len = ordering.size();
for (int i = 0; i < len; i++)
alpha[ordering[i] - 'a'] = i+1;
len = words.size();
for (int i = 0; i < len-1; i++)
{
string::iterator s1 = words[i].begin();
string::iterator s2 = words[i + 1].begin();
while (*s1 == *s2)
{
s1++;
s2++;
}
if (s1 != words[i].end() && s2 == words[i + 1].end())
return false;
if (s1 != words[i].end() && s2 != words[i + 1].end())
if (alpha[*s1 - 'a'] != 0 && alpha[*s2 - 'a'] != 0 && alpha[*s1 - 'a'] > alpha[*s2 - 'a'])
return false;
}
return true;
}
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']));
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']));
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']));
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']));
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']));
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']));
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']));
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']));
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']));
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']));
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']));
function checkWordOrder($input, $sort) {
$resultSet = [];
foreach($input as $word) {
array_push($resultSet, array_search($word[0], $sort));
}
//print_r($resultSet);
$notOrdered = false;
for($i = 0 ;$i < count($resultSet) - 1 ; $i++) {
// echo $resultSet[$i]. "=" .$resultSet[$i+1]."\n" ;
if($resultSet[$i] > $resultSet[$i+1] ){
$notOrdered = true;
}
}
if($notOrdered == true) {
echo "list is not ordered";
} else {
echo "list is ordered";
}
//return $result;
}
$input = ["fish","cat","cdmel","dog"];
$sort = ["a","f","c","d"];
checkWordOrder($input, $sort);
<?php
function checkWordOrder($input, $sort) {
$resultSet = [];
foreach($input as $word) {
array_push($resultSet, array_search($word[0], $sort));
}
//print_r($resultSet);
$notOrdered = false;
for($i = 0 ;$i < count($resultSet) - 1 ; $i++) {
// echo $resultSet[$i]. "=" .$resultSet[$i+1]."\n" ;
if($resultSet[$i] > $resultSet[$i+1] ){
$notOrdered = true;
}
}
if($notOrdered == true) {
echo "list is not ordered";
} else {
echo "list is ordered";
}
//return $result;
}
$input = ["fish","cat","cdmel","dog"];
$sort = ["a","f","c","d"];
checkWordOrder($input, $sort);
?>
import java.util.HashMap;
import java.util.Map;
public class CheckDictionarySorted {
public static void main(String[] args){
String words[] = {"cc", "cb", "b", "bb", "ac"};
char ordering[] = {'c', 'b', 'a' };
boolean actual = isSorted(words, ordering);
System.out.println("testcase1 result " + actual);
words = new String[] {"cc", "cb", "bb", "ac"};
ordering = new char[] {'b', 'c', 'a' };
actual = isSorted(words, ordering);
System.out.println("testcase2 result " + actual);
}
/**
* rely on transitive property of less than
* subproblem: check s(i) < s(i+1)
*
* Assumptions :
* 1) no duplicates in words , ordering
* 2) ordering contains needed alphabets from words
*/
public static boolean isSorted(String[] words, char[] ordering) {
int n = words.length;
if (n < 2) { return true;}
Map<Character, Integer> charToOrdinal = new HashMap<Character, Integer>();
for (int i = 0; i < ordering.length; i++){
charToOrdinal.put(ordering[i], i);
}
char[] prev = words[0].toCharArray();
for (int i = 1; i < n; i++){
char[] current = words[i].toCharArray();
// s1 : prev, s2 : current
char[] s1 = prev, s2 = current;
int s1n = prev.length;
int s2n = current.length;
int j1 = 0, j2 = 0;
boolean smaller = false;
while ((j1 < s1n) && (j2 < s2n)) {
int o1 = charToOrdinal.get(s1[j1]);
int o2 = charToOrdinal.get(s2[j2]);
if (o1 > o2) {
return false;
} else if (o1 < o2) {
smaller = true;
break;
}
j1++; j2++;
}
if (!smaller) {
// substrings identical, enforce 'b' < 'bc'
if (s1n > s2n){
return false;
}
}
prev = current;
}
return true;
}
}
I present two solutions here.
One is the brute force solution which basically involves comparing every word with every letter to see if the words are ordered. This takes O(M*N) where M is the number of the words and N is the number of letters.
The more optimized way which can be done is O(M) time is where you have two pointers which point to the words list and the letters list respectively. As soon as you encounter the first mismatch, return False immediately. Else, if the traversal through the entire list is successful, then return True.
def isOrderedBruteForce(words, ordering):
letter_index = 0
word_index = 0
while letter_index < len(ordering):
cur_word = words[word_index]
cur_letter = ordering[letter_index]
while cur_word.startswith(cur_letter):
word_index += 1 # Move to the next word
if word_index == len(words):
return True
cur_word = words[word_index]
letter_index += 1
if letter_index < len(ordering) and not words[word_index].startswith(ordering[letter_index]):
return False
return False
def isOrderedOptimized(words, ordering):
letter_index = 0
for word_index, word in enumerate(words):
if word.startswith(ordering[letter_index]):
continue
elif letter_index+1 < len(ordering) and word.startswith(ordering[letter_index+1]):
letter_index += 1
continue
else:
return False
return True
print(isOrderedBruteForce(['cc','cb','bb','ac'], ['c','b','a'])) # True
print(isOrderedBruteForce(['cc','cb','bb','ac'], ['b','c','a'])) # False
print(isOrderedBruteForce(['cc','cb','bb','ac','cat', 'aab'], ['c','b','a'])) # False
print('-' * 15)
print(isOrderedOptimized(['cc','cb','bb','ac'], ['c','b','a'])) # True
print(isOrderedOptimized(['cc','cb','bb','ac'], ['b','c','a'])) # False
print(isOrderedOptimized(['cc','cb','bb','ac','cat', 'aab'], ['c','b','a'])) # False
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;
}
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;
}
- koustav.adorable February 28, 2018public 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); }