Ad

Why Does My Algorithm Not Check The Last Element Of The Linkedlist?

- 1 answer

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.

Ad

Answer

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;
Ad
source: stackoverflow.com
Ad