Monday, May 26, 2014

IMAP UID Error: "Your Server reported a UID that does not comply with the IMAP standard. This typically indicates a Server Bug. Your program may not function properly after this."

This post might be helpful for those working on IMAP Server.
In this post I will try to explain why this error occurs.


Error Text.
Your Server reported a UID that does not comply with the IMAP
standard. This typically indicates a Server Bug. Your program may
not function properly after this.

Account: youremail@yourdomain.com
MsgSeqNum 147, New UID 3193, Prev UID:3193, Next UID:0,
Protocol: IMAP
Server: the email server name you are using
Port: 993 or 143
Error Code: 0x800CCCDC


Error Dialog Box Image.


[1] Background For Understanding This Error.
To understand this error we need to first understand 3 things:
[1.1] The NOOP Command.
[1.2] Outlook Behaviour.
[1.3] UID Of A Message In IMAP.

[1.1] The NOOP Command.
RFC 3501 - INTERNET MESSAGE ACCESS PROTOCOL - VERSION 4rev1
http://tools.ietf.org/html/rfc3501#section-6.1.2

6.1.2. NOOP Command
Arguments:  none
Responses:  no specific responses for this command (but see below)
Result:     OK - noop completed
            BAD - command unknown or arguments invalid

   The NOOP command always succeeds.  It does nothing.
   Since any command can return a status update as untagged data, the
   NOOP command can be used as a periodic poll for new messages or
   message status updates during a period of inactivity (this is the
   preferred method to do this).  The NOOP command can also be used
   to reset any inactivity autologout timer on the server.

Example:    C: a002 NOOP
            S: a002 OK NOOP completed
               . . .
            C: a047 NOOP
            S: * 22 EXPUNGE
            S: * 23 EXISTS
            S: * 3 RECENT
            S: * 14 FETCH (FLAGS (\Seen \Deleted))
            S: a047 OK NOOP completed
              
* [MsgSeqNum] EXPUNGE
Gives info(Message Sequence Number) of message deleted.

* [TotalMsg] EXISTS
Gives info of Total Messages currently in mail box.

* [TotalNewMsg] RECENT
Gives info of Total number of New Messages in mail box.

[1.2] Outlook Behaviour.
Outlook fires NOOP command to get the latest details of mailbox in order to refresh its MailList.

[1.3] UID Of A Message In IMAP.
2.3.1.1. Unique Identifier (UID) Message Attribute
RFC 3501 - INTERNET MESSAGE ACCESS PROTOCOL - VERSION 4rev1
http://tools.ietf.org/html/rfc3501#section-2.3.1.1

If IMAP Server have assigned a message a particular UID "U", then
that UID "U" MUST NOT refer to any other message in the mailbox or any
subsequent mailbox with the same name forever.


[2] Main Cause Of This UID Error.
This error can be caused by discrepancies among the UID of messages on IMAP Server and IMAP Client side.
In my case IMAP Server was at fault.

[3] Details Of My IMAP Server System.
Whenever a command is received on IMAP Server for
- Message Delete
- Message state change, i.e making it UNREAD or READ
- etc..
it updates a separate remote Message Storage and Indexing Server.

Also whenever a NOOP command is received the
* EXPUNGE
* EXISTS
* RECENT
information which is required to be send in response to NOOP command, is prepared using this remote Message Storage and Indexing Server.

In IMAP Server, some local data structures are also maintained for satisfying various IMAP commands.
After updating local data structures, the separate remotely maintained Message Storage and Indexing Server is updated in background.
But the response of a command is send to IMAP Client after updating local data structures while Message Storage and Indexing Server gets updated in background.
This way of maintaining all the message information using local and remote data structures was not a problem before I encountered this UID Error.

[4] How The Error Was Traced?
I SELECTed the "Trash" Folder in Outlook and deleted the latest or most recent message from the Folder.
I logged request-response communication which was happening between IMAPServer and IMAPClient.

< means from IMAPClient(Outlook) fired command to IMAPServer.
> means IMAPServer send response of a command to IMAPClient(Outlook).

IMAP Server received following 5 command from Outlook one after another.

2014-05-20 12:16:24.174617500 29397 < 1kaf SELECT "Trash"
2014-05-20 12:16:24.214836500 29397 > * FLAGS (\Draft \Answered \Flagged \Deleted \Seen \Recent)
2014-05-20 12:16:24.214837500 29397 > * OK [PERMANENTFLAGS (\Draft \Answered \Flagged \Deleted \Seen)] Limited
2014-05-20 12:16:24.214838500 29397 > * 147 EXISTS
2014-05-20 12:16:24.214839500 29397 > * 5 RECENT
2014-05-20 12:16:24.214839500 29397 > * OK [UIDVALIDITY 1377145668] Ok
2014-05-20 12:16:24.214854500 29397 > 1kaf OK [READ-WRITE] Ok

2014-05-20 12:16:24.441563500 29397 < b3dq FETCH 147 (UID)
2014-05-20 12:16:24.441578500 29397 > * 147 FETCH (UID 3193)
2014-05-20 12:16:24.441579500 29397 > b3dq OK FETCH completed.

2014-05-20 12:17:50.343603500 29397 < zuvi UID STORE 3170 +FLAGS (\Deleted \Seen)
2014-05-20 12:17:50.504073500 29397 > * 141 FETCH (FLAGS (\Deleted \Seen) UID 3170)
2014-05-20 12:17:50.504075500 29397 > * 141 EXPUNGE
2014-05-20 12:17:50.504075500 29397 > * 146 EXISTS
2014-05-20 12:17:50.504076500 29397 > zuvi OK STORE completed.

2014-05-20 12:17:50.579307500 29397 < l1md NOOP
2014-05-20 12:17:50.623917500 29397 > * 147 EXISTS
2014-05-20 12:17:50.623918500 29397 > * 5 RECENT
2014-05-20 12:17:50.623918500 29397 > * 141 FETCH (FLAGS (\Seen))
2014-05-20 12:17:50.623919500 29397 > l1md OK NOOP completed

2014-05-20 12:17:50.799548500 29397 < bgl4 FETCH 147 (UID)
2014-05-20 12:17:50.799550500 29397 > * 147 FETCH (UID 3193)
2014-05-20 12:17:50.799576500 29397 > bgl4 OK FETCH completed.

