Uber Interview Question
Software EngineersTeam: Uber Eats
Country: United States
Interview Type: In-Person
public class SubStrings {
private static String findSubstring(String word, String[] parts) {
int maxLength = 0;
int maxIndex = 0;
String maxPart = parts[0];
boolean matchFound = false;
for(String part: parts) {
int index = word.indexOf( part );
if(index >= 0) {
int length = part.length();
if(maxLength < length) {
maxLength = length;
maxPart = part;
maxIndex = index;
matchFound = true;
}
}
}
if(matchFound) {
String first = word.substring(0, maxIndex);
String part = word.substring(maxIndex, maxIndex + maxPart.length());
String last = word.substring(maxIndex + maxPart.length(), word.length());
return first + "[" + part + "]" + last;
}
return word;
}
private static String[] findSubstrings(String[] words, String[] parts) {
String[] newWords = new String[words.length];
int i = 0;
for(String word : words) {
newWords[i++] = findSubstring(word, parts);
}
return newWords;
}
public static void main(String[] args) {
String words[] = {"Apple", "Melon", "Orange", "Watermelon"};
String parts[] = {"a", "mel", "lon", "el", "An"};
String[] newWords = findSubstrings(words, parts);
for (String word: newWords ) {
System.out.println(word);
}
}
}
package main
import (
"fmt"
"regexp"
"strings"
)
func findParts(parts []string, words []string) []string {
for index, word := range words {
lastMatchLen := 0
var bestLenIndex int
for partIndex, part := range parts {
findExp, _ := regexp.Compile(part)
found := findExp.FindString(word)
fmt.Printf("Word: %v Part: %v Found: %v\n", word, part, found)
if len(found) > lastMatchLen {
lastMatchLen = len(found)
bestLenIndex = partIndex
}
}
if lastMatchLen > 0 {
foundPart := parts[bestLenIndex]
words[index] = strings.Replace(word, foundPart, "["+foundPart+"]", 1)
}
}
return words
}
func main() {
words := []string{"Apple", "Melon", "Orange", "Watermelon"}
parts := []string{"a", "mel", "lon", "el", "An"}
fmt.Printf("The new words %v", findParts(parts, words))
}
package main
import (
"fmt"
"regexp"
"strings"
)
func findParts(parts []string, words []string) []string {
for index, word := range words {
lastMatchLen := 0
var bestLenIndex int
for partIndex, part := range parts {
findExp, _ := regexp.Compile(part)
found := findExp.FindString(word)
fmt.Printf("Word: %v Part: %v Found: %v\n", word, part, found)
if len(found) > lastMatchLen {
lastMatchLen = len(found)
bestLenIndex = partIndex
}
}
if lastMatchLen > 0 {
foundPart := parts[bestLenIndex]
words[index] = strings.Replace(word, foundPart, "["+foundPart+"]", 1)
}
}
return words
}
func main() {
words := []string{"Apple", "Melon", "Orange", "Watermelon"}
parts := []string{"a", "mel", "lon", "el", "An"}
fmt.Printf("The new words %v", findParts(parts, words))
}
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
public class WordsAndParts {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] words = { "Apple", "Melon", "Orange", "Watermelon" };
String[] parts = { "a", "mel", "lon", "el", "An" };
WordsAndParts wordsAndParts = new WordsAndParts();
String[] result = wordsAndParts.findPartsInWords(words, parts);
Arrays.stream(result).forEach(System.out::println);
}
public String[] findPartsInWords(String[] words, String[] parts) {
List<String> resultList = Arrays.stream(words).map(word -> findPartsInWord(word, parts))
.collect(Collectors.toList());
String[] result = resultList.toArray(new String[resultList.size()]);
return result;
}
private String findPartsInWord(String word, String[] parts) {
String bestPart = Arrays.stream(parts).filter(part -> word.contains(part))
.sorted(Comparator.comparingInt(String::length).reversed()).findFirst().orElse(word);
if (!bestPart.equals(word))
bestPart = replaceWord(word, bestPart);
return bestPart;
}
private String replaceWord(String word, String part) {
String wordReplaced = word;
String replace = "[" + part + "]";
wordReplaced = wordReplaced.replace(part, replace);
return wordReplaced;
}
}
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
public class WordsAndParts {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] words = { "Apple", "Melon", "Orange", "Watermelon" };
String[] parts = { "a", "mel", "lon", "el", "An" };
WordsAndParts wordsAndParts = new WordsAndParts();
String[] result = wordsAndParts.findPartsInWords(words, parts);
Arrays.stream(result).forEach(System.out::println);
}
public String[] findPartsInWords(String[] words, String[] parts) {
List<String> resultList = Arrays.stream(words).map(word -> findPartsInWord(word, parts))
.collect(Collectors.toList());
String[] result = resultList.toArray(new String[resultList.size()]);
return result;
}
private String findPartsInWord(String word, String[] parts) {
String bestPart = Arrays.stream(parts).filter(part -> word.contains(part))
.sorted(Comparator.comparingInt(String::length).reversed()).findFirst().orElse(word);
if (!bestPart.equals(word))
bestPart = replaceWord(word, bestPart);
return bestPart;
}
private String replaceWord(String word, String part) {
String wordReplaced = word;
String replace = "[" + part + "]";
wordReplaced = wordReplaced.replace(part, replace);
return wordReplaced;
}
}
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
public class WordsAndParts {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] words = { "Apple", "Melon", "Orange", "Watermelon" };
String[] parts = { "a", "mel", "lon", "el", "An" };
WordsAndParts wordsAndParts = new WordsAndParts();
String[] result = wordsAndParts.findPartsInWords(words, parts);
Arrays.stream(result).forEach(System.out::println);
}
public String[] findPartsInWords(String[] words, String[] parts) {
List<String> resultList = Arrays.stream(words).map(word -> findPartsInWord(word, parts))
.collect(Collectors.toList());
String[] result = resultList.toArray(new String[resultList.size()]);
return result;
}
private String findPartsInWord(String word, String[] parts) {
String bestPart = Arrays.stream(parts).filter(part -> word.contains(part))
.sorted(Comparator.comparingInt(String::length).reversed()).findFirst().orElse(word);
if (!bestPart.equals(word))
bestPart = replaceWord(word, bestPart);
return bestPart;
}
private String replaceWord(String word, String part) {
String wordReplaced = word;
String replace = "[" + part + "]";
wordReplaced = wordReplaced.replace(part, replace);
return wordReplaced;
}
}
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
public class WordsAndParts {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] words = { "Apple", "Melon", "Orange", "Watermelon" };
String[] parts = { "a", "mel", "lon", "el", "An" };
WordsAndParts wordsAndParts = new WordsAndParts();
String[] result = wordsAndParts.findPartsInWords(words, parts);
Arrays.stream(result).forEach(System.out::println);
}
public String[] findPartsInWords(String[] words, String[] parts) {
List<String> resultList = Arrays.stream(words).map(word -> findPartsInWord(word, parts))
.collect(Collectors.toList());
String[] result = resultList.toArray(new String[resultList.size()]);
return result;
}
private String findPartsInWord(String word, String[] parts) {
String bestPart = Arrays.stream(parts).filter(part -> word.contains(part))
.sorted(Comparator.comparingInt(String::length).reversed()).findFirst().orElse(word);
if (!bestPart.equals(word))
bestPart = replaceWord(word, bestPart);
return bestPart;
}
private String replaceWord(String word, String part) {
String wordReplaced = word;
String replace = "[" + part + "]";
wordReplaced = wordReplaced.replace(part, replace);
return wordReplaced;
}
}
//END
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
public class WordsAndParts {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] words = { "Apple", "Melon", "Orange", "Watermelon" };
String[] parts = { "a", "mel", "lon", "el", "An" };
WordsAndParts wordsAndParts = new WordsAndParts();
String[] result = wordsAndParts.findPartsInWords(words, parts);
Arrays.stream(result).forEach(System.out::println);
}
public String[] findPartsInWords(String[] words, String[] parts) {
List<String> resultList = Arrays.stream(words).map(word -> findPartsInWord(word, parts))
.collect(Collectors.toList());
String[] result = resultList.toArray(new String[resultList.size()]);
return result;
}
private String findPartsInWord(String word, String[] parts) {
String bestPart = Arrays.stream(parts).filter(part -> word.contains(part))
.sorted(Comparator.comparingInt(String::length).reversed()).findFirst().orElse(word);
if (!bestPart.equals(word))
bestPart = replaceWord(word, bestPart);
return bestPart;
}
private String replaceWord(String word, String part) {
String wordReplaced = word;
String replace = "[" + part + "]";
wordReplaced = wordReplaced.replace(part, replace);
return wordReplaced;
}
}
func SearchSubString(words, parts []string) []string {
output := make([]string, len(words))
for idx, word := range words {
replaceWord := ""
lenPart := 0
for _, part := range parts {
if lenPart >= len(part) {
continue
}
fIdx := strings.Index(word, part)
if fIdx > 0 {
lastIdx := fIdx + len(part)
replaceWord = word[:fIdx] + "[" + part + "]" + word[lastIdx:]
lenPart = len(part)
}
}
//fmt.Println("replaceWord:", replaceWord, "word:", word)
if len(replaceWord) > 0 {
output[idx] = replaceWord
} else {
output[idx] = word
}
}
//fmt.Println(output)
return output
}
func SearchSubString(words, parts []string) []string {
output := make([]string, len(words))
for idx, word := range words {
replaceWord := ""
lenPart := 0
for _, part := range parts {
if lenPart >= len(part) {
continue
}
fIdx := strings.Index(word, part)
if fIdx > 0 {
lastIdx := fIdx + len(part)
replaceWord = word[:fIdx] + "[" + part + "]" + word[lastIdx:]
lenPart = len(part)
}
}
//fmt.Println("replaceWord:", replaceWord, "word:", word)
if len(replaceWord) > 0 {
output[idx] = replaceWord
} else {
output[idx] = word
}
}
//fmt.Println(output)
return output
}
func SearchSubString(words, parts []string) []string {
output := make([]string, len(words))
for idx, word := range words {
replaceWord := ""
lenPart := 0
for _, part := range parts {
if lenPart >= len(part) {
continue
}
fIdx := strings.Index(word, part)
if fIdx > 0 {
lastIdx := fIdx + len(part)
replaceWord = word[:fIdx] + "[" + part + "]" + word[lastIdx:]
lenPart = len(part)
}
}
//fmt.Println("replaceWord:", replaceWord, "word:", word)
if len(replaceWord) > 0 {
output[idx] = replaceWord
} else {
output[idx] = word
}
}
//fmt.Println(output)
return output
}
public static void main(String[] args) {
String[] words = {"Apple", "Melon", "Orange", "Watermelon"};
String[] parts = {"a", "mel", "lon", "lon", "el", "An"};
for(int i = 0; i<words.length; i++) {
int pos = words[i].length(), k = -1, plen = 0;
for(int j = 0; j < parts.length; j++) {
int idx = words[i].indexOf(parts[j]);
if(idx>-1 && (parts[j].length() > plen || (parts[j].length() == plen && idx<pos))) {
pos = idx;
k = j;
plen = parts[j].length();
}
}
if(k>-1)
System.out.println(words[i].substring(0, pos) + "[" + words[i].substring(pos, pos+plen) + "]" + words[i].substring(pos+plen, words[i].length()));
else
System.out.println(words[i]);
}
}
}
Output:
Apple
Me[lon]
Or[a]nge
Water[mel]on
Javascript solution
var findSubStrings = function(words, parts) {
let updatedWords = []
for(var i = 0; i < words.length; i++) {
var currentPart = ""
var currentWord = words[i]
for(var j = 0; j < parts.length; j++) {
var part = parts[j]
var search = currentWord.search(parts[j])
if(search > -1 && part.length > currentPart.length) {
currentPart = part
}
}
if(currentPart) {
var updatedWord = currentWord.replace(currentPart, `[${currentPart}]`)
updatedWords.push(updatedWord)
} else {
updatedWords.push(currentWord)
}
}
return updatedWords
}
public class Main {
public static void main(String[] args) {
String words[] = {"Apple", "Melon", "Orange", "Watermelon"};
String parts[] = {"a", "mel", "lon", "el", "An"};
for(String word: words)
{
String newWord= findSubString(word, parts);
System.out.println(newWord);
}
}
static String findSubString(String word, String[] parts)
{
String maxPart = "";
int startIndex = 0;
for (String part: parts) {
boolean matchFound = false;
int wordIndex = 0;
for(int i=0; i<word.length(); i++)
{
char wordChar = word.charAt(i);
for(char partChar :part.toCharArray())
{
if(wordChar == partChar)
{
matchFound=true;
if(wordIndex+1 < word.length()) {
wordChar = word.charAt(++wordIndex);
}
}
else
{
matchFound=false;
break;
}
}
if(matchFound)
{
if(part.length() > maxPart.length())
{
maxPart = part;
startIndex = i;
}
break;
}
wordIndex++;
}
}
String newWord = word;
if(!maxPart.isEmpty()) {
newWord = word.substring(0,startIndex) + "[" + maxPart + "]" + word.substring(startIndex + maxPart.length());
}
return newWord;
}
}
def find_substrings(words, parts):
sorted_parts = sorted(parts, key=len, reverse=True)
return [return_word_with_bracketed_part(word, parts) for word in words]
def return_word_with_bracketed_part(word, sorted_parts):
for part in sorted_parts:
if part in word:
return word.replace(part, "[{part}]".format(part=part))
return word
#include <iostream>
#include <string>
#include <vector>
using namespace std;
template <typename T>
void print(vector<T>& vec) {
for (T& str : vec) {
cout << str << " ";
}
cout << endl;
}
vector<string> findSubstrings(vector<string>& words, vector<string>& parts) {
vector<string> result;
// Sort the parts in decreasing order of length
sort(parts.begin(),parts.end(),[&] (string a, string b) {
return a.length() > b.length();
});
// print(parts);
for (string& str : words) {
size_t first_occuring = string::npos, found = string::npos, max_length = 0;
for (string& s : parts) {
size_t found = str.find(s);
if (found != string::npos) {
if (found < first_occuring && max_length <= s.length()) {
first_occuring = found;
max_length = max(max_length, s.length());
} else {
break;
}
}
}
if (first_occuring != string::npos) {
string sp = str.substr(0, first_occuring) + "[" + str.substr(first_occuring,max_length) + "]" + str.substr(first_occuring + max_length);
result.push_back(sp);
} else {
result.push_back(str);
}
}
return result;
}
int main() {
vector<string> words = {"Apple","Melon","Orange","Watermelon", "canteloupe"};
// vector<string> words = {"Watermelon"};
vector<string> parts = {"a","mel","lon","el","An"};
vector<string> s = findSubstrings(words, parts);
print(s);
}
words = ["Apple", "Melon", "Orange", "Watermelon"]
parts = ["a", "mel", "lon", "el", "An"]
#output ["Apple", "Me[lon]", "Or[a]nge", "Water[mel]on"].
res1 = {i:[] for i in words}
for i in words:
for j in parts:
if i.find(j) != -1:
res1[i].append(j)
keys = tuple(res1.keys())
values = tuple (res1.values())
val = map(lambda x : max(x) if len(x) > 0 else '',values)
a={k:v for k,v in zip(keys,val)}
for i in a.keys():
if a[i]!= '' :
pos = i.find(a[i])
arr = [k for k in i]
arr.insert(pos,'[')
arr.insert(pos+len(a[i])+1,']')
b= ''.join(arr)
print b
else:
print i
public class SubStrings {
private static String findSubstring(String word, String[] parts) {
int maxLength = 0;
int maxIndex = 0;
String maxPart = parts[0];
boolean matchFound = false;
for(String part: parts) {
int index = word.indexOf( part );
if(index >= 0) {
int length = part.length();
if(maxLength < length) {
maxLength = length;
maxPart = part;
maxIndex = index;
matchFound = true;
}
}
}
if(matchFound) {
String first = word.substring(0, maxIndex);
String part = word.substring(maxIndex, maxIndex + maxPart.length());
String last = word.substring(maxIndex + maxPart.length(), word.length());
return first + "[" + part + "]" + last;
}
return word;
}
private static String[] findSubstrings(String[] words, String[] parts) {
String[] newWords = new String[words.length];
int i = 0;
for(String word : words) {
newWords[i++] = findSubstring(word, parts);
}
return newWords;
}
public static void main(String[] args) {
String words[] = {"Apple", "Melon", "Orange", "Watermelon"};
String parts[] = {"a", "mel", "lon", "el", "An"};
String[] newWords = findSubstrings(words, parts);
for (String word: newWords ) {
System.out.println(word);
}
}
}
public class SubStrings {
private static String findSubstring(String word, String[] parts) {
int maxLength = 0;
int maxIndex = 0;
String maxPart = parts[0];
boolean matchFound = false;
for(String part: parts) {
int index = word.indexOf( part );
if(index >= 0) {
int length = part.length();
if(maxLength < length) {
maxLength = length;
maxPart = part;
maxIndex = index;
matchFound = true;
}
}
}
if(matchFound) {
String first = word.substring(0, maxIndex);
String part = word.substring(maxIndex, maxIndex + maxPart.length());
String last = word.substring(maxIndex + maxPart.length(), word.length());
return first + "[" + part + "]" + last;
}
return word;
}
private static String[] findSubstrings(String[] words, String[] parts) {
String[] newWords = new String[words.length];
int i = 0;
for(String word : words) {
newWords[i++] = findSubstring(word, parts);
}
return newWords;
}
public static void main(String[] args) {
String words[] = {"Apple", "Melon", "Orange", "Watermelon"};
String parts[] = {"a", "mel", "lon", "el", "An"};
String[] newWords = findSubstrings(words, parts);
for (String word: newWords ) {
System.out.println(word);
}
}
}
public class SubStrings {
private static String findSubstring(String word, String[] parts) {
int maxLength = 0;
int maxIndex = 0;
String maxPart = parts[0];
boolean matchFound = false;
for(String part: parts) {
int index = word.indexOf( part );
if(index >= 0) {
int length = part.length();
if(maxLength < length) {
maxLength = length;
maxPart = part;
maxIndex = index;
matchFound = true;
}
}
}
if(matchFound) {
String first = word.substring(0, maxIndex);
String part = word.substring(maxIndex, maxIndex + maxPart.length());
String last = word.substring(maxIndex + maxPart.length(), word.length());
return first + "[" + part + "]" + last;
}
return word;
}
private static String[] findSubstrings(String[] words, String[] parts) {
String[] newWords = new String[words.length];
int i = 0;
for(String word : words) {
newWords[i++] = findSubstring(word, parts);
}
return newWords;
}
public static void main(String[] args) {
String words[] = {"Apple", "Melon", "Orange", "Watermelon"};
String parts[] = {"a", "mel", "lon", "el", "An"};
String[] newWords = findSubstrings(words, parts);
for (String word: newWords ) {
System.out.println(word);
}
}
}
What are sizes of the lists? If words.size() is considerably smaller than part.size(), we could take the following approach.
1. Build a trie of all the words in parts. We can do this in O(P.L) time, where L is the average length of the of words in parts, and P, the number of elements in parts. We can maintain the index of the word in the parts array as a value in the leaf node representing the part word.
2. While building the trie above, we could determine the min (m) and max (M) length of any word in parts.
3. For each word in words, generate substrings of size S where m <= S <= M, and lookup each
such substring in the trie constructed in 1 above. Pick the longest substring that's found in the trie.
If there's a tie, pick the one that has the smallest index (we stored in the trie in 1 above)
- papatego February 22, 2018