Finding the kth smallest element

Problem
Given a randomly ordered array of n elements determing the kth smallest element in the set. Overall complexity of this algorithm is O(n)

#include <vector>
#include <iostream>

template < class T>
T kth_smallest( std::vector<T>& a, int k ) {
	int l = 0;
	int u = static_cast<int>(a.size()) - 1;
	while ( l < u ) {
		int i = l; // upper limit of left partition
		int j = u; // lower limit of right partition
		T x   = a[k];
		while(i <= k && j >= k) {
			while( a[i] < x ) 
				i++;			
			while ( x < a[j] ) 
				j--;			
			std::swap(a[i],a[j]);
			i++;
			j--;
		}
		if ( j < k ) 
			l = k;
		if ( i > k )
			u = j;
	}
	return a[k];
}
int main(int argc, char** argv) {
	int arr[10] = {28, 26, 25, 11, 16, 12, 24, 29, 6, 10};
	std::vector<int> my_vec(arr, arr + 10); 
	for ( int i = 0; i < my_vec.size(); i++) 
		std::cout << i << "th smallest element is " << kth_smallest<int> ( my_vec, i ) << std::endl;

	return 0;
}

Same code with minor modification with comparison condition can be used to find the kth largest element

template < class T>
T kth_largest( std::vector<T>& a, int k ) {
	int l = 0;
	int u = static_cast<int>(a.size()) - 1;
	while ( l < u ) {
		int i = l; // upper limit of left partition
		int j = u; // lower limit of right partition
		T x   = a[k];
		while(i <= k && j >= k) {
			while( a[i] > x ) 
				i++;			
			while ( x > a[j] ) 
				j--;			
			std::swap(a[i],a[j]);
			i++;
			j--;
		}
		if ( j < k ) 
			l = k;
		if ( i > k )
			u = j;
	}
	return a[k];
}

Partitioning an array

Problem
Given a randomly ordered array of n elements, partition the element into two subsets such that element <= x are in one subset and elements >= x are in the other subset.

#include <vector>

int main ( int argc, char **argv) {
	int arr[10] = {28, 26, 25, 11, 16, 12, 24, 29, 6, 10};
	std::vector<int> a(arr, arr + 10); 

	int i  = 0;
	int j  = a.size() - 1;
	int x  = 17;

	while ( (i < j ) && ( a[i] <= x)) i++;
	while ( ( i < j) && ( a[j] > x))  j--;

	if ( a[j] > x )  j--;

	while ( i < j )  {
		std::swap( a[i], a[j]);
		i++;
		j--;

		while (a[i] <= x)
			i++;
		while (a[j] > x)
			j--;

	}
	return 0;
}

Algorithm is taken from the book How to Solve It by Computer
My gitHub repository will have all the code.

Interviewstreet Puzzle – Lucky Numbers – 1

Addiction is bad, but I must admit that Interview Street Challenges can be very addictive. This week-end I have started with there latest programming puzzle Lucky Number. Very simple puzzle, you are supposed to find sum of the digits of number then find sum of the square of the digits of a number, see if the both the results are prime , If yes then call that number as Lucky Number. I have started as usual with brute-force approach, and I knew that they are going to reject my approach right away. Here is the first version of the code, will update this post once I improve some more.

#include <iostream>
#include <string>
#include <numeric>
/* trying with brute force approach */
long long sum_of_digits(long long input) {
	long long total = 0;
	while (input != 0) {
		total += input % 10;
		input /= 10;
	}
	return total;
}
long long sum_of_square_digits(long long input) {
	long long total = 0;
	while (input != 0) {
		total += (input % 10)* (input % 10);
		input /= 10;
	}
	return total;
}
bool isPrime(long long x) {
        long long max = static_cast <long long> (x);
        if (x <= 0 || x == 1 || (x % 2 == 0 && x != 2)) return false;
        for (long long i = 3; i < max; i += 2)
            if (x % i == 0)
                return false;
        return true;
}
int main ( int argc, char** argv) {
	int T;
	std::cin >> T;

	while ( T-- ) {
		int result = 0;
		long long A;
		long long B;
		std::cin >> A >> B;
		for ( long long i = A; i <= B; i++) {
			long long sum        = sum_of_digits( i );
			long long sum_square = sum_of_square_digits( i );
			if ( isPrime(sum) && isPrime(sum_square)){
				result++;
			}
		}
		std::cout << result << std::endl;
	}
	return 0;
}

