Programming Pearls

Recursive String Reversal in Java

Posted by

0

Java developers sometimes miss the C pointers. The classic case of string reversal is the prime example of this.

C code to recursively reverse a string :

void reverse(char *str)
{
   if(*str)
   {
       reverse(str+1);
       printf("%c", *str);
   }
}

Beautiful isn’t it. ? Wish you had the same thing for Java ?

Continue reading →

Loop in Singly Linked List.

Posted by

0

I am sure you must know answer to this by now. Nevertheless, its very easy to miss the most valid answers to this which is the lesser known “Tortoise and Hare Algorithm”

Solution with  – O(n) time complexity

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

This solution is "Floyd’s Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

Remove Duplicates from a String.

Posted by

0

Given a string  of ASCII characters, write the write a program to remove the duplicate elements present in them. For example, if the given string is "Potato", then, the output has to be "Pota". Additional constraint is, the algorithm has to be in-place( no extra data structures allowed)

Idea for an O(n) solution :

Let’s start with [‘a’,’b’,’a’,’c’,’a’,’a’,’d’,’b’,’c’]
[i:j:’a’,’b’,’a’,’c’,’a’,’a’,’d’,’b’,’c’]  –  [0,0,0,0] (character map for a,b,c,d)
1st charcter is an ‘a’, it’s not in the map, so we add it and increment i&j
[‘a’,i:j:’b’,’a’,’c’,’a’,’a’,’d’,’b’,’c’]  –  [1,0,0,0]
2nd character is ‘b’, same procedure as before
[‘a’,’b’,i:j:’a’,’c’,’a’,’a’,’d’,’b’,’c’]  –  [1,1,0,0]
third character is an ‘a’, this is already in the map, so we clear the spot, and increment only i
[‘a’,’b’,j:0,i:’c’,’a’,’a’,’d’,’b’,’c’]  –  [1,1,0,0]
fourth character is ‘c’, which is not in the map; since i and j are different we add ‘c’ to the map, move it to position j, clear position i and increment i and j.
[‘a’,’b’,’c’,j:0,i:’a’,’a’,’d’,’b’,’c’]  –  [1,1,1,0]
fifth and sixth character are handled like the third
[‘a’,’b’,’c’,j:0,0,0,i:’d’,’b’,’c’]  –  [1,1,1,0]
seventh character is ‘d’, which is not in the map, so we handle it like the fourth one.
[‘a’,’b’,’c’,’d’,j:0,0,0,i:’b’,’c’]  –  [1,1,1,1]
last two are like third case.
[‘a’,’b’,’c’,’d’,j:0,0,0,0,0]:i  –  [1,1,1,1]
i has incremented beyond the range of the array so we’re done. We have j unique characters starting from position 0.  
Code :

public static void main(String[] args) {
    char[] a = {‘a’,’b’,’a’,’c’,’a’,’a’,’d’,’b’,’c’};
    boolean[] ascii = new boolean[256];
    int j=0;
    for(int i=0;i<255;i++){
        ascii[i] = false;
    }
    for(int i=0; i<a.length;)
    {
        if(ascii[a[i]] == false)
        {
            ascii[a[i]] = true;
            a[j] = a[i];
            if (i != j)
            {   
                a[i] = ‘0’;
            }
            j++;
            i++;
        }
        else if (ascii[a[i]] == true)
        {
            a[j]=’0′;
            a[i]=’0′;
            i++;
        }       
    }

First Repeated Number.

Posted by

0

We need to find the first repeating element in an unsorted array without using any auxiliary storage.
from the array { 1 2 3 4 5 4 2 3}  
we return op = 4  (first repeated number)
If we are allowed auxiliary storage, we can use another array to store the count of every element but without such a luxury, how do we get the best possible solution ?  One O (log n) solution is to sort this and check the adjacent elements for repeated numbers. But what about an O(n) solution ?

If the elements are in the range 1-n, and the array has length n, then you can mark positions in the array. For example, you could flip the sign to denote that a number has occurred before.
So
{ 1 2 3 4 5 4 2 3}  check whether position 1 is marked; it’s not so mark it.
{ -1 2 3 4 5 4 2 3}  check whether position 2 is marked; it’s not so mark it.
{ -1 -2 3 4 5 4 2 3}  check whether position 3 is marked; it’s not so mark it.
{ -1 -2 -3 4 5 4 2 3}  check whether position 4 is marked; it’s not so mark it.
{ -1 -2 -3 -4 5 4 2 3}  check whether position 5 is marked; it’s not so mark it.
{ -1 -2 -3 -4 -5 4 2 3}  check whether position 4 is marked. Since it is marked, it is the first number to be repeated.

Pseudocode :

for i = 1 to N
{
   if(arr[arr[i]] is negative)
     return arr[i];
    else
     arr[arr[i]] *=  (-1);
}
return No_duplicates;
N is the size of array and n <= N.

Programming Pearls 1.2

Posted by

0

One of the best programming (read interview questions) books is Jon Bentley’s Programming Pearls. In an attempt to compile the solutions to the problems described in this superb book, I am starting the “Programming Pearls” series.

Problem 1.2 :

Input – A file containing at most n positive integers, each less than n, where n=10^7.  All integers are unique.

Output – A sorted list in ascending order.

Implementation sketch : A bitmap vector can be used here. For instance, we can store the set {1,2,3,5,8,13} in this bit array [0,1,1,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]

We will represent the file by a String of 10 million bits in which the Ith bit set to 1 only if that integer I is in the file.