Microsoft Interview Question: Write a function that when gi... | Glassdoor

Interview Question

New Graduate - Software Development Engineer In Test Interview Redmond, WA

Write a function that when given a string will return the

  position of the starting point of the largest reoccurring character. (ie. given:"AAABBCCCCD" would return 5 (starting point of C)) Test your code.
Answer

Interview Answer

1 Answer

0

import java.util.ArrayList;

public class TestRun2 {
    public static void main(String[] args) {
        /*
         * Write a function that when given a string will return the position of
         * the starting point of the largest reoccurring character. (ie.
         * given:"AAABBCCCCD" would return 5 (starting point of C))
         */

        String input = "AAABBCCCCD";

        System.out.print(largestReoccuringCharacter(input));
    }

    public static int largestReoccuringCharacter(String input) {
        // 1. Count all the characters, find the character that reoccurs the
        // most
        // 2. Find the position of the first most reoccuring character

        if(input == null || input.isEmpty())
        {
            return -1;
        }

        ArrayList charArrayList = new ArrayList();
        ArrayList charIndexList = new ArrayList();

        // Add all elements in input to ArrayList, and also a HashSet
        for (char c : input.toCharArray()) {
            Character inChar = (Character) c; // convert to object
            charArrayList.add(inChar);

            if (!charIndexList.contains(inChar)) {
                charIndexList.add(inChar);
            }
        }

        // For each char in the index, count occurences in arraylist. Find most
        // occuring
        int highestNumberOfOccurences = -1;
        Character highestChar = null;

        for (Character c : charIndexList) {
            int count = 0;
            while (charArrayList.contains(c)) {
                charArrayList.remove(c);
                count++;
            }

            if (count > highestNumberOfOccurences) {
                highestNumberOfOccurences = count;
                highestChar = c;
            }
        }

        // found character with highest count. Return index position.
        return input.indexOf(highestChar.toString());
    }
}

JUnit Test:

import static org.junit.Assert.*;

import org.junit.Test;

public class TestRun2Test {
    @Test
    public void testLargestReoccuringCharacter() {

        String input1 = "AAABBCCCCD";
        String input2 = "AAABBCCCCDDDDD";
        String input3 = "AAABBCCCCDDDD";
        String input4 = "AAABBCCCC AADDDD";
        String input5 = " ";
        String input6 = "";
        String input7 = null;

        assertEquals(TestRun2.largestReoccuringCharacter(input1), 5);
        assertEquals(TestRun2.largestReoccuringCharacter(input2), 9);
        assertEquals(TestRun2.largestReoccuringCharacter(input3), 5);
        assertEquals(TestRun2.largestReoccuringCharacter(input4), 0);
        assertEquals(TestRun2.largestReoccuringCharacter(input5), 0);
        assertEquals(TestRun2.largestReoccuringCharacter(input6), -1);
        assertEquals(TestRun2.largestReoccuringCharacter(input7), -1);
    }
}

Benny on Dec 17, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.