Web Toolbar by Wibiya

Pages

Monday, April 25, 2011

Sort a stack in ascending order when standard stack operations(push, pop, peek and isEmpty) are given.

Solution #1: We can use another stack to do the sorting. Suppose s1 is the original stack and s2 is the other stack. The algorithm will look like this,

- Pop from s1(e1) and peek s2(e2).
- if e2 < e1, then push e1 on s2,
- if e2 > e1, then keep popping from s2 into s1 till the next element is less than e1 and then push e1 on s2.

Keep doing it till s1 is empty. Now, s2 will be sorted in ascending order! This algorithm will have a time complexity of O(N^2).

Saturday, April 23, 2011

Implement a queue using two stacks.

Solution #1: Suppose we have two stacks, s1 and s2. For enqueue operation we will simply push the data on s1. For dequeue, we will pop everything from s1 into s2 and will then pop from s2 and will again push everything back on s1.

Enqueue Operation:
- Push on s1

Dequeue Operation:
- Pop everything on s1 and push on s2
- Pop s2
- Pop everything on s2 and push again on s1

Now, the dequeue operation can be pretty time consuming when the stack is big. Also, two back to back dequeue operations will require needless moment of elements between two stacks. This can be optimized by letting elements stay in the s2 and en-queuing data to s1 and dequeuing from s2 till s2 becomes empty. So, essentially, we are reducing the number of stack transfers.

Enqueue Operation:
- Push on s1

Dequeue Operation:
- If s2 is not empty, pop from it
- If s2 is empty, pop everything on s1 and push in s2
- Pop s2

Tuesday, April 19, 2011

Given two numbers represented by linked lists with each node containing a single digit. Add them and return the list containing the resulting number.

Solution #1: Traverse both the lists adding their node's digit and storing the sum in the resulting list till one of the lists ends. Continue from the remaining list and add rest of its nodes to the resulting list. Here is the code,

Example:
list 1: 4 -> 5 -> 6
list 2: 7 -> 8 -> 9
result: 1 -> 4 -> 6 > 1

node* addLists(node* lptr1, node* lptr2)
{
    node* list = NULL;
    node* prev = NULL;
    node* remaining = NULL;
    int carry=0;
    int sum=0;

    while((lptr1 != NULL) && (lptr2!= NULL))
    {
        sum = 0;

        node* temp = (node*)malloc(sizeof(node));
        sum = lptr1->data + lptr2->data + carry;
        carry=0;

        if(sum >= 10)
            carry = 1;

        sum = sum%10;
        temp->data = sum;
        temp->next = NULL;

        if(list == NULL)
        {
            list = temp;
            prev = temp;
        }
        else
        {
            prev->next = temp;
        }

        prev = temp;
        
        lptr1 = lptr1->next;
        lptr2 = lptr2->next;
    }

    remaining = (lptr1 != NULL)?lptr1:lptr2;

    while(remaining != NULL)
    {
        node* temp = (node*)malloc(sizeof(node));
        temp->data = remaining->data + carry;
        carry = 0;
        temp->next = NULL;

        prev->next = temp;

        prev = temp;
        remaining = remaining->next;
    }

    return list;
}

In a linked list, delete a node with only a pointer given to that node.

Solution #1: Store the address of the next node in a temporary pointer. Copy the contents of the next node in the given node and delete the next node. Here is the code,

void deleteArbitNode(node* lptr)
{
    node* temp = lptr->next;


    lptr->data = lptr->next->data;
    lptr->next = lptr->next->next;

    free(temp);
}


Also note that this approach is not possible for deleting the last node.

In a linked list, find the nth element from the end.

Solution #1: An intuitive approach would be to do this problem recursively. Recursively travel till the last node and then get back till we reach the nth node from the end. Here is the code,

void nthElementRec(node* lptr, int n)
{
    static int index = 1;

    if(lptr->next == NULL)
        return;

    nthElementRec(lptr->next, n);
    index++;

    if(index == n)
        printf("%d\n", lptr->data);
}


