Amazon Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
Update: Found a bug in my idea. We need to use priority queue , because newly added element may be smaller than actual max element. So, because of it, there is no need to sort first elements , just add them (the value will play the role of priority) in queue. If we want to calculate actual length, just need to ask queue for first and last element.
A minHeap would only return the min value. How could you have a minHeap return a max value?
I guess it is correct (after using the PQ). We have to monitor first and last to find the smallest interval.
What about a binary search tree? You can get min and max both in logarithmic time.
Maybe Queue is a misnomer since you don't respect the FIFO order.
Chaitanya, here is an example:
input {0,10,255} {2 , 11 , 257} {4,12,258}
Let's take the first element from each array and push them into priority queue.
step 0: queue: [0,2,4] range:0-4
step 1: pop 0 from queue , push next element to 0 from first array
queue: [2,4,10] range: 2-10
step2: pop 2 , push 11
queue: [4,10,11] range: 4-11
step3: pop 4 , push 12
queue: [10,11,12] range: 10-12 <----- minimal range
etc...
You algorithm doesnt work for the following example.
input: {2, 20, 10} (1, 5, 6} (22, 23, 24}
Lets take the first element from each array and pust them into priority queue. I understand that I should not sort the elements alter every step as you mentioned above. Correct my understanding if it is wrong
step0: queue: [2, 1, 22] range:2-22
step1: pop 2 from queue, push next element to 2 from first array.
queue: [1, 22, 10] range: 1-10 [This is an invalid range and no element in array 3 is within this range]
step2; pop 1, push 5
queue: [22, 10, 5] range: 22-5
step3: pop 22, push 23
queue: [10, 5, 23] range: 10 - 23 [This is an invalid range and no element in array 2 is within this range]
step4: pop 10, push 20
queue: [5, 23, 20] range: 5-20 [This is an invalid range and no element from array 3 is within this range]
Termenation step reached.
Please corect my understanding if it went wrong somewhere.
1. you should be using a priority queue or a BST as per the discussion above. So [1, 22, 10] will have a range of 1 - 22 and not 1 - 10. BTW in step 0, you should have removed 1 from [2, 1, 22] and not 2.
2. I notice that you do not have a sorted array (could be a typo)!
@GK in the example you have given to chaitanya , you did not reach to upperbound of any of the array, but you still declare 10 -12 as a minimal range.
Can you please explain what do you mean by reaching upperbound ?
The minimum possible range will be,
Min (Max value of each array) -- Max(Min value of each array).
Is this right ?
public class minArrayRange
{
public static void main(String args[])
{
int [][] arrArrays={{3,4,5}, { 5, 58, 62}, {212, 434, 3333}};
int []range=getMinRange(arrArrays);
System.out.println("Min range = min = "+range[0] + " max = " + range[1]);
}
static int [] getMinRange(int [][] arrArrays)
{
int max=-99999, min=99999;
for ( int i=0; i < arrArrays.length; i++)
{
if(max < arrArrays[i][0])
{
max=arrArrays[i][0];
}
if(min > arrArrays[i][0])
{
min=arrArrays[i][0];
}
}
int a[]= { min, max};
return a;
}
}
WRONG SOLUTION (misunderstood the question)
You need to find maximal value among all minimums, and minimal value among all maximums. If maximal minimum is less than minimal maximum, than you can use a range of size one, it may be any number within that range.
void Calculate(const std::vector<std::vector<int> >& src, int& l, int& r){
int mn = src[0].front();
int mx = src[0].back();
for(int i = 1; i < src.size(); ++i){
mn = std::max(mn, src[i].front());
mx = std::min(mx, src[i].back());
}
if(mn <= mx) mx = mn;
l = mn;
r = mx;
}
UPD: Sorry, there was a copy-paste mistake. Fixed now.
UPD2: For {0,10,255} {2 , 11 , 257} {4,12,258} the answer will be any two equal numbers from the range [4, 255], because we need minimal range, in my implementation it's [4, 4].
marut , I suppose you haven't read question carefully. You need to find minimum range, which will contain at least one element from each array. For example {0,10,255} {2 , 11 , 257} {4,12,258} the correct answer is 10-12 , the range is minimum and there is element in each array, which contains in this interval 10 from 1-st array , 11 from second and 12 from third.
I used divide and conquer strategy and it works. Yet, there can be one improvement and that is optimizing the size of nums array.
import java.util.ArrayList;
public class Main {
ArrayList<Integer[]> arrays;
int[] nums;
Range bestRange;
public Main(ArrayList<Integer[]> arrays) {
this.arrays = arrays;
}
private void solve() {
int min = findMin(arrays);
int max = findMax(arrays);
nums = new int[max-min+1];
for (int i = min; i <= max; i++) {
nums[i-min] = i;
}
bestRange = setBestRange(0,nums.length-1);
System.out.println(bestRange.min + "\t" + bestRange.max);
}
//divide and conquer
private Range setBestRange( int first, int last) {
if(first == last){
Range r = new Range(nums[first],nums[first]);
if(doesAllArraysHave(r)){
return r;
}else
return null;
}
if(first == last -1){
Range r = new Range(nums[first],nums[last]);
if(doesAllArraysHave(r)){
return r;
}else
return null;
}
if(doesAllArraysHave(new Range(nums[first],nums[last])) == false){
return null;
}
int mid = (last - first) / 2 + first;
Range firstRange = setBestRange(first, mid);
Range secondRange = setBestRange(mid+1, last);
int p = mid;
int q = mid+1;
Range combination = new Range(first,last);
for (int i = mid; i >= first ; i--) {
for (int j = mid+1; j <= last; j++) {
Range temp = new Range(nums[i],nums[j]);
if(doesAllArraysHave(temp) && temp.getRange() < combination.getRange()){
combination = temp;
}
}
}
return minRangeofThree(firstRange, secondRange, combination);
}
// In the divide and conquer strategy, which division is better?
public Range minRangeofThree(Range r1, Range r2, Range r3){
if(r1 == null && r2==null && r3==null) return null;
int r1GetRange = (r1 == null ? Integer.MAX_VALUE : r1.getRange());
int r2GetRange = (r2 == null ? Integer.MAX_VALUE : r2.getRange());
int r3GetRange = (r3 == null ? Integer.MAX_VALUE : r3.getRange());
int min;
if(r1GetRange < r2GetRange){
min = r1GetRange;
}else{
min = r2GetRange;
}
if(r3GetRange < min){
min = r3GetRange;
}
if(min == r1GetRange) return r1;
if(min == r2GetRange) return r2;
if(min == r3GetRange) return r3;
return null;
}
private boolean doesAnArrayHave(Integer[] ints, Range r){
for (int i = 0; i < ints.length; i++) {
if( ints[i] >= r.min && ints[i] <= r.max)
return true;
}
return false;
}
private boolean doesAllArraysHave(Range r){
for (int i = 0; i < arrays.size(); i++) {
if(!doesAnArrayHave(arrays.get(i), r))
return false;
}
return true;
}
private int findMin(ArrayList<Integer[]> arrays) {
int min = arrays.get(0)[0];
for (int i = 0; i < arrays.size(); i++) {
if(arrays.get(i)[0] < min)
min = arrays.get(i)[0];
}
return min;
}
private int findMax(ArrayList<Integer[]> arrays) {
int max = arrays.get(0)[arrays.get(0).length-1];
for (int i = 0; i < arrays.size(); i++) {
if(arrays.get(i)[arrays.get(i).length-1] > max)
max = arrays.get(i)[arrays.get(i).length-1];
}
return max;
}
public static void main(String[] args) {
ArrayList<Integer[]> arrays = new ArrayList<Integer[]>();
Integer arr1[] = new Integer[]{ 20,30,40,50};
Integer arr2[] = new Integer[]{12,49,100};
Integer arr3[] = new Integer[]{5,15,100};
arrays.add(arr1);
arrays.add(arr2);
arrays.add(arr3);
Main m = new Main(arrays);
m.solve();
}
}
public class FindRangeEachArrayContainingAtleats1Integer {
public static void main(String[] args) {
int a[] = { 1, 2, 3, 5 };
int b[] = { 3, 5, 6, 7 };
int c[] = { 2, 8, 9, 11 };
Set<Integer> se = new HashSet<>();
for (int i = 0; i < a.length; i++) {
se.add(a[i]);
}
for (int i = 0; i < b.length; i++) {
se.add(b[i]);
}
for (int i = 0; i < c.length; i++) {
se.add(c[i]);
}
int length = se.size();
int i = 0,min=0,max=0;
for (int a1 : se) {
if (i == 0) {
min=a1;
}
i++;
if (i == length) {
max=a1;
}
}
System.out.println("Range is={ "+min+ ",.....,"+ max + " } ");
}
}
import sys
from heapq import *
a1 = [1,6,8,10]
a2 = [3,9,20]
a3 = [6,10,20]
iters = [iter(a) for a in (a1, a2, a3)]
heap = [(it.next(), it) for it in iters]
heapify(heap)
min_range = (sys.maxint, (0,0))
max_element = None
while heap:
v, it = heappop(heap)
if max_element and v-max_element > 0:
min_range = min(min_range, (v-max_element, (max_element, v)), key=lambda x:x[0])
max_element = max(v, max_element)
try:
heappush(heap, (it.next(), it))
except:
break
print min_range[1]
import sys
from heapq import *
a1 = [1,6,8,10]
a2 = [3,9,20]
a3 = [6,10,20]
iters = [iter(a) for a in (a1, a2, a3)]
heap = [(it.next(), it) for it in iters]
heapify(heap)
min_range = (sys.maxint, (0,0))
while heap:
# should be fairly easy to add logic to track max element in heap
_max = max(heap, key=lambda x:x[0])[0]
_min, it = heappop(heap)
min_range = min(min_range, (_max-_min, (_min, _max)), key=lambda x:x[0])
try:
heappush(heap, (it.next(), it))
except:
break
print min_range[1]
Please correct me if I am wrong but there is a simple greedy algorithm for this. Sort all the numbers from all the arrays. Start scanning numbers from the smallest (startNum)and stop at a number (stopNum) as soon as a number from each array has been scanned at least once (we know the array from which a number is taken from). save (stopNum,startNum). Next select, the next smallest number as the startNum for a new scan. Repeat till the end of the sorted array. Find the min range amongs the saved (stopNum,startNum) and that would be the answer.
How do you guarantee that a number between (stopNum_i,startNum_i) and a number between (stopNum_i +1, startNum_i +1) is not the range we are looking for?
this is how the above greedy algo works on these arrays ->
a1 = {1 10 255} a2={2 11 255 256} a3= {4 10 257} the min range={10,11}
sorted array A={1 2 4 10 10 11 255 255 256 257}
ie is {a1[0] a2[0] a3[0] a1[1] a3[1] a2[1] a1[2] a2[2] a2[3] a3[2]}
from i=0 to A.length-1{
startNum = a[i]
Initialise an ArraysCoveredMap by adding only the array from which startNum was taken from;
from j=i+1 to A.lenght-1{
check the array A[j] belongs to and add it to the ArraysCoveredMap
if(all arrays were covered in the ArraysCoveredMap){
stopNum = a[j];
store {startNum, stopNum} somewhere
break;
}
}
}
check the min range amongst all the {startNum, stopNum} collected and that should be the answer
Implementation of GK idea as Java Code.
import java.util.Comparator;
import java.util.PriorityQueue;
class Elem{
int val;
int pos;
int arr;
public Elem(int val, int pos, int arr) {
super();
this.val = val;
this.pos = pos;
this.arr = arr;
}
}
public class Problem88 {
static class ElemComparator implements Comparator<Elem>{
public int compare(Elem e1, Elem e2){
return e1.val - e2.val;
}
public static void main(String args[]){
int arr[][] = {{0,10,255}, {2 , 11 , 257} ,{4,12,258}};
ElemComparator ec = new ElemComparator();
PriorityQueue pq = new PriorityQueue(10,ec);
for(int i=0;i<arr.length;i++){
Elem e = new Elem(arr[i][0],0,i);
pq.add(e);
}
Elem mn;
int min = -1;
int max = 9999999;
Elem mx;
while(pq.size() == 3){
mn = (Elem)pq.poll();
mx = (Elem)(pq.toArray())[pq.size()-1];
if((mx.val - mn.val) < (max - min)){
min = mn.val;
max = mx.val;
}
int arr1 = mn.arr;
int pos = mn.pos;
//if(pos >= arr[arr1].length-1 || mx.pos >= arr[arr1].length-1)
// break;
if(pos < arr[arr1].length-1)
pq.add(new Elem(arr[arr1][pos+1],pos+1,arr1));
}
System.out.println("Range is :: "+ min + " - " + max);
}
}
}
I tested this for several of the inputs suggested above. Seems to work. Let me know if it breaks for any input. Use C++11 to compile it.
/*
* min_range.cpp
*
* Created on: Feb 26, 2014
* Author: nvankaya
*/
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <set>
using namespace std;
bool check(deque<int>::const_iterator first,deque<int>::const_iterator last,int K){
set<int> checker;
set<int>::iterator c_itr;
for(deque<int>::const_iterator d_itr = first;d_itr!=last;++d_itr){
checker.insert(checker.begin(),*d_itr);
}
return (checker.size()==K);
}
void main(){
vector<vector<int>> x = {{0,10,255}, {2 , 11 , 257}, {4,12,258} };//{{2, 20, 10}, {1, 5, 6}, {22, 23, 24}};//{{3,256},{ 6,257},{9, 258}};//{{19,33,256},{257,258,259},{2,5,255}};
vector<vector<int>>::iterator x_itr;
int K = x.size(); //Number of arrays
vector<pair<vector<int>::const_iterator,vector<int>::const_iterator> > index;
for(x_itr=x.begin();x_itr!=x.end();++x_itr){
index.push_back(make_pair( (*x_itr).begin(),(*x_itr).end()));
}
std::cout<<"Original Arrays:\n";
vector<pair<vector<int>::const_iterator,vector<int>::const_iterator> >::iterator i_itr;
for(i_itr=index.begin();i_itr!=index.end();++i_itr){
for(vector<int>::const_iterator tmp_itr=i_itr->first;tmp_itr!=i_itr->second;++tmp_itr){
std::cout<<*tmp_itr<<",";
}
cout<<"\n";
}
vector<int> w;
vector<int> s;
while(1){
int minval = 10000;
int minval_num = -1;
vector<int>::const_iterator *minval_index;
int k=1;
for(i_itr=index.begin();i_itr!=index.end();++i_itr,++k){
if( (i_itr->first!=i_itr->second) & (minval>*(i_itr->first))){
minval = *(i_itr->first);
minval_index = &(i_itr->first);
minval_num=k;
}
}
if(minval==10000)
break;
w.push_back(minval);
++(*minval_index);
s.push_back(minval_num);
}
//Merge the arrays in - last step in merge sort
std::cout<<"Merger of the Arrays:\n";
vector<int>::const_iterator itr;
for(itr=w.begin();itr!=w.end();++itr){
std::cout<<*itr<<",";
}
std::cout<<"\nCorresponding label of original arrays:\n";
for(itr=s.begin();itr!=s.end();++itr){
std::cout<<*itr<<",";
}
deque<int> window;
vector<int>::const_iterator s_itr = s.begin();
vector<int>::const_iterator w_itr = w.begin();
int lowerbound,upperbound,range=0,minrange=100000;
for(s_itr=s.begin();s_itr!=s.end();++s_itr,++w_itr){
window.push_back(*s_itr); //expand the window
if(check(window.begin(),window.end(),K)){ //until we get a solution
while(check(window.begin(),window.end(),K)){
window.pop_front(); //shrink the window
}
//window.pop_front(last_val); //now window is the tight and good.
range = *max_element(w_itr-window.size(),w_itr+1)-*min_element(w_itr-window.size(),w_itr+1);
if(range < minrange){
minrange = range;
lowerbound = *min_element(w_itr-window.size(),w_itr+1);
upperbound = *max_element(w_itr-window.size(),w_itr+1);
}
}
}
cout<<"\nRange=("<<lowerbound<<","<<upperbound<<")"<<endl;
}
The idea is, I merge the sorted arrays into a single bigger sorted array, like the last step in "merge sort" algorithm. While I do that I create a accompaining array with corresponding label of the original array. If we have K original arrays, the labels will be in the set {1...K}. Now, I push back each element from this accompaining array into a deque and perform a check*. If it passes the check, then I start to shrink the deque from front until it breaks the check. Here we have a tight window with atleast one of each of the integers 1...K. I use this state of the window to get the corresponding elements from the merged bigger sorted array and compute the range and lower/upper bounds. I repeat the process to find all possible range and lower/upper bound values and get the one that gives the least range.
*The check is to see if the deque has atleast one of each of the integers 1...K. To deal with repetitions, I simply put the elements into a set and check if the set is of size K.
I think the best way to do it is to create a tree which once you print it in order gives all the elements of all the arrays sorted, then while creating that tree, for each element in the tree create a bit string which its size is the number of arrays and each bit says wether or not its contained by that array. At last pick the biggest numbers(they are contained by most of the arrays) and continue on their right and left until you fill your string with ones example(111111).
Later compare your intervals which you traversed to find their minimum:
Time complexity for creating the tree and the binaries for m arrays of size n:
O(m*n*log(m*n))
Time Complexity for traversing the fully sorted array and finding minimum interval(which it can be optimized) at worst case scenario is: O ((m)^2*n)
I'll write a code and post the link when I get the chance! but I don't think its necessary!
public class ListOfArrays {
ArrayList<ArrayList<Integer>> listArray; // list of sorted arrays
ArrayList<Integer> minIndexList; // this list maintains the current index position within each array
int minArray;
boolean bFinal=false;
private class Interval {
Integer min= Integer.MAX_VALUE, max=Integer.MIN_VALUE;
boolean bFirst=true;
void setMinInterval() {
int low=Integer.MAX_VALUE,high=Integer.MIN_VALUE;
for(int i=0;i<minIndexList.size();i++) {
if(listArray.get(i).get(minIndexList.get(i))<low) {
low=listArray.get(i).get(minIndexList.get(i));
minArray=i;
}
if(listArray.get(i).get(minIndexList.get(i))>high) {
high=listArray.get(i).get(minIndexList.get(i));
}
}
if((bFirst==true) || ((long) (high-low)<(long) (max - min))){
min=low;
max=high;
bFirst=false;
}
}
public String toString() {
return String.format("[%d %d]", min, max);
}
}
ListOfArrays(ArrayList<ArrayList<Integer>> arrays) {
listArray=arrays;
}
/////////////////////
//
/////////////////////
private void removeMin() {
int i = minArray;
if(minIndexList.get(i)<listArray.get(i).size()-1) {
minIndexList.set(i, minIndexList.get(i)+1);
} else {
bFinal=true;
}
}
////////////////
//
////////////////
public Interval findMinRange() {
Interval v = new Interval();
minIndexList = new ArrayList<Integer>();
// init index list to 0th element
for(int i=0;i<listArray.size();i++){ minIndexList.add(0);}
v.setMinInterval();
while(bFinal!=true) {
removeMin();
v.setMinInterval();
}
return v;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
/*
2 10 20 53
1 5 52 54
23 24 53 55
5 6 7 152
24 28 50 152
3 21 51 53
*/
ArrayList<ArrayList<Integer>> arrays = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> a,b,c,d,e,f ;
a= new ArrayList<Integer>();
a.add(2);a.add(10);a.add(20);a.add(53);
b= new ArrayList<Integer>();
b.add(1);b.add(5);b.add(52);b.add(54);
c= new ArrayList<Integer>();
c.add(23);c.add(24);c.add(53);c.add(55);
d= new ArrayList<Integer>();
d.add(5);d.add(6);d.add(7);d.add(52);
e= new ArrayList<Integer>();
e.add(24);e.add(28);e.add(50);e.add(52);
f= new ArrayList<Integer>();
f.add(3);f.add(21);f.add(51);f.add(53);
arrays.add(a);arrays.add(b);arrays.add(c);
arrays.add(d);arrays.add(e);arrays.add(f);
ListOfArrays m = new ListOfArrays(arrays);
Interval v = m.findMinRange();
System.out.println("INPUT: "+arrays.toString());
System.out.println("OUTPUT: "+v.toString());
}
}
Here’s an explanation of my approach :
So let us say the 6 sorted arrays are:
2 10 20 25
1 5 6 7
23 24 25 26
5 6 7 8
24 28 50 52
3 21 51 53
initially we have 6 pointers on the 0th index of each array (2,1,23,5,24,3) <<
we find the interval of that set.. here it happens to be [1 24]
so range of {2,1,23,5,24,3} = [1 24]
we immediately remove the lowest element from the set, and insert the next element from that array.. in this case, 1.. w eincrement index of 2nd array.. next element is 5. So set becomes
{2,5,23,5,24,3} and range = [2 24] we replace the min_interval variable with [2 24] as 24-2 < 24-1
if we continue this, we get
2
1
23 [1 24] min = [1 24]
5
24
3
removeMin -> 1
2
5
23 [2 24] min = [2 24]
5
24
3
removeMin ->2
10
5
23 [3 24] min = [3 24]
5
24
3
removeMin ->3
10
5
23 [5 24] min = [5 24]
5
24
21
removeMin ->5
10
6
23 [5 24] min = [5 24]
5
24
21
removeMin ->5
10
6
23 [6 24] min = [6 24]
6
24
21
removeMin ->6
10
7
23 [6 24] min = [6 24]
6
24
21
removeMin -> 6
10
7
23 [7 24] min = [7 24]
7
24
21
after 2 time remove min 7
10
7 (last element)
23 [7 24] min = [7 24]
8
24
21
this is the terminating condition. the lower level cannot go above 7, and the max levels can only go up.. so [7 24] is the answer
new example
2 10 20 53
1 5 52 54
23 24 53 55
5 6 7 52
24 28 50 52
3 21 51 53
{(2,1,23,5,24,3), [1 24]} [1 24] -> {(2,5,23,5,24,3), [2 24]} [2 24] -> {(10,5,23,5,24,3), [3 24]} [3 24] -> {(10,5,23,5,24,21), [5 24]} [5 24]-> {(10,52,23,5,24,21), [5 24]}[5 24] ->{(10,52,23,6,24,21), [6 24]} [6 24]-> {(10,52,23,7,24,21), [7 24]}[7 24] ->{(10,52,23,52,24,21), [10 52]} [7 24] -> {(20,52,23,52,24,21), [20 52]}[7 24] ->{(53,52,23,52,24,21), [21 53]} [7 24] -> {(53,52,23,52,24,51), [23 53]}[7 24] -> {(53,52,24,52,24,51), [24 53]}[7 24] -> {(53,52,53,52,24,51), [24 53]}[7 24] -> (53,52,53,52,28,51), [28 53]}[7 24] -> (53,52,53,52,50,51),[50 53]}[50 53] -> (53,52,53,52,52,51),[51 53]}[51 53] -> (53,52,53,52,52,53),[52 53]}[52 53] -> (53,54,53,52,52,53),[52 54]}[52 53] ->
(53,54,54,52,52,53),[52 55]}[52 53] -> final solution [52 53]
Worst case running time = O(m * m* n)
can someone tell me what the average case running time would be? O (m*n) or O (n*mlgm) ?
worst case list of arrays would be m identical arrays.
I like your approach! I haven't been able to find anything wrong with it! But I think for big m and n my algorithm is better as the time complexity is m*n*log(m*n)! Also if the arrays keep changing my algorithm can keep track of that in almost linear time!
Still yours seems pretty damn good!
(Not Bad Face) :D
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
template<class Iterator, class CONT2, typename FUNC>
Iterator SearchBound(Iterator beg, Iterator end, const CONT2& sorted, FUNC func) {
if (beg == end) return beg;
auto it = beg + std::distance(beg, end) / 2;
if (it == beg) return beg;
auto sv_beg = cbegin(sorted);
auto sv_end = cend(sorted);
while (sv_beg != sv_end) {
if (func(cbegin(*sv_beg), cend(*sv_beg), *it) == cend(*sv_beg)) {
return SearchBound(beg, it, sorted, func);
}
++sv_beg;
}
return SearchBound(it, end, sorted, func);
}
void MinimumRange(const std::vector<std::vector<int> >& sorted_vec) {
std::vector<int> vec;
std::for_each(begin(sorted_vec), end(sorted_vec),
[&vec](const std::vector<int>& c) {
vec.insert(cend(vec), cbegin(c), cend(c));
});
std::sort(begin(vec), end(vec));
vec.erase(std::unique(begin(vec), end(vec)), end(vec));
auto beg = vec.cbegin();
auto end = vec.cend();
auto lower = SearchBound(beg, end, sorted_vec,
[](decltype(beg) a, decltype(end) b, int c) { return std::lower_bound(a, b, c); });
auto upper = SearchBound(beg, end, sorted_vec,
[](decltype(beg) a, decltype(end) b, int c) { return std::upper_bound(a, b, c); });
std::cout << "[" << *upper << ", " << *lower << "]" << std::endl;
}
Here is my idea.
- GK February 25, 2014(A) Let's take the smallest element from each array. For each element we will remember from which array did we take it. Sort them and add to the queue this way : the smallest element will be on the first place.
(B) After this, we know the first and the last element. Let's count length of the interval.
Next step is to pop element (let's call it x) and push next to x element, from the same array. Calculate length of the interval and repeat (B) until one of the arrays reaches its upper bound.