Answer to Question #230342 in Java | JSP | JSF for Anonymous

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).

You are Ron, design a code using an efficient data structure that your magic wand will follow to

keep track of which guest to assign which seat. Explain the running time and also explain why

you have chosen the data structure which you have used.

Answer 1

Code

package ascendinglinkedlist;




public class AscendingLinkedList {
ListNode headNode; 
    ListNode sortedNode; 
  
    class ListNode 
    { 
        char val; 
        ListNode next; 
  
        public ListNode(char val) 
        { 
            this.val = val; 
        } 
    } 
  
    void insert(char val) 
    { 
         
        ListNode newNode = new ListNode(val);
        
        
        newNode.next = headNode; 
        
        
        headNode = newNode; 
    } 
  
    //Using insertion sort to arrange the data alphabetically
    void insertionSort(ListNode headRef) 
    { 
        
        sortedNode = null; 
        ListNode cur = headRef; 
        
       
        while (cur != null) 
        { 
            
            ListNode next = cur.next; 
            
            
            sortedInsert(cur); 
            
           
            cur = next; 
        } 
        
        
        headNode = sortedNode; 
    } 
  
      
   
    void sortedInsert(ListNode newNode) 
    { 
        
        if (sortedNode == null || sortedNode.val >= newNode.val) 
        { 
            newNode.next = sortedNode; 
            sortedNode = newNode; 
        } 
        else
        { 
            ListNode current = sortedNode; 
            
            
            while (current.next != null && current.next.val < newNode.val) 
            { 
                current = current.next; 
            } 
            
            newNode.next = current.next; 
            current.next = newNode; 
        } 
    } 
  
    
    void displayList(ListNode head) 
    { 
        while (head != null) 
        { 
            System.out.print(head.val + " "); 
            head = head.next; 
        } 
    } 
    
    public static void main(String[] args) {
         AscendingLinkedList node = new AscendingLinkedList(); 
        //You can insert more alphabet letters.
        node.insert('a'); 
        node.insert('b'); 
        node.insert('e'); 
        node.insert('d'); 
        
        System.out.println("Before arranging the Linked List alphabetically"); 
        node.displayList(node.headNode); 
        
        node.insertionSort(node.headNode); 
        
        System.out.println("\nAfter arranging the Linked List alphabetically"); 
        node.displayList(node.headNode); 
    }
    
}

The time complexity is $O(n ^ 2)$

Linked List data structure is used to solve the task because it can represent an infinite row of seats with Dumbledore being the first node