Mustafa Veysi Soyvural

WHICH ONE JAVA DOES SUPPROT? CALL BY REFERENCE or CALL BY VALUE

2009-03-27T01:59:00.000-07:00

Many developers know that Java supports "call by references" when a method is invoked. They claim that java only use "call by value" when parameters are primitive types. And what about the truths :) the truth is absolutely different then this myth.

EVERYTHNG IN JAVA PASSED BY VALUE SO JAVA SUPPORTS ONLY "CALL BY VALUE".

C++ also supports both of call by reference and call by value methods. Let's look at an example of C++ code, the below block of code clearly illustrates the differences of these methodologies.

/*
** author: Mustafa Veysi Soyvural
**
*/

#include 
using namespace std;

class A {
private:
 int a;
public:
 A() { a = 0; }
 int getA( ) { return a; }
 void setA(int _a) { this->a = _a; }
};

//call by value
void funcA( A *a ) {
 a = new A();
 cout << "Function using Call By Value " << "a: " << a->getA() << endl;
}

//call by reference
void funcA( A &a ) {
 A *b = new A();
 a = *b;
 cout << "Function using Call By Reference " << "a: " << a.getA() << endl;
}

int main() {
 A *a = new A();
 cout << "Initial value a: " << a->getA() << endl;
 a->setA(6);
 cout << "After a->setA(6), a: " << a->getA() << endl;
 funcA(a);
 cout << "After calling funcA( A *a ), a: " << a->getA() << endl;
 funcA(*a);
 cout << "After calling funcA( A &a ), a: " << a->getA() << endl;
 return 0;
}

The output of this code is here:

1. Initial value a: 0
2. After a->setA(6), a: 6
3. Function using Call By Value a: 0
4. After calling funcA( A *a ), a: 6
5. Function using Call By Reference a: 0
6. After calling funcA( A &a ), a: 0

Pay attention to 4th and 6th raws, if you use "call by reference" method you can change the real object. In this example funcA( A &a ) changes the address of a object where it points to heap memory area. But when you use call by value method you can change the value of pointer which is in the stack.

Briefly, you can change the real object only by using call by reference. Otherwise you can change only the obect which has been copied into the stack.

I also want to give an example from Java to show that Java does only supports "Call By Value" method.

public class CallByValue {
 public static void funcA( String myStr ) {
  myStr = "I am a temp string in funcA :)";
  System.out.println(myStr);
 }
 
 public static void main(String[] args) {
  String s = "Mustafa Soyvural";
  System.out.println(s);
  funcA(s);
  System.out.println(s);
 }
}

Here is the output of this program:

Mustafa Soyvural
I am a temp string in funcA :)
Mustafa Soyvural

Kombinezonsal Devre Simülatörü

2008-04-08T22:47:00.000-07:00

Click here to download...

her türlü sorularınız için: soyvural@gmail.com
ayrıca comment yazarak da anlamadığınız şeyleri sorabilirsiniz böylece diğer arkadaşlar da faydalanmış olur.

NOT: Geliştirme ortamı olarak Eclipse 3.2 veya 3.3 kullanmanız tavsiye edilir. Turkcell Teknoloji'de geliştirme ortamı olarak bu ürünü kullandığımızdan staj döneminde sizin için daha iyi olur.

Kolay gelsin...

GELEN SORULAR ÜZERİNE CEVAPLAR
Q.1. Input dosyasındaki gate sayısının output dosyasına etkisi nedir?
A.1. Hiç bir etkisi yok aslında, gate sayısı programlama yaparken sizin işinizi kolaylaştırması açısından verilmiştir. Ayrıca size verilen format ulusları standartlık kazanmış bir formattır. Size şöyle bir katkı sağlayacak:

public abstract Gate {
/**
* Methods and data members for Gate class
* ...
*/
}

public And extends Gate {
/**
* Methods and data members for And class
* ...
*/
}

public static void main(String[] args) {
int gateNumbers = 0;
//read gate numbers from input
Gate [] gates = new Gate[gateNumbers];

......
if ( gates[i].hasSpecificInput() ) {
 if( gates[i].isOutputReady() ) {
     /**
      * implement your algorithm
      */
 }
}
}

Q.2.) Output dosyasının nasıl hazırlanacağını biraz anlatır mısınız?
A.2.) Öncelikle sizden beklenen dosyadan verileri uygun bir şekilde alıp verilerinizi düzgün bir şekilde yaratmanız( yani Gate objectlerini düzgün biçimde oluşturmanız ), ardından kaç tane input varsa; diyelim 2 input olsun:
0 0
0 1
1 0
1 1
için output değerlerini elde etmeniz.

Ör: 2 input ve 2 output için örnek output dosyası.

Output dosyasında sadece yukarıdaki verilerin olması yeterli.

Q.3.) buf tam olarak anlatılmamış. Lütfen bira açabilir misiniz?
A.3.) Buffer ve from aslında size büyük kolaylık sağlayacak ve de implementasyonu da çok kolay olan kısımlar, "buf ve from" da yapmanız gereken tek şey inputunda ne değer varsa outputunda o değeri göstermeniz.

