CareerCup

You will realize that when you want to move a person in position j to position i, our problem will become remove a person in position j and add it to position i with cost is abs(i - j). This means we can use insert sort to solve this problem.

We can solve this problem by following steps below:
+ Take all seven year old students and the teacher to the left and arranged them.
+ Store all remains eight year old students and arranged latter.

Example:
The initial class:
(1, E) (3, S) (-1, T) (9, S) (2, S) (1, E) (2, E)

Add student 2 to 1
(3, S) (1, E) (-1, T) (9, S) (2, S) (1, E) (2, E) -- cost: 1

Add student 4 to 2
(3, S) (9, S) (1, E) (-1, T) (2, S) (1, E) (2, E) -- cost: 2

Add student 5 to 2
(2, S) (3, S) (9, S) (1, E) (-1, T) (1, E) (2, E) -- cost: 4

Add teacher to end of seven year old students
(2, S) (3, S) (9, S) (-1, T) (1, E) (1, E) (2, E) -- cost: 1

Add student 7 to 5
(2, S) (3, S) (9, S) (-1, T) (2, E) (1, E) (1, E) -- cost: 2

Final answer is: 10

// create enum person type for teacher,
// seven year old students, eight year old students
public enum PersonType {
    TEACHER, SEVEN_YEAR_OLD, EIGHT_YEAR_OLD;
}

// create class Person. A person can be teacher,
// 7 year old student or 8 year old student
public class Person {
    public int height;
    public PersonType type;

    public Person(int height, PersonType type) {
        this.height = height;
        this.type = type;
    }
}

public int numberOfSwap(Person[] persons) {
    // let use example (1, E) (3, S) (-1, T) (9, S) (2, S) (1, E) (2, E)
    // for easy understand

    // init two list:
    // + one for arranging all 7 year old students
    // + one for store all remains 8 year old students
    List<Person> arrangedStudent7 = new ArrayList<Person>();
    List<Person> notArrangedStudent8 = new ArrayList<Person>();

    int n = persons.length;
    int answer = 0;

    // for determine we have met teacher
    boolean meetTeacher = false;

    // in this step we will swap all student year old to
    // the left of teacher and arranged them.
    // This mean after this loop we will have:
    // (2, S) (3, S) (9, S) (-1, T) (1, E) (1, E) (2, E).
    //
    // List arrangedStudent7 will store: (2, S) (3, S) (9, S)
    // List notArrangedStudent8 will store: (1, E) (1, E) (2, E)
    for (int i = 0; i < n; i++) {
        if (persons[i].type == PersonType.SEVEN_YEAR_OLD) {
            // if list arrangedStudent7 is empty,
            // add the first student to position 0
            if (arrangedStudent7.isEmpty()) {
                answer += i;
                arrangedStudent7.add(persons[i]);
            }
            // if not we use binary search to insert current student to list
            else {
                int left = 0;
                int right = arrangedStudent7.size() - 1;
                while (right - left > 1) {
                    int mid = (right + left) / 2;
                    if (persons[mid].height > persons[i].height) {
                        right = mid;
                    } else {
                        left = mid;
                    }
                }

                if (persons[right].height <= persons[i].height) {
                    answer += i - right - 1;
                    arrangedStudent7.add(right + 1, persons[i]);
                } else if (persons[left].height <= persons[i].height) {
                    answer += i - left - 1;
                    arrangedStudent7.add(left + 1, persons[i]);
                } else {
                    answer += i;
                    arrangedStudent7.add(0, persons[i]);
                }
            }

            // if we met teacher, this mean current 7 year old student is in the right
            // of teacher then we must swap to the left of teacher, so the answer increase by one.
            if (meetTeacher) {
                answer++;
            }
        } else if (persons[i].type == PersonType.EIGHT_YEAR_OLD) {
            notArrangedStudent8.add(persons[i]);

            // if we still not meet teacher, this mean current 8 year old student is in the left
            // of teacher then we must swap to the right of teacher, so the answer increase by one.
            if (!meetTeacher) {
                answer++;
            }
        } else {
            meetTeacher = true;
        }
    }

    // currently we arranged all 7 year old students and the teacher
    // the remain task is arrange all 8 year old students by using
    // binary search as above.
    List<Person> arrangedStudent8 = new ArrayList<Person>();
    for (int i = 0; i < notArrangedStudent8.size(); i++) {
        Person currentStudent = notArrangedStudent8.get(i);

        if (arrangedStudent8.isEmpty()) {
            arrangedStudent8.add(currentStudent);
        } else {
            int left = 0;
            int right = arrangedStudent8.size() - 1;
            while (right - left > 1) {
                int mid = (right + left) / 2;
                if (notArrangedStudent8.get(mid).height < currentStudent.height) {
                    right = i;
                } else {
                    left = i;
                }
            }

            if (notArrangedStudent8.get(right).height >= currentStudent.height) {
                answer += i - right - 1;
            } else if (notArrangedStudent8.get(left).height >= currentStudent.height) {
                answer += i - left - 1;
            } else {
                answer += i;
            }
        }
    }

    return answer;
}

