Software Engineer New Grad, Full-time, October 2021, No offer

1. Java: Design a restaurant class with methods to deal with seating people in the restaurant and also maintain waitlists and seat the next person from the waiting list when a person vacates the restaurant.
   My approach:
   Needed 3 hashmaps. One to map each table to the number of people it can accomodate. One map called occupied to keep track of the tables that are occupied, so map from a persons name to the table size they've occupied, and I reflect that change in the accomodate map I had above. One map called waitlists to keep track of the person and the number of people in that group. 4 methods: seat people, maintain waitlist, vacate table, when a table is vacated, make a call to a function to seat people from the waitlist.
   Feedback from the interviewer was positive and was the correct approach.

2. Invert a linked list. Iterative and recursive. In place.
   Gave the interviewer an iterative solution. He said okay let me make it recursive then. I solved it recursively in 5 minutes, he said he didn't understand the solution, even though the solution is pretty standard. It was hard to explain the solution without drawing it out and there was no whiteboard. By the end of the interview he finally understood the solution and said he was thinking about it wrong in the first place...

3. Given a list of error rates, an error rate threshold and a time frame. Check if there is a time window where all the error rates are above the threshold, if yes output "unhealthy" otherwise output "healthy".
   Example:
   error rates: 12% 5% 60% 50% 7% 34% 90%
   threshold = 15%
   time window = 3 seconds
   k ( value the window must contain) : 7%

My approach: simple sliding window. Find the value k the window must contain which is at index i. Start windows of sizes start = (time window - i)+1 and check each element in the window. If even 1 element is above threshold, break the loop. Start a new check for the next window which is at start+=1. Interviewer said it was the correct approach.

4. Given a graph that represents locations on a map and a list of vertices that are data centers, find a location that is furthest away from all the data centers to open a new data center.

Example:
Graph:
a-b-c-d-e-f-g
| |
e h
Data centers that exist : {a,g}
Output: Location thats furthest from a and g. d in this case.

My approach: Do BFS' on data centers that exist. The nodes in the last layer of each vertex should contain the vertices that are furthest away. Check if an element in the last layer is not a data center and is also in the last layer of the BFS' generated from all other elements. Interviewer said it could work but it was getting extremely complex to implement.