## Uber Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

why in the example for "appletablet" "t" is a word, but for "thing" "t" is not a word ?

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

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

if(isRoot()) {
if(children==null) children = new Node(this);
}
}

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);
}
else
isWordBoundary = true;
} else {
if(nextSibling==null) nextSibling = new Node(this.parent);
}

}

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

}

if(dictionary==null) {
dictionary = new Node(null);
}

}

public static int findNumberOfWordsInDictionary(String word,String[] dictionaryWords) {

for(String dictionaryWord :dictionaryWords) {
}

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

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

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

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

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.

Comment hidden because of low score. Click to expand.
0

I dont understand the problem. Could you elaborate?

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

['apple', 't', 'able', 't']

should also be an answer if 't' is in the dictionary.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

import java.lang.*;
import java.util.*;

class WordBreak {
public static void main(String[] args){
Set<String> dic = new HashSet<>();

Set<List<String>> answers = test("ilikesamsung", new ArrayList<>(), dic);
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)){

}
}
}else{
}
return result;
}
}

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

/* 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(){
}

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>>();
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>();
}
}
}
return res;
}
}

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

f[i] the number of sentence made from s[:i]
f[0]=1
f[i]=\sum_j{f[j]*(s[j:i] in dictionary)}

return f[-1] as the result.

The cost would be o(n2)

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

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())) {
}
}
}
return validWords;
}

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

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

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

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

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

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)))
{
if (i == word.length())
{
res.remove(res.size() - 1);
return;
}
else
{
helperDiffSentences(word.substring(i,word.length()), dict, res, reslist);
res.remove(res.size() - 1);
}
}
}
}

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.

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