Uber Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
3
of 3 vote

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input, order;
        input = in.nextLine();
        order = in.nextLine();
        boolean result = true;
        int pos = 0, prevPos = 0;
        HashMap<Character, Integer> H = new HashMap<Character, Integer>();

        for(char ch: order.toCharArray()) {
            H.put(ch, pos);
            pos++;
        }

        for(char ch: input.toCharArray()) {
            if(H.containsKey(ch)) {
                if(prevPos > H.get(ch)) {
                    result = false;
                    break;
                }
                else
                    prevPos = H.get(ch);
            }
        }
        System.out.println(result);
    }

- Arun Vadivel August 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

import re

def func(input, ordering):
	pattern = "[^{0}]".format(ordering)
	matches = re.sub(pattern, '', input)
	uniques = []
	[uniques.append(s) for s in matches if s not in uniques]
	uniques = ''.join(uniques)
	if uniques == ordering:
		return True
	else:
		return False

- mjlepouttre August 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 5 vote

Size of ordering string = m
Size of input string = n
Time Complexity = O(n) + O(m) == O(n+m)
Space complexity = O(min(n, 26))

bool checkOrder(string in, string order) {

    unordered_map<char, int> pos;

    for(int i = 0; i < in.size(); i++){
        pos[in[i]] = i;
    }

    for(int i = 1; i < order.size(); i++){
        if(pos[order[i]] - pos[order[i-1]] < 0){
            return false;
        }
    }

    return true;
}

- swapnilsj August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

string in = "bab";
string order = "ab";

pos[a] = 1;
pos[b] = 2;

pos[b] - pos[a] > 0 which gives us true, but should be false (since we have some b's before a's).

- Alex M. April 11, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm going to make the assumption that there won't be any duplicate characters in the ordering. i.e, in your first example, pattern "hlol!" wouldn't make since sine the first 'l' in the pattern accounts for ALL instances of 'l' in the input.

Swift 2.2

func lastInstanceOf(phrase: String, letter: Character) -> Int? {
    for i in (0 ..< phrase.characters.count).reverse() {
        if (phrase[phrase.startIndex.advancedBy(i)] == letter) {
            return i
            
        }
        
    }
    return nil
    
}

func matchPattern(phrase: String, pattern: String) -> Bool {
    for i in 0 ..< pattern.characters.count {
        if (i < pattern.characters.count - 1) {
            let currentIndex = lastInstanceOf(phrase, letter: pattern[pattern.startIndex.advancedBy(i)])
            for j in i + 1 ..< pattern.characters.count {
                let compareIndex = lastInstanceOf(phrase, letter: pattern[pattern.startIndex.advancedBy(j)])
                if (compareIndex < currentIndex) {
                    return false
                    
                }
                
            }
            
        }
        
    }
    return true
    
}

matchPattern("hello world!", pattern: "hlo!") // false
matchPattern("hello world!", pattern: "!od") // false
matchPattern("hello world!", pattern: "he!") // true
matchPattern("aaaabbbcccc", pattern: "ac") // true

- helloru August 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public class Main {
	public static void main(String[] args) {
		String s = "hello world!" ;
		//String orderingPattern = "hlo!";
		String orderingPattern = "he!";
		if(checkOrderpattern(s,orderingPattern)){
			System.out.println("The string is ordered.");
		}else{
			System.out.println("The string is not ordered.");
		}
	}
	
	public static boolean checkOrderpattern(String s, String orderingPattern){
		for(int i=0;i<orderingPattern.length()-1; i++){
			if(!(  s.lastIndexOf(orderingPattern.charAt(i)) < s.indexOf(orderingPattern.charAt(i+1))  )){
				return false;
			}
		}
		return true;
	}
}

- settyblue August 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def func2(inputstring,orderingstring):
	controlmatrix=[[0 for x in range(len(inputstring))] for y in range(len(orderingstring))]
	#j=0
	for i in range(len(inputstring)):
		for j in range(len(orderingstring)):
			if inputstring[i]==orderingstring[j]:
				controlmatrix[j][i]=i
	for k in range(len(orderingstring)-1):
		if (max(controlmatrix[k][:])>max(controlmatrix[k+1][:])) or (min(controlmatrix[k][:])<min(controlmatrix[k+1][:])) :
			return False
	return True

