DevOps Zone is brought to you in partnership with:

Knut W. has posted 1 posts at DZone. View Full User Profile

Code Puzzler: Favorite Seats

02.03.2014
| 6867 views |
  • submit to reddit

Given an array of n rows numbered 0 to n-1, each of m seats 0 to m-1, where the cells have values True (meaning the seat is available) or False (meaning the seat is taken). A customer states that his favorite seat is at row x and seat y on that row.

If this seat is free, then the customer gets that seat. If it is taken, another seat is searched until a free seat has been found or it is clear that no free seat exist.

The search should start outwards from the preferred seat (x,y) in this fashion where 1 is the preferred seat, all 2's are second best two seats away, 3's are third best three seats away and so on.

3 3 3 3 3
3 2 2 2 3
3 2 1 2 3
3 2 2 2 3
3 3 3 3 3

Obviously the search should never go outside the array!


Published at DZone with permission of its author, Knut W. Hansson.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Elliot Pollard replied on Wed, 2014/02/05 - 9:08am

I had a go at this. (not had time to finish it yet)

  • Create an array of seats
  • Randomly assign seats true/false
  • Create a Map/2D Array to store coordinates of available seats
  • Loop through seats and add available coordinates to Map
  • (This is the part I struggle with) Order the results by the square of the distance away
  • First result will be favourite seat
Unsure on the use of Maps compared to a 2D Array... I'll keep working on it!

Sriram Padmanabhan replied on Tue, 2014/04/08 - 3:25am

Another solution which is basically brute-force method of recursion from the favorite seat to the next favorite seat.  Exception not handled, can me more parameterized.

package com.puzzles;

import java.util.Random;

public class SeatChooser {

	private int rowSize = 2;
	private int columnSize = 3;
	private int[][] seats;

	public static void main(String args[]) throws Exception {
		SeatChooser seatChooser = new SeatChooser();
		String rowSize = args[0];
		String columnSize = args[1];
		if ((rowSize == null) || (columnSize == null)) {
		} else {
			// Not handling the exception in this case and not checking for array out of bound exception.
			seatChooser.rowSize =  Integer.parseInt(rowSize);
			seatChooser.columnSize = Integer.parseInt(columnSize);

		}
		seatChooser.seats = new int[4][4];
		// Filling the arrays randomly
		seatChooser.fillRandomSeats();
		seatChooser.findSeats();
		System.out.println(" found the seats.");
		
	}

	/**
	 * 
	 * @throws Exception
	 */
	private void fillRandomSeats() throws Exception {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				boolean flag = new Random().nextBoolean();
				if (flag)
					this.seats[i][j] = 1;
				else
					this.seats[i][j] = 0;
			}
		}
		
	}

	/**
	 * 
	 * @throws Exception
	 */
	private void findSeats() throws Exception {
		if (this.seats[this.rowSize][this.columnSize] == 0) {
			this.seats[this.rowSize][this.columnSize] = 1;
			System.out.println(" Seats are available and assigned ");
		} else {
			checkForVacantSeats(1, 1);

		}
	}

	private void checkForVacantSeats(int rowDimension, int columnDimension) {

		System.out.println(rowDimension + " " + this.rowSize + " "
				+ columnDimension + " " + columnSize);
		if (((this.rowSize + rowDimension) < 4)
				&& (this.columnSize + columnDimension < 4)) {
			for (int i = (this.rowSize); i < (this.rowSize + rowDimension); i++) {
				for (int j = this.columnSize; j < (this.columnSize + columnDimension); j++) {
					if (this.seats[i][j] == 0) {
						this.seats[i][j] = 1;
						System.out
								.println(" Seats are available and assigned in row  "
										+ i + " and Colum " + j);
						return;
					}
				}

			}
		}

		if (((this.rowSize - rowDimension) >= 0)
				&& ((this.columnSize - columnDimension) >= 0)) {
			for (int i = this.rowSize; i > (this.rowSize - rowDimension); i--) {

				for (int j = this.columnSize; j > (this.columnSize - columnDimension); j--) {
					if (this.seats[i][j] == 0) {
						this.seats[i][j] = 1;
						System.out
								.println(" Seats are available and assigned in row  "
										+ i + " and Colum " + j);
						return;
					}
				}
			}
		}
		rowDimension = rowDimension + 1;
		columnDimension = columnDimension + 1;
		if(( ((this.rowSize + rowDimension) > 4)
				&& (this.columnSize + columnDimension > 4)  
				&& ((this.rowSize - rowDimension) <= 0)
				&& ((this.columnSize - columnDimension) <= 0) ))
			return;
		else
			checkForVacantSeats(rowDimension, columnDimension);
		}

}

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.