Interview Questions on linked-lists, doubly linked-lists and binary trees

I have collected few very good problems on linked-lists surfing through the internet. They include basic conceptual questions as well as hard to bite. I will keep update the blog as soon as I find some good stuff.

  1. Given a linked list, give an algorithm to reverse it using constant space and in single pass.
  2. Given a linked list of n nodes, give an algorithm to reverse every k nodes of the linked list.
  3. A linked list has a closed loop in it, i.e. the last node points to some node in middle of it. Give an algorithm to find the node from which the loop begins. The last node may points to the first node
  4. Given a linked list with each node having a lower-case character. Find whether the word formed by characters of list is palindrome or not.(Do in a single pass with constant space)
  5. Given a doubly linked-list containing integers in sorted sequence, create a height balanced binary search tree model using the same data structure.

Extended Euclidean Algorithm to find Modular Multiplicative Inverse

Modular multiplicative inverse of a number a mod m is a number x such that

ax ≡ 1 (mod m)

It is very helpful where division is carried out along with modular operation. Instead of dividing by a number, its inverse can be multiplied to fetch the same result i.e.

k/a mod m = k*x mod m

Modular multiplicative inverse can be find only if the two numbers are coprimes i.e. their gcd is 1.
Here we are using Extended Euclidean Algorithm to find the inverse.

The algorithm is same as Euclidean algorithm to find gcd of two numbers. Euclid’s algorithm starts with the given two integers and forms a new pair that consists of the smaller number and the remainder of the division of larger number with smaller number numbers. The new pair again applied given algorithm until the remainder is zero. The only extension in extended euclidean algorithm is that every divisor and remainder is represented as linear combination of the original two numbers and coefficients are stored in every iteration.

Algorithm:

We have to find x such that ax ≡ 1 (mod m)
Above equivalence can be stated alternatively as:
ax  = pm + 1
or ax + my = 1 known as Bézout’s identity.

The beginning two numbers are a and m
x and y are coefficients of a and m respectively when dividend is represented as linear combination of a and m.
u and v are coefficients of a and m respectively when divisor is represented as linear combination of a and m.
c and d are coefficients of a and m respectively when remainder is represented as linear combination of a and m.

Initially dividend is m and divisor is a
m = 0*a + 1*m = x*a + y*m
a = 1*a + 0*m = u*a + v*m
So x = 0, y = 1, u = 1, v = 0

m = q*a + r where q is quotient and r is remainder.
From next iteration q  acts as dividend and r as divisor. Let e is dividend and f is divisor in iteration.

e = q*f + r
r = (-q)*f + 1*e = (-q)*(u*a + v*m) + 1*(x*a + y*m) = (x – u*q)*a + (y – v*q)*m

So
c = x – u*q
d = y – v*q
For next iteration roles will be switched as:
f is dividend ⇒ e = f
r is divisor ⇒ f = r
x = u
y = v
u = c
v = d

Termination:

When r is 1
r = c*a + d*m = 1
c is the required modular inverse.

Example:

Consider example of two numbers  a = 29, m = 168

29x + 168y = 1
168 = 0*29  + 1*168                          
29   = 1*29 + 0*168                         

First Step:
168 = 5*29 + 23    
23 = (-5)*29 + 1*168 = (-5)*[1*29 + 0*168] + 1*[0*29  + 1*168]

Second Step:
29 = 1*23 + 6
6 = 1*29 + (-1) *23 = 1*[0*168 + 1*29] + (-1)*[(-5)*29 + 1*168] = 6*29 + (-1)*168

Third Step:
23 = 3*6 + 5
5 = 1*23 + (-3)*6 = 1*[ (-5)*29 + 1*168] + (-3)*[6*29 + (-1)*168] = (-23)*29 + 4*168

Fourth Step:
6 = 1*5 + 1
1 = (-1)*5 + 1*6 = (-1)*[(-23)*29 + 4*168] + 1*[6*29 + (-1)*168] = 29*29 + (-5)*168

Hence final solution comes as:
29*29 + (-5)*168 = 1
x = 29 and y = (-5)

C/C++ Implementation:


int modmulinverse(int a,int m)
{
    int x = 0,y = 1,u = 1,v = 0; 
    int e = m,f = a;
    int c,d,q,r;
    while(f != 1)
    {
        q = e/f;
        r = e%f;
        c = x-q*u;
        d = y-q*v;
        x = u;
        y = v;
        u = c;
        v = d;
        e = f;
        f = r;
    } 
    u = (u+m)%m;
    return u;
}