- Sasha August 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

not using indexof function which indirectly iterates over the array for the no. of time it is being used... so guess time complexity will be less for below code

package string;

public class FindSeqString {
	public static void main(String[] args) {
		
		
		FindSeqString fss = new FindSeqString();
		
		System.out.println(fss.checkStringSeq("hellow", "helow")?"Seq match found":"Seq not found");
		
		
		System.out.println(fss.checkStringSeq("yellow","ylow")?"Seq match found":"Seq not found");
		
		
		System.out.println(fss.checkStringSeq("hhhhellllow","hlleow")?"Seq match found":"Seq not found");
	}

	
	public boolean checkStringSeq(String parentString,String findSeq){
		char[] parentCharArray = parentString.toCharArray();
		char[] seqCheckCharArray= findSeq.toCharArray();
		int seqCheckIndex=0;
		if(parentCharArray.length<seqCheckCharArray.length)
			return false;
		for (char c : parentCharArray){
			if(seqCheckIndex!= seqCheckCharArray.length){
				if(c==seqCheckCharArray[seqCheckIndex])
					seqCheckIndex++;
			}
				
		}
		if (seqCheckIndex!= seqCheckCharArray.length)
			return false;
		else
			return true;
	}
}

- Harry August 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public final class StringOrderingChecker {

private static boolean isStringOrdered(final String input, final String ordered) {
final Map<Character, Integer> lastIndexByCharacter = new HashMap<>(input.length());

int position = 0;
for (final char character : input.toCharArray()) {
lastIndexByCharacter.put(character, position++);
}

int previousPosition = 0;
for (final char character : ordered.toCharArray()) {
final Integer characterLastIndex = lastIndexByCharacter.get(character);
if (characterLastIndex == null) {
continue;
}

if (previousPosition > characterLastIndex) {
return false;
}

previousPosition = characterLastIndex;
}

return true;
}

public static void main(String[] args) {
System.out.println(isStringOrdered("hello world!", "hlo"));
}
}

- java coder August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

and

public final class StringOrderingChecker {

private static boolean isStringOrdered(final String input, final String ordered) {
final Map<Character, Integer> lastIndexByCharacter = new HashMap<>(input.length());

int position = 0;
for (final char character : input.toCharArray()) {
lastIndexByCharacter.put(character, position++);
}

int previousPosition = 0;
for (final char character : ordered.toCharArray()) {
final Integer characterLastIndex = lastIndexByCharacter.get(character);
if (characterLastIndex == null) {
continue;
}

if (previousPosition > characterLastIndex) {
return false;
}

previousPosition = characterLastIndex;
}

return true;
}

public static void main(String[] args) {
System.out.println(isStringOrdered("hello world!", "hlo"));
}
}

and

- java coder August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def checkSpecialSubstr(string, substr):                           
                                                                  
    stringIndex = 0                                               
    for char in substr:                                           
                                                                  
        index = string[stringIndex:].find(char)                   
        if index < 0:                                             
            return False                                          
        stringIndex = stringIndex + index + 1                     
                                                                  
    return True

- Suresh August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def checkSpecialSubstr(string, substr):                           
                                                                  
    stringIndex = 0                                               
    for char in substr:                                           
                                                                  
        index = string[stringIndex:].find(char)                   
        if index < 0:                                             
            return False                                          
        stringIndex = stringIndex + index + 1                     
                                                                  
    return True

- Suresh August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void checkorder(char[] bword, char [] sword)
{
int start = 0;
int success = 0;
for (int i = 0; i < sword.Length; i++)
{
for (int x = bword.Length-1; x >= start; x--)
{

if (sword[i] == bword[x])
{
start = x;
success++;
break;
}
}
}
if (success == sword.Length)
{
Console.WriteLine("True");
}

else
Console.WriteLine("False");
}

- Wahjid August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Size of ordering string = m
Size of input string = n
Time Complexity = O(n) + O(m) == O(n+m)
Space complexity = O(min(n, 26))

bool checkOrder(string in, string order) {

    unordered_map<char, int> pos;

    for(int i = 0; i < in.size(); i++){
        pos[in[i]] = i;
    }

    for(int i = 1; i < order.size(); i++){
        if(pos[order[i]] - pos[order[i-1]] < 0){
            return false;
        }
    }

    return true;
}

