Answer to Question #227908 in Java | JSP | JSF for Rohit

Question

Dumbledore's Luncheon

Dumbledore is hosting a luncheon at Hogwarts, and Ron is incharge of the sitting plans.

Dumledore’s dining table can be thought of as an infinite row of seats with Dumbledore at one

end. Each of Dumbledore’s guests represents a character of English alphabet (a to z).

Dumbledore wants his guests to be seated such that the resulting string formed from the

alphabets should be lexicographically smallest (See examples for reference). He didn’t tell Ron

the total number of guests coming, but he will ask Ron to close the gate once all the guests

arrive (marking the end of incoming guests).

The rules of seating are as follows:

● Seats are allotted in sequential order, a guest who arrives later must be further from

Dumbledore than a guest who arrives earlier.

● An incoming guest must be assigned a seat, as soon as he arrives. He will take a seat.

Answer 1

import java.util.*;
class Main{
static Vector<Integer> restore(int arr[], int N)
{
    Vector<Integer> res = new Vector<>();
 
    HashMap<Integer,
            Integer> m = new HashMap<Integer,
                                      Integer>();
    for (int i = 0; i < N; i++)
    {
 
        if (m.containsKey(arr[i]) &&
            m.get(arr[i]) == 0)
        {
 
            res.add(arr[i]);
 
            if(m.containsKey(arr[i]))
            {
                m.put(arr[i], m.get(arr[i]) + 1);
            }
            else
            {
                m.put(arr[i], 1);
            }
        }
        else
            m.put(arr[i], 0);
    }
 
    return res;
}
 
static void printResult(Vector<Integer> res)
{
    for (int i = 0; i < res.size(); i++)
        System.out.print(res.get(i) + " ");
}
 
public static void main(String[] args)
{
    int arr[] = { 2, 13, 1, 4, 13, 24, 2, 2 };
 
    int N = arr.length;
 
    printResult(restore(arr, N));
}
}