Java Interview Questions | Glassdoor

# Java Interview Questions

6,004

interview questions shared by candidates

## Java Interview Questions

Sort: RelevancePopular Date

Apr 30, 2011

Sep 20, 2011

### Software Engineering Intern at Facebook was asked...

Mar 8, 2012
 Given a sorted array, write a program to decide if two elements sum up to a third.9 AnswersDid you coded a solution < O(n^2 + logn) ?Assuming each number only appears once: //Java code public static void targetsum(int[] arr, int target) { if(arr == null) return; int start = 0; int end = arr.length -1; while(start target end--; } }typedef vector vint; bool check_element_sum(vint &array) { // n^2 algorithm sort(array.begin(),array.end()); //general case : nlogn copy(array.begin(),array.end(),ostream_iterator(cout," ")); cout=0;--i) //n^2 { start=0; end=i-1; target=array[i]; //note a<=b<=c for the tuples formed here hence check for c=a+b only while(startShow More Responsesthe algorithm for 3 elements sum up to a given number is also the same; the only change one needs to make is replace line target=array[i]; with target=total-array[i]; is there an algorithm with a lower order? says O( nlogn ); I am not able to think of anything!we can modify the 3sum algorithm for this.It is possible to do it in O(n) create a binary tree from the sorted array in O(n) subtract each value in array from target and find if its there in the tree, if found push to hash map, with the array item as key and the subtracted value as key next time before subtracting value in the array from target check if it is in the hash map@Pal the hash map gives a lower constan because /2 elements need to be checked but the lookup is still n*lognimport java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util.Random; import java.util.Scanner; import java.util.Set; public class SumOfTwoElements { public static void main(String[] args) { final Scanner in = new Scanner(System.in); final Random random = new Random(); while (true) { System.out.println("Enter array size : "); int size = in.nextInt(); int[] array = new int[size]; for (int i = 0; i > findSummingTriplets2(int[] array) { final Set> summingTriplets = new HashSet>(); for (int k = 2; k array[k]) { j--; } else if (sum > findSummingTriplets(int[] array) { final Set> summingTriplets = new HashSet>(); for (int i = 0; i end) { return false; } int mid = start + (end - start) / 2; if (array[mid] > value) { return contains(array, start, mid - 1, value); } else if (array[mid] < value) { return contains(array, mid + 1, end, value); } else { return true; } } }bool sumExists(vector nums, int target) { auto front = nums.begin(); auto back = nums.end() - 1; while (front != back) { if (*front + *back == target) return true; else if (*front + *back < target) front++; else back--; } return false; }

### Software Engineer at Facebook was asked...

Mar 26, 2012

Dec 30, 2011
 Find occurrences of a number in sorted array (allow duplicates).8 AnswersO(logN) requiredUse binary search to find the number (O(logN)). Once that is done you can search around that index. Though that could become O(N). Better answer: run binary search again twice once you have found the number the first time. For the upper half and the lower half - so total run time is O(logN)I think it is not possible in O(logN) because anyway traversing the complete array is needed to access all the numbers. Worst Case scenario would be the last number repeating itself 5 times. For example : {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5} and if you are asked to find out the occurrences of number '5' then you have to traverse the complete array once which means the complexity should be O(N).Show More ResponsesJAVA Code : // For Sorted and UnSorted Array in O(N) time Complexity. import java.util.HashMap; public class FindOccurrences { /** * @param args */ public static void main(String[] args) { int unsortedArray[] = {4,6,7,8,4,5,6,8,3,2,4,5,7,8,9,3,4,6,7,8}; System.out.println(findOccurrencesUnsorted(unsortedArray,8)); int sortedArray[] = {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5}; System.out.println(findOccurrencesSorted(sortedArray,5)); } private static int findOccurrencesUnsorted(int[] array, int number) { HashMap map = new HashMap(); for(int i=0;iO(logN) is possible for sorted arrays, the key here is to firstly check beginning and end to determine next binary-search steps, I attached my code below, and I think this is O(logN) in worst case. //inputs are the sorted array, k is the number looking for //start and end are two index values, main method calls with (start=0) and (end=length-1) int GetOccurance(int[] inputs, int k, int start, int end) { if(startk) return 0; if(inputs[start]==k&&inputs[end]==k) return end-start+1; int mid = (start+end)/2; if(input[mid]k) return GetOccurance(inputs, k, start, mid-1); else return GetOccurance(inputs, k, start, mid-1)+1+GetOccurance(inputs, k, mid+1, end); }With the last algorithm, how does it ever return anything but 0? If main calls with start := 0 and end := length - 1? The only case where you get past the base case is if the array is length 1... since (start < end) = (0 < length -1) from the input... and returns 0...Also, I think there is a good shot at a stack overflow with this method. I would add an extra variable and solve the problem tail recursively.Try this. int findLeftEdge( int A[], int num, int val ){ int mid = num/2; if( num == 1 ){ return 0; }else{ if( A[mid] == val && A[mid-1] != val ){ return mid; }else if( A[mid] == val || A[mid] > val ){ return findLeftEdge( A, mid, val ); }else if( A[mid] val ){ return findRightEdge( A, mid, val ); } } } int countOccurrenceSortedArray( int A[], int num, int val ){ int left = findLeftEdge( A, num, val ); int right = findRightEdge( A, num, val ); return right-left+1; } int main() { // your code goes here int A[] = { 1, 5, 10, 10, 12, 19, 19, 19, 20, 20}; int ans = countOccurrenceSortedArray( A, sizeof(A)/sizeof(int), 20 ); cout << ans << endl; return 0; }