- swapnilsj August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def check_str(input_str, order_str):
    for item in order_str:
        if item not in input_str:
            return False
        indx = len(input_str) - input_str[::-1].index(item) - 1
        input_str = input_str[indx:]

    return True
print check_str('hello world!', '!od')

- programmer August 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
// TODO code application logic here
Scanner in=new Scanner(System.in);
String s1=in.next();
String s2=in.next();
// char str1[]=s1.toCharArray();
char str2[]=s2.toCharArray();
StringBuffer str=new StringBuffer();
for(int i=0;i<=s2.length()-1;i++)
{
//for(int j=i;j<s1.length();j++)
{
int n=s1.lastIndexOf(str2[i]);
str.append(str2[i]);
s1=s1.substring(n+1);
}
}
if(s2.equals(str))
{
System.out.println("true");
}
else
{
System.out.println("false");
}
}

- g August 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class RelativeStringOrder {

	
	public static void main(String[] args) {
		String input ="aaaabbbcccc";
		String order ="ac";
		boolean ordered = isStringOrdered(input,order);
		System.out.println("The given String is ordered:"+ordered);
	}

	/*
	 * o(n) with extra space
	 */
	private static boolean isStringOrdered(String input, String order) {
		HashMap<Character,Integer> orderMap = new HashMap<>();
		for(int i = 0 ; i<input.length();i++){
			orderMap.put(input.charAt(i), i);
		}
		
		for(int i=0;i<order.length()-1;i++){
			if(orderMap.get(order.charAt(i)) >orderMap.get(order.charAt(i+1))){
				return false;
			}
		}
		return true;
	}

}

- Anonymous August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class RelativeStringOrder {

	
	public static void main(String[] args) {
		String input ="aaaabbbcccc";
		String order ="ac";
		boolean ordered = isStringOrdered(input,order);
		System.out.println("The given String is ordered:"+ordered);
	}

	/*
	 * o(n) with extra space
	 */
	private static boolean isStringOrdered(String input, String order) {
		HashMap<Character,Integer> orderMap = new HashMap<>();
		for(int i = 0 ; i<input.length();i++){
			orderMap.put(input.charAt(i), i);
		}
		
		for(int i=0;i<order.length()-1;i++){
			if(orderMap.get(order.charAt(i)) >orderMap.get(order.charAt(i+1))){
				return false;
			}
		}
		return true;
	}
}

