Given a string s and an array of smaller strings A, design a method to search s for each small string in A.

Question

Sigiloso · Accepted Answer

public class SuffixTree {
    SuffixTreeNode root = new SuffixTreeNode();
    public SuffixTree(String s) {
        for(int i =0; i getIndexes(String s) {
        return root.getIndexes(s);
    }
}

public class SuffixTreeNode {
        HashMap children = new HashMap();
        char value;
        ArrayList indexes = new ArrayList();    
        public SuffixTreeNode() {    }
        public void insertString(String s, int index){
            indexes.add(index);
            if(s != null && s.length() >0) {
                value = s.chartAt(0);
                SuffixTreeNode child = null;
                if(children.containsKey(value)) {
                    child = children.get(value);
                } else {
                        child = new SuffixTreeNode();
                        child.insertString(remainder, index);
            } 
    }
    public ArrayList get Indexes(String s) {
            if (s == null || s.length() == 0) {
                 return indexes;
            }  else {
                    char first = s.charAt(0);
                    if(children.containsKey(first)) {
                        String remainder = s.substring(1);
                        return children.get(first).getIndexes(remainder);
                    }
            }
            return null;
    }
}

public class Question {
        public static void main(String[] args) {
                String testString = "mississippi";
                String[] stringList = {"is", "sip", "hi", "sis"};
                SuffixTree tree = new SuffixTree(testString);
                for(String s : stringList) {
                        ArrayList list = tree.getIndexes(s);
                        if(list != null) {
                            System.out.println(s + ":" + list.toString());
                        }
                }
        }
}

Microsoft

Pergunta de entrevista da empresa Microsoft

Resposta da entrevista

Empresas seguidas

Buscas de vagas