Update 2
Just doing some silly optimization but it also does not accepted by the robot. So this is what I was thinking
1. No need to call square computing function if the sum of the digits are not prime
2. No need compute mod operation twice
3. no need to iterate over the number separately and can be clubed into single function call.

#include <iostream>
#include <string>
#include <numeric>
/* trying with brute force approach */
void sum_of_digits_and_square(long long input, long long& sum, long long& sum_square) {
	sum = sum_square = 0L;
	while (input != 0L) {
		long long digit = input % 10L;
		sum        += digit;
		sum_square += digit * digit;
		input /= 10L;
	}	
}
bool isPrime(long long x) {
	long long max = static_cast <long long> (x);
	if (x <= 0 || x == 1 || (x % 2 == 0 && x != 2)) return false;
	for (long long i = 3; i < max; i += 2)
		if (x % i == 0)
			return false;
	return true;
}
int main ( int argc, char** argv) {
	int T;
	std::cin >> T;

	while ( T-- ) {
		int result = 0;
		long long A;
		long long B;
		std::cin >> A >> B;
		for ( long long i = A; i <= B; i++) {
			long long sum        = 0;
			long long sum_square = 0;
			sum_of_digits_and_square(i,sum,sum_square);
			if ( isPrime(sum)) {
				if ( isPrime(sum_square)){
					result++;
				}
			}
		}
		std::cout << result << std::endl;
	}
	return 0;
}

Attempt No – 2

#include <iostream>
#include <cmath>

bool isPrime(long long number) {
	if (number == 1L)
		return false;
	if (number == 2L)
		return true;
	if((number & 1) == 0)
		return false;
	for (long long  d = 3L; d <= (long long)sqrt((double)number); d += 2)
		if (number % d == 0)
			return false;
	return true;
}
int main ( int argc, char** argv) {
	int T;
	std::cin >> T;

	while ( T-- ) {
		int result = 0;
		long long A;
		long long B;
		std::cin >> A >> B;
		for ( register long long i = A; i <= B; ++i) {
			long long sum        = 0;
			long long sum_square = 0;
			for (register long long  n = i; n > 0; sum += n % 10, n /= 10) ;
			if ( isPrime(sum)) {
				for (register long long  n = i; n > 0; sum_square += (n % 10) * (n % 10), n /= 10) ;
				if ( isPrime(sum_square)){
					result++;
				}
			}
		}
		std::cout << result << std::endl;
	}
	return 0;
}

Find all the unique substring of n strings

This is the problem I am really trying hard to get O(n) solution, but still no success. But in the course of doing same, I came up with nice way of storing all the n strings in a trie, But unfortunately we need to store string starting from each letter till the end to get all the unique sub strings.

#include <string>
#include <iostream>
#include <vector>

const int ALPHABET_SIZE = 26;
char text[2000];
int LEN;
std::vector<std::string> union_unique_strings;

struct trie_node_t { 
    trie_node_t*child_list[ALPHABET_SIZE]; 
    trie_node_t() {
        for(int index = 0; index < ALPHABET_SIZE; index++)
            child_list[index] = (trie_node_t*)0;
    }
};

class Trie {
public:
    Trie():m_root(new trie_node_t) {
    }

    ~Trie() {
        _delete(m_root);
    }

    void _insert(int pos, std::string prefix) {
        int lcv, index; 
        trie_node_t* t = m_root;
        for(lcv = pos; lcv < LEN; lcv++) {
            index = text[lcv] - 'a';
            if (t->child_list[index] == (trie_node_t*)0) { 				
                t->child_list[index] = new trie_node_t;
            }
            t = t->child_list[index];
        }
    }
    void insert() {
        for ( int i = 0; i < LEN; i++) {
            _insert(i, "");
        }
    }