- testCode August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class RelativeStringOrder {

	
	public static void main(String[] args) {
		String input ="aaaabbbcccc";
		String order ="ac";
		boolean ordered = isStringOrdered(input,order);
		System.out.println("The given String is ordered:"+ordered);
	}

	/*
	 * o(n) with extra space
	 */
	private static boolean isStringOrdered(String input, String order) {
		HashMap<Character,Integer> orderMap = new HashMap<>();
		for(int i = 0 ; i<input.length();i++){
			orderMap.put(input.charAt(i), i);
		}
		
		for(int i=0;i<order.length()-1;i++){
			if(orderMap.get(order.charAt(i)) >orderMap.get(order.charAt(i+1))){
				return false;
			}
		}
		return true;
	}

- testCode August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class RelativeStringOrder {

	
	public static void main(String[] args) {
		String input ="aaaabbbcccc";
		String order ="ac";
		boolean ordered = isStringOrdered(input,order);
		System.out.println("The given String is ordered:"+ordered);
	}

	/*
	 * o(n) with extra space
	 */
	private static boolean isStringOrdered(String input, String order) {
		HashMap<Character,Integer> orderMap = new HashMap<>();
		for(int i = 0 ; i<input.length();i++){
			orderMap.put(input.charAt(i), i);
		}
		
		for(int i=0;i<order.length()-1;i++){
			if(orderMap.get(order.charAt(i)) >orderMap.get(order.charAt(i+1))){
				return false;
			}
		}
		return true;
	}
}

- MyNameIs August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def func (input, ordering):
	pos = {}
	for i, char in enumerate(input):
		pos[char] = pos.get(char, []) + [i]

	n = len(ordering)
	for j in range(n-1):
		first = ordering[j]
		second = ordering[j+1]
		for order1 in pos[first]:
			for order2 in pos[second]:
				if order1 < order2:
					continue
				else:
					return False
	return True

- potatoML August 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Linear approach runs in O(m+n)

Implementation in golang:

func checkOrder(input string, order string) bool{
	// Maps a char to an array. First element is the first appearance of 
	// the char and the second element is the last appearance of the char
	var m = make(map[string][]int) 

	// Runs through the input once to determine the first and last 
	// instance of each char
	for i := 0; i < len(input); i++{
		if m[ string(input[i]) ] == nil{
			m[ string(input[i]) ] = []int{ i , i }; 
		}else{
			m[ string(input[i]) ] = []int{ m[ string(input[i]) ][0] , i }; 
		}
	}

	// Runs through the order and use the map to see if order
	// is enforced
	for i := 1; i < len(order); i++{
		if m[string(order[i])][0] < m[string(order[i - 1])][1]{
			return false;
		}
	}
	return true
}

Implementation in Java:

public static boolean checkOrder(String input, String order){
		HashMap<String, int[]> map = new HashMap<String, int[]>();
		for(int i = 0; i < input.length(); i++){
			if ( !map.containsKey(input.substring(i,i+1)) ){
				int[] arr = {i, i};
				map.put(input.substring(i,i+1), arr);
			}else{
				int[] arr = {map.get(input.substring(i,i+1))[0] , i};
				map.put(input.substring(i,i+1), arr);
			}
		}

		for(int i = 1; i < order.length(); i++){
			if(map.get(order.substring(i, i+1))[0] <  map.get(order.substring(i - 1, i))[1] ){
				return false;
			}
		}
		return true;
	}

- JH August 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
using namespace std;

bool checkOrdering(string a, string b) {
	int order[b.length()];
	for (int i=0;i<b.length();i++){
		int pos = a.rfind(b[i]);
		order[i]=pos;
	}
	for (int i=0;i<(sizeof(order)/sizeof(order[0]))-1;i++){
		if (order[i]==string::npos || order[i]>order[i+1]){
				return false;
		}
	}
	return true;
}

- harry688tan August 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool stringOrder (char* input, char* check )
{
if (sizeof(check) > sizeof(input)) return false;
int i =0;
for (int j =0; j != '\0'; j++)
{
if (check[i] == input[j])
{
i++;
}
}

if ( i == sizeof(check))
return true;
}

- C August 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    char str[100];
    char pattern[100];
    unordered_map<char, int> positions;
    int farthest_pos;

    cout<<"Enter main string: ";
    cin >> str;
    
    cout<<"string is : "<<str<<endl;

    cout<<"pattern : ";
    cin>>pattern;
    
    cout<<"pattern is : "<<pattern<<endl;

    for (int i=0; i < strlen(str); i++) {
        positions[str[i]] = i;
    }
    farthest_pos = positions[pattern[0]];
    
    for (int j=0; j < strlen(pattern)-1; j++)
    {
        if (positions[pattern[j]] > positions[pattern[j+1]]) {
            cout<<"Problemm is:  "<< pattern[j] << " pos "<< positions[pattern[j]] << " AND : " << pattern[j+1] << " pos "<< positions[pattern[j+1]]<<endl;
            cout <<"false"<<endl;
            return 0;
        }
    }
    cout <<"true"<<endl;
    
}

- Sandy August 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    char str[100];
    char pattern[100];
    unordered_map<char, int> positions;
    int farthest_pos;

    cout<<"Enter main string: ";
    cin >> str;
    
    cout<<"string is : "<<str<<endl;

    cout<<"pattern : ";
    cin>>pattern;
    
    cout<<"pattern is : "<<pattern<<endl;

    for (int i=0; i < strlen(str); i++) {
        positions[str[i]] = i;
    }
    farthest_pos = positions[pattern[0]];
    
    for (int j=0; j < strlen(pattern)-1; j++)
    {
        if (positions[pattern[j]] > positions[pattern[j+1]]) {
            cout<<"Problemm is:  "<< pattern[j] << " pos "<< positions[pattern[j]] << " AND : " << pattern[j+1] << " pos "<< positions[pattern[j+1]]<<endl;
            cout <<"false"<<endl;
            return 0;
        }
    }
    cout <<"true"<<endl;
    
}

