3
\$\begingroup\$

I am a beginner in programming, started about 2 months ago with Java, changing careers from law.

I have recently applied for an internship but was denied because I failed to do the pre-interview test right.

One of the tasks was to keep deleting 3 consecutive same integers from the array until the list is either empty or has no 3 consecutive same numbers. The assignment can be found here.

Below a description of the task with examples:

Three brothers walk into a bar. All the beverages are placed in one line at the long bar table. The size of each glass is represented in an array of integers, glasses. The brothers will drink a round if they can find 3 consecutive glasses of the same size. The barman removes the empty glasses from the table immediately after each round. Find the maximum number of rounds the three brothers can drink.

For glasses = [1, 1, 2, 3, 3, 3, 2, 2, 1, 1], the output should be brothersInTheBar(glasses) = 3. The brothers can start with a round of size 3, then after the glasses are cleared, a round of size 2 can be formed, followed by a round of size 1. One glass will be left at the table.

For glasses = [1, 1, 2, 1, 2, 2, 1, 1], the output should be brothersInTheBar(glasses) = 0. There are no 3 consecutive glasses of the same size.

This is my code:

    public int brothersInTheBar(int[] glasses){

    if(glasses.length<=2)
        return 0;

    ArrayList<Integer> glassesAsList = new ArrayList<Integer>();
    Arrays.stream(glasses).forEach(i -> glassesAsList.add(i));

    int counter=0;
    for (int x=0;x<glassesAsList.size()-2;++x){

        if(glassesAsList.get(x) == glassesAsList.get(x+1) && glassesAsList.get(x) == glassesAsList.get(x+2)){
            glassesAsList.remove(x);
            glassesAsList.remove(x);
            glassesAsList.remove(x);
            counter++;
            x=-1;
        }
        if(glassesAsList.isEmpty())
            break;
    }
 return counter;
 }

I sent the email back asking what I did wrong, so I can improve in the future. The response from the company only said that I have to look more into algorithm complexity and that my code is inefficient.

So my question is how to improve my algorithm and what is wrong with it?

\$\endgroup\$
1
3
\$\begingroup\$

Remove(x) deletes the element and then shifts every element up so it alone is an O(n) operation making your entire algorithm O(n^2). I actually wrote a removeAtFast(x) which swaps the item being removed and the last element then removes the last element normally. But you can't do this because it messes up the ordering.

I'd create a new array like what Pure Evil suggested. Just go through the elements and if you find 3 consecutive numbers skip 3 ahead and continue copying.

Edit: Also it would appear your code would fail the first example given in the assignment.

\$\endgroup\$
3
\$\begingroup\$

Welcome to Code Review. I'm starting from this declaration:

ArrayList<Integer> glassesAsList = new ArrayList<Integer>();

Better use declare it as a List and not ArrayList:

List<Integer> glassesAsList = new ArrayList<Integer>();

Here the main problem of your code:

for (int x=0;x<glassesAsList.size()-2;++x){
    if(glassesAsList.get(x) == glassesAsList.get(x+1) && glassesAsList.get(x) ==    glassesAsList.get(x+2)){
        glassesAsList.remove(x);
        glassesAsList.remove(x);
        glassesAsList.remove(x);
        counter++;
        x=-1;
     }
     if(glassesAsList.isEmpty())
          break;
}

You're iterating over a list and the operation is generally safe unless as in your case the loop contains a remove operation, because when you remove an element from a list all the elements at the right of it will be shifted and then all their indexes are changed by 1. One option to avoid the problem is use an iterator like below:

while (it.hasNext()) {
       Integer i = it.next();
       it.remove();
       //other instructions, I saved the value of the list element in the variable i
}

Due to the task, for me one list is not enough to solve it, you have to create another helper list where to store elements for comparisons with the current element i in the original list, below the full code of the class:

public class Rounds {

    public static int brothersInTheBar(int[] glasses) {
        if (glasses.length < 3) {
            return 0;
        }
        int rounds = 0;
        List<Integer> helper = new ArrayList<Integer>();
        List<Integer> glassesAsList = new ArrayList<Integer>();
        Arrays.stream(glasses).forEach(i -> glassesAsList.add(i));
        Iterator<Integer> it = glassesAsList.iterator();
        while (it.hasNext()) {
            Integer i = it.next();
            it.remove();
            int size = helper.size();
            if (size >= 2 && helper.get(size - 1) == i && helper.get(size - 2) == i) {
                helper.remove(size - 1);
                helper.remove(size - 2);
                ++rounds;
            } else { 
                helper.add(i);
            }
        }

        return rounds;
    }

    public static void main(String[] args) {
        System.out.println(brothersInTheBar(new int[] {1, 1, 2, 3, 3, 3, 2, 2, 1, 1}));
        System.out.println(brothersInTheBar(new int[] {1, 1, 2, 1, 2, 2, 1, 1}));

    }

}

The comparison will be between the last two elements of helper list and your element i in the loop, if all three are equals the last two elements will be deleted and rounds will be increment by 1, otherwise you will add the element i in the helper list.

Note : probably it is possible a solution that uses a list iterator (or perhaps a couple) and combinating it or them with the list, checks the two elements before the current and delete them together without an helper list.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ glassesAsList should be glasses since hungarian notation is not common in java. since that name is already taken you could simply refer to them as collection or rename the input parameter as int[] rawGlasses - very nice review +1 \$\endgroup\$ – Martin Frank Feb 20 '20 at 16:45
  • 1
    \$\begingroup\$ @MartinFrank Nice point, I haven't noticed it. \$\endgroup\$ – dariosicily Feb 20 '20 at 17:52
2
\$\begingroup\$

I'm not that good with java so I'll just say what I understand.

In my opinion what you could have done is instead of copying to another array you could have just checked the original array and if you didn't find the the number to be consecutive just add it to the new array.

We need to check the whole array so that is gonna take $$\mathcal{O}(n)$$ time. Copying the whole array would be more costly in my opinion.

If you are looking to improve your understanding of algorithm I would recommend these books 'Introduction to Algorithm' or 'Algorithm design'.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.