tHe puZZlingG wOrlD: March 2012

Saturday, March 31, 2012

Reader write lock without any priority

#include <pthread.h>

enum locktype{
READER =0,
WRITER
};

typedef struct QNode {
locktype _type;
struct QNode* pNext;
} QNode;

tyepdef struct Queue {
QNode* _pHead;
} Queue;

typdef struct RWLock {
Queue* _pQueue;
ptread_mutex_t _lock;
pthread_cond_t _condv;
uint32_t _currentReaderCount;
bool _writeLocked;
} RWLock;

void

int
rw_lock_init(RWLock* pLock)
{
if (pLock == NULL) {
return ENULL;
}

pLock->pQueue = (Queue*) malloc(sizeof(queue));
if (pLock->pQueue == NULL) {
return ENULL;
}
initQueue(pLock->pQueue);

if (pthread_mutex_init(&pLock->_lock)) {
return EMUTEX_INIT;
}

if (pthread_cond_init(&pLock0>conv)) {
return ECOND_INIT;
}

_readCount = 0;
_writerLocked = false;
}

int
reader_rw_lock(RWlock* pRWLock)
{
if (pRWLock == NULL) {
return ENULL;
}

if (pthread_mutex_lock(&pRWLock->_lock)) {
return EMUTEX_LOCK;
}

while((pQueue->pHead) || pQueue->_writerLocked)) {
pQueue->insert(READER);
if (pthread_cond_wait(&pRWLock->_lock, &pRWLock->condv)) {
pthread_mutex_unlock(&pRWLock->lock));
return ECONDWAIT;
}
}
pRWLock->readCount++;

pthread_mutex_unlock(&pRWlock->_lock);

return 0;
}

int.
reader_rw_destroy(RWLock* pRWLock)
{
if (pRWLock == NULL) {
return ENULL;
}

pthread_mutex_lock(&pRWlock->_lock);
if (pRWLock->_readerCount || pRWLock->_writeLock || pRWLock->_pHead) {
pthread_mutex_unlock(&pRWlock->_lock);
return EBUSY;
}

pthread_cond_destroy(pRWLock->_condv);

pthread_mutex_unlock(&pRWlock->_lock);
pthread_mutex_destory(&pRwlock->lock);

return 0;
}
int
writer_rw_lock(RWLock* pRWlock)
{
if (pRWlock == NULL) {
return ENULL;
}

if (pthread_mutex_lock(&pRWlock->_lock) {
return EMUTEX_LOCK;
}

while ((pQueue->pHead) || (pQueue->_writeLocked) || pQueue->_readCount)) {
pQueue->insert(WRITER);
if (pthread_cond_wait(&pRWLock->_lock, &pRWLock->condv)) {
pthread_mutex_unlock(&pRWLock->lock));
return ECONDWAIT;
}
}

pRWLock->writerLocked = true;

pthread_mutext_unlock(&pRWlock->_lock);

return 0;
}

