Question

Java Programming (Queues and LinkedLists)

The annual First robotics competition is hosted by SVSU every year, and each year students from different schools come in numbers to compete and show off their technical prowess.The  winner of the competition wins the prestigious Michigan state championship and bragging rights for the next 12 months.

The first step to participate in the competition is to register yourself as an contestant. This can be done at the registration booth at SVSU, where contestant form a single queue. Each student has a unique id within their respective schools, but 2 students from different schools may have the same id.

At the registration booth, there is a long queue of students from different schools. As the queue has started getting very long very quickly, students are starting to employ devious tactics to complete their registration sooner than other schools. When a new student arrives at the queue,  they do 2 things

1. They start searching for a schoolmate from the end of the queue. As soon as they find a schoolmate in the queue, the student will stand behind the schoolmate in the queue.
2. If no schoolmate is found, the student will stand  at the very end of the queue.

When the student at the beginning of the queue is registered, they are immediately removed form the queue.

So there are 2 types of operations that can take place on the queue.

• E x y : A new student of school x with id y joins the queue according to the strategy
• D : The student at the front of the queue is registered and is removed from the queue.

Given a set operations defined above, your task is to output the order in which students registered for the competition. See below for the input and output format

Input Format 12 E 1 1 E 2 1 E 3 2 E 1 5 D E 2 2 E 4 1 D D D D D

Output Format 1 1 1 5 2 1 2 2 3 2 4 1

Explanation

The 12 in the first line means we will do 12 operations, which are then listed below.

Let's go through this one operation at a time. Initially the queue is empty

Denoting Front of Queue as F, rear of Queue as R

F/R

1. E 1 1

   F/R

   (1,1)

   Initially the queue is empty, so add the first student with school 1 and id 1 to queue

2. E 2 1

   F R

   (1,1)

   (2,1)

   Next student with school 2 and id 1 arrives. As there are no schoolmates that go to school 2 in the queue, student (2,1) joins the back of the queue

3. E 3 2

   F R

   (1,1)

   (2,1)

   (3,2)

   Next student with school 3 and id 2 arrives. As there are no schoolmates that go to school 2 in the queue currently, student (3,2) joins the back of the queue

4. E 1 5

   F R

   (1,1)

   (1,5)

   (2,1)

   (3,2)

   Now, when student with school 1 and id 5 arrives they, start form the rear and start searching for another schoolmate, they find one (1,1) and joins the queue behind them
5. D

   F R

   (1,5)

   (2,1)

   (3,2)

   D means a student finished registering, so output their details and remove them from the queue

   Output : 1 1
   
6. E 2 2

   F R

   (1,5)

   (2,1)

   (2,2)

   (3,2)

   Next student with school 2 and id 2 arrives, starts scanning from the rear, and finds student (2,1) and joins behind them.

7. E 4 1

   F R

   (1,5)

   (2,1)

   (2,2)

   (3,2)

   (4,1)

   Next student with school 4 and id 1 arrives, starts searching for a schoolmate, finds none, thus joins the back of the queue.

8. D Output : 1 5
9. D Output : 2 1
10. D Output : 2 2
11. D Output : 3 2
12. D Output : 4 1

Operations 8-12 will simply output the school and student id at the front of the queue and remove them .

So the final output will look like

1 1

1 5

2 1

2 2

3 2

4 1

You may assume that a maximum of 4 schools participated.

As there may be multiple approaches to this problem, please make sure output matches mine exactly. That is each line in your output should be exactly 2 numbers separated by a single whitespace, denoting the school and id of the student being registered,

To ensure this please use the following template code and write all your code inside this class

Squeue.java

Sample runs

Run 1

Input 12 E 1 1 E 2 1 E 3 2 E 1 5 D E 2 2 E 4 1 D D D D D

Output 1 1 1 5 2 1 2 2 3 2 4 1

Run 2

Input 5 E 1 1 E 2 1 E 1 2 D D

Output 1 1 1 2

PreviousNext

Answer 1

Here's the full working solution. Comments are added for better understanding

PS: The comments for understanding are marked BOLD. So do not get confused with the non bold commented lines in code,that was just for debugging the code. Thank You.