- Sandeep August 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    char str[100];
    char pattern[100];
    unordered_map<char, int> positions;
    int farthest_pos;

    cout<<"Enter main string: ";
    cin >> str;
    
    cout<<"string is : "<<str<<endl;

    cout<<"pattern : ";
    cin>>pattern;
    
    cout<<"pattern is : "<<pattern<<endl;

    for (int i=0; i < strlen(str); i++) {
        positions[str[i]] = i;
    }
    farthest_pos = positions[pattern[0]];
    
    for (int j=0; j < strlen(pattern)-1; j++)
    {
        if (positions[pattern[j]] > positions[pattern[j+1]]) {
            cout<<"Problemm is:  "<< pattern[j] << " pos "<< positions[pattern[j]] << " AND : " << pattern[j+1] << " pos "<< positions[pattern[j+1]]<<endl;
            cout <<"false"<<endl;
            return 0;
        }
    }
    cout <<"true"<<endl;
    
}

- sandeep.bvb August 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Map;

public class OrderingProblem {

	public static void main(String[] args) {
		OrderingProblem orderingProblem = new OrderingProblem();
		System.out.println("Result = " + orderingProblem.checkStringOrdering("hello world!", "hlo!"));
		System.out.println("Result = " + orderingProblem.checkStringOrdering("hello world!", "!od"));
		System.out.println("Result = " + orderingProblem.checkStringOrdering("hello world!", "he!"));
		System.out.println("Result = " + orderingProblem.checkStringOrdering("aaaabbbcccc", "ac"));
	}

	private boolean checkStringOrdering(String source, String target) {
		if (null == source || null == target || 0 == source.length() || 0 == target.length()) {
	        return true;
		}

	    // Collect the first occurrence of all the chars in target string
	    Map<Character, Integer> mapOfFirstOccurence = new HashMap<Character, Integer>();
	    for (int i = 0; i < target.length(); i++) {
	        if (null != mapOfFirstOccurence.get(target.charAt(i))) {
	            continue;
	        }
	        
	        for (int j = 0; j < source.length(); j++) {
	            if (source.charAt(j) == target.charAt(i)) {
	                mapOfFirstOccurence.put(target.charAt(i), j);
	                break;
	            }
	        }
	    }


	    for (int i = 0; i < target.length(); i++) {
	        // find the last occurrence of target.charAt(i) within source string
	        int lastOccurenceIndex = -1;
	        for (int j = source.length() - 1; j >= 0; j--) {
	            if (source.charAt(j) == target.charAt(i)) {
	                lastOccurenceIndex = j;
	                break;
	            }
	        }

	        if (lastOccurenceIndex == -1) {
	            // Did not find any match
	            return false;
	        }

	        // Check all the chars after the current target's character if they are appearing before the last occurence of target's char in source string
	        for (int k = i + 1; k < target.length(); k++) {
	            Integer firstOccurrenceIndex = mapOfFirstOccurence.get(target.charAt(k));
	            if (null == firstOccurrenceIndex) {
	                continue;
	            }

	            if (firstOccurrenceIndex < lastOccurenceIndex) {
	                return false;
	            }
	        }
	    }

	    return true;
	}
}

- AR September 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
     * N - str.length()
     * M - order.length()
     * <p>
     * time: O(N+M)
     * space: O(M)
     */
    public static boolean hasCorrectOrdering(String str, String order) {
        checkNotNull(str, "null 'str' parameter passed");
        checkNotNull(order, "null 'order' parameter passed");

        if (order.length() > str.length()) {
            return false;
        }

        final int orderLength = order.length();
        Map<Character, Integer> orderIndex = new HashMap<>();

        for (int i = 0; i < orderLength; ++i) {
            if (orderIndex.put(order.charAt(i), i) != null) {
                throw new IllegalArgumentException("'order' parameter contains duplicate characters: '" + order + "'");
            }
        }

        int lastIndex = -1;

        for (int i = 0, length = str.length(); i < length; ++i) {
            char ch = str.charAt(i);

            if (orderIndex.containsKey(ch)) {

                int curIndex = orderIndex.get(ch);

                // check 1st character is hit properly
                if (lastIndex == -1 && curIndex != 0) {
                    return false;
                }
                // check other characters
                else if (curIndex < lastIndex) {
                    return false;
                }

                lastIndex = curIndex;
            }
        }

        // check we found all characters from 'order'
        return lastIndex == orderLength - 1;
    }