Q.4.)
.i 11
.o 3
.ilb 1 2 3 4 5 6 7 8 9 10 81
.olb 143 145 147
açıklayabilir misiniz?
A.4.)
.i 11 --> 11 tane input var demek (tüm devrenin 11 girişi var, ara değerler sayılmıyor)
.o 3 --> 3 tane çıkış var, yine tüm devreye ait çıkışlar
.ilb 1 2 3 4 5 6 7 8 9 10 81 -->Devrenin girişleri, 11 tane olarak belirtilen girişler
.olb 143 145 147 -->Devrenin çıkışları, 3 tane olarak belirtilen çıkışlar

Q.5.) Örnekte verilen input ve output dosyası birbirini tutmuyor.
A.5.) Evet örnekte sadece format olarak örnek koymak istemiştim. Word dosyasındaki output dosyası verilen input'a ait değildir. Sadece format olarak örnek vermek için koydum.

Son olarak şunu önemle vurgulamak istiyorum, kafanıza takılan herhangi bir soruyu çekinmeden sorabilirsiniz. Problem tanımıyla alakalı kafanızda herhangi bir soru işareti kalmasını istemem. Programlama dili olarak Java, C++, C# kullanabilirsiniz bu konuda tamamen serbestsiniz ama benim tavsiyem Java ve Eclipse kullanmanız ve bu şekilde Turkcell Teknolojideki iş sürecine uyumunuzu hızlandırmanız. Programlamada, tasarımda, problemde karşılaştığınız herhangi bir sorunu lütfen SORUN, SORUN, SORUN :)

Değerlendirme aşamasında ise üzerinde duracağım temel şey OOP kriterlerine uygunluğunuz.
Örneğin: Her gate için ayrı sınıf ve metodlar oluşturmak sizce de son derece kötü bir çözüm olmaz mı?

Ayrıca sizin işinizi kolaylaştıracak bazı noktalar da var ben bunlardan birini size ipucu olarak verdim zaten. Problemi iyi anlayıp, OOP bilgilerinizi de güzel bir şekilde kullanırsanız çok kolaylıkla halledeceğinize inanıyorum.

Hepnize Kolay Gelsin

Regular Expressions with Finite State Machines

2008-01-28T02:10:00.000-08:00

Let's make a "Finite State Machine" which is used to check "a*b" regular expression.
At first we must design the FSM.

class State {
protected:
 State * const nextState;
 bool isFinal;
public:
 State( State & next, bool _isFinal ) : nextState( &next ) { isFinal = _isFinal; }
 virtual State * transition( char in ) = 0;
 bool isFinalState( ) { return isFinal; }
 ~State( ) { isFinal = false; }
};

class State1 : public State {
public:
 State1( State & nextState, bool _isFinal ) : State( nextState, _isFinal ) { }
 State * transition( char in );
};

State * State1::transition( char in ) {
 if( in >= '0' && in <= '9' ) return this->nextState;
 else return NULL;
}

class State2 : public State {
public:
 State2( State & nextState, bool _isFinal ) : State( nextState, _isFinal ) { }
 State * transition( char in );
};

State * State2::transition( char in ) {
 if( in == '*' ) return this->nextState;
 else return NULL;
}

class FSM {
 State1 state1;
 State2 state2;
 State1 state3;
 State2 final;
 State * current;
public:
 FSM( ) : state1( state2, false ), state2( state3, false ), state3( final, false ), final( final,true ), current( &state1 ) { }
 bool run( const char *s );
};

bool FSM::run(const char *s) {
 int len = strlen( s );
 int i = 0;
 do {
  current = current->transition( s[i] );
  if( current && current->isFinalState( ) )
   return true;
  i++;
 } while( NULL != current && i < len );
 
 return false;
}

int main() {
 char s[ ] = "3*4";
 FSM fsm;

 if( fsm.run( s ) ) {
  cout << s << " is a regular expression like \"a*b\" " << endl;
 }

 return 0;
}

malloc, free & realloc with buddy algorithm

2008-01-27T11:07:00.000-08:00

struct m_list {
   void *address;
   unsigned int size;
   unsigned int in_use:1;
   m_list *next;
   m_list( void *_address, long _size) { size = _size; address = _address; next = NULL; in_use = 0; }
};

//1 KB buffer
char buffer[1024];

unsigned int get_next_two_power( unsigned int n ) {
   unsigned int num = 1;
   while( num < n ) {
       num <<= 1;
   }
   return num;
}

void * my_malloc( unsigned int size, m_list **memlist ) {
   if ( NULL == memlist || NULL == *memlist ) return NULL;
   int alloc_size = get_next_two_power( size );

   m_list *p = *memlist;
   while( p ) {
       if( p->in_use == 0 ) {
           if( alloc_size == p->size ) {
               p->in_use = 1;
               return p->address;
           }
           if ( alloc_size < p->size ) {
               m_list *node = new m_list(NULL, p->size >> 1);
               node->address = (void *)((int)(p->address) + (p->size >> 1));
               node->next = p->next;
               p->next = node;
               p->size = p->size >> 1;
               return my_malloc( alloc_size, memlist );
           }
       }
       p = p->next;
   }

   return NULL;
}