int
rw_unlock(RWLock* pRWlock)
{
if (pRWLock == NULL) {
return ENULL;
}

if (pthread_mutex_lock(&pRWlock->_lock) {
return EMUTEX_LOCK;
}

if (pRWLock->_readcount) {
pRWLock->_readcount -= 1;
}

if (pRWLock->_writelocked) {
pRWLock->_writeLock = false;
}

if ((pRWLock->_readCount == 0)&& (pRWLock->_writeLocked == false)) {
if (pRWLock->_pHead) {
if (pRWlock->_pHeade->_type == READER) {
while (pRWLock->pHeader && (pRWLock->pHeader->_ptype == WRITER) {
pthread_cond_signal(pRWLock->pCondv);
removeHead(pRWLock->pQueue);
}
} else {
pthread_cond_signal(pRWLock->pCondv);
removeHead(pRWLock->pQueue);
}
}
}
return 0;
}

Find square root of a number without using square root

Give a number find square root of number without using square root function.

Solution:
So given x we need to find sqrroot(x) = y
i.e. x = y^2

so we need to a find a y whose square is x.

We can use binary search to find such a y

Fo eg we need to find sqrroot(100)
We can start doing binary search between 0 and 100. First iteration we find 50 and 50^2 > 200 so we move left partition and visit 0 and 50 and keep continuing till we find our number

Given a dictionary of words find the ranking of characters

You are given a dictionary with set of words i.e. in the dictionary words are arranged in special lexicographical order. The lexicographical order is what you need to find. i.e. this dictionary is not arranged like a standard dictionary where a < b < c ... < z I is based on different character ranking you need to find that ranking.

Solution:
Consider subset of dictionary order

LBD
LBK
EMN
ERQ
GLQ
HFG

Look at first character of words. We know L < E < G < H
Consider second cloumn characters whose first character are same eg (EMN, ERQ) we know M < R
consider third column whose first two columns are same (LBD, LBK) we know D < K

Now consider that each character is a node in the graph when we find a relations ship that character1 < character2 we add directed edger from character1->character2

Using above method we traverse through all columns and build the graph.

In next step the character which comes first will have incoming degree 0. That will character which comes first we visit that node and remove it. As a result we will find next node with incoming degree 0 that will be character with next ranking. We will continue doing this until we have visited all nodes.

If at any stage we get two nodes with indegree of 0 we do not have enough input. Also if the input is given that there is a cycle in the graph solution will need to detect such bad inputs.

Normalize a path by removing redundant separators and resolving up-level references

Write a function to normalize a path by removing redundant separators and resolving
up-level references. I.e., given "/foo/bar//./baz/..//boo" returns "/foo/bar/boo".
- You may assume that the given path is always absolute (i.e., begins with "/").
- You may not use any library functions.
- Ideally, the solution should function in-place without allocating any buffers.

#define E_NULL -1
#define E_INVALID -2
int
normalizePath(char* pPath,
unsigned startIndex,
unsigned writeOffset,
unsigned level)
{
unsigned lastIndex = startIndex + 1;
unsigned retValue = 1;
unsigned ii, jj;

printf("level=%d start index=%d writeOffset=%d\n", level, startIndex, writeOffset);
if (pPath == NULL) {
return E_NULL;
}

if (pPath[startIndex] == 0) {
pPath[writeOffset] = 0;
return 0;
}

if (pPath[startIndex] != '/') {
return E_INVALID;
}

do {
if (pPath[lastIndex] == 0) {
pPath[writeOffset] = 0;
break;
}
// find next / or NULL
while (pPath[lastIndex] && pPath[lastIndex] != '/') {
lastIndex++;
}
printf("%d\n", lastIndex);
// missing ignoring series of ////

if (pPath[startIndex + 1] == '.') {
if (pPath[startIndex + 2] == '.') {
if (level == 0) {
continue;
}
return 1;
} else {
retValue = normalizePath(pPath, lastIndex, writeOffset, level +1 );
}
} else {
// startIndex to lastIndex to writeOffset

for(ii = startIndex, jj= 0; ii < lastIndex; ii++, jj++) {
pPath[writeOffset + jj] = pPath[startIndex + jj];
}
retValue = normalizePath(pPath, lastIndex, writeOffset + jj, level + 1);
}
startIndex = lastIndex + 1;
lastIndex += 1;
} while (retValue == 1);

return 0;
}

int
main()
{
char *pPath = "/ab/../de/../mn/./..";
normalizePath(pPath, 0, 0,0 );
printf("path=%s", pPath);
return 0;
}

Merge Two Balanced Binary Search Trees

Source

You are given two balanced binary search trees e.g., AVL or Red Black Tree. Write a function that merges the two given balanced BSTs into a balanced binary search tree. Let there be m elements in first tree and n elements in the other tree. Your merge function should take O(m+n) time.

In the following solutions, it is assumed that sizes of trees are also given as input. If the size is not given, then we can get the size by traversing the tree (See this).

Method 1 (Insert elements of first tree to second)
Take all elements of first BST one by one, and insert them into the second BST. Inserting an element to a self balancing BST takes Logn time (See this) where n is size of the BST. So time complexity of this method is Log(n) + Log(n+1) … Log(m+n-1). The value of this expression will be between mLogn and mLog(m+n-1). As an optimization, we can pick the smaller tree as first tree.

Method 2 (Merge Inorder Traversals)
1) Do inorder traversal of first tree and store the traversal in one temp array arr1[]. This step takes O(m) time.
2) Do inorder traversal of second tree and store the traversal in another temp array arr2[]. This step takes O(n) time.
3) The arrays created in step 1 and 2 are sorted arrays. Merge the two sorted arrays into one array of size m + n. This step takes O(m+n) time.
4) Construct a balanced tree from the merged array using the technique discussed in this post. This step takes O(m+n) time.