- m@}{ November 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
     * N - str.length()
     * M - order.length()
     * <p>
     * time: O(N+M)
     * space: O(M)
     */
    public static boolean hasCorrectOrdering(String str, String order) {
        checkNotNull(str, "null 'str' parameter passed");
        checkNotNull(order, "null 'order' parameter passed");

        if (order.length() > str.length()) {
            return false;
        }

        final int orderLength = order.length();
        Map<Character, Integer> orderIndex = new HashMap<>();

        for (int i = 0; i < orderLength; ++i) {
            if (orderIndex.put(order.charAt(i), i) != null) {
                throw new IllegalArgumentException("'order' parameter contains duplicate characters: '" + order + "'");
            }
        }

        int lastIndex = -1;

        for (int i = 0, length = str.length(); i < length; ++i) {
            char ch = str.charAt(i);

            if (orderIndex.containsKey(ch)) {

                int curIndex = orderIndex.get(ch);

                // check 1st character is hit properly
                if (lastIndex == -1 && curIndex != 0) {
                    return false;
                }
                // check other characters
                else if (curIndex < lastIndex) {
                    return false;
                }

                lastIndex = curIndex;
            }
        }

        // check we found all characters from 'order'
        return lastIndex == orderLength - 1;

}

- m@}{ November 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
     * N - str.length()
     * M - order.length()
     * <p>
     * time: O(N+M)
     * space: O(M)
     */
    public static boolean hasCorrectOrdering(String str, String order) {
        checkNotNull(str, "null 'str' parameter passed");
        checkNotNull(order, "null 'order' parameter passed");

        if (order.length() > str.length()) {
            return false;
        }

        final int orderLength = order.length();
        Map<Character, Integer> orderIndex = new HashMap<>();

        for (int i = 0; i < orderLength; ++i) {
            if (orderIndex.put(order.charAt(i), i) != null) {
                throw new IllegalArgumentException("'order' parameter contains duplicate characters: '" + order + "'");
            }
        }

        int lastIndex = -1;

        for (int i = 0, length = str.length(); i < length; ++i) {
            char ch = str.charAt(i);

            if (orderIndex.containsKey(ch)) {

                int curIndex = orderIndex.get(ch);

                // check 1st character is hit properly
                if (lastIndex == -1 && curIndex != 0) {
                    return false;
                }
                // check other characters
                else if (curIndex < lastIndex) {
                    return false;
                }

                lastIndex = curIndex;
            }
        }

        // check we found all characters from 'order'
        return lastIndex == orderLength - 1;
    }

- max November 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Created by dushyant.sabharwal on 11/20/16.
 */
public class OrderingString {
    public static void main(String []args) throws IOException {
        System.out.println("Please enter the main string");
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String main = bufferedReader.readLine();
        System.out.println("Please enter the ordering string");
        String ordering = bufferedReader.readLine();
        bufferedReader.close();

        int [] order = new int[ordering.length()];

        for (int i=0; i < ordering.length(); i++) {
            order[i] = main.lastIndexOf(ordering.charAt(i));
        }
        int i;
        if (order.length > 1) {
            for (i = 0; i < order.length - 1; i++) {
                if (order[i] == -1 || order[i] > order[i + 1]) {
                    break;
                }
            }

            if (i == order.length - 1) {
                System.out.println("TRUE");
            } else {
                System.out.println("FALSE");
            }
        } else {
            System.out.println(-1 != main.lastIndexOf(ordering.charAt(0)));
        }
    }

}

- dushyant.sabharwal November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
    public static void main (String[] args) {
        String input = "aaaabbbcccc", ordering = "ac";
        System.out.println(isPresent(input, ordering));
	}
	
	private static boolean isPresent(String input, String ordering) {
	    int n = input.length(), m = ordering.length();
	    int[] arr = new int[256];
	    for (int i = 0; i < n; i++) {
	        arr[input.charAt(i)] = i;
	    }
	    for (int j = 1; j < m; j++) {
	        if (arr[ordering.charAt(j)] < arr[ordering.charAt(j - 1)]) {
	            return false;
	        }
	    }
	    return true;
	}
}

