Interview Questions 5: Successor with delete – Sigmainfy – Learn, Share, Inspire

Interview Questions 5: Successor with delete – Sigmainfy – Learn, Share, Inspire

We try to relate the solution to the problem of Successor with delete to Union-Find algorithm here and discuss how to relate them and make it more straightforward in the first place from two different angles: 1) Analyze it in a recursive way and give an informal proof; 2)  Draw it out by hand.

Problem Definition:

Note this problem is from the "Algorithm Part 1″ on Coursera. The detailed description is as follows:

Successor with delete. Given a set of N integers S={0,1,…,N−1} and a sequence of requests of the following form:

• Remove x from S
• Find the successor of x: the smallest y in S such that y >= x.

Design a data type so that all operations (except construction) should take logarithmic time or better.

Analysis:

Well, I think the Union-Find approach to solve this problem should already be known to quite a number of people, the challenge would be how to relate the solution to Union-Find approach at the first place without any hints about Union-Find. I first directly give the approach and then discuss how to relate it to Union-Find from two different angles to help consider the approach in Union-Find way more naturally.

Read full article from Interview Questions 5: Successor with delete – Sigmainfy – Learn, Share, Inspire