import java.util.*;
class test {
   public static void main(String[] args){
       Scanner sc = new Scanner(System.in);
       int numOfOp = sc.nextInt(); //Taking input number of Operations to be performed
       /*Hashmap will store the school id of students belonging to a particular class
       For ex. Students are there like (1,1),(2,1),(1,5)
       So Hashmap will store [1]->1,5; [2]->1
       */
       HashMap<Integer,ArrayList<Integer>> hm = new HashMap<>();
       //This arraylist acts as a queue here.
       ArrayList<Integer> queue = new ArrayList<Integer>();
   int x,y;
   char ch;
   for(int l1=0;l1<numOfOp;l1++){
   ch = sc.next().charAt(0); //Takes the first char as input
   if(ch=='E'){ //if it is 'E'
               //System.out.println("Entered\n");
   x = sc.nextInt();
   y = sc.nextInt();
               if(queue.contains(x)){ //if queue already has students of that particular school then it will search for the student from the last and add the new student behind that student
                   ArrayList<Integer> q1 = new ArrayList<Integer>();
                   for(int i=queue.size()-1;i>=0;i--){
                       if(x==queue.get(i)){
                           for(int j=0;j<=i;j++){
                               q1.add(queue.get(j));
                           }
                           q1.add(x);
                           for(int j=i+1;j<queue.size();j++){
                               q1.add(queue.get(j));
                           }
                           queue = q1;
                           break;
                       }
                   }
               }else{
                   queue.add(x); //Else it'll just add it in queue
               }
               if(hm.containsKey(x)){
                   hm.get(x).add(y);
               }else{
                   ArrayList<Integer> a = new ArrayList<Integer>();
                   a.add(y);
                   hm.put(x,a);
               }
               //System.out.println("Hashmap:"+hm);
               //System.out.println("Queue:"+queue);
   }else{
               int top = queue.get(0);
               ArrayList<Integer> al = hm.get(top);
               System.out.println(top+" "+al.get(0));
               queue.remove(0);
               al.remove(0);
               if(al.size()==0)
                   hm.remove(top);
               else
                   hm.put(top,al);
              
               //System.out.println("Hashmap:"+hm);
               //System.out.println("Queue:"+queue);
           }
   }
   }
}

Answer 2

Please find the JAVA code below

_____________________________

package com;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class Registration {

public static void main(String[] args) {

System.out.println("Enter the input details");

//create a list to maintain the student data

LinkedList<SchoolAndId> list1 = new LinkedList<SchoolAndId>();

String var[] = null;

//variable to take the input

String trace = null;

Scanner input =new Scanner(System.in);

//initializing the index to -1

int index =-1;

//Read the number of operations

int operations = input.nextInt();

//iterate the while loop until the end of operations

while(operations>=0) {

//input the student ID and school ID with spaces in between

trace = input.nextLine();

var = trace.split(" ");

//condition to check whether to insert or to delete

if(var[0].equals("E")) {

//create a school object and place it in the list defined earlier

SchoolAndId obj = new SchoolAndId(var[1],var[2]);

//check whether the school ID is already present or not in the given list

index= checkforschool(list1,var[1]);

//if the school ID is already present in the list place the present object in the list after that index

if(index!= -1)

list1.add(index+1,obj);

else

list1.add(obj);

}else if(var[0].equals("D")) {

System.out.println(list1.get(0).getSchool() +" " + list1.get(0).getId());

list1.remove(0);

}

operations = operations-1;

}

}

public static int checkforschool(LinkedList<SchoolAndId> list1, String schoolId) {

//we are using the list to store other than queue so we should iterate the list from backward to check for the school ID in the list

int index = list1.size()-1;

while(index>=0) {

// return index if found

if(list1.get(index).getSchool().equals(schoolId))

return index;

index= index - 1;

}

//return -1 if not found

return -1;

}

}

package com;

public class SchoolAndId {

private String school;

private String id;

public String getSchool() {

return school;

}

public SchoolAndId(String school, String id) {

super();

this.school = school;

this.id = id;

}

public void setSchool(String school) {

this.school = school;

}

public String getId() {

return id;

}

public void setId(String id) {

this.id = id;

}

}

Output

______