Let's analyse these 5 command:
[a]
2014-05-20 12:16:24.174617500 29397 < 1kaf SELECT "Trash"
2014-05-20 12:16:24.214838500 29397 > * 147 EXISTS
< IMAPClient selected Folder "Trash".
> IMAPServer said the folder has 147 messages in it.

[b]
2014-05-20 12:16:24.441563500 29397 < b3dq FETCH 147 (UID)
2014-05-20 12:16:24.441578500 29397 > * 147 FETCH (UID 3193)
< IMAPClient tried to fetch UID of Message whose sequence number is 147.
> IMAPServer said UID of Message with sequence number 147 is 3193.

[c]
2014-05-20 12:17:50.343603500 29397 < zuvi UID STORE 3170 +FLAGS (\Deleted \Seen)
2014-05-20 12:17:50.504073500 29397 > * 141 FETCH (FLAGS (\Deleted \Seen) UID 3170)
2014-05-20 12:17:50.504075500 29397 > * 141 EXPUNGE
2014-05-20 12:17:50.504075500 29397 > * 146 EXISTS
< IMAPClient send a command "STORE" to delete a message whose UID is 3170.
> IMAPServer successfully deleted the message and told the IMAPClient that now there are 146 mails in the Trash Folder.

[d]
2014-05-20 12:17:50.579307500 29397 < l1md NOOP
2014-05-20 12:17:50.623917500 29397 > * 147 EXISTS
2014-05-20 12:17:50.623918500 29397 > * 5 RECENT
2014-05-20 12:17:50.623918500 29397 > * 141 FETCH (FLAGS (\Seen))
< IMAPClient send a NOOP command.
> IMAPServer told IMAPClient that there are 147 messages and the flags of message number 141 has changed.

[e]
2014-05-20 12:17:50.799548500 29397 < bgl4 FETCH 147 (UID)
2014-05-20 12:17:50.799550500 29397 > * 147 FETCH (UID 3193)
< IMAPClient tried to fetch the UID of message whose sequence number is 147.
> IMAPServer told IMAPClient that UID of message with sequence number 147 is 3193.

In between these 5 commands no new mails were delivered to "Trash Folder".
In third command[c] after deleting message with UID 3170 when the IMAPServer told that there EXISTS 146 messages in Trash Folder then, in the response of next NOOP command[d] IMAPServer should have told that there EXISTS 146 messages.
But IMAPServer replied that there EXISTS 147 messages, as can be seen in the response of commmand[d].
So IMAPClient might have thought that 1 new message has been arrived in the mailbox.
Therefore in the next command[e] IMAPClient tried to fetch the UID of new message and IMAPServer replied with UID of 3193.
Now UID 3193 was previously send by IMAPServer as can be seen in the response of command[b].
And as per IMAP standard the UID of new messages should increase and should not have been be used previously.

[5] Why I Encountered This UID Error?
I encountered this UID error due to some delay or latency in updating the remote Message Storags and Indexing Server.
Time difference between STORE command[c] response send from IMAPServer and the next NOOP command[d] received on IMAPServer was 75231000 nsec [579307500 - 504076500].
In such a small time frame of 75231000 nsec the Message Storage and Indexing Server was not updated in background.
The message with UID 3170 was deleted from local data structures and corresponding informations was posted to remote Message Storage and Indexing Server.
Before the Message Storage and Indexing Server could get updated, Outlook fired NOOP. And as NOOP response is prepared using Message Storage and Indexing Server in my IMAP Server System, the response included the deleted message with UID 3170.

[6] What Exactly Was The Problem?
There was no problem in IMAPServer with respect to assigning new UID to new messages.
The real problem happened due to very small time gap between successive commands received on iMAPServer.

Also the problem was related to synchronization of local and remote data structures on IMAPServer side.
This error does not occurs frequently because exactly when NOOP will be fired from Outlook is not predictable after a message is deleted.

[7] How To Reproduce This Problem?
This UID Error can occur in any Folder.

If IMAP Server System uses some local caches and remote storage for message data then this error might pop up due to delay as explained above.
Send some 50 test mails to an account. Now keep deleting them one by one at a time gap of 2 sec.
In my case Outlook fires NOOP at an interval of 60 seconds.


[8] Some Quick Resolutions w.r.t This Error For IMAPClients.
http://support.microsoft.com/kb/294779

Friday, November 22, 2013

Effort estimation for converting one character string to another.


//-------------------------------------------------------------------------
/*
Problem Statement:
-------------------
Given two strings string_x and string_y, find the effort required to convert string_x into string_y.

Definition of Effort Required : Number of characters which needs to be ADDED or DELETED from 
string_x inorder to convert string_x into string_y.
*/
//-------------------------------------------------------------------------


//-------------------------------------------------------------------------
//----- file: stringconversioneffort.c ------------------------------------
//-------------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//-------------------------------------------------------------------------
/*
//Function: 
int find_effort(char *string_x, char *string_y, int *char_to_be_added, int *char_to_be_deleted)

//Parameters: 
[in]string_x : source string to be converted
[in]string_y : destination string to which source string needs to be converted
[out]char_to_be_added : number of characters which needs to be added in source string.
[out]char_to_be_deleted : number of characters which needs to be deleted in source string.

//Return-Value:
total effort required
*/
//-------------------------------------------------------------------------
int find_effort(char *string_x, char *string_y, int *char_to_be_added, int *char_to_be_deleted)
{
        int i, j;

        int length_x = strlen(string_x);
        int length_y = strlen(string_y);

        int total_effort = -1;

        if( (length_x == 0) && (length_y != 0) )
        {
                (*char_to_be_added) = length_y;
                (*char_to_be_deleted) = 0;
                total_effort = (*char_to_be_added) + (*char_to_be_deleted);

                return total_effort;
        }
        else if( (length_x != 0) && (length_y == 0) )
        {
                (*char_to_be_added) = 0;
                (*char_to_be_deleted) = length_x;
                total_effort = (*char_to_be_added) + (*char_to_be_deleted);

                return total_effort;
        }
        else if( (length_x == 0) && (length_y == 0) )
        {
                (*char_to_be_added) = 0;
                (*char_to_be_deleted) = 0;
                total_effort = (*char_to_be_added) + (*char_to_be_deleted);

                return total_effort;
        }

        int **c = NULL;
        c = (int**) malloc ((length_x + 1) * sizeof(int*));
        for(i = 0; i <= length_x; ++i)
        {
                c[i] = (int*) malloc ((length_y + 1) * sizeof(int));
                memset(c[i], 0, (length_y + 1));
        }

        for(i = 1; i <= length_x; ++i)
        {
                for(j = 1; j <= length_y; ++j)
                {
                        if(string_x[i-1] == string_y[j-1])
                        {
                                c[i][j] = c[i-1][j-1] + 1;
                        }
                        else if(c[i-1][j] >= c[i][j-1])
                        {
                                c[i][j] = c[i-1][j];
                        }
                        else
                        {
                                c[i][j] = c[i][j-1];
                        }
                }
        }

        for(i = 0; i <= length_x; ++i)
        {
                free(c[i]);
        }
        free(c);

        (*char_to_be_added) = length_y - c[length_x][length_y];
        (*char_to_be_deleted) = length_x - c[length_x][length_y];
        total_effort = (*char_to_be_added) + (*char_to_be_deleted);

        return total_effort;
}


void print_result(char *string_x, char *string_y, int total_effort, int char_to_be_added, int char_to_be_deleted)
{
        printf("Effort Required to convert \n\"%s\"   into\n\"%s\"\ntotal_effort = %d\ncharacters to be added = %d\ncharacters to be deleted = %d\n", string_x, string_y, total_effort, char_to_be_added, char_to_be_deleted);
}

int main(int argc, char *argv[])
{
        if(argc != 3)
        {
                printf("ERROR\nbinary USAGE: [binary_path] [string_x] [string_y]\n");
                return 0;
        }

        char string_x[1024];
        char string_y[1024];

        int total_effort = 0;
        int char_to_be_added = 0;
        int char_to_be_deleted = 0;

        strcpy(string_x, argv[1]);
        strcpy(string_y, argv[2]);

        total_effort = find_effort(string_x, string_y, &char_to_be_added, &char_to_be_deleted);
        print_result(string_x, string_y, total_effort, char_to_be_added, char_to_be_deleted);

        return 0;
}
//-------------------------------------------------------------------------
//----- file: stringconversioneffort.c ------------------------------------
//-------------------------------------------------------------------------


//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
[stringconversioneffort]$ gcc -o sce stringconversioneffort.c
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------


//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//Outputs:
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce abcd abcde
Effort Required to convert
"abcd"   into
"abcde"
total_effort = 1
characters to be added = 1
characters to be deleted = 0
//-------------------------------------------------------------------------

//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce abcde abc
Effort Required to convert
"abcde"   into
"abc"
total_effort = 2
characters to be added = 0
characters to be deleted = 2
//-------------------------------------------------------------------------

//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce a1b2c3 ac
Effort Required to convert
"a1b2c3"   into
"ac"
total_effort = 4
characters to be added = 0
characters to be deleted = 4
//-------------------------------------------------------------------------

//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce agd 4e
Effort Required to convert
"agd"   into
"4e"
total_effort = 5
characters to be added = 2
characters to be deleted = 3
//-------------------------------------------------------------------------


//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//Logic used:
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
Concept of Longest Common Subsequence [LCS] is used to solve the problem.
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

The value c[length_x][length_y] in above function stores length of LCS
of string_x and string_y. This LCS length helps in finding the effort required.
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------

Friday, April 19, 2013

Android App for Computer Science and Engineering exams.

  • Check out this simple App which will helps you remain in touch with concepts from Computer Science and Engineering. 
  • Concepts from following subjects are included in this App :
  • Maths
  • Digital Logic
  • Computer Architecture and Organization
  • Database Systems
  • Operating Systems
  • Compilers
  • Computer Networks
  • Software Engineering
  • Data Structures and Algorithms
Alternatively, you can play with this App by simply solving "match the columns".


Minimum requirement :
  • Firmware\ Android Version 2.1 or higher.

How to Play :
  • As in "match the columns", there are 2 columns. Left column for Questions and right column for Answers as shown below :


  • You simply try to match each Question with its corresponding Answer.Trick is to match the background colors. 
  • That means, the background color of Question should match the background color of its corresponding Answer. 
  • You can change the background color of Answers by simply clicking on them.
       
For example consider this "match the column" on Time Complexity :
  • Question : Counting Sort
  • Correct Answer : O(n)
  • Question : Balanced Binary Search Tree
  • Correct Answer : O(log(n))
  • Question : Selection Sort
  • Correct Answer : O(N*N)
  • Question : Heap Sort 
  • Correct Answer : O(N*log(N))

Please see below pictorial explanation of what does it means by matching the background colors:

Correctly matched the column


Incorrectly matched the column


App Heading :
  • While using the App you will notice following heading : 
  •  G-YYYY : means this SET was asked in Graduate Aptitude Test In Engineering [Computer Science and Engineering] Year YYYY.

 
Feedback, Suggestions and Contributions
  • Please use this email address for communication [ csexapp@yahoo.com ]
  • Feedback, suggestions and corrections are most welcomed. 
  • Also, you can contribute your SETS for other to download. Send four Questions and their corresponding Answers @ the mentioned email address.
  • Contributors page :  Appreciating the contributors.


History :  
  • Friday, April 19, 2013
    • Released  Application Version 1.0
    • After installation,  initially the App will contain 10 SETS in its database.
    • More SETS can be downloaded as and when they are published.
  • Monday, April 29, 2013
    • Released  New SETS [Question 11 to 20]
    • Please use "Download SETS..." facility in the App to directly add New Questions to existing database of Questions.
  • Tuesday, May 07, 2013
    • Released  New SETS [Question 21 to 30]
    • Please use "Download SETS..." facility in the App to directly add New Questions to existing database of Questions.
  • Monday, June 03, 2013
    • Released  New SETS [Question 31 to 40]
    • Please use "Download SETS..." facility in the App to directly add New Questions to existing database of Questions.
  • Thursday, October 24, 2013
    • App Download Count reached 1K+ mark.
  • Tuesday, November 07, 2017
    • Released App Version 2.0


Direct Download  Link for .apk File:
CSExApp.apk File


Also Available on SlideME



Thursday, April 18, 2013

CSExApp Contributors


Appreciating the following Contributors :


  1. Shankar / Mumbai / Set 8
  2. Siddhesh / Mumbai / Testing the App

Friday, March 15, 2013

Utility function for generating required number digits after decimal point.


//
#include <stdio.h>
#include <string.h>
//

/**
-------------------------------------------------------------------
Problem :
-------------------------------------------------------------------
For a given fraction [x / y] finding "n" number of digits after the 
decimal point. 

"x" and "y" are positive integers

The value after the decimal will not be rounded but will be 
truncated to "n" digits
-------------------------------------------------------------------
 
-------------------------------------------------------------------
Example :
-------------------------------------------------------------------
[1]
x = 22
y = 7
x / y = 3.1428571428571428571428571428571...
Required DigitsAfterDecimalPoint = 20
BufferPrecision = "14285714285714285714"
 
[2]
x = 7
y = 22
x / y = 0.3181818181818181818181818181818...
Required DigitsAfterDecimalPoint = 20
BufferPrecision = "31818181818181818181"

[3]
x = 7
y = 7
x / y = 1.00000000000000000000000000000000...
Required DigitsAfterDecimalPoint = 20
BufferPrecision = "00000000000000000000"
-------------------------------------------------------------------

-------------------------------------------------------------------
Function Description :
-------------------------------------------------------------------
void GetRequiredPrecision(int _x, int _y, int _iDigitsAfterDecimalPoint, char *_pcBufferPrecision);
[in]_x : Dividend
[in]_y : Divisor
[in]_iDigitsAfterDecimalPoint : The number of digits which are required after the decimal point
[out]_pcBufferPrecision : Pointer to buffer which will hold the result.
_pcBufferPrecision should point to a buffer of length (_iDigitsAfterDecimalPoint + 1)
-------------------------------------------------------------------
/**/
void GetRequiredPrecision(int _x, int _y, int _iDigitsAfterDecimalPoint, char *_pcBufferPrecision)
{
 if((_x % _y) == 0)
 {
  memset(_pcBufferPrecision, '0', _iDigitsAfterDecimalPoint);
  _pcBufferPrecision[_iDigitsAfterDecimalPoint] = 0;
  return;
 }

 int table[11];
 table[0] = _y * 0;
 table[1] = _y * 1;
 table[2] = _y * 2;
 table[3] = _y * 3;
 table[4] = _y * 4;
 table[5] = _y * 5;
 table[6] = _y * 6;
 table[7] = _y * 7;
 table[8] = _y * 8;
 table[9] = _y * 9;
 table[10] = _y * 10;

 int iCount = 0;
 int iReminder = _x % _y;  
 int iNewReminder = 0;

 while(_iDigitsAfterDecimalPoint-- > 0)
 {
  iNewReminder = (iReminder << 3) + (iReminder << 1);

  if((iNewReminder >= table[0]) && (iNewReminder <= (table[1]-1)))
  {
   _pcBufferPrecision[iCount] = '0';
   iReminder = iNewReminder;
  }   
  else if((iNewReminder >= table[1]) && (iNewReminder <= (table[2]-1)))
  {
   _pcBufferPrecision[iCount] = '1';
   iReminder = iNewReminder - table[1];
  }
  else if((iNewReminder >= table[2]) && (iNewReminder <= (table[3]-1)))
  {
   _pcBufferPrecision[iCount] = '2';
   iReminder = iNewReminder - table[2];
  }
  else if((iNewReminder >= table[3]) && (iNewReminder <= (table[4]-1)))
  {
   _pcBufferPrecision[iCount] = '3';
   iReminder = iNewReminder - table[3];
  }
  else if((iNewReminder >= table[4]) && (iNewReminder <= (table[5]-1)))
  {
   _pcBufferPrecision[iCount] = '4';
   iReminder = iNewReminder - table[4];
  }
  else if((iNewReminder >= table[5]) && (iNewReminder <= (table[6]-1)))
  {
   _pcBufferPrecision[iCount] = '5';
   iReminder = iNewReminder - table[5];
  }
  else if((iNewReminder >= table[6]) && (iNewReminder <= (table[7]-1)))
  {
   _pcBufferPrecision[iCount] = '6';
   iReminder = iNewReminder - table[6];
  }
  else if((iNewReminder >= table[7]) && (iNewReminder <= (table[8]-1)))
  {
   _pcBufferPrecision[iCount] = '7';
   iReminder = iNewReminder - table[7];
  }
  else if((iNewReminder >= table[8]) && (iNewReminder <= (table[9]-1)))
  {
   _pcBufferPrecision[iCount] = '8';
   iReminder = iNewReminder - table[8];
  }
  else if((iNewReminder >= table[9]) && (iNewReminder <= (table[10]-1)))
  {
   _pcBufferPrecision[iCount] = '9';
   iReminder = iNewReminder - table[9];
  }
  ++iCount;   
 }

 _pcBufferPrecision[iCount] = 0;
}

int main(int argc, char*argv[])
{
 int x = 22;
 int y = 7;
 char BufferPrecision[21];
 int iDigitsAfterDecimalPoint = 20;
 GetRequiredPrecision(x, y, iDigitsAfterDecimalPoint, BufferPrecision);
 printf("after dividing %d by %d, the %d digits after decimal point are\n%s", x, y, iDigitsAfterDecimalPoint, BufferPrecision);
 return 0;
}

Tuesday, September 18, 2012

Smallest Repeating Prefix in a non empty String.


Below is the implementation of method
int find_smallest_repeating_prefix_length(string &s);


/**
-------------------------------------------------------------------
Problem :
-------------------------------------------------------------------
Finding Smallest Repeating Prefix "p" in a non-empty string "s". 
Length of "s" = slen.
Length of "p" = plen.

Following equation should be satisfied
slen = plen * k, where k > 0. 
-------------------------------------------------------------------

-------------------------------------------------------------------
Constraints :
-------------------------------------------------------------------
time  : O(n)
space : O(n)
-------------------------------------------------------------------

-------------------------------------------------------------------
Example :
-------------------------------------------------------------------
[1]
s = ababab
slen = 6
p = ab
plen = 2
k = 3


[2]
s = abh
slen = 3
p = abh
plen = 3
k = 1
-------------------------------------------------------------------
/**/

#include <iostream>
#include <conio.h> 

#include <vector>
#include <string>

using namespace std;


void kmpPreprocess( string &str,  int slen, vector &barray)
{
    int i = 0;
    int j = -1;
    barray[i] = j;
    while(i < slen)
    {
        while( (j >= 0) && (str[i] != str[j]) )
        {
            j = barray[j];
        }
        ++i;
        ++j;
        barray[i] = j;
    }
}

void print_barray( string &s, vector &barray)
{
    int i;
    int slen = s.length();

    cout << endl;
    cout << "index  :  ";
    for(i = 0; i < (slen+1); ++i)
    {
    cout << i << " ";
    }
    cout << endl;

    cout << "string :    ";
    for(i = 0; i < slen; ++i)
    {
    cout << s[i] << " ";
    }
    cout << endl;
    cout << "barray : ";
    for(i = 0; i < (slen+1); ++i)
    {
    cout << barray[i] << " ";
    }
    cout << endl;
}


int using_barray_method_1(string &s, vector &barray)
{        
    string srp_curr = s;    
    int srp_length_curr;
    int srp_length_prev;

    srp_length_curr = srp_curr.length();
    srp_length_prev = srp_length_curr;
    
    while( (srp_length_curr = barray[srp_length_curr]) > 0)
    {    
        if( (srp_length_prev % srp_length_curr) == 0)
        {     
            int k = srp_length_prev / srp_length_curr;

            string chain_of_k_parts;
            chain_of_k_parts.clear();
            while(k--)
            {
                chain_of_k_parts.append(srp_curr.c_str(), srp_length_curr); 
            }

            if(srp_curr.compare(chain_of_k_parts) == 0)
            {
                srp_length_prev = srp_length_curr;                         
                
                srp_curr = srp_curr.substr(0, srp_length_prev);
            }            
        }
    }

    return srp_length_prev;
}


int using_barray_method_2(string &s, vector &barray)
{
    int slen = s.length();

    int srp_length = slen;

    if( (slen % (slen - barray[slen])) == 0 ) 
    {
        srp_length = slen - barray[slen];        
    }

    return srp_length;
}


int find_smallest_repeating_prefix_length(string &s) 
{
    int slen = s.length();

    if(slen == 0)
    {
        return -1;
    }

    vector barray(slen+1);
    
    kmpPreprocess(s, slen, barray);    
    print_barray(s, barray);

        
    int srp_length = -1;

    srp_length = using_barray_method_1(s, barray);
    srp_length = using_barray_method_2(s, barray);
                
    return srp_length;
}


bool check(int slen, int plen, int k)
{
    if( slen == (plen * k) )
    {
        return true;
    }
    else
    {
        return false;
    }
}


void process_string(string &s)
{
    int plen = find_smallest_repeating_prefix_length(s);

    if(plen == -1)
    {
        cout << "error in input string" << endl;
        getch();
        return;
    }

    int i;
    int slen = s.length();    

    int k = slen / plen;    

    if(check(slen, plen, k) == true)
    {
        cout << "[successfully satisfied]  slen == (plen * k)" << endl;
    }
    else
    {
        cout << "[fail to satisfy]  slen != (plen * k)" << endl;
        getch();
        return;
    }

    cout << "s = " << s << endl;
    cout << "slen = " << slen << endl;

    cout << "p = ";
    for(i = 0; i < plen; ++i)
    {
        cout << s[i]; 
    }
    cout << endl;

    cout << "plen = " << plen << endl;    
    cout << "k = " << k << endl;    
}


void main()
{
    string s;
    
    s = "ababab";
    process_string(s);    
    cout << endl << endl;

    s = "abh";
    process_string(s);
    cout << endl << endl;    

    getch();
}


/**
-------------------------------------------------------------------
Output :
-------------------------------------------------------------------

index  :  0 1 2 3 4 5 6
string :    a b a b a b
barray : -1 0 0 1 2 3 4
[successfully satisfied]  slen == (plen * k)
s = ababab
slen = 6
p = ab
plen = 2
k = 3



index  :  0 1 2 3
string :    a b h
barray : -1 0 0 0
[successfully satisfied]  slen == (plen * k)
s = abh
slen = 3
p = abh
plen = 3
k = 1
-------------------------------------------------------------------
/**/

These methods works on following logic :
"barray" stores lengths of various Borders of the string.
Border "b" of a string "s" is a proper prefix which is also the proper suffix of a string "s".
Therefore we can see a border of a string "s" as a prefix "p" which is repeated atleast two times in that string "s".

For more information on Border and how barray is created, please refer Knuth-Morris-Pratt Algorithm.
KMP Algorithm

-----------------------------------------------------------------------------------------------------
Method 1: (using_barray_method_1)
reference : Utilization of KMP Algorithm
-----------------------------------------------------------------------------------------------------
We recursively try to find smallest repeating prefix inside an existing\current smallest repeating prefix.
We start by considering the original string "s" itself as the smallest repeating prefix.
[1] The next smallest prefix "x" (and not the smallest 'REPEATING' prefix) which is repeated in the string "s" can be found
using the "barray" [refer Knuth-Morris-Pratt Algorithm].
[2] Now we check whether this smallest prefix "x" is the smallest repeating prefix in the string "s".
This is done by
[a] checking whether the (length of "x") fully divides (length of "s")
i.e [((strlen(s) % strlen(x)) == 0]
[b] if "x" fully divides "s" then let k = strlen(s) / strlen(x);
[3] Now we try to confirm whether repeating string "x", 'k' number of time give us string "s".
i.e, if string "xxxx...[k times]" == string "s", then we can say string "x" can be the smallest repeating prefix which is repeated 'k' number of times in string "s".
[4] Now if there is a smallest repeating prefix "y" in "x" then it will be our new smallest repeating prefix in "s".
This is true because length of "y" will be smaller then "x".
So we make "s" = "x" and repeat the above steps to find smallest repeating prefix in "x".
-----------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------
Method 2: (using_barray_method_2)
-----------------------------------------------------------------------------------------------------
There is one more direct and fast method to find smallest repeating prefix after computing "barray" of string "s".
Came to know about this direct method when discussing this problem on one of the forums Smallest Repeating Prefix
Dateng LIN suggested this method.
-----------------------------------------------------------------------------------------------------

Monday, March 12, 2012

Substring Matching Algorithm : BMH

Here is a very good reference link and code for an algorithm to find all occurrences of a pattern(sub-string) in a given text.


/**
---------------------------------------------------------------------------
problem :
----------
- find all occurrences of a provided pattern(sub-string) in a given text. 
---------------------------------------------------------------------------
input :
----------
- unsigned char* text : the text string to be searched.
- int n : length of text string.
- unsigned char* pattern : the pattern(sub-string) to be searched in the text.        
- int m : length of pattern.
---------------------------------------------------------------------------
output :
----------
- all position within text from where the pattern can be found.
---------------------------------------------------------------------------
constraints :
-------------
- for each element or letter 't' of text : 0 <= t <= 254.
- for each element or letter 'p' of pattern : 0 <= p <= 254.
- text of pattern cannot contain any letter or element with value 255. 
---------------------------------------------------------------------------
/**/
 
//-------------------------------------------------------------------------
#include <iostream>
#include <conio.h>

#define MAX_ALPHABET_SIZE 256
#define CHARACTER_NOT_IN_THE_TEXT 255

void boyer_moore_horspool(unsigned char* text, int n, unsigned char* pattern, int m)
{
 int d[MAX_ALPHABET_SIZE], i, j, k, lim;

 // Preprocessing
 for(k = 0; k < MAX_ALPHABET_SIZE; ++k) 
 {
  d[k] = m; 
 }

 for(k = 0; k < m; ++k )
 {
  d[pattern[k]] = m - k;
 }

 // To avoid having code
 pattern[m] = CHARACTER_NOT_IN_THE_TEXT; 

 lim = n - m;

 // Searching
 for(k = 0; k <= lim; k += d[text[k + m]]) 
 {
  i = k;
  j = 0;
  while(text[i] == pattern[j])
  {
   ++i;
   ++j;
  }

  if(j == m)
  {
   cout << "pattern found in text at position : " << k << endl;
   if( (k + (m<<1)) >= n)
   {
    break;
   }
  }
 }
}
//-------------------------------------------------------------------------

/**
---------------------------------------------------------------------------
solution :
------------
- complexity : 
average case = O(n) , O(length of text, n).
worst case = O(nm), O([length of text:n]*[length of pattern:m]). 
---------------------------------------------------------------------------
/**/


void main()
{
//positions.....012345678901234567890
 char text[] = "ZZACCABCDBDABCDABCDQQ";
 char pattern[] = "ABCD";
 boyer_moore_horspool(text, strlen(text), pattern, strlen(pattern));

 getch();
}

/**
---------------------------------------------------------------------------
output :
------------
pattern found in text at position : 5
pattern found in text at position : 11
pattern found in text at position : 15
---------------------------------------------------------------------------
/**/

Have used the above code from the following link :
Boyer-Moore-Horspool Algorithm

Friday, March 9, 2012

Substring Matching Algorithm : KMP

Here is the link to a good algorithm for finding all occurrences
of a sub-string(or pattern) in a given text(or string).

Knuth-Morris-Pratt Algorithm.

Monday, February 20, 2012

finding duplicate entry in an array.


/**
---------------------------------------------------------------------------
problem : 
----------
- find first duplicate value in the given array without modifying the array.
---------------------------------------------------------------------------
input : 
----------
- int *a : array of integers
- int l : number of elements in a
- int m : loose upper bound for value of an element of array a.  
        : 0 <= value_of_element_of_a < m
- relation between l and m : l > m
---------------------------------------------------------------------------
output : 
----------
- first duplicate value occuring in the array.
---------------------------------------------------------------------------
constraints : 
------------- 
- space requirement should be O(1)
- after the function returns the array should be same as original.
---------------------------------------------------------------------------
/**/

//-------------------------------------------------------------------------
int find_firstduplicate(int *a, int l, int m)
{
 int original = 0;
 int index = 0;
 int is_index_already_used = 0;
 const int adjustment_for_zero_value = 1;
 int duplicate = -1;

 for(index = 0; index <= m; ++index)
 {
  is_index_already_used = 0;
  original = a[index];

  if(a[index] < 0)
  {
   //means there is already an element with value = index
   is_index_already_used = 1;

   //reversing the step of procedure to handle zero value
   a[index] += adjustment_for_zero_value;

   //original value of the element
   original = abs(a[index]);
  }
  
  if(a[original] >= 0)
  {
   //negating
   a[original] = (- a[original]);
   
   //substracting 1, to handle zero value, since (minus ZERO) = (ZERO) 
   a[original] = a[original] - adjustment_for_zero_value;

   //restoring the fact that index is used.
   a[index] -= is_index_already_used;   
  }
  else
  {
   //duplicate found.
   duplicate = original;
   break;   
  }
 }

 //readjusting the values of array so that they resemble the original.
 for(index = 0; index <= m; ++index)
 {
  if(a[index] < 0)
  {   
   a[index] += adjustment_for_zero_value;
   a[index] = - a[index];
  }
 } 

 return duplicate;
}
//-------------------------------------------------------------------------

/**
---------------------------------------------------------------------------
solution :
- hint : use the value of element as an index 'i' and negate the value at  
index i.
- complexity : O(m) 
---------------------------------------------------------------------------
/**/

void main()
{
 int m = 5;
 int a[] = {1, 0, 3, 0, 4, 5};
 int l = sizeof(a) / sizeof(a[0]);
 int duplicate = find_firstduplicate(a, l, m);
 if(duplicate != -1)
 {
  cout << "first duplicate = " << duplicate << endl;
 }
 else
 {
  cout << "duplicate does not exist." << endl;
 }
 getch();
}

/**
output :
--------
first duplicate = 0
/**/

Friday, October 14, 2011

70 Years, programmed the world.


"C is quirky, flawed, and an enormous success."
-Dennis MacAlistair Ritchie (September 9, 1941 – October 8, 2011)


He developed see programming language, though which I was saw possibilities through programming.


#include <stdio.h>
int main(int argc, char *argv[])
{
printf("Hello Heaven\n");
return 0;
}


Sir Dennis's World...

Tuesday, July 5, 2011

Top scorer.

Original Newspaper Article.










Publication:The Economic Times Delhi; Date: Jul 4, 2011; Section: Corporate; Page: 5


TechGig to Launch Season 2 of Indian Programming League

OUR BUREAU NEW DELHI

Technology community site TechGig.com, developed by TimesJobs, will launch the second season of the Great Indian Programming League (GIPL), an innovative method of hiring talented software developers from across the country. TechGig created GIPL to connect with coding buffs who normally work behind the scenes and provide a recruitment platform for companies looking for quality talent.

TechGig.com product head Amit Gupta said: “The IPL is a great way of benchmarking one’s coding skills with some of the best software developers in India. We are now launching Season 2 of the IPL, so there is a lot more action in store.” At GIPL, recruiters looking for high quality technical talent get an objective benchmark to automatically measure the competence of people.

The contest attracts passive candidates to participate even if they aren’t looking for a job. Moreover, the scores are easy to measure, making it easy to find the best people at the top. This renders the contest a great platform to sort and hire. During its first season last month, GIPL got more than 11,000 entries from over 2,700 programmers from across India.

The second contest is coming up due to popular demand from techies and tech firms. In the last season, a large number of coders, programmers and software developers from Delhi NCR, Pune, Bangalore, Hyderabad and Chennai battled it out for iPods, daily movie tickets but more importantly recognition among peers.

Omnitech Infosolutions COO and head of global operations Anurag Shah said: “The Great Indian Programming League is an aspiring initiative taken by techgig.com to not just recognize the talented coders but also provide them a platform to achieve global recognition, which will surely motivate them to feature their best practices in the industry.”

Coding as a field is indeed as promising as other professional fields which require technical as well as domain expertise. Coders play a vital role in the software development and act as a bloodline of the projects. The initiative would bring required awareness and change in perception to help coding attain the deserving limelight, Shah added.

The contest involves writing actual code across five to seven different programming languages, including C #, Java, C and C++, to solve a problem live. The software automatically compiles the code to assess its quality and comprehensiveness in solving the problem.

The second season expects to be more promising going by the reaction of programmers who came from across the country in the first season, just for their love for coding. “Just coding, am mad on coding,” said TCS software developer Vishnu Priya Subramanian while Sameer Namdeo said his motivation was a passion for coding, and chance to evaluate him among peers.

Dotsquares

team lead Deepak Tanwar said GIPL was all about personal enhancement, profile upgrade and opportunity to compete with programmers of different languages.

Users complimented Tech-Gig on the range and complexity of the problems set. Uniprose India product manager Vijendra Kumar pointed out the best part of the contest was that the code could not be seen by other programmers and online instant verification of code.

Winning for software developer Jagdesh from Infosys Technologies Limited was overwhelming while Mahindra Satyam Computer Services Limited project leader Amit Kantilal said: “I feel very proud that I have demonstrated my programming skills. I successfully completed the program to solve the sudoku puzzle which has been on my cards since quite some time.”




Monday, January 10, 2011

Finding Diameter of a Binary Tree.

Diameter Of A Binary Tree:

[1] calculate shortest paths between all possible pairs of nodes in the tree.

[2] the path which is longest among all the shortest paths found in step [1] is the Diameter of Tree.



Sample Binary Tree.




Method 1 (Using Recursive functions.)





Table to be used for reference with the code.


Source code


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


struct Node
{
    Node()
    {
        pLeft = NULL;
        pRight = NULL;
        cData = 0;
        iMaxLeftWeight = 0;
        iMaxRightWeight = 0;
        iMax = 0;
        iTotalWeight = 0;
    }

    Node *pLeft;
    Node *pRight;
    char cData;

    //max possbile length of left subtree
    int iMaxLeftWeight;

    //max possbile length of right subtree
    int iMaxRightWeight;

    //max possible length of path that can be obtained from
    //traversing either left or right subtree.
    int iMax;

    //iTotalWeight = iMaxLeftWeight + iMaxRightWeight;
    //used to determine center of whole tree.
    //node with max iTotalWeight will be center.
    int iTotalWeight;
};

//structure to store all Node::iTotalWeight of tree.
//MaxWeightNodes stores elements in desending order of iTotalWeight.
//So, its first element corresponds to center of tree.
//definition : MaxWeightNodes[INDEX] = DATA
//here INDEX = Node::iTotalWeight and DATA = pointer to Node itself.
multimap<int, Node*, greater<int> > MaxWeightNodes;

//instead of using map we can keep track of node with max
//iTotalWeight and afterwards this node can be considered as center



int GetMaxWeight(Node *pNode)
{
    if(pNode->pLeft)
        pNode->iMaxLeftWeight = 1 + GetMaxWeight(pNode->pLeft);

    if(pNode->pRight)
        pNode->iMaxRightWeight = 1 + GetMaxWeight(pNode->pRight);

    pNode->iTotalWeight = pNode->iMaxLeftWeight + pNode->iMaxRightWeight;

    MaxWeightNodes.insert(make_pair(pNode->iTotalWeight, pNode));

    pNode->iMax = max(pNode->iMaxLeftWeight, pNode->iMaxRightWeight);

    return pNode->iMax;
}


Node* Traverse(Node *pNode)
{
    Node *pTempNode = NULL;

    if( (pNode->iMaxLeftWeight == 0) && (pNode->iMaxRightWeight == 0) )
        return pNode;

    if(pNode->iMaxLeftWeight > pNode->iMaxRightWeight)
        pTempNode = pNode->pLeft;
    else
    if(pNode->iMaxLeftWeight < pNode->iMaxRightWeight)
        pTempNode = pNode->pRight;
    else
        pTempNode = pNode->pRight;
        //pTempNode = pNode->pLeft;(anything will do)

    return Traverse(pTempNode);
}


void FindEndPointsOfDiameter(Node *pNode, Node **ppLeftEndPoint, Node **ppRightEndPoint)
{
    if(pNode->pLeft)
        (*ppLeftEndPoint) = Traverse(pNode->pLeft);
    else
        (*ppLeftEndPoint) = pNode;

    if(pNode->pRight)
        (*ppRightEndPoint) = Traverse(pNode->pRight);
    else
        (*ppRightEndPoint) = pNode;

    return;
}

void main()
{
/**
Node *pRoot = NULL;

//fill the tree
//assign pRoot to root of tree
//now pRoot points to the root of tree.

//GetMaxWeight() function will traverse every node of tree and fill
//following members (iMaxLeftWeight iMaxRightWeight iTotalWeight iMax)
//of traversed nodes.
GetMaxWeight(pRoot);

//first element of map 'MaxWeightNodes' corresponds to center of tree.
Node *pCenter = MaxWeightNodes.begin()->second;

//finding length of diameter of tree
//diameter can be obtained from center of tree.
//diameter = iTotalWeight = (max length of left subtree + max length of Right subtree)
int iDiameterOfTree = pCenter->iTotalWeight;

//finding endpoints of diameter of tree
Node *pLeftEndPoint = NULL;
Node *pRightEndPoint = NULL;
FindEndPointsOfDiameter(pCenter, &pLeftEndPoint, &pRightEndPoint);

//in similar manner we can find diameter(and its endpoints) correspoding
//to other centers of tree. Other center can be found from map MaxWeightNodes
//by fetching starting elements having max iTotalWeight.
/**/


    Node a1, a2, a3, a4, a5, a6, a7, a8, a9;

    a1.pLeft = &a2;
    a1.pRight = &a3;
    a1.cData = 1;

    a2.pLeft = &a4;
    a2.pRight = &a5;
    a2.cData = 2;

    a3.pLeft = NULL;
    a3.pRight = NULL;
    a3.cData = 3;

    a4.pLeft = &a6;
    a4.pRight = &a7;
    a4.cData = 4;

    a5.pLeft = NULL;
    a5.pRight = &a8;
    a5.cData = 5;

    a6.pLeft = &a9;
    a6.pRight = NULL;
    a6.cData = 6;

    a7.pLeft = NULL;
    a7.pRight = NULL;
    a7.cData = 7;

    a8.pLeft = NULL;
    a8.pRight = NULL;
    a8.cData = 8;

    a9.pLeft = NULL;
    a9.pRight = NULL;
    a9.cData = 9;


    Node *pRoot = &a1;

    GetMaxWeight(pRoot);

    Node *pCenter = MaxWeightNodes.begin()->second;

    int iDiameterOfTree = pCenter->iTotalWeight;

    Node *pLeftEndPoint = NULL;
    Node *pRightEndPoint = NULL;
    FindEndPointsOfDiameter(pCenter, &pLeftEndPoint, &pRightEndPoint);

}



Tuesday, August 3, 2010

Common Pitfall : While using malloc instead of new.

Two mostly used things that help in allocating memory are malloc and new.

Sometimes knowledge of using malloc, for allocating memory in common and less complicated situations, can prove wrong in complicated situations.

Situation [1] (Complication Level 1):
int *pData = (int*)malloc(10 * sizeof(int));
Now to access integers at index from 0 to 9 simply use pData[1] or *(pData+2)...
Very simple!!!

Situation [2] (Complication Level 2):
struct ABC
{
int P1;
char P2;
};
ABC *pData = (ABC*)malloc(10 * sizeof(ABC));

Now to access integer P1 of say 4th struct ABC : pData[3].P1
Again Very simple!!!

Situation [3] (Complication Level 3):
struct ABC
{
int P1;
char P2;
};

struct PQR
{
int P1;
char P2;
ABC P3;
};
PQR *pData = (PQR*)malloc(10 * sizeof(PQR));

Now to access integer P1 of ABC which is inside of say 5th struct PQR : pData[4].P3.P1
Again Moderately simple!!!

In above 3 situations memory was allocated and then utilized according to the structure\ layout of structs.

Situation [4] (Complication Level 4):
struct XYZ
{
int P1;
char P2;
CList P3;
};
XYZ *pData = (XYZ*)malloc(10 * sizeof(XYZ));

Now try to insert elements in the list P3 of say 4th struct XYZ:
pData[3].P3.AddTail(2);
Complie Status OK.
Run Status CRASH!!!
Without reading further think a minute why the code did not worked even though memory was already allocated?

This happened because though memory was allocated for all the data members of list XYZ::P3 but those data members were not initialized with default values.

struct XYZ in above example is composite data type (a class or user defined data type) in which the default value initialization of its data-members is normally done in constructor of the class.

In a composite data type the data-members are created (here created means calling of their respective constructor) prior to the invocation of composite data type constructor itself. ("Refer how Object creation takes place")

So what will initialize the data-members along with the task of allocating the memory for members.
Answer : operator new

XYZ *pData = new XYZ[10];
Here 'new' invokes the constructor of both, the data members of struct XYZ and the struct XYZ itself. Inside the CList constructor, members can be initialized with default values.




Conclusion:
[1]Anyway, in C++ new is the preferred mechanism for memory allocation.
[2]Also try to minimize mixing of malloc and new.


Monday, July 19, 2010

Second technical article.

While working with functions, I found a common pattern. A pattern in which all the parameters constituting the parameter-list were bundled in a struct and that struct was passed as a parameter to the function. Therefore, gave a thought on this, in order to find what can be the pros and cons of this pattern. Outcome was the following article:


Description: An article highlighting advantage of using composite data-type for passing parameters to functions.
Parameter Passing :- by Train vs by Truck.

Wednesday, July 14, 2010

C\ C++ Pointer confusion.

Working with pointers by passing them here and there and not getting expected result!!!
Don't go here and there but go directly to :
Pointer Alises.

Tuesday, July 13, 2010

First technical article.

Check out my first technical article on codeproject.com.
Description: An article on creating a framework for command processing using Command Design Pattern.
Converting a class into a CommandHandler.

Hello World

Yes, most of the aspiring programmers starts their programming journey by displaying "Hello World". As simple as that. Today I created my blog and just want to say Hello World. Yes, you guessed right!. I also want to start hitting the keyboard...