void merge_buddies( m_list **memlist ) {
   m_list *curr = *memlist, *next = curr;
   bool is_merge = false;
   while( curr ) {
       if( curr->in_use == 0 ) {
           if( NULL != curr->next ) {
               next = curr->next;
               if( 0 == next->in_use && (next->size == curr->size) ) {
                   curr->size += next->size;
                   curr->next = next->next;
                   is_merge = true;
                   free(next);
               }
           }
       }
       curr = curr->next;
   }
   if ( is_merge ) {
       merge_buddies( memlist );
   }
}

void my_free( void * address, m_list **memlist ) {
   if( NULL == address || NULL == memlist || NULL == *memlist ) return;
   m_list *curr = *memlist, *back, *next;

   while( curr ) {
       if( curr->address == address ) {
           curr->in_use = 0;
           merge_buddies( memlist );
           return;
       }
       curr = curr->next;
   }
}

void * my_realloc( void * address, unsigned int size, m_list **memlist ) {
 my_free(address, memlist);
 void *adr = my_malloc(size, memlist);
 memcpy(adr, address, size );

 return adr;
}

int main() {
 m_list *memlist = new m_list((void *)buffer, 1024);
 printf("buffer address:: %p\n", buffer);
 printf("memlist address:: %p\n", memlist->address);

 int *p1 = (int *)my_malloc(sizeof(int)*100, &memlist);
 for( int i = 0; i < 100; i++ ) {
  p1[i] = i;
 }

 p1 = (int *)my_realloc(p1, sizeof(int)*256, &memlist);
 for( int i = 0; i < 100; i++ ) {
  cout << p1[i] << " * ";
 }
 cout << endl;

 my_free( p1, &memlist );

 char *p2 = (char *)my_malloc(sizeof(char)*240, &memlist);
 *p2 = '\0';
 strcpy( p2, "Mustafa Veysi Soyvural\0" );
 cout << p2 << endl;
 my_free( p2, &memlist );

 return 0;
}

Rotation of a String

2007-12-23T12:17:00.000-08:00

Q.)Given a string s1 and a string s2, write a snippet to say whether s2 is a
rotation of s1 using only one call to strstr routine?

(eg given s1 = ABCD and s2 = CDAB, return true,
given s1 = ABCD, and s2 = ACBD , return false)

If you add s1by itself then you will get s1=ABCDABCD, as you can see now you will be able to make a decision whether s2 is a rotation or not.

Test Cases:
- s1 = NULL
- s2 = NULL
- Both s1 and s2 are NULL
- s1 = "\0", s2 = "\0" ( the rotation of empty string is itself:) )
- s1 = "ABCD", s2 = "CDAB"
- s1 = "ABCD", s2 = "CD"
- s1 = "ABCD", s2 = "CDBA"
- s1 = "KUJU", s2 = "JUKU"

typedef enum { False, True } Boolean;

Boolean isStringRotate( const char s1[ ], const char s2[ ] ) {
    int len1 = 0, len2 = 0;
    char *s = NULL;
    if ( NULL == s1 || NULL == s2 )    
        return False;

    len1 = strlen( s1 );
    len2 = strlen( s2 );
    if ( len1 != len2 ) return False;

    s = ( char * )malloc( len1 + len2 + 1 );
    s[ 0 ] = '\0';
    strcat(s, s1);
    strcat(s, s1);
    
    if ( !strncmp(&s[ len1 / 2 ], s2, len1) )
        return True;
    return False;
}

Reverse Words of a String

2007-12-17T03:57:00.000-08:00

Q.) How do you reverse the words in a string?

"My name is Amit Agarwal"
to
"Agarwal Amit is name My"

A O(n) and 'in space' solution is appreciable.

- First reverse the whole string
- Then reverse each word in the string

Test Cases:
- NULL string
- "" empty string
- "a" string that consists only one word
- "mustafa"
- "a b"
- "Mustafa Veysi Soyvural"
- "Mustafa Veysi Soyvural" more than one space between words

void reverse_words( char s[] ) {
    char *p, temp;
    int len = 0, i = 0, index = 0, word_len = 0;
    if ( NULL == s ) return;
    for ( p = s; *p != '\0'; p++ );
    len = p - s;
    
    /* reverse whole string */
    for ( i = 0; i < (len / 2); i++ ) {
        temp = s[ i ];
        s[ i ] = s[ len - i - 1 ];
        s[ len - i - 1 ] = temp;
    }

    /* reverse each word */
    p = s;
    while ( index < len ) {
        if ( *p != ' ' && *p != '\0' ) p++;
        else {
            word_len = p - &s[ index ];
            /* reverse word */
            for ( i = 0; i < (word_len / 2 ); i++ ) {
                temp = s[ i + index ];
                s[ i + index ] = s[ index + word_len - i - 1 ];
                s[ index + word_len - i - 1 ] = temp;
            }
            index += word_len + 1;
            p++;
        }
    }
}

Singleton Pattern

2007-12-14T06:07:00.000-08:00

Sometimes you need to only one instance of a class exist during the program runs.
Here is a Singleton Pattern Implementation in C++.

hedar file:

class Singleton {
private:
    static Singleton * single;
    Singleton( ) { }
    Singleton( const Singleton & instance ) { }
    const Singleton & operator = ( const Singleton & instance ) {  }
public:
    static Singleton * getInstance();
    ~Singleton( ) { }
};

source file:

