Uber Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
//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
}
Dictionary Tree version
class Node{
boolean isWord = false;
HashMap<Character, Node> children = new HashMap<>();
}
class DictTree{
private Node root = new Node();
private int maxLen = 0;
void addWord(String s){
Node cur = root;
for(int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
if(!cur.children.containsKey(ch)){
Node newNode = new Node();
cur.children.put(ch, newNode);
cur = newNode;
}
else{
cur = cur.children.get(ch);
}
}
cur.isWord = true;
if(s.length() > maxLen) {
maxLen = s.length();
}
}
List<Integer> getPrefix(String s){
List<Integer> ret = new ArrayList<>();
int len = Math.min(s.length(), maxLen);
Node cur = root;
for(int i = 0; i < len; i++){
char ch = s.charAt(i);
if(!cur.children.containsKey(ch)){
return ret;
}
cur = cur.children.get(ch);
if(cur.isWord){
ret.add(i + 1);
}
}
return ret;
}
}
class Solution {
public boolean tryToSegment(String s, List<String> dict) {
if(s.length() == 0){
return false;
}
DictTree dt = new DictTree();
for (String str : dict) {
dt.addWord(str);
}
return tryToSegment2(s, dt);
}
private boolean tryToSegment2(String s, DictTree dt){
if(s.length() == 0) return true;
List<Integer> ret = dt.getPrefix(s);
for(Integer i : ret){
if(tryToSegment2(s.substring(i), dt)){
return true;
}
}
return false;
}
}
Here's a backtracking solution written in C#:
- swerddogg May 12, 2016