Click here to Skip to main content
14,033,409 members
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

1.6K views
2 bookmarked
Posted 15 Mar 2019
Licenced MIT

Interview Question, Part 6

, 15 Mar 2019
Rate this:
Please Sign up or sign in to vote.
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

The Answer

#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;
}

License

This article, along with any associated source code and files, is licensed under The MIT License

Share

About the Author

Martin Vorbrodt
Software Developer (Senior)
United States United States
No Biography provided

You may also be interested in...

Comments and Discussions

 
Questionisnt this a trivial problem ?? Pin
Member 1172068118-Mar-19 8:47
memberMember 1172068118-Mar-19 8:47 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web03 | 2.8.190423.1 | Last Updated 15 Mar 2019
Article Copyright 2019 by Martin Vorbrodt
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid