CODEWITHSUNDEEP
javaalgorithmlinked-list
user8827176
user8827176

Reputation:

Why does my algorithm not check the last element of the linkedlist?

I made a small system which takes a seatCount to fill a cinema with a certain amount of seats (no rows). Now I made a method which fills the seats and returns a Map, the map returns at what position a certain amount of seats are free (for instance 3-2 means there are two seats next to eachother beginning at place 3.

This works pretty well but if for example I say there are 5 seats maximum and seat 5 is free, the method does not return it to the map.

Here is the code used:

Object Seat

public class Seat {
    public Integer availability;
    public Integer seatNumber;

    public boolean IsFree() {
        if(availability == 0){
            return true;
        }
        else return false;
    }

    public String toString() {
        return "{ " + seatNumber + ", free: " + IsFree() + " } ";
    }
}

This method creates a LinkedList and fills the availibility with '1' (taken) or '0' (available) via the giveRandomAvailability() method

static LinkedList fillList(int seats){

    LinkedList<Seat> list = new LinkedList<Seat>();
    seats = seatCount;

    for(int i = 0; i < seats; i++){
        Seat seat = new Seat();
        seat.availability = giveRandomAvailability();
        seat.seatNumber = (i + 1);
        list.add(seat);
    }

    return list;
}

This is the method which does not work correctly, it should fill the map with the available seats, but when the last element is available, it does not map is. Here is an example output:

[{ 1, free: true } , { 2, free: true } , { 3, free: false } , { 4, free: true } , { 5, free: true } ]
{1=2}

You can see that the first part is handled well but it should also contain 4 = 2.

The method:

static Map fillSeats(){
    int n = 3;
    LinkedList<Seat> newList = fillList(seatCount);
    int consecutiveLength = 0; // Consecutive free seats length
    int index = 0;
    int startIndex = -1; // Store the start of consecutive free seats
    System.out.println(newList.toString());
    Map<Integer, Integer> consecutiveMap = new HashMap<>(); // Store startIndex -> length

    for (Seat seat : newList) {
        if (seat.IsFree()) {
            if (startIndex < 0) {
                startIndex = index;
            }
            consecutiveLength ++;
        } else {
            consecutiveMap.put(startIndex + 1, consecutiveLength);
            if (consecutiveLength == n) {
                // Found, do something here
            }
            // Reset
            startIndex = -1;
            consecutiveLength = 0;
        }
        index++;
    }
    return consecutiveMap;
}

I can not find the issue here, help would be greatly appreciated.

Upvotes: 4

Views: 78

Answers (2)

Jeroen Steenbeeke
Jeroen Steenbeeke

Reputation: 4013

Your call to consecutiveMap.put only exists within the else clause of your loop, and since the final element in your list is free, this code never gets executed for the final two seats.

  1. seat.IsFree() == true, increment counter
  2. seat.IsFree() == true, increment counter
  3. seat.isFree() == false, add value to map, reset counter
  4. seat.isFree() == true, increment counter
  5. seat.isFree() == true, increment counter

Then the loop terminates, so the final counter is not added to your map.

Upvotes: 1

Eran
Eran

Reputation: 393771

Well, your loop doesn't add the last group of consecutive seats if that group includes the last element of the List. You should add logic after your loop to add that last group:

for (Seat seat : newList) {
    if (seat.IsFree()) {
        if (startIndex < 0) {
            startIndex = index;
        }
        consecutiveLength ++;
    } else {
        consecutiveMap.put(startIndex + 1, consecutiveLength);
        if (consecutiveLength == n) {
            // Found, do something here
        }
        // Reset
        startIndex = -1;
        consecutiveLength = 0;
    }
    index++;
}
// added logic:
if (startIndex >= 0) {
    consecutiveMap.put(startIndex + 1, consecutiveLength);
}
return consecutiveMap;

Upvotes: 4

Related Questions