Data-Structures-101

Question 1

Explain Quick Sort & Write a programme?

Answer 1

// Write a logial tree first and then write small functions to do just one job
	public int[] quickSort(int arr[]) {
		int pivot = 0;
		quickSortHelper(arr, pivot, pivot+1, arr.length-1);

	return arr;
}

private void quickSortHelper(int arr[], int pivot, int lowerLimit, int upperLimit) { // need not to do return if it the pass by reference

	if(lowerLimit >= upperLimit) // Use an upper limit to restriict infinity
		return ;

	while(lowerLimit <= upperLimit) {

			if(arr[lowerLimit] > arr[pivot] &amp;&amp; arr[upperLimit] < arr[pivot]) {
				swap(arr, lowerLimit, upperLimit);
				lowerLimit++;
				upperLimit--;
			}else if(arr[lowerLimit] <= arr[pivot] &amp;&amp; arr[upperLimit] >= arr[pivot]) {
				lowerLimit++;
				upperLimit--;
			} 

		else if(arr[lowerLimit] > arr[pivot]) {
			upperLimit--;
		} else if(arr[upperLimit] < arr[pivot]) {
			lowerLimit++;
		}

	}

	if(arr[pivot] > arr[upperLimit]) {
		swap(arr, pivot, upperLimit );
	}

	quickSortHelper(arr, pivot, pivot+1, upperLimit);

	quickSortHelper(arr, lowerLimit, lowerLimit+1, arr.length -1);

}

private void swap(int[] arr, int upperLimit, int lowerLimit) {
	int temp = arr[lowerLimit];
	arr[lowerLimit] = arr[upperLimit];
	arr[upperLimit] = temp;

}

Question 2

Write the logic for Fibonacci Series nth number?

Answer 2

take two temps, the first two ( starting will be given)
do while loop till nth

long start1 =0;
long start2 = 1;

while(n > 0)
fibo = start1 + start2;
start1 = start2;
start1 = fibo
n++