binary search in sorted rotated array

Problem Given a Sorted Array which can be rotated find an Element in it in minimum Time Complexity.

#include <iostream>
#include <assert.h>

int binary_search( int arr[], int low, int high, int target) {
	while ( low <= high ) {

		int mid =  ( low + high ) / 2 ;

		if (target == arr[mid] )
			return mid;

		if ( target < arr[mid] ) 
			high = mid - 1;
		else 
			low = mid + 1;
	}
	return -1;
}
int binary_search_rotation( int arr[], int rotation, int target, int size ) {
	int rc = -1;
	if ( target == arr[rotation - 1] ) {
		rc = rotation - 1;
	} else if ( target < arr[rotation - 1] && target >= arr[0]) {
		rc = binary_search( arr, 0, rotation - 1, target);
	} else  {
		rc = binary_search(arr, rotation, size , target );
	}
	return rc;
}

int main ( int argc, char **argv) {
	int arr[] ={6,7,8,9,10,1,2,3,4,5};
	int rot_cnt = 5;
	int target = 9;
	int result = 0;

	for ( int idx = 0; idx < 10; idx++ ) {		
		int target = arr[idx];
		assert ( binary_search_rotation(arr,5, target, 10) == idx );	
	}

	return 0;
}

Convert a binary search tree into circular doubly linked list

The Challenge
The challenge is to take an ordered binary tree and rearrange the internal pointers to make a circular doubly linked list out of it.

#include <iostream>

struct tree_node {
	tree_node *left;
	tree_node *right;
	int data;
};

void insert(tree_node **current, int data ) {
	if ( *current == (tree_node*)0 ) {
		*current = new tree_node();
		(*current)->left  = ( tree_node *) 0;
		(*current)->right = ( tree_node *) 0;
		(*current)->data  = data;
	} else {
		if ( data < (*current)->data )  {
			insert ( &((*current)->left) , data );
		} else {
			insert ( &((*current)->right), data );
		}
	}
}
void print_tree(tree_node *current) {
	if ( ! current ) 
		return;
	print_tree(current->left );
	std::cout << current->data << " ";
	print_tree(current->right);

}
struct dlist {
	dlist *left;
	dlist *right;
	int data;
};

dlist *head = (dlist *)0;
dlist *cur  = ( dlist *)0;

void create_dlist(tree_node *current) {
	if ( ! current ) {		
		return;
	}
	create_dlist( current->left);
	if ( ! head ) {
		head = new dlist;
		head->left = ( dlist *) 0;
		head->right = ( dlist *) 0;
		head->data  = current->data;		
		cur = head;
	} else {
		dlist *temp = new dlist;

		temp->right = ( dlist *)0;
		temp->left  = cur;
		temp->data  = current->data;

		cur->right  = temp;

		cur = temp;
	}
	create_dlist( current->right);
	cur->right = head;
	head->left = cur;
}

void print_dlist() {
    std::cout << std::endl;
	dlist *current = head;
	while ( current->right != head ) {
		std::cout << current->data << " ";
		current = current->right;
	}
    std::cout << current->data;
    std::cout << std::endl;
}


int main( int argc, char** argv) {
	int arr[] = {5,2,7,1,8,3,9};
	int len = sizeof(arr)/sizeof(arr[0]);
	tree_node *my_tree =  ( tree_node *)0;
	for ( int i = 0; i < len; i++ ) {
		insert(&my_tree, arr[i]);
	}
	print_tree(my_tree);	
	create_dlist(my_tree);
	print_dlist();
	return 0;
}

Multithreading in C++0x

One new feature in C++0x standard is multi-threading support. Previously one need to use different API’s for each platform, which cause headache in porting. Now now C++0x compiler has made mandatory to implement threads for each platform. Let us go through the std::thread class .

Creating a new thread
You just need to construct an object/instance of std::thread and pass a thread start function to it. Thread will finish when the thread start function returns.