Singleton * Singleton::single = NULL;
Singleton * Singleton::getInstance( ) {
    if( NULL == single ) {
        single = new Singleton( );
    }
    return single;
}

Linked List Class

2007-12-13T16:16:00.001-08:00

Here is the node.h file where node class and methods definitions exist:

#ifndef NODE_H_
#define NODE_H_

template <typename Type>
class Node {
    Type data;
    Node<Type> * next;
    Node( ) { }
public:
    Node( Type );
    Type getData( ) const;
    Node * getNext( ) const;
    void setNext( Node<Type> * );
    ~Node( );
};

#endif

Here is the node.cpp file where Node Class methods are implemented.

template <typename Type>
Node<Type>::Node( Type _data ) {
    this->data = _data;
    this->next = 0;
}

template <typename Type>
Type Node<Type>::getData( ) const {
    return this->data;
}

template <typename Type>
Node<Type>* Node<Type>::getNext( ) const {
    return this->next;
}

template <typename Type>
void Node<Type>::setNext( Node<Type> *node ) {
    this->next = node;
}

template <typename Type>
Node<Type>::~Node( ) {
    this->next = 0;
}

Here is the list.h file where List Class and methods exist.

#ifndef LIST_H_
#define LIST_H_

#include "node.h"

template <typename Type>
class List {
    Node<Type> * head;
    Node<Type> * tail;
    unsigned int length;
public:
    List( ); 
    List( const List & );
    bool insert( Type data );
    bool remove( unsigned int );
    bool removeAtLast( unsigned int );
    void insertSorted( Type data );
    void reverse( );
    void print( std::ostream & out ) const;
    unsigned int size( ) const;
    bool isEmpty( ) const;
    Type get( unsigned int index ) const;
    const Node<Type> * getMidNode( ) const ; 
    const List<Type> & getFirstHalf( ) const ;
    const List<Type> & operator = ( const List<Type> & );
    List<Type> operator + ( const List<Type> & ) const;
    void operator += ( const List<Type> & );
    bool operator == ( const List<Type> & ) const;
    bool operator != ( const List<Type> & ) const;
    void clear( );
    ~List( );
};

#endif

Here is the list.cpp file where List Class methods are implemented:

#include "node.h"
template <typename Type>
List<Type>::List( ) {
    this->head = this->tail = 0;
    this->length = 0;
}

template <typename Type>
List<Type>::List( const List<Type> & list ) {
    this->head = this->tail = 0;
    this->length = 0;
    
    for ( Node<Type> * p = list.head; p; p = p->getNext( ) ) {
        this->insert( p->getData( ) );
    }
}

template <typename Type>
bool List<Type>::insert( Type data ) {
    Node<Type> * node = new Node<Type>( data );
    if ( 0 == node ) return false;
    if ( 0 == head ) {
        this->head = this->tail = node;
    } else {
        this->tail->setNext( node );
        this->tail = node;
    }
    this->length++;
    return true;
}

template <typename Type>
void List<Type>::insertSorted( Type data ) {
    if ( this->isEmpty( ) ) {
        this->insert( data );
    } else {
        Node<Type> * node = new Node<Type>( data );
        Node<Type> * p = head, * q; 
        while ( p->getNext( ) && data > p->getData( ) ) {
            q = p;
            p = p->getNext( );
        }
        if ( p == head ) { //insert beginning of the list
            node->setNext( head );
            head = node;
        } else if ( p->getNext( ) == 0 ) {  //insert end of the list
            p->setNext( node );
            this->tail = node;
        } else { //insert 
            node->setNext( p );
            q->setNext( node );
        }
        this->length++;
    }
}

template <typename Type>
void List<Type>::print( std::ostream & out ) const {
    for ( Node<Type> * p = head; p; p = p->getNext( ) ) {
        out << p->getData( ) << " - "; 
    }
    out << endl;
}

template <typename Type>
unsigned int List<Type>::size( ) const {
    return length;
}

template <typename Type>
Type List<Type>::get( unsigned int index ) const {
    if ( this->isEmpty( ) ) {
        throw "List is empty.";
    }

    if ( index >= this->length ) 
        throw "Index is out of boundary.";  
    
    int counter = 0;
    Node<Type> *p = this->head;
    while ( p && ( counter < index ) ) {
        counter++;
        p = p->getNext( );
    }
    return p->getData( );
}




template <typename Type>
void List<Type>::reverse( ) {
    Node<Type> * p, * q, * r;
    p = q = r = 0;
    r = this->head;
    while ( r ) {
        q = p;
        p = r;
        r = r->getNext( );
        p->setNext( q );
    }
    this->head = p;
}

template <typename Type>
const List<Type> & List<Type>::getFirstHalf( ) const {
    List<Type> *list = new List( );
    Node<Type> *p, *q;
    q = p = this->head;
    
    int counter = 1;
    while ( p ) {
        p = p->getNext( );
        if( counter++ % 2 == 0 ) {
            list->insert( q->getData( ) );
            q = q->getNext( );
        }
    }
    return *list;
}

template <typename Type>
const Node<Type> * List<Type>::getMidNode( ) const {
    Node<Type> *p, *q;
    q = p = this->head;
    
    int counter = 1;
    while ( p ) {
        p = p->getNext( );
        if( counter++ % 2 == 0 ) {
            q = q->getNext( );
        }
    }
    return q;
}


template <typename Type>
bool List<Type>::isEmpty( ) const {
    if ( 0 == this->head ) return true;
    return false;
}

/*********************************
** n between 0 and length - 1 
**********************************/
template <typename Type>
bool List<Type>::remove( unsigned int n ) {
    if ( n >= this->length ) return false;
    if ( this->length == 1 ) {
        this->clear( );
        return true;
    }
    
    int counter = 0;
    Node<Type> *p, *q;
    q = p = this->head;
    while ( counter++ < n && p ) {
        q = p;
        p = p->getNext( );
    }
    if ( counter <= n ) return false;
    
    if ( p == this->head ) {
        this->head = p->getNext( );
    } 
    else {
        q->setNext( p->getNext( ) );
    }
    if ( p == this->tail ) {
        this->tail = q;
    } 
    
    delete p;
    this->length--;
    return true;
}

/******************************
** n between 0 and length - 1
*******************************/
template <typename Type>
bool List<Type>::removeAtLast( unsigned int n ) {
    return this->remove( this->length - n - 1 );    
}

template <typename Type>
const List<Type> & List<Type>::operator =( const List<Type> & list ) {
    this->clear( );
    
    for ( Node<Type> * p = list.head; p; p = p->getNext( ) ) {
        this->insert( p->getData( ) );
    }

    return *this;
}

template <typename Type>
List<Type> List<Type>::operator +(const List<Type> & list) const {
    List<Type> result;
    
    for ( Node<Type> * p = this->head; p; p = p->getNext( ) ) {
        result.insert( p->getData( ) );
    }

    for ( Node<Type> * p = list.head; p; p = p->getNext( ) ) {
        result.insert( p->getData( ) );
    }

    return result;
}

template <typename Type>
void List<Type>::operator += ( const List<Type> & list ) {
    for ( Node<Type> *p = list.head; p; p = p->getNext( ) ) {
        this->insert( p->getData( ) );
    }
}

template <typename Type>
bool List<Type>::operator == ( const List<Type> & list ) const {
    if ( this->length != list.length ) return false;
    Node<Type> *p = this->head, *q = list.head;
    while ( p && q ) {
        if ( p->getData( ) != q->getData( ) ) return false;
        p = p->getNext( );
        q = q->getNext( );
    }
    if ( (p && !q) || (!p && q) ) return false;
    return true;
}

template <typename Type>
bool List<Type>::operator != ( const List<Type> & list ) const {
    return !( this->operator==( list ) );
}

template <typename Type>
void List<Type>::clear( ) {
    Node<Type> *p = this->head, *next;
    while ( p ) {
        next = p->getNext( );
        delete p;
        p = next;
    }
    this->head = 0;
    this->tail = 0;
    this->length = 0;
}

template <typename Type>
List<Type>::~List( ) {
    this->clear( );
}

Linked List

2007-12-11T17:02:00.000-08:00

hi,
i wanna just give some problems of linked list and solutions.

Q.1.)Given a singly-linked, find out the mid point of a single linked list in a
single parse of the list. Assume the program would be loaded in read-only
memory so no manipulation of the list is allowed.

Having two pointers makes easy to implement gettig middle node of a linked list.
while one pointer goes on the whole list the other pointer goes as half as first pinter's.

node_t * get_mid_node( list_t * list ) {
    node_t *p, *q; 
    int counter = 1;
    if ( NULL == list ) return NULL;
    p = list->head;
    q = list->head;

    while ( p ) {
        p = p->next;
        if ( counter++ 2 == 0 ) {
            q = q->next;
        }
    }
    return q;
}

Q.2.)Given: 2 Unsorted single linked list

Todo: Fastest and optimised way to merge and make a single sorted list with
these 2 unsorted single linked list.

list_t * get_intersection_of_two_sorted_list ( list_t * list1, list_t * list2 ) {
    node_t *first, *second;
    list_t *intersection_list;
    if ( !list1 || !list2 )    return NULL;

    intersection_list = ( list_t * ) malloc( sizeof( list_t ) );
    if ( NULL == intersection_list ) {
        fprintf(stderr, "Bad memory allocation error\n");
        return NULL;
    }
    while ( first && second ) {
        if ( first->data < second->data ) first = first->next;
        else if ( second->data < first->data ) second = second->next;
        else {
            add_list( intersection_list, first->data );
            first = first->next;
            second = second->next;
        }
    }
}

Q.3.)Given a linked list, your are asked to find out the nth last element in
the linked-list. (n would be given as the argument to the function)

Last nth element is ( l - n + 1)th element from the beginning, so having two pointers:
- Two pointers indicates the list->head at first
- First pointer goes to nth node from the beginning
- Both pointers goes simultaneously until first pointer comes to the end of the list
- Now second pointer walks ( l - n ) nodes, head node is also assumed one walk for two pointers.
- Then secod pointer now indicates the last nth element.

Test Cases:
- List is null
- List is empty
- List with length 1 ( get 1 )
- List with length 2 ( get 1, 2 )
- List with length 3 ( get 3, 1, 2 )
- Any value larger than the size of list

