Multiple Inheritance : Overriding same named functions in derived.

Technique for overriding same named functions in Base classes in a multiple inheritance: ( See : Item 43 in Effective C++ , see also, Exceptional C++ )

#include < iostream >
using namespace std;

class Base1{
    public:
    virtual int func(){ cout << "base1::func" << endl; }
};

class Base2{
    public:
    virtual int func(){ cout << "base2::func" << endl; }
};

class Der : public Base1, public Base2
{
    public:
    // overrides both Base1, and Base func
    virtual int func() { cout << "der::func" << endl; }
};

/** Using auxillary classes  */
class AuxBase1: public Base1{
    public:
        virtual int base1_func() = 0;
        virtual int func() {return base1_func(); }
};
class AuxBase2: public Base2{
    public:
        virtual int base2_func() = 0;
        virtual int func() {return base2_func(); }
};

class Der2 : public AuxBase1, public AuxBase2
{
    int base1_func() { cout << __func__ << endl; }
    int base2_func() { cout << __func__ << endl; }
    
};

int main()
{
    Der *pd = new Der();
    Base1 *p1 = pd;
    Base2 *p2 = pd;
    p1->func();
    p2->func();
    pd->func();

    Der2 *pd2 = new Der2();
    p1 = pd2;
    p2 = pd2;
    p1->func();
    p2->func();
}

Output :
der::func
der::func
der::func
base1_func
base2_func

Finding anagrams, rhyming words and misspelled words in a dictionary.

Surprisingly, finding anagrams, rhyming words and corrections (for misspelled words) have a common O(n) solution.
- To find anagrams, we have a dictionary in which all the words are sorted internally and then compare the input( which is again sorted ). see Bentley (1998) Programming Pearls Addison-Wesley for further discussion on this.

- To find rhyming words, we have a dictionary in which we have the words in reverse order and we reverse the input and compare for similarity towards the end (say last 3 characters )

- A find the spelling correction, we use a related hybrid approach, to quote Knuth The Art of Computer Programming Vol.3 (Sorting and Searching) p.394 :

More complicated search problems can often be reduced to the simpler case
considered here. For example, suppose that the keys are words that might be
slightly misspelled; we might want to find the correct record in spite of this
error. If we make two copies of the file, one in which the keys are in normal
lexicographic order and another in which they are ordered from right to left (as
if the words were spelled backwards), a misspelled search argument will probably
agree up to half or more of its length with an entry in one of these two files.

Binary search to find the last and first occurance of an key

Given an sorted array with duplicates how do we find the first and last occurance of a Key?

There are three solutions in the code fragment below, all take log(n); the most efficient is from Bentley ( see Programming Pearls Column 9, a bit trickier to understand )

The obvious way to solve it is to keep saving the last found location. In case of normal binary search, we stop one the key is found. But to find the first occurrence (or the last occurance), instead of stopping, we set the upper bound to mid-1 ( and to find the last occurrence, we set the lower bound to mid+1 ) and continue. When the element is not found, we simply return the last occurrence. Bentley's method from Programming Pearls is obviously more efficient, since it eliminates one comparison in the inner loop (however, I found it a bit trickier to understand and implement).