void thread_fn() {
}
std::thread my_thr(thread_fn);

There is no restriction that one need to use only normal function, as a thread start function. You also can pass object of the class which overload operator()

class thread_fn {
public:
    void operator() {
    };
};
thread_fn thr_fn_obj;
std::thread my_thr(thr_fn_obj);

Note that this way you are sending copy of the object thread_fn class. If you want to avoid the same and need to use the same object even after thread is finsihed, use std::ref, just wrap the object of your class using std::ref as follows

thread_fn thr_fn_obj;
std::thread my_thr(std::ref(thr_fn_obj));

Argument passing to thread function
In new standard you can pass any number of argument to thread function. C++0x uses variadic template facility to allow variable number of argument in typesafe manner.

void thread_fn(int x, int y) {
}
int a = 5;
int b = 6;
std::thread my_thr(thread_fn,a, b);

Waiting for thread to finish
Going with the POSIX standard, C++0x has provided join API to do the same.

void thread_fn() {
}
std::thread my_thr(thread_fn);
my_thr.join();

Protecting data
With great power of multithreading, it comes the responsibility of the sharing the data. C++0x has provided following basic facility for protecting shared data.

  • non-recursive mutex std::mutex
  • recursive mutes std::recursive_mutex
  • non-recursive with facility to apply timeout for locking std::timed_mutex
  • recursive mutes with timeout for locking std::recursive_timed_mutex

All of those options provides you ownership of the one thread, if you try to lock non-recursive mutex more than once, before unlocking previous ownership, you get undefined behavior. recursive mutex just increment the lock count, for each call and one need to make sure that same number of unlock is being called.
All those classes have lock and unlock member function, it is best to use std::unique_lock and std::lock_guard template, as they are locking in construction. no need to explain the advantage of this approach.
std::unique_lock is very basic and can be used in following form

std::mutex mlock;
my_class data;
void foo() {
    std::lock_guard<std::mutex> lck(mlock);
    perform_operation(data);
} // mutex unlocked here

std::unique_lock provided great list of facility and allows following

  • deferred locking
  • trying to a lock
  • try to lock with a timeout
  • unlocking lock before object is destroyed.
std::timed_mutex m;
my_class data;
void foo() {
    std::unique_lock<std::timed_mutex>
    lk(m,std::chrono::milliseconds(3)); // wait up to 3ms
    if(lk) // if we got the lock, access the data
       process(data);
} // mutex unlocked here

How to avoid deadlock
No need to explain what is dealock and repeating the deadly dreams on solving where is deadlock. C++0x thread library alleviates this problem. In case you need to take multiple locks together, it provides generic std::lock function which can lock all the locks at once.

struct shared_data {
   std::mutex m_lck;
   int a;
   std::string b;
};
void lock_me(shared_data& a, shared_data& b) {
    std::unique_lock<std::mutex> lock_a(a.m_lck,std::defer_lock);
    std::unique_lock<std::mutex> lock_b(b.m_lck,std::defer_lock);
    std::lock(lock_a,lock_b);
    // do something with the internals of a and b
}

Now even if the lock_me is called with lock_me(b,a ), no deadlock will happen.

Maximum Contigous subsequence Sum Problem

Given (Possible Negative) integers A1,A2,A3,..An, Find and identify the sequence corresponding too, The maximum value of sub-sequence is defined as sum of K in Input array from I to J

Obvious O(n3) Solution

#include <vector>
#include <iostream>

