Lift queries | HackerEarth Programming Problems and Solution

Lift queries is an easy HackerEarth problem, but it is a good example of a simulation task: you keep some state (where each lift is), update it after every query, and answer based on the current state, not the starting one. Many beginners compute each answer from the initial positions and get the second query wrong.

It also has a tie-breaking rule that you must apply exactly as stated, and up to 100,000 queries, so slow input reading in Java can become a real problem. Small problem, three useful habits.

Problem

A hostel block (BH3) has 7 floors and 2 lifts. Lift A starts at the ground floor, which is floor 0, and lift B starts at the top floor, floor 7. When someone calls a lift from floor N, the lift nearer to that floor goes there and stays there afterwards. If both lifts are the same distance away, the lift that is on the lower floor goes.

For each call, print which lift responds.

Input format: the first line has T, the number of calls. Each of the next T lines has one integer N, the floor making the call.

Output format: T lines, each with A or B.

Constraints: 0 <= N <= 7, 1 <= T <= 100000.

Input
2
3
5

Output
A
A

The first call from floor 3 is 3 away from A and 4 away from B, so A goes and is now at floor 3. The second call from floor 5 is 2 away from both lifts, so the lower lift, A, goes.

Approach

Keep two variables, the current floors of lift A and lift B. For each call:

1. Compute the distance from each lift to floor N using Math.abs.
2. If one distance is smaller, that lift goes.
3. If they are equal, the lift on the lower floor goes.
4. Move the chosen lift to floor N and print its letter.

Dry run on a longer case: calls 7, 0, 4, 4, 6.

• 7: A is 7 away, B is 0 away. B goes, B stays at 7.
• 0: A is 0 away. A goes, A stays at 0.
• 4: A is 4 away, B is 3 away. B goes, B moves to 4.
• 4: B is already there. B goes.
• 6: A is 6 away, B is 2 away. B goes, B moves to 6.

Output: B A B B B.

A small observation: lift A always stays below lift B. For B to jump below A, it would have to be strictly closer than A to some floor under A, but any floor under A is nearer to A than to B. The two lifts also never land on the same floor, because the lift already on the calling floor is at distance 0 and always wins. That is why simple code that subtracts without abs can still work, but using abs makes the logic obviously correct without needing that argument.

Solution in Java

The older solution here gave correct answers, but for a lucky reason. Its tie check was b - n == n - 1 where it meant n - a, a typo. It did not matter because both that branch and the final else chose A. It also relied on signed distances, which only work because of the observation above. I compared its output with the version below on 100,000 random calls and they matched, but the new code says what it means.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());

        int liftA = 0;   // starts at the ground floor
        int liftB = 7;   // starts at the top floor
        StringBuilder out = new StringBuilder();

        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            int distA = Math.abs(n - liftA);
            int distB = Math.abs(n - liftB);

            boolean sendA;
            if (distA != distB) {
                sendA = distA < distB;          // nearer lift wins
            } else {
                sendA = liftA <= liftB;         // tie: the lift on the lower floor
            }

            if (sendA) {
                liftA = n;                      // lift A now waits at floor n
                out.append('A');
            } else {
                liftB = n;
                out.append('B');
            }
            out.append('\n');
        }
        System.out.print(out);
    }
}

I used BufferedReader and a StringBuilder because 100,000 separate System.out.println calls and Scanner reads are noticeably slow. With this version, 100,000 random calls finished in about 0.3 seconds including JVM start-up.

Edge cases I tested: the sample (A A), the sequence 7 0 4 4 6 (B A B B B), and 6 5 7, which gives B B B. In that last one, B moves to 6, then floor 5 is 1 away from B and 5 away from A, and then floor 7 is again closest to B.

Output

A
A

Complexity

Time: O(1) per call, O(T) in total.

Space: O(1) for the lift positions, plus the output buffer, which is O(T).

Common mistakes

• Not moving the lift. If you forget to update the lift's floor after it answers a call, every later answer is computed from the starting floors.
• Tie goes to A "because it is first". The rule is the lower lift, not lift A. It happens to be A here because A never passes B, but write the rule as stated.
• Forgetting floor 0. The ground floor is 0, so there are 8 possible values of N, from 0 to 7.
• Slow I/O. Scanner plus println for 10^5 lines can time out on some judges. Buffer your input and output.

Related: Lift from TCS CodeVita is a harder lift simulation, and Cost of balloons is another HackerEarth problem.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerEarth solutions All coding problems MCQ practice