## Uber Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 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);
}``````

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``````

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;
}``````

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).

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``````

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;
}
}``````

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``````

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;
}
}``````

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"));
}
}

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``

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``````

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``````

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");
}

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;
}``````

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')``````

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");
}
}

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;
}

}``````

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;
}
}``````

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;
}``````

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;
}
}``````

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``````

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;
}``````

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;
}``````

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;
}

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;

}``````

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;

}``````

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;

}``````

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;
}
}``````

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;
}``````

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;``````

}

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;
}``````

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)));
}
}``````

}

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;
}
}``````

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"));
}
}

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"));
}
}``````

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;
}``````

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;
}

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;
}

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;
}``````

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;
}

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;
}``````

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));``````

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``````

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()
}}}

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