Interview Question Java Developers
Country: France
Your First two steps are correct but for actual min value linear search must be done.
1) sort A
2) X = max (B, C)
3) Linear Search for element greater or equal to X in A.
if A is sorted then:
* Linear Search for element Y in A where A >= X takes linear time
* Binary search for Y in A where A >= X takes logarithmic time
Is the problem/question: Find the lowest element in A that is greater than every element in B and C?
Isn't that trivial to do in O(A+B+C) ?
Find X, the largest number in B or C (O(B+C)), then find the lowest number in A that is above X.
I just threw something together here, maybe I forgot something...
import sys
A = [126, 110, 130]
B = [125]
C = [105, 115]
maxi = max(max(B),max(C))
mini = sys.maxint
for x in A:
if x < mini and x > maxi:
mini = x
print mini
It assumes that B and C are not empty. If they can be, you can just add checks for that.
It sounds good!, but you need to deal with corner cases:
A = [125]
B = [126, 110, 130]
C = [105, 115]
output: 9223372036854775807 (should be: -1)
A = [126, 110, 125, 130]
B = [125]
C = [105, 115]
output: 126 (should be: 125)
Honestly, it's something I would have asked and had specified in an interview.
For your first example, it wasn't specified how it would handle the case where there's no proper answer. -1 is often a better answer, but should be clarified in the interview. If you do, just add an if at the end.
For the second one, it wasn't clear in your question that you wanted the maximum to be inclusive. The clarification I asked specified that the element in A should be strictly greater than all elements in B and C. In any case, you just have to change it to "and x >= maxi".
{{
package com.practice.www;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Practice {
public static ArrayList<Integer> n = new ArrayList<Integer>();
public static void main(String[] args) {
Integer[] A = { 126, 110, 130 };
Integer[] B = { 125 };
Integer[] C = { 105, 115 };
int max1 = (int) Collections.max(Arrays.asList(C));
int max2 = (int) Collections.max(Arrays.asList(B));
for (int i = 0; i < A.length; i++) {
if ((A[i] > max1) && (A[i] > max2)) {
n.add(A[i]);
}
}
System.out.println(n.get(0));
}
}
}}
Here is another way to do it in java:
package com.yogesh.samples;
import java.util.Arrays;
import java.util.Random;
public class MinArrayElem {
public int minArrayElem (int[] a, int[] b, int[] c){
if (a.length > b.length){
if (a.length > c.length){
return findMaxElem(a, b, c);
}
} else {
if ( b.length > c.length){
return findMaxElem(b, a, c);
}
}
return findMaxElem(c, a, b);
}
private int findMaxElem(int[] sortArray, int[] other1, int[] other2) {
Arrays.sort(sortArray);
Arrays.sort(other1);
Arrays.sort(other2);
int maxO = other1.length-1, maxO1 = other2.length-1, maxS = 0;
boolean found = false;
while (!found && maxS < sortArray.length){
if (sortArray[maxS] > other1[maxO]) {
if (sortArray[maxS] > other2[maxO1]) {
found = true;
}
}
maxS++;
}
return sortArray[maxS-1];
}
public void fillArray(int[] arr){
for (int i=0; i < arr.length; i++){
arr[i] = (new Random().nextInt(100));
}
}
public void printArray(int[] arr){
for (int i=0; i < arr.length; i++){
if (i != 0){
System.out.print( " " + arr[i]);
} else{
System.out.print(arr[i]);
}
}
}
public static void main(String[] args) {
MinArrayElem min = new MinArrayElem();
int x1 = (new Random().nextInt(10))+1, x2 = (new Random().nextInt(10))+1, x3 = (new Random().nextInt(10))+1;
int[] ax1 = new int[x1];
int[] ax2 = new int[x2];
int[] ax3 = new int[x3];
min.fillArray(ax1);
min.fillArray(ax2);
min.fillArray(ax3);
System.out.print("ax1[");
min.printArray(ax1);
System.out.println("]");
System.out.print("ax2[");
min.printArray(ax2);
System.out.println("]");
System.out.print("ax3[");
min.printArray(ax3);
System.out.println("]");
int minMax = min.minArrayElem(ax1, ax2, ax3);
System.out.println("minimum from array but max for other 2 arrays = "+ minMax);
}
}
Your code doesn't really work properly. First of all, you change around the order of the arrays in minArrayElem, which is against the project specification.
Also, it doesn't always create the correct result. Here's the output from one of the runs of your program:
ax1[47 22 26 31 89 50 12]
ax2[71 68 57 98 0 24]
ax3[45]
minimum from array but max for other 2 arrays = 89
89 is not larger than all the elements in ax2 and ax3. In ax2, there's 98 which is larger, so the output is wrong.
Also, sorting them in this case is unnecessary since it has the time complexity O(n*log(n)) at best, while finding the maximum element is O(n). In this case, your algorithm seems to get the time complexity O(A*log(A) + B*log(B) + C*log(C)), where a more optimal (and easier) algorithm would have O(A+B+C)
public static void main(String[] args) {
int[] A = {12, 34, 20, 78, 56, 67, 52};
int[] B = {50};
int[] C = {1, 9, 51, 9};
getNum(A, B, C);
}
public static void getNum(int[] A,int[] B,int[] C ){
int maxOfA = getMax(A);
int maxOfB = getMax(B);
int maxOfC = getMax(C);
int[] aa = {maxOfB, maxOfC};
int numToCompare = getMax(aa);
int resultNum = maxOfA;
System.out.println("Number to Compare : "+numToCompare+" - "+resultNum);
for(int i : A){
if(numToCompare < i && resultNum > i){
resultNum = i;
}
}
System.out.println(resultNum);
}
public static int getMax(int[] arr){
int result = 0;
for(int i : arr){
if(i > result){
result = i;
}
}
return result;
}
public class ArrayminMax {
static int[] a = {126, 110, 130};
static int[] b = {125};
static int[] c = {105, 115};
public static int minMax() {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int x = 0; x < b.length; x++) {
if (b[x] > max) {
max = b[x];
}
}
for (int x = 0; x < c.length; x++) {
if (c[x] > max) {
max = c[x];
}
}
for (int x = 0; x < a.length; x++) {
//System.out.println(a[x]);
if (a[x] < min && a[x] >= max) {
min = a[x];
}
}
if (min == Integer.MAX_VALUE) {
return -1;
} else {
return min;
}
}
public class ArrayminMax {
static int[] a = {126, 110, 130};
static int[] b = {125};
static int[] c = {105, 115};
public static int minMax() {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int x = 0; x < b.length; x++) {
if (b[x] > max) {
max = b[x];
}
}
for (int x = 0; x < c.length; x++) {
if (c[x] > max) {
max = c[x];
}
}
for (int x = 0; x < a.length; x++) {
//System.out.println(a[x]);
if (a[x] < min && a[x] >= max) {
min = a[x];
}
}
if (min == Integer.MAX_VALUE) {
return -1;
} else {
return min;
}
}
int minMax(int *a, int n1, int *b, int n2, int *c, int n3){
sort(a, a+n1);
sort(b, b+n2);
sort(c, c+n3);
if((a[n1-1] > b[n2-1]) && (a[n1-1]) > c[n3-1])
return 1;
else
return 0;
}
I understand from your code that n1, n2, n3 are the length of a, b, c.
Forget to mention that all values are greater or equal to zero.
What do mean the return values 0 and 1 in your function? The function should return the value. Examples:
1)
A = [126, 110, 130]
B = [125]
C = [105, 115]
func(A, B, C) returns 126
func(B, A, C) returns -1 // -1 means no minimum element found in B that satisfies the constraints min(B) > max(A, C)
2)
A = [110, 126, 130]
B = [128]
C = [105, 115]
func(A, B, C) returns 130
The function should accept any arbitrary number of arrays as argument, where the first argument is the array that might hold the min value.
I just implemented the solution with Java 8:
/**
* Find element y = min(int[] a) where y >= max(int[] b1, int[] b2,..., int[] bn)
* Elements in arrays are greater or equal to 0
* @return element else -1 if not found
*/
public static int min(final int[] a, final int[]... b) {
final int NOT_FOUND = -1;
if (a == null) throw new NullPointerException("first argument cannot be null");
if (a.length == 0 || b.length == 0) return NOT_FOUND;
int max = NOT_FOUND;
for (int[] c : b) {
int tmp = Arrays.stream(c).max().orElse(NOT_FOUND);
if (max < tmp) max = tmp;
}
if (max == NOT_FOUND) return max;
Arrays.sort(a);
if (max == 0) return a[0];
int min = binarySearch(max, a);
return min;
}
private static int binarySearch(int val, int[] a) {
int lo = 0;
int hi = a.length - 1;
while (lo != hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] <= val) lo = mid + 1;
else hi = mid;
}
return a[lo] >= val ? a[lo] : -1;
}
public static void main(String[] args) {
System.out.println(min(new int[]{126, 110, 130}, new int[]{125}, new int[] {105, 115})); // 126
System.out.println(min(new int[]{126, 110, 130}, new int[]{128}, new int[] {105, 115})); // 130
System.out.println(min(new int[]{125}, new int[]{126, 110, 130}, new int[] {105, 115})); // -1
System.out.println(min(new int[]{80,120,90,126,127,128}, new int[]{125}, new int[] {105, 115})); // 126
}
Your program will fail with given below data.
A = [80,120,90,126,127,128]
B = [125]
C = [105, 115]
The answer should be 126 but your code will print 127.
So i told to use linear search.
- Satish February 25, 2015import java.util.Arrays; public class TestS { public static void main(String[] args) { int[] A = {12, 34, 20, 78, 56, 67, 52}; int[] B = {50}; int[] C = {1, 9, 51, 9}; Arrays.sort(A); Arrays.sort(B); Arrays.sort(C); int Max=B[B.length-1]>=C[C.length-1]?B[B.length-1]:C[C.length-1]; int X=Max; for (int i:A) { if (i>Max) {Max=i; break; } } if (Max==X) System.out.println("Doesnot exist!"); else System.out.println(Max); }}