Question

java

You are creating an array where each element is an (age, name) pair representing guests at a dinner Party.
You have been asked to print each guest at the party in ascending order of their ages, but if more than one
guests have the same age, only the one who appears first in the array should be printed.
Example input:
(23, Matt)(2000, jack)(50, Sal)(47, Mark)(23, will)(83200, Andrew)(23, Lee)(47, Andy)(47, Sam)(150, Dayton)

Example output:

(23, Matt) (47, Mark) (50, Sal (150, Dayton) (2000, Jack) (83200, Andrew)

Read all your party goers from a file. That is passed through the command line.

In your readme:
Describe a solution that takes O (1) space in addition to the provided input array. Your algorithm may modify the input array.
This party has some very old guests and your solution should still work correctly for parties that have even older guests, so your algorithm can’t assume the maximum age of the partygoers.
Give the worst-case tight-O time complexity of your solution.

I have been working on this problem but have been struggling with reading the file and
not getting errors such as no element found.

Answer 1

SOURCE CODE:

*Please follow the comments to better understand the code.

**Please look at the Screenshot below and use this code to copy-paste.

***The code in the below screenshot is neatly indented for better understanding.

GUESTS.TXT

(23, Matt)
(2000, jack)
(50, Sal)
(47, Mark)
(23, will)
(83200, Andrew)
(23, Lee)
(47, Andy)
(47, Sam)
(150, Dayton)

=============================

SortGuests.java

import java.io.File;
import java.util.Scanner;
public class SortGuests
{
    // assume maximum 100 people will come
    private static final int MAX_NUM =100 ;

    public static void main(String[] args) throws Exception {
        // pass the path to the file as a parameter
        File file = new File("/home/praveen_kumar/hu16-java-leavetracker/dummy/src/guests.txt");
        Scanner sc = new Scanner(file);

        // declare two arrays
        int[] age=new int[MAX_NUM];
        String[] names=new String[MAX_NUM];

        // read line by line into two parallel arrays
        int count = 0;
        while (sc.hasNextLine())
        {
            String data= sc.nextLine();
            age[count] = Integer.parseInt(data.split(",")[0].substring(1));
            String temp =data.split(" ")[1];
            names[count] = temp.substring(0,temp.length()-1);
            count++;
        }
        // Now we have the data in separate arrays
        for(int i=0;i<count-1;i++)
        {
            for(int j=0;j<count-i-1;j++)
            {
                if(age[j]>age[j+1])
                {
                    //swap ages
                    int temp = age[j];
                    age[j]=age[j+1];
                    age[j+1]=temp;

                    // swap names
                    String tempName = names[j];
                    names[j]=names[j+1];
                    names[j+1]=tempName;
                }
            }
        }
        System.out.println("\n\nThe Sorted Data is: ");
        // print the first guest
        System.out.print("("+age[0]+", "+names[0]+") ");

        // print only non-repeated guests ages
        for(int i=1;i<count;i++)
        {
            if(age[i]!=age[i-1]) //check if repeated
                System.out.print("("+age[i]+", "+names[i]+") ");
        }
    }
}

======================

SCREENSHOT:

FILE:

OUTPUT:

1. Here we are using the arrays used to store the given data. We are not using any other arrays. We are just replacing the values as in swap(). Hence it is O(1) space complexity
2. We are not assuming any age of the guests. it will work for any age.
3. We are using the Bubble Sort here. So, the time complexity is O(n²) in the worst case as we are using two loops.