Solution #2: Take two pointers, p1 and p2, and make them point to first and nth element from the beginning respectively. Now increment both the pointers till p2 reaches the end. At this point p1 will point to the nth element from the end. Here is the code,

void nthElement(node* lptr, int n)
{
    node* p1;
    node* p2;
    int i;

    p1 = p2 = lptr;

    for(i=0; i<n-1; i++)
        p2=p2->next;

    while(p2->next != NULL)
    {
        p1 = p1->next;
        p2 = p2->next;
    }

    printf("%d\n", p1->data);
}


Monday, April 18, 2011

Remove duplicates from a linked list.

Solution #1: If we are allowed to use extra space, iterate through the list storing each node's  data in a hash table. Now, if a node's data is already present in the hash table then it's a duplicate, so remove it.

Solution #2: Iterate over the list, checking all previous elements for duplication. If a duplicate is found, remove it. Here is the code,

void removeDup(node* lptr)
{
    node* curr = NULL;
    node* iter = NULL;
    node* prev = NULL;

    curr = lptr->next;
    iter = lptr;
    prev = lptr;

    while(curr != NULL)
    {
        while(iter != curr)
        {
            if(iter->data == curr->data)
            {
                prev->next = curr->next;
                free(curr);
                curr = prev;
                break;
            }
            iter = iter->next;
        }

        iter = lptr;
        prev = curr;
        curr = curr->next;
    }
}

Sunday, April 17, 2011

To check whether a string is a rotation of another string or not.

Solution #1: The first thing, of course, would be to make sure that both the strings have same length. Now, suppose these strings are str1 and str2 and one of them is a rotation of the other(eq. str1 = "google" and str2 = "oglego"). Append str2 to itself(making "oglegooglego"). Now, if we have a function to find a substring within a string, we can use it to find str1 in modified str2. If found, then str2 is a rotation of str1.

Replace all spaces in a string with '%20'.

Solution #1: The most straight forward approach is to scan the entire string while copying it to another buffer and replacing each space with a '%20' in the new buffer. Time complexity will be O(n).

Solution #2: If we can assume that the string buffer is sufficiently large then we can scan the entire string to count the number of spaces and then modify the same string buffer by scanning it backwards and adjusting its length. Here is the code,

void replaceSpaces(char* str)
{
    int space_count=0;
    char* ptr = str;
    char* new_end = NULL;

    while(*ptr != '\0')
    {
        if(*ptr == ' ')
            space_count++;

        ptr++;
    }
        
    new_end = ptr + space_count*2;

    *new_end = '\0';
    
    while(ptr != str)
    {
        if(*ptr == ' ')
        {
            *new_end-- = '0';
            *new_end-- = '2';
            *new_end-- = '%';
        }
        else
        {
            *new_end-- = *ptr;
        }
        ptr--;
    }
}

Determine if two strings are anagrams or not.

Solution #1: If destruction of strings is allowed then we can sort the strings in O(n log n) time and then compare them in O(n) time.

Solution #2: If we have the luxury of using plenty of extra memory then we can create two arrays of size 256 and store the occurrence of all unique characters in both strings in each array and then compare the arrays. Here is a pretty straight forward code. Time complexity being O(n + n + 1) ~ O(n).

int areAnagrams(char* str1, char* str2)
{
    int i;
    int arr1[256] = {0,};
    int arr2[256] = {0,};

    int unique_char_1 = 0;
    int unique_char_2 = 0;
    char* ptr1 = str1;
    char* ptr2 = str2;

    while(*ptr1 != '\0')
    {
        if(arr1[*ptr1] == 0)
            unique_char_1++;

        arr1[*ptr1]++;
        ptr1++;
    }

    while(*ptr2 != '\0')
    {
        if(arr2[*ptr2] == 0)
            unique_char_2++;

        arr2[*ptr2]++;
        ptr2++;
    }

    if(unique_char_1 != unique_char_2)
        return 0;

    for(i=0; i<256; i++)
    {
        if(arr1[i] != arr2[i])
            return 0;
    }

    return 1;
}