Time complexity of this method is O(m+n) which is better than method 1. This method takes O(m+n) time even if the input BSTs are not balanced.
Following is C++ implementation of this method.

#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};

// A utility unction to merge two sorted arrays into one

int *merge(int arr1[], int arr2[], int m, int n);

// A helper function that stores inorder traversal of a tree in inorder array

void storeInorder(struct node* node, int inorder[], int *index_ptr);

/* A function that constructs Balanced Binary Search Tree from a sorted array

   See http://www.geeksforgeeks.org/archives/17138 */

struct node* sortedArrayToBST(int arr[], int start, int end);

/* This function merges two balanced BSTs with roots as root1 and root2.

   m and n are the sizes of the trees respectively */

struct node* mergeTrees(struct node *root1, struct node *root2, int m, int n)

{

    // Store inorder traversal of first tree in an array arr1[]

    int *arr1 = new int[m];

    int i = 0;

    storeInorder(root1, arr1, &i);

    // Store inorder traversal of second tree in another array arr2[]

    int *arr2 = new int[n];

    int j = 0;

    storeInorder(root2, arr2, &j);

    // Merge the two sorted array into one

    int *mergedArr = merge(arr1, arr2, m, n);

    // Construct a tree from the merged array and return root of the tree

    return sortedArrayToBST (mergedArr, 0, m+n-1);

}

/* Helper function that allocates a new node with the

   given data and NULL left and right pointers. */

struct node* newNode(int data)

{

    struct node* node = (struct node*)

                        malloc(sizeof(struct node));

    node->data = data;

    node->left = NULL;

    node->right = NULL;

    return(node);

}

// A utility function to print inorder traversal of a given binary tree

void printInorder(struct node* node)

{

    if (node == NULL)

        return;

    /* first recur on left child */

    printInorder(node->left);

    printf("%d ", node->data);

    /* now recur on right child */

    printInorder(node->right);

}

 // A utility unction to merge two sorted arrays into one
int *merge(int arr1[], int arr2[], int m, int n)
{
    // mergedArr[] is going to contain result
    int *mergedArr = new int[m + n];
    int i = 0, j = 0, k = 0;
 
    // Traverse through both arrays
    while (i < m && j < n)
    {
        // Pick the smaler element and put it in mergedArr
        if (arr1[i] < arr2[j])
        {
            mergedArr[k] = arr1[i];
            i++;
        }
        else
        {
            mergedArr[k] = arr2[j];
            j++;
        }
        k++;
    }
 
    // If there are more elements in first array
    while (i < m)
    {
        mergedArr[k] = arr1[i];
        i++; k++;
    }
 
   // If there are more elements in second array
    while (j < n)
    {
        mergedArr[k] = arr2[j];
        j++; k++;
    }
 
    return mergedArr;
}
 
// A helper function that stores inorder traversal of a tree rooted with node
void storeInorder(struct node* node, int inorder[], int *index_ptr)
{
    if (node == NULL)
        return;
 
    /* first recur on left child */
    storeInorder(node->left, inorder, index_ptr);
 
    inorder[*index_ptr] = node->data;
    (*index_ptr)++;  // increase index for next entry
 
    /* now recur on right child */
    storeInorder(node->right, inorder, index_ptr);
}
 
 
/* A function that constructs Balanced Binary Search Tree from a sorted array
   See http://www.geeksforgeeks.org/archives/17138 */
struct node* sortedArrayToBST(int arr[], int start, int end)
{
    /* Base Case */
    if (start > end)
      return NULL;
 
    /* Get the middle element and make it root */
    int mid = (start + end)/2;
    struct node *root = newNode(arr[mid]);
 
    /* Recursively construct the left subtree and make it
       left child of root */
    root->left =  sortedArrayToBST(arr, start, mid-1);
 
    /* Recursively construct the right subtree and make it
       right child of root */
    root->right = sortedArrayToBST(arr, mid+1, end);
 
    return root;
}
 


 