Interview Question

Member of Technical Staff Software Engineer Interview Palo Alto, CA

Given a series of strings, find the biggest common prefix.

Tags:
string logic
Answer

Interview Answer

3 Answers

1

/**
     * Jun Zheng, Rice Univ
     * Given a series of strings, find the biggest common prefix.
     * Real question of VMware
     * Java7; running time: O(n^2)
     * @param str
     * @return
     */
    private String biggestPrefix(String[] strs){
        String prefix=strs[0];
        for(int i=1;i<strs.length && prefix.length()>0;i++){
            int j;
            for(j=0;j<strs[i].length() && j<prefix.length();j++){
                if(prefix.charAt(j)==strs[i].charAt(j)) continue;
                else break;
            }
            //String.substring sucks!
            prefix=strs[i].substring(0, j);
        }
        return (prefix.length()>0)? prefix:"No such prefix!";
    }

Jun Zheng on Feb 20, 2013
0

How that works?
You are considering "prefix" must come from the very first string, which is not true.

In the following string set, the biggest common prefix is "xyzasd" - which this program fails to find!

String[] arr = {"MxyzasdNmm", "kxyzasdDodal", "I am a Good Boy", "JadxyznasdM Golmal", "ABCDEF", "ABCDEFGH", "Sunnyvale", "CaliforniaKxyzaszzMon"};

Java User on Feb 20, 2013
1

What? Prefix is not started from the very first string? Jesus I cannot read Eng!

Jun Zheng on Feb 21, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.