A question often asked in interviews is: what’s the best way to store a set? There are many different ways to store well-ordered data so that it can be queried quickly. Many people find that a hash table gives them the best performance characteristics, so much so that if you are in an interview and answer with anything else, you will immediately raise the suspicions of the interviewer. However, assuming you have a good hash function, a hash table still has one key flaw: it really doesn’t tell you anything about your relative neighbors. This means that you can’t easily extract an ordered list out of a hash table. You could query all possible keys in order, but this will give you abysmal performance. Furthermore, if you use e.g. a dictionary (strcmp) ordering of strings, you will have an infinite number of keys between any two finite keys. That makes exhaustive search impossible.
But besides extracting an ordered list, there are other uses for having neighbor access. Suppose, for example, you had a set of non-overlapping time intervals which represent different policies in effect at Company X. Each time interval has some starting time as well as an ending time. Now, given a moment in time, you would like to find the time interval that contains it, if there is one; this corresponds to the policy which was in effect at that time. (Assume for now that if the interval starts at a query moment, it contains that moment.) What is a good data structure which would allow you to efficiently add new time intervals and query moments in time intervals?
Think for a few minutes before reading below…
Actually, any sort of balanced binary tree suffices for both O(log n) insert and query performance. The query will find the latest interval start which is less than or equal to the query moment. It will then verify that the query moment falls before the end, and will fail if it doesn’t.
How does that query work? Presumably you know how to search for an element q in a binary tree tree:
- let e = tree.root
- While e != null:
- if e < q: // Current element less than query element, so look at larger elements
- e := e.right
- else if e > q: // Current element greater than query element, so look at smaller elements
- e := e.left
- return true // e == q
- if e < q: // Current element less than query element, so look at larger elements
- return false
Note: The symbol “:=” means assignment, if you haven’t seen it before. Functional programmers hate assignment and they will write the above in a tail-recursive manner.
In this algorithm, inductively, e contains an element on the path from the tree’s root to q (or where q would be if it existed). The root is on the path. Given the element in some path, we can find the next element by either looking in the set of all elements reachable on this path which are larger, or the set of all elements reachable on this path which are smaller.
To find the largest element which is smaller than or equal to a given element q:
- let e = tree.root
- let x = null
- While e != null:
- if e < q:
- x := e
- e := e.right
- else if e > q:
- e := e.left
- return e // e == q
- if e < q:
- return x
In this algorithm, x represents the largest element we’ve seen so far which is less than q. This is hopefully fairly easy to see: we store e in x if and only if it is smaller than q. Since this algorithm follows the same path as the search algorithm, the only thing left to realize is that, in fact, the largest element in the set which is less than or equal to e (let’s call that element y) will be present on the path to e. That’s the key to the algorithm.
So, after all that, we’ve finally gotten to what you might think of as the crux of the algorithm, somewhat analogous to the meat patty found deep within the layers of condiments of an overly dressed Fuddruckers burger (you can only blame yourself there, though). Take a breath and make sure you understand why this is so important. After all, we’re only looking at a tiny, log-sized slice of the set, but are making a statement about the whole thing.
The induction hypothesis is that either we have encountered y, or y is contained in the set we recurse on. This is surely true for the root, since it contains all elements.
Inductively, when examining e and deciding which way to go, consider the set that we didn’t choose. If e < q, then the set to the left of e is smaller than e, but e < q, so e itself is a better choice than anything to the left. We therefore say that e is “good” and we remember it. If there is a better choice, it is to the right, so we proceed to recurse to the right. On the other hand, if e > q, then e is not a good choice because it is too big, and furthermore anything to the right will be even bigger. Therefore, we recurse on the left, where y must be if it exists.
What we have shown is already enough for a good algorithm. That algorithm would simply be to remember the biggest thing we’ve seen which is smaller than q. But the above algorithm is a little better; it always picks the last thing we’ve seen which is smaller than q and doesn’t bother to compare it to the last one we picked. The reason this works becomes clear if you examine what we observed earlier. Whenever we see a good e, we always recurse to the bigger set. But that means if we see another good e, it must be bigger and therefore better than the last good e we saw.
How about using this algorithm with your favorite data structure libraries? Java has a similar algorithm in TreeMap as a method called “highestLessThan”. This method isn’t exposed (who knows why not?), but you can activate it by calling headMap. (Or, use a TreeSet which internally uses a TreeMap.) The Java algorithm is about twice as slow as it needs to be, though, because it does two tree traversals, first to find an element and then to find its predecessor. C++ STL does the above algorithm in the form of upper_bound (at least in the SGI implementation). It’s also worth mentioning a typical SQL database. Suppose you had some table interval where each row contained an interval (start, end). Set up a descending index on start: create unique index foo on interval (start desc) This essentially gives you both a balanced tree and a singly linked list in the descending direction. Then you can select max(start) from interval where start <= ?. This will get you the start of the interval, which you can then use to query the rest. I’m not really a DB expert, so someone else can fill me in. As for other languages… fill me in!
There are some other directions we could go with this. If intervals could overlap, this adds complications. If we want the interval to start strictly before the moment in time, this changes the algorithm a little. But I have to stop somewhere.
I think you should stress the non-overlapping part of this problem. I overlooked that single word and was trying to reengineer interval trees to answer the queries. Then I was confused in reading your solution, because it doesn’t handle the non-disjoint case.
+1 (I also missed the non-overlapping requirement.)
In C++, this problem is easily solved y using the set STL container and redefining operator
#include
#include
#include
using namespace std;
struct Interval
{
int m_Start, m_End;
Interval(int p_S, int p_E)
{
if ( p_S > p_E )
std::swap( p_S, p_E );
m_Start = p_S;
m_End = p_E;
}
bool operator iSet;
while(1)
{
string s1, s2;
cout > s1 >> s2;
if ( s1 == “quit” || s2 == “quit” )
break;
int s = atoi( s1.c_str() );
int e = atoi( s2.c_str() );
Interval i(s, e);
set::iterator itr = iSet.find( i );
if ( itr != iSet.end() )
{
cout
The submission didn’t quite work. Wish a blog on algorithms would accept code snippets.
Basically, use the set container, and overload the less-than operator of struct Interval to mean: I1
By popular demand, I added a “code” button and the ability to preview comments to make sure they look OK. You can either enclose your stuff in
<code>or you can use the “c” button. It seems to work OK. Here’s another example:#include <foo.h>
for (int i = 0; i < n; i++) {
foo();
}
Thanks!
I think you can solve the problem by defining two intervals as “equal” if they have a non-null intersection. I1 is less than I2 if I1.start and I1.end are less than I2.start. This way, you could just use a normal tree search to find whether the interval (a, a) intersects with an existing interval in the tree.
6e2550827b6c0625c0e2…
6e2550827b6c…
effexor impotence…
news…
propecia…
news…
ativan without prescription…
news…
nexium…
news…
buy adderall…
news…
vicodin…
news…
zyban abuse…
news…
ephedra yellow jackets…
news…
effects of lexapro…
news…
seroquel anger…
news…
lamisil digger figure…
news…
clomid success rates…
news…
protonix 40mg…
news…
acyclovir dosages…
news…
cipro…
news…
alprazolam…
news…
aded19275004a0c17f08…
aded19275004…
neurontin side effects…
news…
does metformin cause weight loss…
news…
amoxicillin side effects…
news…
tramadol hcl…
news…
cheapest tramadol…
news…
synthroid problems…
news…
norco bank robbery documentary…
news…
adderall…
news…
generic tylenol recall…
news…
tylenol 3…
news…
flomax and homepage…
news…
bupropion side effects…
news…
clomid babies…
news…
buy percocet online…
news…
does meridia work…
news…
fioricet and blood work…
news…
prozac side effects…
news…
hydrocodone apap 5 500…
news…
ativan treatmenr for seizures…
news…
nexium side effects…
news…
cipro flatulence…
news…
lorazepam side effects…
news…
phentermine diet pills…
news…
ephedrine side effects…
news…
interactions between elavil and ephedrine…
news…
diflucan birth control pills…
news…
alcohol and zoloft…
news…
valium side effects…
news…
prednisone…
news…
adderall xr…
news…
oxycodone stomach problems…
news…
zocor eye…
news…
buy norco online…
news…
oxycodone extraction iv…
news…
cheapest cialis…
news…
valtrex and weight loss…
news…
ephedra weight loss products…
news…
metformin more effective than avandia…
news…
vicodin withdrawal…
news…
vicodin side effects…
news…
prednisone withdrawal…
news…
alprazolam south america…
news…
buy valtrex online…
news…
zoloft and breastfeeding…
news…
danger of ephedrine…
news…
ritalin without prescription…
news…
side effects for valtrex…
news…
valtrex…
news…
doxycycline dosage…
news…
zoloft generic…
news…
online pharmacy oxycodone…
news…
half life of elavil…
news…
valtrex side effects…
news…
doxycycline side effects…
news…
alprazolam from mexico…
news…
hydroxycut with ephedra…
news…
buy carisoprodol…
news…
carisoprodol fedex cod…
news…
zoloft sexual side effects…
news…
oxycodone…
news…
tchnvrbi…
tchnvrbi…
long term use of percocet…
news…
percocet 93-490…
news…
amoxicillin…
news…
valtrex medication…
news…
doxycycline taken with desonide…
news…
doxycycline hyclate…
news…
ephedra products…
news…
doxycycline 100mg…
news…
doxycycline…
news…
buy ephedra online…
news…
doxycycline pleural…
news…
oxycodone extraction…
news…
buy valtrex without prescription…
news…
ephedra pills…
news…
what is lorazepam…
news…
amoxicillin trihydrate…
news…
forex…
news…
side effects of zoloft…
news…
propecia generic…
news…
pill propecia…
news…
ephedra…
news…
ephedra diet pills…
news…
‘08 candidates begin to firm…
WASHINGTON — Positions on the country’s direction at home and abroad are starting to take shape in the blur of…
N Korea Talks Resume After…
N Korea Talks Resume After Funds ReleasedBuzzle, CA -1 hour ago… implementing measures to shut down North Korea’s nuclear facilities within 60…
Run for a reason -…
Run for a reasonTallahassee.com, FL -Apr 5, 2007… a “Haiku at Hai Noon” poetry contest and a meet-the-author signing with Martha Lou…
propecia side effects…
news…
Let us trust our people…
Let us trust our peopleThe Daily Star, Bangladesh -1 hour agoLet us concentrate more on salvaging the nation from the evil of…
propecia online uk…
news…
propecia side effects fre…
news…
HIGHLIGHTS (Financial Express)…
Robots On STAR Movies International Monday at 7-00 pm Even in a world populated entirely by mechanical beings Rodney Copperbottom…
forex trading seminar az…
news…
micro forex trading…
news…
forex training…
news…
Community college presidents approved -…
Community college presidents approvedMontgomery Advertiser, AL -6 hours agoExley received his Ph.D. at the University of Texas at Austin and has worked…
propecia and online drugs stores…
news…
tramadol side effects…
news…
zoloft side effects…
news…
buy propecia…
news…
Off the radar at swim…
Off the radar at swim showsMiami Herald, FL -Jul 17, 2007Jessica Simpson may represent the height of pop culture vapidness, but she…
phentermine…
news…
tramadol hydrochloride…
news…
phentermine online…
news…
discount phentermine…
news…
percocet dependency…
news…
Home Developers Target Growing Hispanic…
Ferman Gonzales grew up on San Antonio’s south side, part of a large Hispanic community where developers used to be…
COMPLETE TNA SACRIFICE 2007 COVERAGE:…
Welcome to PWInsider.com’s live coverage of TNA Sacrifice. This will be the final PPV where TNA uses the NWA letters…
Cellphone revolution has people talking…
In a country where most people live without paved roads, running water or even electricity, there’s one modern convenience that…
propecia pill…
news…
Vikings vs. Philadelphia: Just a…
Vikings vs. Philadelphia: Just a phone call awayMinneapolis Star Tribune (subscription), MN -Oct 27, 2007When Childress looks across the field, he will…
zoloft…
news…
Hunting for Treasure - Press-Enterprise…
Hunting for TreasurePress-Enterprise (subscription), CA -Aug 9, 2007All the galleries contributed to the treasure hunt. “Each of the galleries was responsible to…
Courier News Online - PISCATAWAY:…
The Piscataway Public Library continues its Film Movement Series, a presentation of award-winning, first-run, independent and foreign films, with a…
Crocs, Dragons skinned - Adelaidenow…
Crocs, Dragons skinnedAdelaidenow, Australia -22 hours agoBaby Shaq grabbed 18 boards against the Kings, swatted a few shots and got called for…
He is still the Chairman…
He is still the Chairman of the Wampanoag Tribe of MashpeeCape Cod Today, MA -4 hours agoA law enforcement source told me…
Rugged, fanless vehicle PC runs…
— Aug. 20, 2007 — Acrosser has introduced a compact, fanless computer aimed at the harsh environments found in trucks,…
The disturbing case of Izhar…
The disturbing case of Izhar Ul-Haque: your laws at workCrikey (subscription), Australia -Nov 12, 2007The decision handed down by NSW Supreme Court…
cheap tramadol…
news…
Spin sends chill through English…
Spin sends chill through English spineIndian Express, India -Aug 19, 2007The met department has predicted another wet day tomorrow, but luckily, the…
California Manufacturers See 5.25% Factory…
California Manufacturers See 5.25% Factory Drop in 2006; 1.4% Drop …PCB007 (press release), OR -2 hours agoVisitors to http://www.mnileads.commay generate custom…
ephedrine hcl…
news…
biotek ephedrine…
news…
WWII as only Ken Burns…
WWII as only Ken Burns can tell the storySan Francisco Chronicle, USA -Sep 21, 2007You can download Firefox at getfirefox.com. The…
tramadol…
news…
Nigeria: Liberation of the Naira…
Nigeria: Liberation of the Naira by the Central BankAllAfrica.com, Washington -Aug 24, 2007The spraying of money on occasions such as wedding ceremonies,…
ICSA STC Intercollegiate Offshore Regatta…
ICSA STC Intercollegiate Offshore RegattaSail World, Australia -17 hours agoIn addition to holding various prestigious offshore racing events (among them the Fort…
percocet…
news…
Marketplace gets thumbs-up for customer…
Shana Shriber says she is thrilled that her commute for shopping and dining is just a two-mile trip even though…
amoxicillin for acne…
news…
amoxicillin no prescription…
news…
amoxicillin dosage…
news…
dosage for valtrex…
news…
Abstinence Rally Held At Battlefield…
Stop hatin’ on the waitin’. That was the theme of today’s youth abstinence rally in Jackson. Nearly 200 people gathered…
ephedrine weight loss products…
news…
vaspro ephedrine…
news…
buy vicodin without script…
news…
Duck diversity - Wyoming Tribune…
Duck diversityWyoming Tribune, WY -17 hours agoThere are a couple unidentifiable ducks at Sloan’s Lake that are the offspring of domestic white…
Recreation, senior centers slated for…
Recreation, senior centers slated for opening by AprilKilleen Daily Herald, TX -8 hours agoThe senior center will include a covered drop-off area,…
percocet online…
news…
vicodin detox…
news…
amoxicillin acne…
news…
Hacking into iPhones, worming into…
Hacking into iPhones, worming into PCsDaily Breeze, CA -Aug 30, 2007A new Trojan worm is being spread via e-mail this month,…
1721095184…
1721095184…