Solution #3: The above code can also be written using just one array like this,

int areAnagrams(char* str1, char* str2)
{
    int arr[256] = {0,};

    int unique_char_1 = 0;
    int unique_char_2 = 0;

    char* ptr1 = str1;
    char* ptr2 = str2;

    while(*ptr1 != '\0')
    {
        if(arr[*ptr1] == 0)
            unique_char_1++;

        arr[*ptr1]++;
        ptr1++;
    }

    while(*ptr2 != '\0')
    {
        if(arr[*ptr2] == 0)
            return 0;

        arr[*ptr2]--;

        if(arr[*ptr2] == 0)
        {
            unique_char_2++;

            if(unique_char_1 == unique_char_2)
                return 1;
        }

        ptr2++;
    }

    return 0;
}

Wednesday, April 13, 2011

Remove duplicates in a string.

Solution #1: Let us first consider the case when extra buffer is not allowed. Scan every character in the string and compare it with every previous character, if it is a duplicate then ignore it, otherwise copy it. This approach will have a time complexity of O(n^2). Here is the code,

void removeDuplicates(char* ptr)
{
    int end = 1;
    int length = strlen(ptr);
    int current;
    int i;

    current = 1;

    for(end=1; end<length; end++)
    {
        for(i=0; i<end; i++)
        {
            if(ptr[end] == ptr[i])
                break;
        }

        if(i == end)
        {
            ptr[current] = ptr[i];
            current++;
        }
    }
    ptr[current] = 0;
}

int main(int argc, char** argv)
{
    char str[256] = {0,};

        gets(str);

    removeDuplicates(str);

    printf("%s\n", str);

    return 1;
}


2) Now, let's consider the case when we have the luxury of using extra memory. Also consider that the string is made up of extended ASCII characters. So let's make a bit array of 256 bits. Now, we can scan the string and use this array to keep a track of all the characters we encounter and ignore the duplicate ones.

Tuesday, April 12, 2011

Reverse a string.

Solution #1: If extra space is available then copy the string in reverse order to a newly allocated string in O(n) time.

Solution #2: Again, if extra space is permissible then we can use a stack to first push the entire string on the stack and then pop it in reverse order.

Solution #3: If it has to be done in place, then we can take two pointers at the start and end of the string and can swap the characters they point to while incrementing and decrementing them respectively till they collide.

Solution #4: Approach three can also be done recursively as follows,

void reverse(char *start, char *end)
{
    char temp;

    if(start >= end)
        return;
    
    temp = start[0];
    start[0] = end[0];
    end[0] = temp;

    reverse(start+1, end-1);    
}

int main(int argc, char** argv)
{
    char str[256] = {0,};
    int len;

        gets(str);
    len = strlen(str);

    reverse(str, str+len-1);

    printf("%s\n", str);

    return 1;
}

Monday, April 11, 2011

Determine if a string has all unique characters.

Solution #1: The most simple approach will be to check each character with every other character. The time complexity will be O(n^2) with no extra space requirement.

Solution #2:If changes are allowed, then we can sort the string in O(n log n) time and then check the adjacent elements for duplicates. Total time complexity is n log n + n ==> n log n.

Solution #3: If the string is formed of extended ASCII characters then we can make an array of size 256 and store the occurrence of each character in this array.
    int main(int argc, char** argv)
    {
        int arr[256] = {0,};
        char *ptr = NULL;
    
        ptr = argv[1];
    
        while(*ptr != '\0')
        {
            if(arr[*ptr])
            {
                printf("Found Duplicate...\n");
                return 0;
            }
            else
            {
                arr[*ptr] = 1;
            }
            ptr++;
        }
    
        printf("No duplicates...\n");
    
        return 1;
    }
    
    

    This code can further be optimized by using a bit array instead of using an int array. For that we will need 256 bits.