Feb 9, 2011

Feb 8, 2013

Apr 24, 2011

### Software Engineer In Test at Google was asked...

Jan 15, 2010
 You are a parking lot attendant in a lot that has one open spot, and you want to move the cars from their original positions into a new arrangement. Create a program that will print out instructions on how to move the cars most efficiently. 7 AnswersThe problem is not too difficult, what you have to do is find the empty spot, then look in the desired arrangement for what car should be in that spot, and move that car there. Repeat until complete.Does this really work? If I the empty spot is expected to be the same, but the positions of two (or more) cars are switched, how to rearrange it without a complete search?It's the Tower of Hanoi Problem.Show More ResponsesSo there are actually 2 empty spots then or is there a way to 'stack' cars I don't know of?The parking lot problem has nothing to do with Tower of Hanoi, which requires O(2^n -1). This problem, however, can be solved in O(n) - that's because all you need to do is to perform (0 or more) rotations using the empty parking spot.Here is a C# implementation, using generics and .NET 4.0 Tuple: IEnumerable> RearrangeCars( TCar emptyCarMarker, IDictionary initial, IDictionary desired) { // reverse the lookup: car -> spot Dictionary pending = initial.ToDictionary(p => p.Value, p => p.Key); // remove emptySpot from lookup TSpot emptySpot = pending[emptyCarMarker]; pending.Remove(emptyCarMarker); while (pending.Any()) { // check if the empty spot is where is should be if (desired[emptySpot].Equals(emptyCarMarker)) { while (true) { // pick a car (any car would do) var carToMove = pending.First(); // check if this car is already in its desired position if (desired[carToMove.Value].Equals(carToMove.Key)) { // remove from pending, no moving is necessary pending.Remove(carToMove.Key); if (pending.Any() == false) yield break; } else { yield return new Tuple(carToMove.Key, carToMove.Value, emptySpot); // move the car TSpot newSpot = emptySpot; emptySpot = carToMove.Value; pending[carToMove.Key] = newSpot; break; } } } // move the car into its desired spot var car = desired[emptySpot]; var newEmptySpot = pending[car]; yield return new Tuple(car, newEmptySpot, emptySpot); emptySpot = newEmptySpot; pending.Remove(car); } } Note that there is a while-loop inside another while-loop. However, the complexity is still O(n) since at every iteration of internal or external loop, the "pending" map is reduced by one element. Below are some examples (emptyCarMarker == ""). EXAMPLE 1: Input: initial == { "", "B", "A"} desired == { "", "A", "B"} Output: (B, 1, 0) // move car B from spot #1 to #0 (A, 2, 1) // move car A from spot #2 to #1 (B, 0, 2) // move car B from spot #0 to #2 EXAMPLE 2: Input: initial == { "", "B", "A", "D", "C" } desired == { "A", "B", "", "C", "D" } Output: (A, 2, 0) (D, 3, 2) (C, 4, 3) (D, 2, 4)Here is a Java Implementation, using Google's guava library for the BiMap. It takes O(n) to first create the BiMap and O(n) to move the cars, total O(2n), i.e. O(n) time complexity. import com.google.common.collect.BiMap; import com.google.common.collect.HashBiMap; import java.util.Map; import java.util.Set; class ParkingAttendant { static class ParkingConfiguration { static final Integer EMPTY = -1; Integer moves = 0; BiMap conf, i_conf; static ParkingConfiguration getInstance(int[] conf){ return new ParkingConfiguration(conf); } private ParkingConfiguration(int[] conf){ this.conf = arrayToMap(conf); this.i_conf = this.conf.inverse(); } BiMap arrayToMap(int[] arr){ BiMap m = HashBiMap.create(arr.length); for(int i=0;i> entrySet(){ return conf.entrySet(); } } static void moveCars(ParkingConfiguration from, int[] to){ for(int pos=0; pos e : p.entrySet()){ int pos = e.getKey(); int car = e.getValue(); System.out.format("%1\$s, ", ParkingConfiguration.EMPTY.equals(car)?"_":car); } System.out.println("]"); } static void printCars(int[] p){ System.out.print("["); for(int pos=0; pos

Oct 31, 2016