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 ?

- zr.roman November 18, 2015 | Flag Reply
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;
        }


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

- raptor.flaps February 10, 2016 | Flag Reply
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 
}

- NoOne October 08, 2016 | Flag Reply
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.

- revanthpobala November 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont understand the problem. Could you elaborate?

- bradfordli November 18, 2015 | Flag
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.

- Mabooka November 19, 2015 | Flag Reply
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) {
		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;
		}
	}
}

- Dheeraj Tyagi December 05, 2015 | Flag Reply
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) {
		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;
		}
	}
}

- Dheeraj Tyagi December 05, 2015 | Flag Reply
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) {
		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;
		}
	}
}

- dheeraj2311 December 05, 2015 | Flag Reply
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);
	}

- ilobak January 20, 2016 | Flag Reply
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);
	}

- ilobak January 20, 2016 | Flag Reply
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;
}

- jackdanielsparrow March 16, 2016 | Flag Reply
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<>();
        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;
    }
}

- Igor April 08, 2016 | Flag Reply
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(){
        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;
	}
}

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

How about dynamic programming:

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)

- zhangtemplar May 03, 2016 | Flag Reply
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())) {
                    validWords.add(sb.toString());
                }
            }
        }
        return validWords;
    }

- Anonymous June 02, 2016 | Flag Reply
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;
}

- shysta July 04, 2016 | Flag Reply
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;
}

- Siva August 29, 2016 | Flag Reply
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)))
			{
				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);
				}
			}		
		}
	}

- Denim March 29, 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