Interview Question: Puzzle - 100 Prisoners

In my latest interview I encountered the following puzzle.

There are 100 prisoners in the prison. All of them have either black or white cap.

Jailer has asked them to stand in the queue such that nth guy can see caps of all the guys standing ahead of him, but he can not see his own cap.

It means Guy standing at 100th position can see caps of all other 99 guys. Prisoner standing at 99th position can see caps of rest of 98 guys standing ahead of him.

Now jailer proposes to release the guy who can guess correct color of his own cap.

Assuming All the prisoner are nice guys ;), who can sacrifice for others, device a method which can help to release maximum number of prisoners.

Interview Question: Database Query: Find nth maximum salaried employee.

This question was asked to me in an screening process of a product based company.

Oracle database has employee table having EMPLOYEE_ID and SALARY as columns. Identify all the employee who get 3rd best salary in the company.

My instant answer was as follows:

SELECT * FROM EMPLOYEE WHERE ROW_NUMBER = 3 ORDER BY SALARY DESC

There was instant reaction, this query is wrong. Yes, it is. It will give me the 3rd most earning employee of the company but it will give me the THIRD BEST salary of the company.

So I modified my query a little bit and answered as follows:

SELECT * FROM EMPLOYEE WHERE SALARY = (SELECT DISTINCT(SALARY FROM EMPLOYEE WHERE ROW_NUMBER = 3 ORDER BY SALARY DESC) )


This query will work fine on oracle database but will not run on any other database. Interviewer was right. Now I did not know the way to figure out the third best salary. I did some Google search and found following options.

SELECT * FROM (SELECT EMPLOYEE_ID, SALARY, RANK() OVER (ORDER BY SALARY DESC) RANKSAL FROM EMPLOYEE) WHERE RANKSAL = 3;


SELECT * FROM EMPLOYEE E WHERE 3=(SELECT COUNT(DISTINCT SALARY) FROM EMPLOYEE WHERE E.SALARY<= SALARY);

SELECT LEVEL,MAX(SALARY) FROM EMPLOYEE WHERE LEVEL =3 CONNECT BY PRIOR SALARY > SALARY GROUP BY LEVEL;

So there are few ways to to figure out the third best salary.

Now during interview this question can be twisted in the following manner.

• Find the 3rd Minimum Salary.
• Find 10th Maximum/Minimum Salary.
• Find nth Maximum/Minimum salary of the Employee.
• Find all employees having salary less than 3rd best salary.

Interview Questions - Puzzle

A person has 50 Red Balls, 50 Blue Balls and two empty Jars with the capacity of 200 balls. This guy has to distribute following balls in the jars available to him.

Distribute the balls such that probability of withdrawing the red ball is maximum.

Assumptions:

• Person can pick any ball from any of the jars.
• Jars need not to have number of balls.
• It is not possible to place all the red balls on top of blue balls (This ordering will not work.) Person can shake the jars before withdrawing the ball.

In case of any doubts regarding the question, please comment.

Time Complexity of the Solution

Could you suggest me time complexity of the following solution:

02.// import java.math.*;

03.class Solution {

04. 

05.int sum = 0;

06.int sumTillCurrentIndex = 0;

07.int sumFromBack = 0;

08.int equi ( int[] A ) {

09.for(int i : A){

10.sum += i;

11.}

12. 

13.if(sum - A[0] == 0 ){

14.return 0;

15.}

16.if((sum - A[A.length -1]) == 0){

17.return(A.length -1);

18.}

19.sumFromBack = sum - A[0];

20.for(int index = 1; index < A.length - 1; index++){

21.sumTillCurrentIndex += A[index - 1];

22.sumFromBack -= A[index];

23.System.out.println("" + sum + ":"

24.+ sumTillCurrentIndex + ":" + sumFromBack );

25.if(sumFromBack == sumTillCurrentIndex){

26.return(index);

27.}

28.}

29.return -1;

30.}

31.}