    void iterate() {
        _iterate(m_root, "");
    }

    void _iterate(trie_node_t *t, std::string prefix) {    
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            if (t->child_list[i] != (trie_node_t*)0) {
                std::string next_prefix = prefix + static_cast<char>('a' + i);
				union_unique_strings.push_back(next_prefix);
                _iterate(t->child_list[i], next_prefix);
            }   
        }
    }   
private:     
    trie_node_t* m_root;
    void _delete (trie_node_t* t) {
        int index; 
        if (t != (trie_node_t*)0) {
            for(index = 0; index < ALPHABET_SIZE; index++)
                _delete(t->child_list[index]);
            delete t;
        }
    }    
};

Generating Random string of length n.

While solving programming puzzle you will need to generate lot of test cases.  Here is the small Perl script to do the same.
This script will generate a string of random characters of the specified length.

#!/usr/bin/perl
sub generate_random_string {
    my $length_of_randomstring=shift;
    my @chars=('a'..'z');
    my $random_string;
    foreach (1..$length_of_randomstring) {
        $random_string.=$chars[rand @chars];
    }
    return $random_string;
}
my $random_string = &generate_random_string(2000);
print "Random string: ".$random_string."\n";
print "Length: ".length($random_string)."\n";

Generating all unique substring of a string.

Here is the code to generate unique substring , using suffix array.

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

char txt[2000], *p[2000];
int m, n;

int cmp(const void *p, const void *q) {
    int rc = memcmp(*(char **)p, *(char **)q, m);
    return rc;
}
int main() {
    std::cin >> txt;
    n = strlen(txt);
    int k; int i;
    for (m = 1; m <= n; m++) {
        for (k = 0; k+m <= n; k++)
            p[k] = txt+k;
        qsort(p, k, sizeof(p[0]), &cmp);
        for (i = 0; i < k; i++) {
            if (i != 0 && cmp(&p[i-1], &p[i]) == 0){
                continue;
            }
            char cur_txt[2000];
            memcpy(cur_txt, p[i],m);
            cur_txt[m] = '\0';
            std::cout << cur_txt << std::endl;
        }
    }
    return 0;
}

Find Strings Interview Street Problem

Problem details are here

Following is my solution , This is n-squared solution and will not be accepted by Robot. Need to come up with something smart and faster solution.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <functional>

/* Simple O(n2) Solution */

std::vector<std::string> S;

void solve() {
    size_t Qi = 0;
    std::cin >> Qi;

    if ( S.size() < Qi - 1 ) {
        std::cout << "INVALID" << std::endl;
    } else {
        std::cout << S[Qi - 1] << std::endl;
    }
}
void get_unique_sub_string(std::string &str, std::vector<std::string> &sTemp) {
    size_t length = str.size();
    for( size_t i = 0 ; i < length ; i++ ) {
        for( size_t j = 1 ; j <= length - i ; j++ ) {
            sTemp.push_back(str.substr(i, i + j));
        }
    }
    std::sort(sTemp.begin(), sTemp.end());
    sTemp.erase(std::unique(sTemp.begin(), sTemp.end()), sTemp.end());
}
int main ( int argc, char **argv ) {
    int n; // number of strings
    std::cin >> n;
    for ( int i = 0; i < n ; i++){
        // Read the string
        std::string str;
        std::cin >> str;

        std::vector<std::string> sTemp;
        get_unique_sub_string(str,sTemp);

        std::vector<std::string> Stemp_result;
        Stemp_result.resize (sTemp.size() + S.size());

        std::set_union(sTemp.begin(), sTemp.end(), S.begin(), S.end(), Stemp_result.begin());
        S = Stemp_result;

    }
    std::vector<std::string>::iterator it = std::remove_if(S.begin(), S.end(),std::mem_fun_ref(&std::string::empty));
    S.erase(it, S.end());

    int q; // number of queries
    std::cin >> q;
    for ( int i = 0; i < q; i++) {
        solve();
    }
    return 0;
}