Uber Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
To solve this problem I would propose creating a dictionary like a trie structure and searching for words within this structure. Here is the solution.
// author raptor flaps
import java.util.ArrayList;
import java.util.List;
public class StringAndDictionary {
private static Node dictionary;
private static class Node {
char aChar = 0;
boolean isWordBoundary;
Node parent;
Node nextSibling;
Node children;
public Node(Node parent) {
this.parent = parent;
}
public void addWord(String word){
if(isRoot()) {
if(children==null) children = new Node(this);
children.addWordInternal(word);
}
}
public void addWordInternal(String word) {
if(word.length()==0) {
return;
}
if(this.aChar==word.charAt(0) || this.aChar==0 ) {
this.aChar = word.charAt(0);
if(word.length()>1) {
if(this.children==null) children = new Node(this);
children.addWordInternal(word.substring(1));
}
else
isWordBoundary = true;
} else {
if(nextSibling==null) nextSibling = new Node(this.parent);
nextSibling.addWordInternal(word);
}
}
public int matchWord(String word) {
if(word.length()==0)
return 0;
int count = 0;
if(isRoot()) {
count = children.matchWordInternal(word) + this.matchWord(word.substring(1));
}
return count;
}
private int matchWordInternal(String word){
if(word.length()== 0) return 0;
int count = 0;
if(aChar == word.charAt(0)) {
count += isWordBoundary?1:0;
count += children !=null?children.matchWordInternal(word.substring(1)):0;
}else {
if(nextSibling!=null) {
count += nextSibling!=null?nextSibling.matchWordInternal(word):0;
}
}
return count;
}
public boolean isRoot(){
return parent==null;
}
}
public static void addWordToDictionary(String word){
if(dictionary==null) {
dictionary = new Node(null);
}
dictionary.addWord(word);
}
public static int findNumberOfWordsInDictionary(String word,String[] dictionaryWords) {
for(String dictionaryWord :dictionaryWords) {
addWordToDictionary(dictionaryWord.toLowerCase());
}
return dictionary.matchWord(word.toLowerCase());
}
public static void main (String ...args) {
System.out.println(" Found : " + StringAndDictionary.findNumberOfWordsInDictionary("app", new String[]{"app", "left","let", "apple", "applet","jin","jinx"}));
System.out.println(" Found : " + StringAndDictionary.findNumberOfWordsInDictionary("jinx", new String[]{"app", "left","let", "apple", "applet","jin","jinx"}));
}
}
//ZoomBA : Imperative Style , almost
def part_word( word , dictionary ){
len = #|word|
for ( n : [ 0 : 2 ** ( len-1) ] ){
bm = str(n,2)
bm = '0' ** ( len - #|bm| -1 ) + bm
println( bm )
last = len - 1
start = 0
splits = list()
for ( i = len-2 ; i >=0 ; i -= 1){
if ( bm[i] == '1' ){
splits += word [ i + 1: last ]
last = i
}
}
splits += word[ start : last ]
println ( splits )
successful = !exists(splits) :: { ! ( $.o @ dictionary ) }
if ( successful ) return true
}
return false
}
Use regex.and compile all the words in the dictionary. match those words to the given string. append all the words into a list and output the list.
package uber;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class StringAndDictionary {
Set<String> d = new HashSet<String>();
static int count = 0;
Node node = new Node();
public static void main(String[] args) {
// TODO Auto-generated method stub
StringAndDictionary sd = new StringAndDictionary();
String s = "appletablet";
sd.get(s);
System.out.println(count);
}
private void get(String s) {
d.add("apple");
d.add("tablet");
d.add("applet");
d.add("able");
d.add("t");
d.add("app");
d.add("let");
d.add("t");
Iterator<String> dr = d.iterator();
while (dr.hasNext()) {
insert(dr.next());
}
int i = 0;
int n = s.length();
find(s, i, n - 1);
}
private void find(String s, int l, int h) {
if (l == h+1) {
count++;
return;
}
Node temp = node;
int i = l;
while (i <= h && temp != null) {
temp = temp.nodes[s.charAt(i) - 'a'];
i++;
if(temp != null && temp.end){
find(s,i,h);
}
}
}
private void insert(String s) {
int i = 0;
int n = s.length();
Node temp = node;
while (i < n) {
if (temp.nodes[s.charAt(i) - 'a'] == null) {
temp.nodes[s.charAt(i) - 'a'] = new Node();
}
temp = temp.nodes[s.charAt(i) - 'a'];
i++;
}
temp.end = true;
}
}
class Node {
Node nodes[];
boolean end;
public Node() {
nodes = new Node[26];
for (int i = 0; i < 26; i++) {
nodes[i] = null;
end = false;
}
}
}
package uber;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class StringAndDictionary {
Set<String> d = new HashSet<String>();
static int count = 0;
Node node = new Node();
public static void main(String[] args) {
// TODO Auto-generated method stub
StringAndDictionary sd = new StringAndDictionary();
String s = "appletablet";
sd.get(s);
System.out.println(count);
}
private void get(String s) {
d.add("apple");
d.add("tablet");
d.add("applet");
d.add("able");
d.add("t");
d.add("app");
d.add("let");
d.add("t");
Iterator<String> dr = d.iterator();
while (dr.hasNext()) {
insert(dr.next());
}
int i = 0;
int n = s.length();
find(s, i, n - 1);
}
private void find(String s, int l, int h) {
if (l == h+1) {
count++;
return;
}
Node temp = node;
int i = l;
while (i <= h && temp != null) {
temp = temp.nodes[s.charAt(i) - 'a'];
i++;
if(temp != null && temp.end){
find(s,i,h);
}
}
}
private void insert(String s) {
int i = 0;
int n = s.length();
Node temp = node;
while (i < n) {
if (temp.nodes[s.charAt(i) - 'a'] == null) {
temp.nodes[s.charAt(i) - 'a'] = new Node();
}
temp = temp.nodes[s.charAt(i) - 'a'];
i++;
}
temp.end = true;
}
}
class Node {
Node nodes[];
boolean end;
public Node() {
nodes = new Node[26];
for (int i = 0; i < 26; i++) {
nodes[i] = null;
end = false;
}
}
}
package uber;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class StringAndDictionary {
Set<String> d = new HashSet<String>();
static int count = 0;
Node node = new Node();
public static void main(String[] args) {
// TODO Auto-generated method stub
StringAndDictionary sd = new StringAndDictionary();
String s = "appletablet";
sd.get(s);
System.out.println(count);
}
private void get(String s) {
d.add("apple");
d.add("tablet");
d.add("applet");
d.add("able");
d.add("t");
d.add("app");
d.add("let");
d.add("t");
Iterator<String> dr = d.iterator();
while (dr.hasNext()) {
insert(dr.next());
}
int i = 0;
int n = s.length();
find(s, i, n - 1);
}
private void find(String s, int l, int h) {
if (l == h+1) {
count++;
return;
}
Node temp = node;
int i = l;
while (i <= h && temp != null) {
temp = temp.nodes[s.charAt(i) - 'a'];
i++;
if(temp != null && temp.end){
find(s,i,h);
}
}
}
private void insert(String s) {
int i = 0;
int n = s.length();
Node temp = node;
while (i < n) {
if (temp.nodes[s.charAt(i) - 'a'] == null) {
temp.nodes[s.charAt(i) - 'a'] = new Node();
}
temp = temp.nodes[s.charAt(i) - 'a'];
i++;
}
temp.end = true;
}
}
class Node {
Node nodes[];
boolean end;
public Node() {
nodes = new Node[26];
for (int i = 0; i < 26; i++) {
nodes[i] = null;
end = false;
}
}
}
public static class result{
int cnt ;
boolean success;
public result(int a, boolean s){ cnt = a; success = s;}
}
public static result extractWords(String s, HashMap<String, Integer> dic){
if(s.length() == 0) return new result(1, true);
int cnt = 0;
for(int i = 1; i <= s.length(); i++){
if(dic.containsKey(s.substring(0, i))){
result r = extractWords(s.substring(i), dic);
if(r.success) cnt+=r.cnt;
}
}
if(cnt >0){
return new result(cnt, true);
}
return new result(0, false);
}
public static class result{
int cnt ;
boolean success;
public result(int a, boolean s){ cnt = a; success = s;}
}
public static result extractWords(String s, HashMap<String, Integer> dic){
if(s.length() == 0) return new result(1, true);
int cnt = 0;
for(int i = 1; i <= s.length(); i++){
if(dic.containsKey(s.substring(0, i))){
result r = extractWords(s.substring(i), dic);
if(r.success) cnt+=r.cnt;
}
}
if(cnt >0){
return new result(cnt, true);
}
return new result(0, false);
}
// Example program
#include <iostream>
#include <string>
#include <set>
#include <vector>
using namespace std;
bool foo(string s, set<string> dic, int &cnt){
if(s.empty())
return true;
for(int i=0;i<s.length();++i){
string prefix = s.substr(0,i), suffix = s.substr(i);
if((dic.count(prefix)&&dic.count(suffix))
||(dic.count(prefix)&&foo(suffix,dic,cnt))){
cnt++;
}
}
return true;
}
int main()
{
string s = "applet";
set<string> dic{"","app","let","t","apple","applet"};
int cnt = 0;
foo(s,dic,cnt);
cout<<cnt;
}
import java.lang.*;
import java.util.*;
class WordBreak {
public static void main(String[] args){
Set<String> dic = new HashSet<>();
dic.add("i");
dic.add("like");
dic.add("sam");
dic.add("sung");
dic.add("samsung");
dic.add("mobile");
dic.add("ice");
dic.add("cream");
dic.add("icecream");
dic.add("man");
dic.add("go");
dic.add("mango");
Set<List<String>> answers = test("ilikesamsung", new ArrayList<>(), dic);
System.out.printf("Total answers %s\n", answers.size());
for(List<String> list : answers){
for(String word: list){
System.out.printf("%s ", word);
}
System.out.println();
}
}
private static Set<List<String>> test(String input, List<String> path, Set<String> dic){
Set<List<String>> result = new HashSet<>();
if(input.length() > 0){
for(int i = 1; i <= input.length(); i++){
String prefix = input.substring(0, i);
if(dic.contains(prefix)){
path.add(prefix);
result.addAll(test(input.substring(i), new ArrayList<>(path), dic));
}
}
}else{
result.add(path);
}
return result;
}
}
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
Set<String> dict = new HashSet();
public Main(){
dict.add("app");
dict.add("apple");
dict.add("applet");
dict.add("t");
dict.add("a");
dict.add("let");
}
public static void main (String[] args) throws java.lang.Exception{
Main c = new Main();
System.out.println(c.getSentences(""));
}
public List<List<String>> getSentences(String str){
return getSentences(str, 0);
}
private List<List<String>> getSentences(String str, int start){
List<List<String>> res = null;
if(start >= str.length()){
res = new ArrayList<List<String>>();
res.add(new ArrayList<String>());
return res;
}
for(int i=start; i<str.length(); ++i){
String subStr = str.substring(start, i+1);
//System.out.println("Sub " + subStr);
if(!dict.contains(subStr)){
continue;
}
else{
//System.out.println("word " + subStr);
List<List<String>> subRes = getSentences(str, i+1);
if(subRes == null){
continue;
}
if(res == null){
res = new ArrayList<List<String>>();
}
for(List<String> sentence : subRes){
List<String> currSentence = new ArrayList<String>();
currSentence.add(subStr);
currSentence.addAll(sentence);
res.add(currSentence);
}
}
}
return res;
}
}
public static Set<String> findValidStrings(String str) {
if (str.length() == 0) {
throw new IllegalArgumentException("Strings of length 0 are illegal");
}
final Set<String> validWords = new HashSet<String>();
for (int i = 0; i < str.length(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = i; j < str.length(); j++) {
sb.append(str.charAt(j)); // O(1) complexity.
if (dictionary.contains(sb.toString())) {
validWords.add(sb.toString());
}
}
}
return validWords;
}
function getWords(s, dict) {
var result = [];
var characters = s.split('');
var avail = {}
var char, word, valid, i, j, spent;
for (i = 0, ii = characters.length; i < ii; i++) {
char = characters[i];
avail[char] = avail[char] || 0;
avail[char]++;
}
for (i = 0, ii = dict.length; i < ii; i++) {
word = dict[i]
characters = word.split('');
spent = {};
valid = true;
for (j = 0, jj = characters.length; j < jj; j++) {
char = characters[i];
spent[char] = spent[char] || 0;
spent[char]++;
if (spent[char] > avail[char]) {
valid = false;
break;
}
}
if (valid) {
result.push(word);
}
}
return result;
}
void checkDictionary(string word, map<string,int> arrayDict, int *count ){
for(int i=1; i<word.length(); i++)
{
if(arrayDict.find(word.substr(0,i+1)) != arrayDict.end() && arrayDict[word.substr(0,i+1)] == 0)
{
cout<<word.substr(0,i+1)<<endl;
arrayDict[word.substr(0,i+1)]++;
(*count)++;
}
}
if(word.length()>1)
checkDictionary(word.erase(0,1), arrayDict, count);
}
int main(int argc, const char * argv[]) {
map<string, int> ar = {{"apple",0}, {"appletablet",0},{"able",0},{"let",0},{"app",0},{"tab",0},{"hello",0},{"p",0}};
string word = "appletablet";
int count;
checkDictionary(word, ar, &count);
cout<<"Count is "<<count<<endl;
return 0;
}
public static List<List<String>> findDiffSentences(String word, Set<String> dict)
{
List<List<String>> reslist = new ArrayList<List<String>>();
helperDiffSentences(word, dict, new ArrayList<String>(), reslist);
return reslist;
}
private static void helperDiffSentences(String word, Set<String> dict, List<String> res, List<List<String>> reslist) {
for (int i = 1; i <= word.length(); i++)
{
if (dict.contains(word.substring(0, i)))
{
res.add(word.substring(0, i));
if (i == word.length())
{
reslist.add(new ArrayList<String>(res));
res.remove(res.size() - 1);
return;
}
else
{
helperDiffSentences(word.substring(i,word.length()), dict, res, reslist);
res.remove(res.size() - 1);
}
}
}
}
why in the example for "appletablet" "t" is a word, but for "thing" "t" is not a word ?
- zr.roman November 18, 2015