- selimeki December 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringOrdering {

public static boolean checkOrdering(String s, String order) {
String ss = "";
char ch;
for (int i=0; i<s.length(); i++) {
ch = s.charAt(i);
if (order.contains(ch + "")) {
if (ss.length()> 0 && ss.charAt(ss.length() -1) == ch) {
} else {
ss+= ch;
}
}
}
System.out.println(ss);
if (ss.equals(order)) {
return true;
} else {
return false;
}

}
public static void main(String[] args) {

System.out.println(checkOrdering("hello world!", "hlo!"));
System.out.println(checkOrdering("hello world!", "!od"));
System.out.println(checkOrdering("hello world!", "he!"));
System.out.println(checkOrdering("aaaabbbcccc", "ac"));
}
}

- Anonymous January 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringOrdering {

    public static boolean checkOrdering(String s, String order) {
        String ss = "";
        char ch;
        for (int i=0; i<s.length(); i++) {
            ch = s.charAt(i);
            if (order.contains(ch + "")) {
                if (ss.length()> 0 && ss.charAt(ss.length() -1) == ch) {
                } else {
                    ss+= ch;
                }
            }
        }
        System.out.println(ss);
        if (ss.equals(order)) {
            return true;
        } else {
            return false;
        }

    }
    public static void main(String[] args) {

        System.out.println(checkOrdering("hello world!", "hlo!"));
        System.out.println(checkOrdering("hello world!", "!od"));
        System.out.println(checkOrdering("hello world!", "he!"));
        System.out.println(checkOrdering("aaaabbbcccc", "ac"));
    }
}

- a.a January 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I can see many of the solutions in Java are using String.indexOf() function which is O(n) complexity. My solution with a trade-of of O(n) space complexity does the operation in O(n) time. I use two HashSets , one with already traversed characters which aren't allowed to occur in the string and another with allowed set of characters. I move a character from the second to the first HashSet whenever I encounter an allowed character. I also use a temp character variable to detect the last character added to the first HashSet since this is the only character in the first HashSet which is allowed to present in the string. Please let me know if you find any problem with the solution.

public static boolean findOrdered(String str1, String str2){
    if(str1==null||str2==null||str1.length()<=1||str2.length()<=1)
      return true;
    HashSet<Character> charList = new HashSet<>();
    for(int i=0;i<str2.length();i++)
      charList.add(str2.charAt(i));
    char temp=str2.charAt(0);
    HashSet<Character> traversedCharList = new HashSet<>();
    int j=0;
    for(int i=0;i<str1.length();i++){
      if(str1.charAt(i)==str2.charAt(j)) {
        traversedCharList.add(str2.charAt(j));
        temp=str2.charAt(j);
        charList.remove(str2.charAt(j));
        j=(j==str2.length()-1)?j:j+1;
      } else if(charList.contains(str1.charAt(i))) {
        while(str2.charAt(j)!=str1.charAt(i)){
          traversedCharList.add(str2.charAt(j));
          charList.remove(str2.charAt(j++));
        }
          traversedCharList.add(str2.charAt(j));
          temp=str2.charAt(j);
          charList.remove(str2.charAt(j));
      } else if(traversedCharList.contains(str1.charAt(i))&&temp!=str1.charAt(i)) {
        return false;
      }
    }
    return true;
 }

- Saikrishnan February 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isRelativeOrderSame(String str, String order) {
if(order.length()==0)
return false;
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
map.put(str.charAt(i), i);
}


for (int i = 0; i < order.length() - 1; i++) {
if (!map.containsKey(order.charAt(i)) || !map.containsKey(order.charAt(i+1)))
return false;
if (map.get(order.charAt(i)) > map.get(order.charAt(i + 1))) {
return false;
}
}
return true;
}

- Anonymous February 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isRelativeOrderSame(String str, String order) {
if(order.length()==0)
return false;
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
map.put(str.charAt(i), i);
}


for (int i = 0; i < order.length() - 1; i++) {
if (!map.containsKey(order.charAt(i)) || !map.containsKey(order.charAt(i+1)))
return false;
if (map.get(order.charAt(i)) > map.get(order.charAt(i + 1))) {
return false;
}
}
return true;
}