Just count the inversions in an array.

Just need to count the inversions in an array where 7 year old are smaller than teacher and these are all smaller than 8 year olds.

public static void main

cs.rit.edu/~grd-665/hw2/

problem 2

are you asking home work question here???

Not quite sure if I understood the question right but I am assuming we want to sort them in asc/desc order of height. If that is the case why not Quick sort them? It is nlogn and requires only 5 swaps for the input given. Simplifying the input given here is how the initial array looks like: 3,4,1,2,0,6,5
After swap 1: 0,4,1,2,3,6,5
After swap 2: 0,2,1,4,3,6,5
After swap 3: 0,1,2,4,3,6,5
After swap 4: 0,1,2,4,3,5,6
After swap 5: 0,1,2,3,4,5,6

Other nlogn sorting algorithms - merge sort doesn't swap in its simple form and heap sort has more swaps than quicksort.

{

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class schoolLine {
 public void getLine() throws Exception{
	 List<Float> list = new ArrayList<Float>();
	 BufferedReader buf = new BufferedReader(new FileReader("C:\\Users\\Hitesh\\Desktop\\class.txt"));
	 String line;
	
	 Pattern p = Pattern.compile("\\d*\\.\\d+");
	 while((line = buf.readLine())!= null){
		 String[] arr = line.split(" ");
		 
		 for(int i =0;i<arr.length;i++){
			 Matcher m = p.matcher(arr[i]);
			 while(m.find()){
			System.out.println(m.group());
			list.add(Float.valueOf(m.group()));
	
			 }
			
		 }
		
		 }
	 float[] arrFinal = new float[list.size()];
	 for(int i=0;i<list.size();i++){
		 arrFinal[i] = (float)list.get(i);
		 System.out.println(arrFinal[i]);
	 }
	
	sort1(arrFinal);
	
	 }
 public void sort1(float[] list){
	int high = list.length - 1;
	int low = 0;
	int sum =0;
	List<Integer> list1 = new LinkedList<Integer>();
	 quickSort(list, low, high, list1);
	 System.out.println(list1);
	 for(int f : list1){
		 sum = sum + f;
	 }
	 System.out.println(sum);
 }
 
 private float array[];
 private int length;

 public static void quickSort(float[] arr, int low, int high, List<Integer> list1) {
	 int cnt = 0;
	 
		if (arr == null || arr.length == 0)
			return ;

		if (low >= high)
			return ;

		// pick the pivot
		int middle = low + (high - low) / 2;
		float pivot = arr[middle];

		// make left < pivot and right > pivot
		int i = low, j = high;
		while (i <= j) {
			while (arr[i] < pivot) {
				i++;
			}

			while (arr[j] > pivot) {
				j--;
			}

			if (i <= j) {
				float temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				cnt++;
				i++;
				j--;
				list1.add(cnt);
			}
			
		}
		
		// recursively sort two sub parts
		if (low < j)
			quickSort(arr, low, j, list1);

		if (high > i)
			quickSort(arr, i, high, list1);
		
	}
 

	public static void main(String[] args) {
		// TODO Auto-generated method stub
schoolLine sc = new schoolLine();
try {
	sc.getLine();
} catch (Exception e) {
	// TODO Auto-generated catch block
	e.printStackTrace();
}
	}

}

}