int maximum_subsequence_sum( std::vector<int> &input, int& start_pos, int& end_pos ) {
	int size    = input.size();
	int max_sum = 0;
	for ( int i = 0; i < size; i++) {
		for ( int j = i; j < size; j++) {
			int current_sum = 0;
			for ( int k = i; k <= j; k++) {
				current_sum += input[k];
			}
			if ( current_sum > max_sum ) {
				max_sum = current_sum;
				start_pos = i;
				end_pos   = j;
			}
		}
	}
	return max_sum;
}
int main ( int argc, char **argv) {
	int input1[6] = {-2, 11, -4, 13, -5, 2};
	std::vector<int> in1(input1, input1 + 6);
	int start_pos = 0;
	int end_pos   = 0;
	std::cout << "Sum = " << maximum_subsequence_sum(in1, start_pos, end_pos) << std::endl;
	for ( int i = start_pos; i <= end_pos; i++) {
		std::cout << in1[i] << " ";
	}
	std::cout << std::endl;
}

A quadratic maximum contiguous subsequence sum algorithm

#include <vector>
#include <iostream>

int maximum_subsequence_sum( std::vector<int> &input, int& start_pos, int& end_pos ) {
	int size    = input.size();
	int max_sum = 0;
	for ( int i = 0; i < size; i++) {
		int current_sum = 0;
		for ( int j = i; j < size; j++) {
			current_sum += input[j];
			if ( current_sum > max_sum ) {
				max_sum = current_sum;
				start_pos = i;
				end_pos   = j;
			}
		}
	}
	return max_sum;
}
int main ( int argc, char **argv) {
	int input1[6] = {-2, 11, -4, 13, -5, 2};
	std::vector<int> in1(input1, input1 + 6);
	int start_pos = 0;
	int end_pos   = 0;
	std::cout << "Sum = " << maximum_subsequence_sum(in1, start_pos, end_pos) << std::endl;
	for ( int i = start_pos; i <= end_pos; i++) {
		std::cout << in1[i] << " ";
	}
	std::cout << std::endl;
}

A linear maximum contiguous subsequence sum algorithm

#include <vector>
#include <iostream>

int maximum_subsequence_sum( std::vector<int> &input, int& start_pos, int& end_pos ) {
	int size    = input.size();
	int max_sum = 0;
	int current_sum = 0;

	for ( int i = 0, j = 0 ; j < size; j++) {		
		current_sum += input[j];
		if ( current_sum > max_sum ) {
			max_sum = current_sum;
			start_pos = i;
			end_pos   = j;
		} else if ( current_sum < 0 ) {
			i = j + 1;
			current_sum = 0;
		}
	}
	return max_sum;
}
int main ( int argc, char **argv) {
	//int input1[6] = {-2, 11, -4, 13, -5, 2};
	int input1[6] = {1,2,3,4,5,6};
	std::vector<int> in1(input1, input1 + 6);
	int start_pos = 0;
	int end_pos   = 0;
	std::cout << "Sum = " << maximum_subsequence_sum(in1, start_pos, end_pos) << std::endl;
	for ( int i = start_pos; i <= end_pos; i++) {
		std::cout << in1[i] << " ";
	}
	std::cout << std::endl;
}

Reverse all the words in a sentence.

Given string containing a set of words separated by white spacer we would like to transform it to a string in which the words appear in the
reverse order. For example, “Alice likes Bob” will become “Bob likes Alice”. We do not need to keep the original string.

This is very simple problem, If you try to figure out the position for each character in a single pass, it becomes fairly complex. If you do this in two stages, it becomes fairly easy. In the first step, reverse the entire string and in the second step reverse each word.

#include <algorithm>
#include <string.h>
#include <iostream>

void reverse_string( char *input, size_t length ) {
	for ( int i = 0; i < length / 2; i++) {
		std::swap(input[i], input[ length - i - 1] );
	}
}
void reverse_word(char *input) {
	size_t length = strlen(input);
	reverse_string(input, length);
	int start = 0;
	while ( start < length ) {
		int end = start;
		// find the first space location
		while ( end < length && input[end] != ' ') {
			end++;
		}
		reverse_string( input + start, end - start );
		start  = end + 1;
	}

}
int main( int argc, char **argv) {
	char test[] = "ram is costly";
	reverse_word(test);
	std::cout << test << std::endl;

	return 0;
}