14,032,063 members
Tip/Trick
alternative version

#### Stats

1.6K views
2 bookmarked
Posted 15 Mar 2019
Licenced MIT

# Interview Question, Part 6

, 15 Mar 2019
Interview question - a programming puzzle

Given a set of integer ranges defined as [LO, HI) and a value P, find which range P falls into.

My approach to this programming puzzle was to first define a `range` as a `struct` that can be sorted (thanks to `operator <`), then perform binary search on a `vector` of sorted ranges. The code is pretty self explanatory.

### Example Input and Output

```LO: 0, HI: 10
LO: 10, HI: 20
LO: 20, HI: 30
LO: 30, HI: 40
LO: 40, HI: 50
LO: 50, HI: 60
LO: 60, HI: 70
LO: 70, HI: 80
LO: 80, HI: 90
LO: 90, HI: 100
P = 15 falls in range LO: 10, HI: 20
P = 16 falls in range LO: 10, HI: 20
P = 4 falls in range LO: 0, HI: 10
P = 73 falls in range LO: 70, HI: 80
P = 25 falls in range LO: 20, HI: 30
P = 28 falls in range LO: 20, HI: 30
P = 19 falls in range LO: 10, HI: 20
P = 60 falls in range LO: 60, HI: 70
P = 83 falls in range LO: 80, HI: 90
P = 76 falls in range LO: 70, HI: 80
Program ended with exit code: 1```

```#include <iostream>
#include <mutex>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

mutex cout_lock;
#define trace(x) { scoped_lock<mutex> lock(cout_lock); cout << x << endl; }

const int COUNT = 10;

struct range
{
unsigned int lo;
unsigned int hi;

bool in_range(unsigned int p) const { return lo <= p && p < hi; }
};

bool operator < (const range& lhs, const range& rhs)
{
return lhs.lo < rhs.lo;
}

ostream& operator << (ostream& os, const range& r)
{
os << "LO: " << r.lo << ", HI: " << r.hi;
return os;
}

range BinarySearch(const vector<range>& v, unsigned int p)
{
size_t index = v.size() / 2;
size_t step = index / 2 + 1;

while(true)
{
if(v[index].hi <= p) index += step;
if(v[index].lo > p) index -= step;
step /= 2;
if(step == 0) step = 1;
if(v[index].in_range(p)) break;
}

return v[index];
}

int main(int argc, char** argv)
{
srand((unsigned int)time(NULL));

vector<range> ranges =
{
{50, 60}, {60, 70}, {70, 80}, {80, 90}, {90, 100},
{0, 10}, {10, 20}, {20, 30}, {30, 40}, {40, 50}
};

sort(begin(ranges), end(ranges));

for(const auto& r : ranges)
trace(r);

for(int i = 0; i < COUNT; ++i)
{
unsigned int p = rand() % 100;
trace("P = " << p << " falls in range " << BinarySearch(ranges, p));
}

return 1;
}```

## About the Author

 Software Developer (Senior) United States
No Biography provided

## Comments and Discussions

 First Prev Next
 isnt this a trivial problem ?? Member 1172068118-Mar-19 8:47 Member 11720681 18-Mar-19 8:47
 Last Visit: 23-Apr-19 6:11     Last Update: 23-Apr-19 6:11 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.