Single Pass Palindrome Determination

Develop an algorithm which would determine whether the given input string is a palindrome or not. However there are certain constraints on the algorithm. The constraints are as follows -

1. We do not know the length of the input string.
2. We can read each character of the input string only once (I think the implication of this constraint along with the previous one should be clear).
3. We have to employ constant space.

This problem is very interesting because its solution employs concepts which every computer engineer must have studied but very few will be able to connect the problem with it.

If we look carefully at the above constraints, we will recognize that they together specify a Deterministic Finite Automata. In other words, we are asked to recognize whether a string is palindrome or not through a DFA. This is clearly not possible.

Lets see how each constraint maps the required automaton to a DFA. (1) is just given to disallow quirks. (2) ensures that you cannot move back and forth on the input tape. This is again a characteristic of DFA where you scan symbols on input tape only once. (3) is again a characteristic of DFA, we should have finite states.

Hope you enjoyed the problem.

Find the Non-Duplicate Element

You are given an array of 2n + 1 numbers. Out of these 2n + 1 numbers, 2n are duplicate. You are supposed to find the number which is not duplicate.

Clearly a naive brute-force algorithm is possible, which will scan through the list for each number and see whether its duplicate exists. This is a O(n²) algorithm and require only O(1) space. We can avoid O(n²) time complexity by using additional space in the form of a hash. Hence we will have O(n) time complexity and O(n) space complexity. However there exists a better approach -- one that has O(n) time complexity and O(1) space complexity.

Lets try to have an intuitive understanding of the problem. If we think deeply, O(n²) time complexity gives us lot of computing power and we can do lot more than this trivial stuff. After all we can sort the list in O(nlogn) and then do a linear pass over the list to discover the duplicate and this can be done in O(1) space complexity. (However this only makes sense if we don't mind the original array getting destroyed). Further we cannot go below O(n) as we have to examine each element at least once.

Let us try to concentrate on solving the problem in O(n). Clearly this implies that for each element, we can do some O(1) processing. Before we try to prove or disprove whether such a O(n) is possible or not, let us consider another problem given below-

Suppose we are given an array having 2n +1 elements such that among these 2n + 1 elements, we have n pairs of x and -x. Only one number y is there whose minus is not there. Find the number y.

Clearly for above problem, we can easily find the number by simply adding together all the numbers. Here when we add together all the elements the x and -x cancel out and what remains is the element y.

Now keeping above example in mind, we find that it is similar to our original problem. It differs only in the fact that we had to find a function f such that f(x,x) generates a number z suzh that for other some other number a f(z, a) = a. To put in more simple words, we want a function which when operated on two equal numbers reduces them to the identity element of the operation. Clearly one such operation is xor.

So the solution boils down, to

Just do the xor of all the elements in the array. Whatever remains is the number which has no duplicate.

Following is a python solution for the problem.

1 def find_non_duplicate(array):
2     result = array[0]
3     for i in array[1:]:
4         result ^= i
5     return result

And clearly a C version is not too difficult and it also follows:

1 int find_non_duplicate(int *array, int size)
2 {
3     int result = array[0];
4     int i;
5     for (i = 1; i < size; i++)
6         result ^= array[i];
7     return result;
8 }

Three Prime Numbers

This is an interesting piece of question related to prime numbers, asked to me by my colleague. The question is as follows:

There are three prime numbers, p, q and r. Further p and q are consecutive prime numbers. In other words, there is no prime number k such that p < k < q. We are also given that p + q = 2r. Find the smallest such triplet (p, q, r).

Duplicating Link List with Random Pointers

Recently I came across a very interesting question on Link Lists. I tried a lot of crap before i got a click and I solved the problem. The problem can be stated as follows

We are given a singly-linked list A. The nodes of A consists of usual data and next pointer. Along with these there is another pointer random which points to a random node of A. We are supposed to make a new linked list B which is copy of A as far as the structure is concerned but all its nodes are newly allocated. Develop an algorithm such that its time complexity is O(n).

Following is my solution coded in C. I thoroughly enjoyed solving the problem and urge everyone to try to solve it yourself. You will surely get to the solution.

/*

 * duplicate_link_list.c

*

* duplicates a given link list where each node has a next pointer

* and a random pointer pointing to any node in the link list

*

 */

#include <assert.h>

#include <malloc.h>

#include <stdlib.h>

#include <stdio.h>

typedef struct _node Node;

struct _node {

    int  data;

    Node *next;

    Node *random;

};

/*

 * duplicates link list given as src and put the duplicate into

 * *dst

 *

 * assumes the link list are having sentinal elements

 *

 */

void duplicate(Node *src, Node **dst) {

    Node *i_s, *i_d, *t;

    assert(*dst != NULL);

    /* FIRST PASS Allocate new nodes */

    i_s = src;

    i_d = *dst;

    i_s = i_s->next;

    while(i_s)

    {

        t = (Node *)malloc(sizeof(Node) * 1);

        assert(t != NULL);
        t->data     = i_s->data;
        t->next     = i_s->random;
        t->random   = NULL;
        i_s->random = t;
        i_s = i_s->next;
    }
    /* SECOND PASS: Adjust all new nodes to have there
    *              correct random pointers
*/
    i_s = src->next;
    while(i_s)
    {
        Node *n;
        n = i_s->random;
        n->random = (n->next)->random;
        i_s = i_s->next;
    }
    /* THIRD PASS: Unzip the teo link lists */
    i_s = src->next;
    i_d = *dst;
    while(i_s)
    {
        t           = i_s->random;
        i_s->random = t->next;
        t->next     = NULL;
        i_d->next   = t;
        i_d         = t;
        i_s         = i_s->next;
    }
}