Programming Interview Questions

Shilpi_Roy

Developer at Hewlett Packard

Questions (9)

Comments (3)

Followers (5)

Reputation 265

Page:

Comment hidden because of low score. Click to expand.

of 0 vote

1) One can sort the array and then get the three largest from the end of the array. But this will be O(nlogn) solution depending on the sorting technique used.

2) Initiate first, second and third element with MIN_Value. Compare each element with the first ,second and third element as we move along the array.
Time Complexity : O(n) Space Complexity : O(1)

public class ThreeLargest {
	private static void get3Largest(int[] arr) {
		int first = Integer.MIN_VALUE;
		int second = Integer.MIN_VALUE;
		int third = Integer.MIN_VALUE;
		
		for (int i =0 ; i< arr.length; i++){
			if(arr[i] > first){
				third = second;
				second = first;
				first = arr[i];
			}else if(arr[i] > second){
				third = second;
				second = arr[i];
			}else if(arr[i] > third){
				third = arr[i];
			}
		}
		System.out.println("The three Largest element are:");
		System.out.println(first+ "\t"+ second + "\t"+ third);
	}

	public static void main(String[] args) {
		int[] arr ={10,8,1,0,9};
		
		get3Largest(arr);

	}

}

- Shilpi_Roy November 04, 2017 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

ChrisK, Thank you for the answer. It explains a lot.
He actually did ask me the exact follow up. How to scale and distribute the application across several machine? How will it work if players are in geographically different locations?
What can be the best answer in this scenarios?

- Shilpi_Roy November 02, 2017 | Flag Reply

Comment hidden because of low score. Click to expand.

of 3 vote

The given input array might contain both negative and positive integers. Therefore, the idea is use two pointers.
1) One pointer at the left end (low =0)and another pointer on the right end(high = arr.length-1) index of array.
2)Resulting array of squares is filled from right to left (arr.length-1 to 0) i.e largest square to smallest square.
3)Compare the absolute value of the element pointed by the two pointers whichever is greater the result array takes the square of that element.
4)Every element in the array is processed at least once
Time Complexity : O(n)

Note : But the key here is that when an large integer is squared it might overflow the integer bounds. So either a custom class to handle that situation or Long or BigInteger class in java should be used to handle that.

The below code is not doing that but is rather a simple method to do the required.

public class GetSortedSquares {

	public static void main(String[] args) {
		int[] arr = {-6,-3,2,3,4};
		int[] arr1= {1,2,3,4};
		
		int[] result = getSortedSquares(arr);
		int[] result1 = getSortedSquares(arr1);
		
		printArr(result);
		printArr(result1);
		
	}
// The function to get the Squares in Sorted order
	private static int[] getSortedSquares(int[] arr) {
		int[] result = new int[arr.length];
		int low =0 , high = arr.length-1, i = arr.length-1;
			while(low <= high && i >= 0){
				if(Math.abs(arr[low]) >= Math.abs(arr[high])){ // absolute value of array element on the left is greater than the array element on right
					result[i]= arr[low]*arr[low];
					i--;
					low++;
				}else if (Math.abs(arr[low]) < Math.abs(arr[high])){
					result[i]= arr[high]*arr[high];
					i--;
					high--;
				}		
			}
		
		return result;
	}

	private static void printArr(int[] result) {
		for(int n : result)
			System.out.println(n);
		
	}

}

- Shilpi_Roy October 20, 2017 | Flag Reply

Page:

CareerCup

Shilpi_Roy

Books

Videos

Resume Review

Mock Interviews