int getLastNth( list_t *list, unsigned int n ) {
    int counter;
    node_t *p, *q;
    
    if ( NULL == list ) {
        fprintf( stderr, "list is null...(getLastNth)\n" );
        exit(1);
    }

    p = list->head;
    q = list->head;
    for ( counter = 0; p && counter < n - 1; p = p->next, counter++ );

    if ( NULL == p ) {
        fprintf( stderr, "Index is out boundary...(getLastNth)\n" );
        exit(1);
    }
    
    while ( p->next ) {
        q = q->next;
        p = p->next;
    }
    return q->data;
}

Q.4.)Print reverse order of a singly linked list.

void print_list_reverse_order( node_t * head ) {
    if ( NULL == head ) return;
    print_list_reverse_order( head->next );
    printf("%d\n", head->data);
}

An Impressing Operator (Xor)

2007-12-11T13:26:00.000-08:00

Now, lets talk about Xor operator. You can use this operator in many ways that you will see in some exercises here.

i ll give some remindful information about Xor gate:
- it yields 1 if there exists odd number of 1 value inputs
- x Xor 1 = not(x)
- x Xor 0 = x

Q.1.) Given two arrays A and B. Array 'A' contains all the elements of 'B' but
one more element extra.....

Find out the extra element......

Restrictions: Dont use any relational ops ( > or > or == etc....), array
elements are not in order ...,

int getDistinctElementFromTwoArrays( int arr1[ ], int len1, int arr2[ ], int len2 ) {
    if ( len1 < 0 || len2 < 0 ) throw out_of_range( "Length of arrays must be bigger than 0." );
    
    int result = arr1[ 0 ];
    for ( int i = 1; i < len1; i++ ) {
        result ^= arr1[ i ];
    }
    
    for ( int i = 0; i < len2; i++ ) {
        result ^= arr2[ i ];
    }

    return result;
}

#include <iostream>
using namespace std;

int main ( int argc, char *argv[] ) {
    try {
        int arr1[ ] = { 1, 3, 5, 6, 7, -1, -3 };
        int arr2[ ] = { 7, -3, 6, 1, -1, 5 };
        int len1 = sizeof( arr1 ) / sizeof( arr1[ 0 ] )
        int len2 = sizeof( arr2 ) / sizeof( arr2[ 0 ] );
        
        cout << getDistinctElementFromTwoArrays( arr1, len1, arr2, len2 ) << endl;
    }
    catch ( out_of_range orex ) {
        cout << orex.what( ) << endl;
    }
    return 0;
}

Q.2.)Given an array of numbers, except for one number all the others, occur
twice. Give an algorithm to find that number which occurs only once in the
array.

int getDistinctElement( int arr1[], int len1 ) {
    if ( len1 < 0 ) throw  out_of_range("Length must be bigger than 0");
    int result = arr1[ 0 ];
    
    for ( int i = 1; i < len1; i++ ) {
        result ^= arr1[ i ];
    }

    return result;
}

#include <iostream>
#include <stdexcept>
using namespace std;

int main ( int argc, char *argv[] ) {
    try {
        int arr1[ ] = { -1, 1, 2, 3, 2, 1, -1 };
        int len1 = sizeof( arr1 ) / sizeof( arr1[ 0 ] );
                
        cout << getDistinctElement( arr1, len1 ) << endl;
    }
    catch ( out_of_range orex ) {
        cout << orex.what( ) << endl;
    }
    
    return 0;
}

Shifting Operation

2007-12-11T05:36:00.000-08:00

Hi, there is a good division and multiplication method by using shifting.
Lets take an example 833794 and divide this number by 10, shift this number to right only once: 83379, and if you want to divide by 100 shift this number to right twice:
8337. The same method is validate also for multiplication with only a little bit change, that is, only shift to left.

Now lets do some exercises :)

Q.1.)Given a numbers x and n, where n is a power of 2, write C code, which
gives the multiple of n which is greater than or equal to x.
ex :
I/P: 13 8
O/P: 16

I/P: 17 16
O/P: 32

The challenge: Do not use division or modulo operator.

unsigned int getBiggerPowerOf2( unsigned int x, unsigned int n ) {
   if ( n == 0 ) return 0;
   while ( n < x  ) {
       n = n << 1;
   }
   return n;
}

Q.2.)Write a C function, which takes a number n and positions p1 and p2 and returns if the the bits at positions p1 and p2 are set or not.

bool isBitsSet( int num, int p1, int p2 ) {
    int temp = 0;
    temp = ( 1 << (p1 - 1) ) + ( 1 << (p2 - 1) );
    num = num & temp;
    if ( num == temp ) return true;
    return false;
}

Q.3.)Write a C function, which takes a number n and positions p1 and p2 and returns if the the bits at positions p1 and p2 are same or not.

bool isSameBits( int num, int p1, int p2 ) {
    int temp = num;
    
    temp = 1 & ( temp >> (p1 - 1) );
    num = 1 & ( num >> (p2 - 1) );
    
    return ( temp == num );
}

Q.4.) Give a fast way to multiply a number by 7.

    number * 8 = number << 3;
    number = ( number << 3 ) - number;

Reverse a stack "in-place"

2007-11-27T23:26:00.000-08:00

While i am searchig data structure questions on
the net, i encountered a very nice question
about stacks.Thanks Gowri Kumar for this
question and solution.

