Linkedin Interview Question Software Engineer in Tests
Country: United States
Interview Type: Phone Interview
Minor correction:
in if statement
if(a[m]==target){}
if( m==right || (m<right && a[m+1] != a[m])){
if(right > bound[1]){
bound[1] = right;
}
}
should be
if( m==right || (m<right && a[m+1] != a[m])){
if(m > bound[1]){
bound[1] = m;
}
}
and
if(m==left || (m>left && a[m-1] != a[m])){
if(left < bound[0]){
bound[0] = left;
}
}
should be
if(m==left || (m>left && a[m-1] != a[m])){
if(m < bound[0]){
bound[0] = m;
}
}
You can use binary search to find the index of number. Then split into a left array and right array and binary search on those to find the edges. 2logn = O(logn)
start_index = end_index = -1
num = 2 # input number
for index, value in enumerate(s_r):
if num == value:
if start_index < 0:
start_index = end_index = index
else:
end_index = index
print start_index, end_index
This will work fine, but is really inefficient. It will be O(n) and will iterate over the entire list in every case. You can have it break once it finds the end, which will still be linear, or even better, you can use binary search to find the index of number. Then split into a left array and right array and binary search on those to find the edges. 2logn = O(logn)
var arr = [0, 2, 3, 3, 3, 10, 10]
function findRange(arr, num) {
if (arr.length === 0) return;
var startIndex = -1, endIndex = -1, flag = true, result = [];
for (var i=0; arr[i] <= num; i++) {
if (arr[i] === num && flag) {
startIndex = i;
endIndex = i;
flag = false;
}
else if (arr[i] === num) {
endIndex = i;
}
}
result.push(startIndex);
result.push(endIndex);
return result;
}
$("#res").text(findRange(arr, 10));
Here is pseudo code to find the range: Problem can be solved with BS.
Find the given number in array using BS
if given value not found
return
else
use BS to find value at smallest index from low to (find index – 1)
use BS to find value at highest index from (find index + 1) to high
low and high are variables that are initially with 0 and Length - 1, and keep updating as we narrowing search.
public class FindRange {
public static int[] findRange(int[] a, int num) {
if(a==null){
System.out.println("Please provide the valid array to find the range index!");
}
int firstIndex = -1;
int lastIndex = -1;
int[] rangeArray = new int[2];
boolean flag = true;
for (int i = 0; i < a.length; i++) {
if (a[i] == num && flag) {
firstIndex = i;
lastIndex = i;
flag = false;
} else if (a[i] == num) {
lastIndex = i;
}
}
rangeArray[0] = firstIndex;
rangeArray[1] = lastIndex;
return rangeArray;
}
public static void main(String[] args) {
int result[] = new int[2];
result = findRange(new int[]{0, 2, 3, 3, 3, 10, 10}, 3);
for (int i = 0; i < result.length; i++) {
System.out.println(result[i]);
}
}
}
Here is a sample implementation in java. Hopefully this can be improved.
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class ReturnRangeForDuplicates {
public static void main(String[] args) {
// TODO Auto-generated method stub
int sizeofarray = 0;
System.out.println("Please enter the size of array:");
Scanner in = new Scanner(System.in);
sizeofarray = in.nextInt();
Integer[] myarray = new Integer[sizeofarray];
System.out.println("Please enter the contents of array");
for (int i = 0; i < sizeofarray; i++) {
myarray[i] = in.nextInt();
}
System.out.println("please enter the element you want to know the index range for duplicates");
int searchElement = in.nextInt();
Arrays.sort(myarray);
List<Integer> mylist = Arrays.asList(myarray);
System.out.println("Min index" +mylist.indexOf(searchElement));
System.out.println("Max index" +mylist.lastIndexOf(searchElement));
in.close();
}
}
Used modified binary search for the range.
public void modifiedBS(int left, int right, int [] a, int [] bound, int target){
if(left>right){
return;
}
int m = (left+right)/2;
if(a[m] == target){
if( m==right || (m<right && a[m+1] != a[m])){
if(right > bound[1]){
bound[1] = right;
}
}
if(m<right && a[m+1]==target){
modifiedBS(m+1,right,a,bound,target);
}
if(m==left || (m>left && a[m-1] != a[m])){
if(left < bound[0]){
bound[0] = left;
}
}
if(m>left && a[m-1] == a[m]){
modifiedBS(left,m-1,a,bound,target);
}
}else if(a[m] < target){
modifiedBS(m+1,right,a,bound,target);
}else{
modifiedBS(left,m-1,a,bound,target);
}
}
public int [] findBound(int []a, int target){
int bound[] = new int[2];
if(a.length == 0){
bound[0] = -1;
bound[1] = -1;
return bound;
}
bound[0] = a.length-1;
bound[1] = 0;
modifiedBS(0,a.length-1,a,bound, target);
if(bound[0] == a.length-1 && bound[1] == 0 ){
bound[0] = -1;
bound[1] = -1;
}
return bound;
}
Using modified BS in python
def find_range(num_list, search_num):
def find_range_internal(l_index, r_index):
if l_index == r_index:
return (l_index, r_index) if num_list[l_index] == search_num else (-1, -1)
mid_index = (l_index + r_index) / 2
mid_result = mid_index if num_list[mid_index] == search_num else -1
l_result = -1 if num_list[mid_index] < search_num else min(find_range_internal(l_index, mid_index - 1))
r_result = -1 if num_list[mid_index] > search_num else max(find_range_internal(mid_index + 1, r_index))
result = [l_result, mid_result, r_result]
result = [i for i in result if i != -1]
if result:
return result[0], result[-1]
return -1, -1
return find_range_internal(0, len(num_list) - 1)
small fix
def find_range(num_list, search_num):
def find_range_internal(l_index, r_index):
if l_index > r_index:
return -1, -1
if l_index == r_index:
return (l_index, r_index) if num_list[l_index] == search_num else (-1, -1)
mid_index = (l_index + r_index) / 2
mid_result = mid_index if num_list[mid_index] == search_num else -1
l_result = (-1, -1) if num_list[mid_index] < search_num else find_range_internal(l_index, mid_index - 1)
r_result = (-1, -1) if num_list[mid_index] > search_num else find_range_internal(mid_index + 1, r_index)
result = []
result.extend(l_result)
result.append(mid_result)
result.extend(r_result)
result = [i for i in result if i != -1]
if result:
return result[0], result[-1]
return -1, -1
return find_range_internal(0, len(num_list) - 1)
This can be done in logarithmic time using binary search.
Here is the java code:
public static void TestFindRange() {
int[] arr1 = {0, 2, 3, 3, 3, 10, 10};
FindRange(arr1, 3);
FindRange(arr1, 6);
}
public static void FindRange(int arr[], int number) {
int low = 0;
int high = arr.length - 1;
int mid = 0;
while (high >= low) {
mid = low + ((high - low) / 2);
if (arr[mid] == number) {
break;
} else if (arr[mid] > number) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if (high < low) {
System.out.println("Number not found" + -1);
return;
}
// Found number at mid. Look for range.
int right = mid, left = mid;
while (right < arr.length - 1 && arr[right + 1] == number) {
right++;
}
while (left > 1 && arr[left - 1] == number) {
left--;
}
System.out.println("(" + left + "," + right + ")");
}
public static int getIndexofMaxLess(int[] arr, int target) {
int ret = -1;
int s = 0;
int e = arr.length - 1;
while (s <= e) {
int m = (s + e) / 2;
if (arr[m] <= target) {
ret = m;
s = m + 1;
} else {
e = m - 1;
}
}
return ret;
}
public static Interval findRange(int[] arr, int target) {
Interval ret = new Interval();
int s = getIndexofMaxLess(arr, target - 1);
int e = getIndexofMaxLess(arr, target);
if (e == -1 || s == -1 || arr[s + 1] != target || arr[e] != target) {
ret.start = -1;
ret.end = -1;
} else {
ret.start = s + 1;
ret.end = e;
}
return ret;
}
As mentioned by others, you can use modified binary search to search for elements. There are three cases :
* middle element == number whose start, end index has to be found
If number after middle element is also the search number, then search in right half
If number before middle element is also the search number, then search left half
* If middle element is less than search number, then search in right half
* If middle element is greater than search number, then search in left half.
Based on above algo, following is a recursive implementation of the same :
#include <iostream>
#include <deque>
#include <utility>
namespace
{
typedef std::deque<int> array;
typedef std::pair<int, int> startend;
}
class find_range
{
public :
std::pair<int, int> operator()(const std::deque<int>& a, const int& n)
{
// No elements to search
if(a.empty()) return std::make_pair(-1, -1);
int start(-1), end(-1);
size_t l(0), r(a.size() - 1);
find_range_r(a, l, r, n, start, end);
return std::make_pair(start, end);
}
private :
void find_range_r(const std::deque<int>& a, size_t l, size_t r, const int& n, int& s, int& e)
{
if(l > r) return;
if(r > (a.size() - 1)) return;
size_t m(l + (r - l) / 2); //std::cout << "\nl" << l << " m" << m << " r" << r << " s" << s << " e" << e << " a[m]" << a[m] << " n" << n;
if(a[m] == n)
{
if(m == 0) s = static_cast<int>(m);
else if((m - 1) >= 0)
{ if((a[m - 1] != n)) s = static_cast<int>(m); }
else s = static_cast<int>(m);
//std::cout << "\nsafter" << s;
if((m + 1) <= (a.size() - 1))
{ if((a[m + 1] != n)) e = static_cast<int>(m); }
else { e = static_cast<int>(m); }
//std::cout << "\neafter" << e;
if((s != -1) && (e != -1)) return;
if(((m - 1) >= 0) && (a[m - 1] == n)) find_range_r(a, l, m - 1, n, s, e);
if(((m + 1) <= (a.size() - 1)) && (a[m + 1] == n)) find_range_r(a, m + 1, r, n, s, e);
}
else if(a[m] < n) { find_range_r(a, m + 1, r, n, s, e); }
else if(a[m] > n) { find_range_r(a, l, m - 1, n, s, e); }
}
};
int main()
{
array a{0, 2, 3, 3, 3, 10, 10};
startend se(find_range()(a, 3));
std::cout << "\n(" << se.first << ", " << se.second << ")";
array a_2{0, 2, 3, 3, 3, 10, 10};
startend se_2(find_range()(a_2, 6));
std::cout << "\n(" << se_2.first << ", " << se_2.second << ")";
array a_3{0, 2, 3, 3, 3, 10, 10};
startend se_3(find_range()(a_3, 10));
std::cout << "\n(" << se_3.first << ", " << se_3.second << ")";
array a_4{0, 2, 3, 3, 3, 10, 10};
startend se_4(find_range()(a_4, 0));
std::cout << "\n(" << se_4.first << ", " << se_4.second << ")";
array a_5{0, 2, 3, 3, 3, 10, 10};
startend se_5(find_range()(a_5, 2));
std::cout << "\n(" << se_5.first << ", " << se_5.second << ")";
array a_6{0, 0, 2, 3, 3, 3, 10, 10};
startend se_6(find_range()(a_6, 0));
std::cout << "\n(" << se_6.first << ", " << se_6.second << ")";
array a_7{0, 2, 2, 2, 3, 3, 3, 10, 10};
startend se_7(find_range()(a_7, 2));
std::cout << "\n(" << se_7.first << ", " << se_7.second << ")";
array a_8{0, 2, 2, 2, 3, 3, 3, 10, 10, 10};
startend se_8(find_range()(a_8, 10));
std::cout << "\n(" << se_8.first << ", " << se_8.second << ")";
array a_9{0, 2, 2, 2, 3, 3, 3, 10, 10, 10};
startend se_9(find_range()(a_9, 12));
std::cout << "\n(" << se_9.first << ", " << se_9.second << ")";
array a_10{0, 2, 2, 2, 3, 3, 3, 10, 10, 10};
startend se_10(find_range()(a_10, -1));
std::cout << "\n(" << se_10.first << ", " << se_10.second << ")";
array a_11;
startend se_11(find_range()(a_11, 3));
std::cout << "\n(" << se_11.first << ", " << se_11.second << ")";
array a_12{1};
startend se_12(find_range()(a_12, 1));
std::cout << "\n(" << se_12.first << ", " << se_12.second << ")";
array a_13{1, 2};
startend se_13(find_range()(a_13, 1));
startend se_14(find_range()(a_13, 2));
std::cout << "\n(" << se_13.first << ", " << se_13.second << ")";
std::cout << "\n(" << se_14.first << ", " << se_14.second << ")";
return 0;
}
package interv.linkedIn;
import ms.searching.BinarySearch;
public class FindDuplicateRange {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = { 0, 2, 3, 3, 3, 10, 10 };
FindDuplicateRange fDR = new FindDuplicateRange();
fDR.findRange(input, 6);
}
public int binaryS(int[] input, int i, int j, int k) {
int low, high, mid, key;
low = i;
high = j;
key = k;
if (low > high)
return -1;
mid = (low + high) / 2;
if (input[mid] > key)
return binaryS(input, low, mid - 1, key);
else if (input[mid] < key)
return binaryS(input, mid + 1, high, key);
else
return mid;
}
private void findRange(int[] input, int key) {
// TODO Auto-generated method stub
if (input.length <= 0) {
System.out.println("Empty array");
return;
}
int startIndex = -1, endIndex = -1;
int keyIndex = binaryS(input, 0, input.length - 1, key);
if (keyIndex != -1) {
startIndex = keyIndex;
endIndex = keyIndex;
while (startIndex > 0) {
if (input[startIndex - 1] == key)
startIndex--;
else
break;
}
while (endIndex < input.length - 1) {
if (input[endIndex + 1] == key)
endIndex++;
else
break;
}
}
System.out.println("Start Index = " + startIndex + " End Index = "
+ endIndex);
}
}
package interv.linkedIn;
public class FindDuplicateRange {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = { 0, 2, 3, 3, 3, 10, 10 };
FindDuplicateRange fDR = new FindDuplicateRange();
fDR.findRange(input, 6);
}
public int binaryS(int[] input, int i, int j, int k) {
int low, high, mid, key;
low = i;
high = j;
key = k;
if (low > high)
return -1;
mid = (low + high) / 2;
if (input[mid] > key)
return binaryS(input, low, mid - 1, key);
else if (input[mid] < key)
return binaryS(input, mid + 1, high, key);
else
return mid;
}
private void findRange(int[] input, int key) {
// TODO Auto-generated method stub
if (input.length <= 0) {
System.out.println("Empty array");
return;
}
int startIndex = -1, endIndex = -1;
int keyIndex = binaryS(input, 0, input.length - 1, key);
if (keyIndex != -1) {
startIndex = keyIndex;
endIndex = keyIndex;
while (startIndex > 0) {
if (input[startIndex - 1] == key)
startIndex--;
else
break;
}
while (endIndex < input.length - 1) {
if (input[endIndex + 1] == key)
endIndex++;
else
break;
}
}
System.out.println("Start Index = " + startIndex + " End Index = "
+ endIndex);
}
}
public int[] searchRange(int[] A, int target) {
int[] range = new int[2];
range[0] = searchMaxLessThan(A,target,0,A.length - 1);
range[1] = searchMaxLessThan(A,target +1,0,A.length - 1);
if(range[0] == range[1]){
// target not found
range[0] = -1;
range[1] = -1;
}else{
range[0]++;
}
return range;
}
public int searchMaxLessThan(int[] a, int target, int s, int e) {
//base case
if(s >= e) return a[s]<target ? s:s -1;
//recursive case
int m = (s+e)/2;
if(a[m] < target){
return searchMaxLessThan(a,target,m+1,e);
}else{
return searchMaxLessThan(a,target,s,m-1);
}
}
public static void findIndex(int[] arr, int start, int end, int value){
if(end<=start){
//no values found
System.out.println("-1,-1");
return;
}
if(arr[start]==value && arr[end]==value){
System.out.println(start+","+end);
return;
}
if(arr[start]!=value && arr[end]==value) {
findIndex(arr, start+1, end, value);
}
if(arr[start]!=value && arr[end]!=value) {
findIndex(arr, start+1, end-1, value);
}
if(arr[start]==value && arr[end]!=value) {
findIndex(arr, start, end-1, value);
}
}
public static void main(String[] args) {
int[] arr = {0, 2, 3, 3, 3, 10, 10};
System.out.println("find index:");
findIndex(arr, 0, arr.length-1, 3);
int[] arr1 = {0 ,2 ,3 ,3, 3, 10, 10};
System.out.println("find index:");
findIndex(arr1, 0, arr1.length-1, 10);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] arr ={0,0,3,3,3,10,10};
findRange(arr,0);
}
public static void findRange (int[] arr, int j)
{
Map<Integer,Integer> rangMap = new LinkedHashMap<Integer, Integer>();
for (int i: arr){
if(!rangMap.containsKey(i)){
rangMap.put(i, 1);
} else {
rangMap.put(i, rangMap.get(i)+1);
}
}
System.out.println("Range is");
int rangeUpper = 0;
int rangeLower = 0;
if(rangMap.containsKey(j)){
for (int i : rangMap.keySet()){
if (i == j){
int val = rangMap.get(i);
rangeUpper = rangeLower+val-1;
break;
} else {
rangeLower= rangeLower+rangMap.get(i);
}
}
}
System.out.println("Range is"+rangeLower);
System.out.println("Range is"+rangeUpper);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] arr ={0,0,3,3,3,10,10};
findRange(arr,0);
}
public static void findRange (int[] arr, int j)
{
Map<Integer,Integer> rangMap = new LinkedHashMap<Integer, Integer>();
for (int i: arr){
if(!rangMap.containsKey(i)){
rangMap.put(i, 1);
} else {
rangMap.put(i, rangMap.get(i)+1);
}
}
System.out.println("Range is");
int rangeUpper = 0;
int rangeLower = 0;
if(rangMap.containsKey(j)){
for (int i : rangMap.keySet()){
if (i == j){
int val = rangMap.get(i);
rangeUpper = rangeLower+val-1;
break;
} else {
rangeLower= rangeLower+rangMap.get(i);
}
}
}
System.out.println("Range is"+rangeLower);
System.out.println("Range is"+rangeUpper);
}
int[] findBound(int[] array, int num){
int firstFoundIndex = binarySearch(array, 0, array.length-1, num)
println("First found index = $firstFoundIndex")
if(firstFoundIndex == -1){
return [-1,-1]
}
int leftBound = firstFoundIndex
int rightBound = firstFoundIndex
while(leftBound > 0 && array[leftBound-1]==num){
int newLeftBound = binarySearch(array, 0, leftBound-1, num)
println("New left bound = $newLeftBound")
if(newLeftBound == -1){
break;
}
leftBound = newLeftBound;
}
while(rightBound < array.length-1 && array[rightBound+1]==num){
int newRightBound = binarySearch(array, rightBound+1,array.length-1, num)
println("New right bound = $newRightBound")
if(newRightBound == -1){
break;
}
rightBound = newRightBound;
}
return [leftBound, rightBound]
}
int binarySearch(int[] arr, int low, int high, int no)
{
if (high < low)
return -1;
int mid = (low + high)/2;
if (no == arr[mid])
return mid;
if (no > arr[mid])
return binarySearch(arr, (mid + 1), high, no);
else
return binarySearch(arr, low, (mid -1), no);
}
void findRange(int[] inp, int num) {
int startIndex = -1;
int endIndex = -1;
int index = 0;
boolean numExists = false;
while (index < inp.length) {
if (inp[index] == num) {
numExists = true;
break;
}
index++;
}
if (numExists) {
startIndex = index;
while (index < inp.length) {
if (inp[index] != num) {
break;
}
index++;
}
endIndex = index - 1;
}
System.out.println("range: (" + startIndex + "," + endIndex + ")");
}
def findIndex_withBinarySearchApproach(s_r, num):
min = 0
max = len(s_r) -1
start_index = end_index = -1
while min < max:
m = (min + max) /2
if s_r[m] < num:
min = m+1
elif s_r[m] > num:
max = m-1
else:
start_index = end_index = m
while start_index >0:
if s_r[start_index-1] == num:
start_index -=1
else:
break
while end_index < len(s_r)-1:
if s_r[end_index+1] == num:
end_index +=1
else:
break
print start_index, end_index
break
findIndex_withBinarySearchApproach([0,2,3,3,3,10,10], 3)
public class FindRange {
public static void main(String[] args) {
int a[]=new int[]{0,2,3,3,3,10,10};
finRange(a,3);
}
public static void finRange(int a[], int num)
{
int lastIndex=-1;
int firstIndex=-1;
boolean flag=true;
for(int i=0;i<a.length;i++)
{
if(a[i]==num&&flag)
{
firstIndex=i;
lastIndex=i;
flag=false;
}
else
if(a[i]==num)
lastIndex=i;
}
System.out.println("firstIndex="+firstIndex+"lastIndex="+lastIndex);
}
}
public class FindRange {
public static int[] findRange(int[] a, int num) {
if(a==null){
System.out.println("Please provide the valid array to find the range index!");
}
int firstIndex = -1;
int lastIndex = -1;
int[] rangeArray = new int[2];
boolean flag = true;
for (int i = 0; i < a.length; i++) {
if (a[i] == num && flag) {
firstIndex = i;
lastIndex = i;
flag = false;
} else if (a[i] == num) {
lastIndex = i;
}
}
rangeArray[0] = firstIndex;
rangeArray[1] = lastIndex;
return rangeArray;
}
public static void main(String[] args) {
int result[] = new int[2];
result = findRange(new int[]{0, 2, 3, 3, 3, 10, 10}, 3);
for (int i = 0; i < result.length; i++) {
System.out.println(result[i]);
}
}
}
Since the array is sorted use binary search to find first and last occurrence of the number.
The findLast gets in to while loop for the below input
{1, 2, 3, 4, 4, 4, 5, 5, 5, 5, 6, 7, 8, 9, 10}
right implementation of findLast
{
int left = 0;
int size = array.length - 1;
int right = size;
while(left <= right) {
int middle = (left + right)/2;
if(array[middle] < number){
left = middle + 1;
} else if (array[middle] > number) {
right = middle - 1;
} else {
if(middle == size || array[middle + 1] != number) {
return middle;
} else{
left = middle + 1;
}
}
}
return -1;
}
}
Why not use binary search to find the first occurrence of the number and then walk linearly in both directions to find the range?
Use modified binary search
- sh88990 April 29, 2014public void modifiedBS(int left, int right, int [] a, int [] bound, int target){ if(left>right){ return; } int m = (left+right)/2; if(a[m] == target){ if( m==right || (m<right && a[m+1] != a[m])){ if(right > bound[1]){ bound[1] = right; } } if(m<right && a[m+1]==target){ modifiedBS(m+1,right,a,bound,target); } if(m==left || (m>left && a[m-1] != a[m])){ if(left < bound[0]){ bound[0] = left; } } if(m>left && a[m-1] == a[m]){ modifiedBS(left,m-1,a,bound,target); } }else if(a[m] < target){ modifiedBS(m+1,right,a,bound,target); }else{ modifiedBS(left,m-1,a,bound,target); } } public int [] findBound(int []a, int target){ int bound[] = new int[2]; if(a.length == 0){ bound[0] = -1; bound[1] = -1; return bound; } bound[0] = a.length-1; bound[1] = 0; modifiedBS(0,a.length-1,a,bound, target); if(bound[0] == a.length-1 && bound[1] == 0 ){ bound[0] = -1; bound[1] = -1; } return bound; }