Empresa engajada
Pergunta de entrevista da empresa LinkedIn
This time it was a tough question about writing a program where given a sorted array, repetitions allowed, and given an integer, I had to return the start index and end index of that integer in the array. I chose the Binary Search approach but some modifications had to be made to make it optimistic in run-time.
Resposta da entrevista
Sigiloso
Suppose the the array is A. and Number is N. Then do a binary search for N in array A and find the number just bigger than N (lets say index = 5) Similary do another binary seach and find the number just below than N (lets say index =1) This implies that from index =2 to index =4 the array has number N. How to find index of a number just greater than N. Example : Array A : 1,2,2,2,2,4,5,6 N : 2 public int modifiedBinarySearch(int[] A, int N) { int i = 0; int j = A.length; int m = (i+j)/2; while(i O(logn)