Write a C Program to reverse a stack "in place"
using recursion ?
You can only use the following ADT functions
on Stack:
IsEmpty
IsFull
Push
Pop
Top

What we require is:
Before : A B C D
After : D C B A

Before : A B C D
Step 1 : D A B C
Step 2 : D C A B
Step 3 : D C B A

Basically, at each step I am bringing the
bottom most element to the top of the
stack and pushing all the other elements one
down (this I call Percolate, (pecolating up).

void percolate_up( stack_t *stack ) {
    int a, b;
    if ( !stack ) return;
    a = Pop( stack );
    if ( isEmpty( stack ) ) {
        Push( stack, a );
        return;
    }
    percolate_up( stack );
    b = Pop( stack );
    Push( stack, a );
    Push( stack, b );
}

void reverse_stack( stack_t * stack ) {
    int a;
    if ( !stack ) return;
    if ( isEmpty( stack ) ) {
        return;
    }
    percolate_up( stack );
    a = Pop( stack );
    reverse_stack( stack );
    Push( stack, a );
}

I do it in the following steps:
Before : A B C D

After one PercolateUp
Step 1 : D A B C
After one PercolateUp
Step 1 : D A B C

D is in right postion, Pop it and do the Reverse
on the remaining elements. After the reverse
of remaining elements, push the element which
we stored earlier.

PercolateUp reminds me the Bubble Sort,
which has a similar work mechanism.
Bubble sort moves the largest element
to the end of the list in each step
and Percolate function moves
the bottom element to the top of the
list in each step similarly.

Sorting a Stack "in-place"
Lets think about how to sort a stack
by stick to "in-place".
Actually, i have given a hint when mentioned
about the similarity between PercolateUp and
Bubble Sort algorithm.
Make some changes on PercolateUp:

void sorting_percolate_up( stack_t * stack ) {
    int a, b;
    a = Pop( stack );
    if ( isEmpty( stack ) ) {
        Push( stack, a );
        return;
    }
    sorting_percolate_up( stack );
    b = Pop( stack );
    if ( a < b ) {
        Push( stack, b );
        Push( stack, a );
    } else {
        Push( stack, a );
        Push( stack, b );
    }
}

void sort_stack( stack_t * stack ) {
    int a;
    if ( !stack ) return;
    if ( isEmpty( stack ) ) return;
    sorting_percolate_up( stack );
    a = Pop( stack );
    sort_stack( stack );

    Push( stack, a );

}

Now, you have a stack sort function,
by making a few changes.
that's all :)

Binary Search Tree

2007-10-30T01:52:00.000-07:00

Hi you all:)
i wanna just talk about binary search tree which is also familiar among most of the software engineers.

BST (Binary Search Tree) has a few simple rules:
- Each node must have a value
- All the left subtree nodes must have values less than the node's value
- All the right subtree nodes must have values greater or equal than the node's value

As you can see, there are not any complexity to understand a search tree work mechanism, but a figure could be mohttp://www.youtube.com/watch?v=t3ASa4jpqgkre illustrative :))

After this introductory definition, and now it is the best time to do some exercises on BST. First of all, lets start with traversals of BST.

1. Inorder Traversal ( Left, Root, Right )
2. Preorder Traversal (Root, Left, Right )
3. Postorder Traversal ( Left, Right, Root )

//recursive inorder traversal
void print_inorder( node_t *root) {
if ( !root ) return;
print_inorder( root->left );
printf( "%d ", root->data );
print_inorder( root->right );
}

But you can convert recursive functions to iterative by using stack. Because, recursive functions use stack to hold parameters, local variables and return values in stack.

//iterative inorder traversal
void print_inorder_iter( node_t *root ) {
stack_t stack;
if ( !root ) return;
initialize( &stack );

do {
while ( root ) {
    Push( &stack, root );
    root = root->left;
}
if ( !isEmpty( &stack ) ) {
    root = Pop( &stack );
    printf("%d ", root->data);
}
root = root->right;
} while ( root || !isEmpty( &stack ) );
}

//recursive preorder traversal
void print_preorder( node_t *root ) {
if ( !root ) return;
printf( "%d ", root->data );
print_preorder( root->left );
print_preorder( root->right );
}

//iterative preorder traversal
void print_inorder_iter( node_t *root ) {
stack_t stack;
if ( !root ) return;
initialize( &stack );

do {
 while ( root ) {
     Push( &stack, root );
     root = root->left;
 }
 if ( !isEmpty( &stack ) ) {
     root = Pop( &stack );
     printf("%d ", root->data);
 }
 root = root->right;
} while ( root || !isEmpty( &stack ) );
}

//recursive postorder traversal
void print_postorder( node_t *root ) {
if ( !root ) return;
print_postorder( root->left );
print_postorder( root->right );
printf( "%d ", root->data );
}

1.) How do you get the node numbers of a Binary Tree ?

//this is also known as size of a tree
int get_node_numbers( node *root ) {
if ( !root ) return 0;
return  1 + get_node_numbers( root->left ) + get_node_numbers( root->right );
}

2.) How do you get the Binary Tree height?

int get_tree_height( node *root ) {
if ( !root ) return -1;
return 1 + max( get_tree_height( root->left ), get_tree_height( root->right ) );
}

3.) Get the sum of all nodes in a Binary Tree.

