Interview Question
Country: United States
Interview Type: Phone Interview
public static boolean isSeatingAvail(int[] row, int seatsRequests) {
if (row == null || row.length == 0 || seatsRequests < 0) {
return false;
}
final int openSeatsNeeded = seatsRequested + 2;
int openSeats = 1; // Start with one for first seat
for (int seat : row) {
if (seat == 0) {
openSeats ++;
} else {
openSeats = 0;
}
if (openSeats >= openSeatsNeeded) {
return true;
}
}
// Add one for end seat and recheck
openSeats ++;
if (openSeats >= openSeatsNeeded) {
return true;
}
return false;
}
This concise function yields the max number of seats possible:
```
public static int countMaxPossibleAllocation(int[] seats) {
int count = 1, ans = 0;
for(int i = 0; i < seats.length; i++) {
if(seats[i] == 1) {
ans += (count - 1) / 2;
count = 0;
}else{
count++;
}
}
if(count > 0) ans += count / 2;
return ans;
}
```
In the following code, the GetAvailableSeats() method returns the indices where the newcomers can be seated.
It runs in O(n).
class Program
{
static void Main(string[] args)
{
var seats = new int[] { 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0 };
var availableSeats = GetAvailableSeats(seats);
for (var i = 0; i < seats.Length; i++)
{
Console.Write($"{seats[i]} ");
}
Console.WriteLine();
for (var i = 0; i < seats.Length; i++)
{
Console.Write(availableSeats.Contains(i) ? "Y " : $" ");
}
Console.WriteLine("\n");
}
private static int[] GetAvailableSeats(int[] seats)
{
var n = 1;
var result = new List<int>();
for (var i = 0; i < seats.Length; i++)
{
switch (seats[i])
{
case 0:
if (++n == 3)
{
result.Add(i - 1);
n -= 2;
}
break;
case 1:
n = 0;
break;
default:
throw new ArgumentException("Array should contain either 0 or 1");
}
}
if (n == 2)
{
result.Add(seats.Length - 1);
}
return result.ToArray();
}
}
package main
import "fmt"
func isPossible(seats []int, count int) bool {
possible := 0
freeCount := 0
if len(seats) == 0 {
return false
}
if seats[0] == 0 {
freeCount = 1
}
for i := 0; i < len(seats); i++ {
if seats[i] == 0 {
freeCount++
} else {
possible += (freeCount - 1) / 2
if possible >= count {
return true
}
freeCount = 0
}
}
possible += freeCount / 2
if possible >= count {
return true
}
return false
}
func main() {
seats := []int{1, 0, 0, 0, 0, 0, 1, 0, 0}
fmt.Println(isPossible(seats, 3))
fmt.Println(isPossible(seats, 4))
seats = []int{1, 0, 0, 1, 0, 0, 1, 0, 0}
fmt.Println(isPossible(seats, 1))
fmt.Println(isPossible(seats, 2))
seats = []int{0}
fmt.Println(isPossible(seats, 1))
fmt.Println(isPossible(seats, 2))
}
static boolean isNumberOfSeatsAvailable(int[] seats, int peopleNumber) {
int availableSeats = 0;
if (seats.length == 0) {
return true;
}
boolean isSeatAfterEmpty, isSeatBeforeEmpty=(seats[0]==0);
for (int i = 1; i <seats.length-1 ; i++) {
isSeatAfterEmpty=(seats[i+1]==0);
if (isSeatBeforeEmpty && seats[i]==0 && isSeatAfterEmpty){
//sit a person here
availableSeats++;
if (availableSeats >= peopleNumber) {
return true;
}
isSeatBeforeEmpty=false;
}
else{
//is this an empty seat?
isSeatBeforeEmpty=(seats[i]==0);
}
}
if (isSeatBeforeEmpty && seats[seats.length-1]==0){
availableSeats++;
}
return (availableSeats >= peopleNumber);
}
public boolean areSeatsAvailable(int[] row, int noOfPeople) {
if (row.length < noOfPeople) {
return false;
}
int emptySeatsCount = 0;
int i=0;
while (i < row.length) {
if (row[i] == 0) {
emptySeatsCount++;
if (emptySeatsCount >= noOfPeople &&
getAreSeatsBeforeEmpty(i, row, noOfPeople) &&
getIsSeatAfterEmpty(i, row)) {
return true;
}
} else {
emptySeatsCount = 0;
}
i++;
}
return false;
}
public boolean getAreSeatsBeforeEmpty(int i, int[] row, int n) {
// return true if they're the first n seats of the row
if (i - n == -1) {
return true;
}
return row[i - n] == 0;
}
public boolean getIsSeatAfterEmpty(int i, int[] row) {
// return true if this is the last seat of the row
if (i == row.length-1) {
return true;
}
return row[i+1] == 0;
}
# "row" is just an array of 0s and 1s
# where 1 means the seat is occupied, and 0 means the seat is free
# "number" - is amount of people we want to seat
def get_available_seats(row, number)
# we're searching for the longest sequence of 0s
max = 0 # store the longest
cur = 0 # accumulate the current
# appent and prepend row sequence with 0s to ensure that people can seat
# at the edge of the row
([0]+row+[0]).each do |seat|
if seat == 1
# found occupied seat, compare sequence with max and reset current
max = max > cur ? max : cur
cur = 0
else
# counting current sequrnce
cur += 1
end
end
# reached the end, compare last sequence with max
max = max > cur ? max : cur
# people don't like to seat next to each other, so we leave 2 seats around
number <= max - 2
end
p get_available_seats([1,0,0,0,0,0,1,0,0], 3) # true
p get_available_seats([1,0,0,0,0,0,1,0,0], 4) # false
puts
p get_available_seats([1,0,0,1,0,0,1,0,0], 1) # true
p get_available_seats([1,0,0,1,0,0,1,0,0], 2) # false
puts
p get_available_seats([0], 1) # true
p get_available_seats([0], 2) # false
import java.util.*;
import java.io.*;
import java.lang.*;
public class Solution {
boolean function(int a[],int val){
if(a[0]==0){ if(a[1]!=1){val--;}}
if(a[a.length-1]==0){if(a[a.length-2]!=1){val--;}}
int j=a.length;
while(j>0){
if(a[j]==0){if(a[j-1]!=1&&a[j+1]!=1){val--;}}
j--;
}
if(val==0){return true;}
else{return false;}
}
public static void main(String[] args) {
Solution solution=new Solution();
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int array[]=new int[n];
for(int i=0;i<n;i++){
array[i]=sc.nextInt();
}
int person=sc.nextInt();
if(solution.function(array, person)==true){System.out.println("possible");}
else{System.out.println("Not possible");}
}
}
bool cansit(std::vector<bool> o, int c) {
for(std::vector<bool>::iterator itr = o.begin(); c > 0 && itr != o.end(); ++itr) {
if(*itr) {
++itr;
}
else {
std::vector<bool>::iterator next = itr;
++next;
if(next != o.end() && *next == true) {
itr = next;
++itr;
}
else if(next == o.end() || *next == false) {
c--;
itr = next;
}
}
if(itr == o.end())
break;
}
return c <= 0;
}
- Matoy February 03, 2017static boolean isNumberOfSeatsAvailable(int[] seats, int peopleNumber) { int availableSeats = 0; if (seats.length == 0) { return true; } boolean isSeatAfterEmpty, isSeatBeforeEmpty=(seats[0]==0); for (int i = 1; i <seats.length-1 ; i++) { isSeatAfterEmpty=(seats[i+1]==0); if (isSeatBeforeEmpty && seats[i]==0 && isSeatAfterEmpty){ //sit a person here availableSeats++; if (availableSeats >= peopleNumber) { return true; } isSeatBeforeEmpty=false; } else{ //is this an empty seat? isSeatBeforeEmpty=(seats[i]==0); } } if (isSeatBeforeEmpty && seats[seats.length-1]==0){ availableSeats++; } return (availableSeats >= peopleNumber); }