Amazon.com

  www.amazon.com
  www.amazon.com

Interview Question

Software Development Engineer Intern Interview

Write a function to remove all redundant characters in a

  given string.
Answer

Interview Answer

3 Answers

0

solution in Java:

public class RemoveDuplicateChars {
    String str1 = "foo";

    public String removeDuplicates(String str1) {
        String result = "";
        for (int i=0; i < str1.length(); i++) {
            if (!result.contains("" + str1.charAt(i))) {
                result += "" + str1.charAt(i);
            }
        }
        return result; // returns "fo"
    }
}

Chase on Jan 11, 2014
0

Careful, because result.contains may require n time to go through, where n is the length of the result. So the worst case would be O(n^2). You could optimise in time sorting the string in O(n logn) time and then look for adjacent elements or if space is not a problem use a Map<String, Integer>, where the key is a char of the string and the value is the number of occurrences of the char. At the end consider only chars that occurrence once. This would be O(n) in time and O(n) in space.

Luca on Jan 13, 2014
2

public static String removeDups(String str){
        if(str == null) return null;
        boolean[] carr = new boolean[256];
        String result = "";
        for(int i=0;i<str.length();i++){
            if(!carr[str.charAt(i)]){
                carr[str.charAt(i)] = true;
                result+=str.charAt(i);
            }
        }
        return result;
    }

Naan on Jan 29, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.