int get_tree_sum( node *root ) {
if ( !root ) return 0;
return root->data + get_tree_sum( root->left ) + get_tree_sum( root->right );
}

4.) What is the number of leaves in a Binary Tree ?

int get_leaf_number( node *root ) {
if ( !root ) return 0;
if ( !root->left && !root->right ) return 1;
return get_leaf_number( root->left ) + get_leaf_number( root->right );
}

5.) What is the minimum value in a Binary Tree?

int get_minimum_value( node *root ) {
if ( !root ) return 0;

while ( root->left ) {
   root = root->left;
}
return root->data;
}

6.) What is the maximum value in a Binary Tree ?

int get_maximum_value( node *root ) {
if ( !root ) return 0;

while ( root->right ) {
    root = root->right;
}
return root->data;
}

7.) Write a function that tests the binary tree whether it is a BST or not. Now, you must be careful about the maximum value of left subtree must be less than the current node's value and also the minimum of the right subtree must be greater than the current node's value.
Lets discuss about this case in the below:

If you tests only nodes left and right value, then this tree will surprisingly become a BST which is a really bad situation for a developer :))

if ( root->data > root->left->data && root->data <>right->data ) { ... }
This control is not sufficient to test all cases, so be careful while writing all your test functions and try to consider all cases.

Boolean isBinaryTree( node * root ) {
 if ( !root ) return True;

 if ( root->left != NULL && get_maximum_value( root->left ) > root->data )
     return False;

 if ( root->right != NULL && get_minimum_value( root->right ) <= root->data )
     return False;

 if ( isBinaryTree( root->left ) || !isBinaryTree( root->right ) )
     return False;
 return True;
}

8.) Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found.
For example; for this tree and check path sum: 25

path1: 12 - 9 - 3 : 24 ( false )
path2: 12 - 9 - 15 : 36 ( false )
path3: 12 - 13 : 25 ( true )

To achieve this problem you will substract all nodes' value while traversiing nodes along a path.

Boolean check_path_sum( node *root, int check_sum ) {
    if ( !root ) {
        return ( check_sum == 0 );
    }
    return ( check_path_sum( root->left, check_sum - root->data) || check_path_sum( root->right, check_sum - root->data) );
}

9.) Give back all nodes in a binary tree to memory, in other words you will free a binary tree. Hint : If you free a parent before childs so how do you access childs adress, as a result of this problem you have to free childs before parent. As you can see, it is easy to see postorder traversal must be used.

void free_tree( node *root ) {
   if ( !root ) return;
   free_tree( root->left );
   free_tree( root->right );
   free( root );
}

10.) Change the roles of the left and right pointers of a node. Mirror a binary tree :)

previous version:

mirror version:

void mirror_tree( node *root ) {
   if ( !root ) return;
   mirror_tree( root->left );
   mirror_tree( root->right );

   node *p = root->left;
   root->left = root->right;
   root->right = p;
}

11.) For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. double a binary tree.

void double_tree( node *root ) {
   node *p;
   if ( !root ) return;
   double_tree( root->left );
   double_tree( root->right );
  
   //take a new node
   p = ( node * )malloc(sizeof(node));
   p->left = NULL;
   p->right = NULL;
   p->data = root->data;
  
   if ( !root->left ) {
       root->left = p;
   }
   else {
       p->left = root->left;
       root->left = p;
   }
}

12.) Get the sum of path numbers from root to each leaves. I have also mentioned how to get the number of leaves in a binary tree. This is exactly equal to the path numbers of a binary tree from root to each leaves :)

13.) Find the number of nodes between two nodes. The value of two nodes are given as first and second. Assume that two nodes are in the same subtree.
First, you will search first value in the BST then search second value in the subtree of first.
For example; BST is given in the follow, first 9 and second is 15.

First search 9 and then search 15 in the subtree of 9.

    9
  / \
 3  15

node * lookup( node * root, int data ) {
    if ( !root ) return NULL;
    if ( data == root->data ) return root;
    else if ( data < root->data ) return lookup( root->left, data );
    else return lookup( root->right, data );
}

int get_number_between_two_nodes( node * root, int first, int second ) {
    int counter = 0;
    root = lookup( root, first );
    //now, root points to first root     
    if ( root == NULL ) return -1;
    //find the last node
    while ( root ) {
        if ( second < root->data ) {
            counter++;
            root = root->left;
        }
        else if ( second > root->data ) {
            counter++;
            root = root->right;
        }
        else {
            counter--;
            break;
        }
    }
    if ( !root ) return -1;
    if ( first == second ) return 0;
    return counter;
}

14.) Print all paths from root to each leaf.

void print_array( int array[ ], int length ) {
    int i = 0;
    for ( i = 0; i < length; i++ ) {
        printf( "%d - ", array[ i ] );
    }
    printf( "\n" );
}

void print_paths_rec( node * root, int path[ ], int len ) {
    if ( !root ) return;
    path[ len++ ] = root->data;
    if ( root->left == NULL && root->right == NULL ) {
        print_array( path, len );
    }
    print_paths_rec( root->left, path, len );
    print_paths_rec( root->right, path, len );
}

void print_paths( node *root ) {
    int path[ 1000 ];
    print_paths_rec( root, path, 0 );
}