- Anonymous February 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isRelativeOrderSame(String str, String order) {
		if(order.length()==0)
			return false;
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		for (int i = 0; i < str.length(); i++) {
			map.put(str.charAt(i), i);
		}
		
		
		for (int i = 0; i < order.length() - 1; i++) {
			if (!map.containsKey(order.charAt(i)) || !map.containsKey(order.charAt(i+1)))
				return false;
			if (map.get(order.charAt(i)) > map.get(order.charAt(i + 1))) {
				return false;
			}
		}
		return true;
	}

- Anonymous February 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isRelativeOrderSame(String str, String order) {
if(order.length()==0)
return false;
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
map.put(str.charAt(i), i);
}


for (int i = 0; i < order.length() - 1; i++) {
if (!map.containsKey(order.charAt(i)) || !map.containsKey(order.charAt(i+1)))
return false;
if (map.get(order.charAt(i)) > map.get(order.charAt(i + 1))) {
return false;
}
}
return true;
}

- Anonymous February 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<unordered_map>
#include<string>

using namespace std;

bool stringOrdering(string s1, string s2)
{
	unordered_map<char,int> map;

	for(int i=0;i<s1.length();i++)
	{
		map[s1[i]] = i;
	}

	int idx = -1;

	for(int i=0;i<s2.length();i++)
	{
		if(idx < map[s2[i]])
			idx = map[s2[i]];
		else
			return false;
	}

	return true;
}

int main()
{
	cout << stringOrdering("hello world!","hlo!") << endl;
	cout << stringOrdering("hello world!","he!") << endl;
	cout << stringOrdering("aaaaaabbcc","ac") << endl;
	cout << stringOrdering("hello world!", "!od") << endl;

	return 0;
}

- Mehul October 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
   * Javascript Implementation.
   * validateStringWithPattern
   
Given an input string and ordering string, need to return true if 
the ordering string is present in Input string. 

input = "hello world!" 
ordering = "hlo!" 
result = FALSE (all Ls are not before all Os) 

input = "hello world!" 
ordering = "!od" 
result = FALSE (the input has '!' coming after 'o' and after 'd', 
                but the pattern needs it to come before 'o' and 'd') 

input = "hello world!" 
ordering = "he!" 
result = TRUE 

input = "aaaabbbcccc" 
ordering = "ac" 
result = TRUE

*/


function validateStringWithPattern(str, pattern) {
  let map = {};
  
  for(let index = 0, length = str.length; index < length; index++) {
    const char = str[index];
    if(map[char]) {
      map[char].push(index);
    } else {
      map[char] = [index];
    }
  }
  
  for(let index = 1, length = pattern.length; index < length; index++) {
    let mapCharArr1 = map[pattern[index-1]];
    let mapCharArr2 = map[pattern[index]];                   
    //First index of second char should be more than the last index of first char.
    if(mapCharArr2[0] < mapCharArr1[mapCharArr1.length - 1]){
      return false;
    }
  }
  return true;
}

//Test Case 1
let str = 'hello world!';
let pattern1 = 'hlo!';
let pattern2 = '!od';
let pattern3 = 'he!';
console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern1  + "' ===> " + validateStringWithPattern(str, pattern1));
console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern2  + "' ===> " + validateStringWithPattern(str, pattern2));
console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern3  + "' ===> " + validateStringWithPattern(str, pattern3));

//Test Case 2
str = 'aaaabbbcccc';
pattern1 = 'ac';

console.log("Validating String -> '"+ str + "' with Pattern -> '" +pattern1  + "' ===> " + validateStringWithPattern(str, pattern1));

- Amit Bansal March 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def check_order(input, ordering):
    chars_in_ordering = set([char for char in ordering])
    chars_to_process = iter(ordering)
    target_char = chars_to_process.next()
    processed = set()
    for i in input:
        if i == target_char or i not in chars_in_ordering:
            pass
        elif i in processed:
            return False
        else:
            processed.add(target_char)
            target_char = chars_to_process.next()
    return True

- suz July 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

func checkIfOrdered(_ mainStr : String, _ subStr : String) -> Bool {
var indexesOfChars = [Int]()

for ch in subStr {
var currentIndex = -1
for (i,str) in mainStr.enumerated() {

if (String(str) == String(ch)) {

currentIndex = i
}
}

indexesOfChars.append(currentIndex)
}

if indexesOfChars.contains(-1) {
return false
}

return indexesOfChars == indexesOfChars.sorted()
}}}

- Henly July 22, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More