Important ds question

a) Write a function that validates whether a tree is a BST or not.

b) Write a function to find the common ancestor of two given nodes of binary tree.

c) In a BST, value of  two of the nodes got exchanged by mistake. Write a function to correct the BST.

d) In a array, there exists a majority element(a no. repeated atleast n/2 + 1 times) and rest of the no.s can be anything. find that majority element in a single pass without using extra space.

e) Find the no. of root nodes in a Binary tree.

f) write a function to create  a mirror image of  a given binary tree without using recursion.

1).merge two height balanced binary trees to get another height balanced
 binary tree.
------------------------------

--------------------------------------------------------------
2).given an unsorted array of n integers, find that pair of integers
which gives the maximum sum.
--------------------------------------------------------------------------------------------
3) slight modification.(use heap)
 find the maximum sum giving combination of k integers.
--------------------------------------------------------------------------------------------
4)sudoku solver
--------------------------------------------------------------------------------------------
5)How do you find  a loop in a linked list?

               1) ptr method
               2) Go on reversing the linked list.
                     Ifyou reach the head again, the list has a loop
--------------------------------------------------------------------------------------------
6) construct a n element binary tree from its inorder and preorder traversals kept in two arrays A[n] and B[n].
{ u can get the roots of each subtree in preorder array. Then we can Partion the inorder array into left and right subtrees. Thus this problem can be solved recursively...}

--------------------------------------------------------------------------------------------
7)we are given the answers to a crossword puzzzle...we need to generate the blocks...that is the question is to be framed..what datastructure do u think should we use for this????(may be trie,linked list.??)
----------------------------------------------------------------------------------------------------
8)how can v reverse a sentence.its not string reversal
example;
given input "this is me"
the output should b "me is this"
{Use a stack !! first "push" every word in correct order.. then "pop" them out... the resulting string will be in reverse order !}
------------------------------ ----------------------------------------------------------------------
9)def. of tree,graph,linked list.nd many more
----------------------------------------------------------------------------------------------------
10) How do you find a loop in a Binary tree in a most efficient way.
{ by maintaining flag variable in node data.if already traversed ,flag value z true,otherwise  false.
suppose recursive function access the already traversed node,then we can conclude that this tree z havng loop.}
----------------------------------------------------------------------------------------------------
11) If 'n' is even donfiltered=n/2
Else if 'n' is odd donfiltered=3*n+1.
If you keep on doing above said operations 'n'will converge to 1 at some point.
You are given a set of numbers (say 65 to 125.Give an efficient soln to find out which number converges to 1 the quickest.
----------------------------------------------------------------------------------------------------
 12) sort an array having elements only 0 and 1 in O(n)time and sorting should terminate immediately after array gets sorted.(1. find the first occurence of
 1. now find the first occurence of 0.
2. when u are having two marker one at first 1 and other at first 0. swap  them.}
----------------------------------------------------------------------------------------------------
13)findout the median of two sorted arrays as if this is one sorted array with O(1) space constraint.
----------------------------------------------------------------------------------------------------
14)how will you find out that a given binary tree is binary search tree.
 (inorder traversal nd check 4 sorted nos.)

{  isBST(Node *node){
if(node == NULL)
return TRUE;
if (node->left->data > node->data )
return FALSE;
else
return isBST(node->left);
if(node->right->data < node->data)
return FALSE;
else
return isBST(node->right);
}
----------------------------------------------------------------------------------------------------
15) given two node pointers in a binary tree . find out the closest common ancestor of the  nodes.

{
     int postOrderToFindLCA(elem *root,elem a,elem b)
{
if(root==NULL) return 0;
if(root->left!=NULL)
left=postOrderToFindLCA(root->left);
if(root->right!=NULL)
right=postOrderToFindLCA(root->right);
if(right+left == 2)
{
printf("I am the LCA%d\n",root->id) ;
return 0;
}
if(root->id == a->id || root->id == b->id)
{
return 1;
}
return (left+right);
}
----------------------------------------------------------------------------------------------------
16. Algorithm to swap two words in a given sentence.
Constraint: You can use only one extra char variable
( reverse the whole sentence. then reverse it with delimiter ' '.)
----------------------------------------------------------------------------------------------------
17). Given the root of a binary tree, write a routine to find the depth of the tree.
 depth ( Tree  T)
{
If isnull(T) then return 0;
else return
max(depth(T->right),depth(T>left))+1
}
----------------------------------------------------------------------------------------------------
18)Given the head pointer of a singly linked list, print the contents of the list in reverse order.
Constraints - O(1) space
 print(node head)
{
if ( head != null)
{
if(head->next == null)
printf("%d",head->element);

print(head->next);

printf("%d",head->element);
}
----------------------------------------------------------------------------------------------------
19) Algorithm to find the number of ones in the binary form of a given number "n". An efficient method.
#include
main()
{
int x,count=0;
scanf ("%d",&x);
while (x!=0)
{
count++;
x=(x&(x-1));
}
printf (" %d  ",count);
}
----------------------------------------------------------------------------------------------------
20)Given a string of length N, find whether there exits an even length palindrome substring.
----------------------------------------------------------------------------------------------------
21) Given an array arr[a1 a2 ... an b1 b2 ...bn]
Arrange in order arr[a1 b1 a2 b2 .. an bn] in O(n)
----------------------------------------------------------------------------------------------------
22) Given N sets of integers( Assume suitable representation), Device an algorithm to print the cross product of N sets, N known at runtime. complexity?
----------------------------------------------------------------------------------------------------
23)Algo to compute determinant of an array[N][N]
----------------------------------------------------------------------------------------------------
24) Array of size N is given, N is even. In this array one entry is repeated n/2 times and the remaining n/2 entries are unique. Write algo to find the repeated value. Complexity?
----------------------------------------------------------------------------------------------------
25)Given an array which represents a tree. Find out the distance between two elements. Distance between tree-nodes is length of their path from one to other through root. Assume array is represented as heap.
----------------------------------------------------------------------------------------------------
26)Convert a tree into doubly linked list such that the elements in the list are in order same as inorder traversal of tree.
------------------------------------------------------------------------------------------ ----------
27)write a program for Intersection of two sets for general data structures in O(nlogn) complexity or if u can minimise the complexity lower than that it would be great..
----------------------------------------------------------------------------------------------------
28) Can any one come up with generic solution for structurally unique binary search trees if yu are give a set of numbers?
( http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtaln5.html)
----------------------------------------------------------------------------------------------------
29)Compute the minimum (min) or maximum (max) of two integers without branching
int x;  // we want to find the min,max of x and y
int y;
int r;  // the result goes here
r = x - ((x - y) & -(x < y)); // max(x, y)
r = y + ((x - y) & -(x < y)); // min(x, y)
----------------------------------------------------------------------------------------------------
30)int v;      // we  want to find the absolute value of v
int r;      // the result goes here

r = (v ^ (v >> (sizeof(int) * CHAR_BIT - 1))) -
   (v >> (sizeof(int) * CHAR_BIT - 1));
----------------------------------------------------------------------------------------------------
30)Compute the sign of an integer
int v;      // we want to find the sign of v
int sign;   // the result goes here
// CHAR_BIT is the number of bits per byte (normally 8).
sign = v >> (sizeof(int) * CHAR_BIT - 1); // if v < 0 then -1, else 0.
----------------------------------------------------------------------------------------------------
31)Determining if an integer is a power of 2
unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here
f = (v & (v - 1)) == 0;
Note  that 0 is incorrectly considered a power of 2 here. To remedy this, use:
f = !(v & (v - 1)) && v;
----------------------------------------------------------------------------------------------------
32)Reverse bits the obvious way
unsigned int v;           // reverse the bits in this
unsigned int t = v << 1;  // t will have the reversed bits of v
int i;
v >>= 1;
for (i = sizeof(v) * CHAR_BIT - 2; i; i--)
{
 t |= v & 1;
 t <<= 1;
 v >>= 1;
}
t |= v;
( good link-> http://graphics.stanford.edu/~seander/bithacks.html)
----------------------------------------------------------------------------------------------------
33) Reverse an N-bit quantity in parallel in 5 * lg(N) operations:

unsigned int v; // 32  bit word to reverse bit order

int const S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
int const B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};

v = ((v >> S[0]) & B[0]) | ((v << S[0]) & ~B[0]); // swap odd and even bits
v = ((v >> S[1]) & B[1]) | ((v << S[1]) & ~B[1]); // swap consecutive pairs
v = ((v >> S[2]) & B[2]) | ((v << S[2]) & ~B[2]); // swap nibbles ...
v = ((v >> S[3]) & B[3]) | ((v << S[3]) & ~B[3]);
v = ((v >> S[4]) & B[4]) | ((v << S[4]) & ~B[4]);

The following variation is also O(lg(N)), however it requires more operations to reverse v. Its virtue is in taking less memory by computing the table entries on the fly.

unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2
unsigned int mask = ~0;
while ((s >>= 1) > 0)
{
 mask ^= (mask << s);
 v = ((v >> s) & mask) | ((v << s) & ~mask);
}

------------------------------------------------------------------------------------------------------
34)Compute modulus division by 1 << s without a division operator

const unsigned int n;          // numerator
const unsigned int s;
confiltered= 1 << s; // So d will be one of: 1, 2, 4, 8, 16, 32, ...
unsigned int m;                // m will be n % d
m = n & (d - 1);
-------------------------------------------------------------------------------------------------------
35)largest sum of contiguous integer
-------------------------------------------------------------------------------------------------------
36)  Given an array of  numbers,How can we find the most frequently occuring element?Without using extra space...
-------------------------------------------------------------------------------------------------------
37)  If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?.learn general approach
-----------------------------------------------------------------------------------------------------
38)absolute value code(2 lines)
-----------------------------------------------------------------------------------------------------
39)Write a routine that prints out a 2-D array in spiral order(o(1)
space)
-----------------------------------------------------------------------------------------------------
40) A version of the "There are three persons X Y Z, one of which always lies".. etc..
-----------------------------------------------------------------------------------------------------
41)An  array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings.
-----------------------------------------------------------------------------------------------------
42) Given a list of numbers ( fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).
------------------------------------------------------------------------------------------------------
43)http://www.blackboxjobs.com/show/?co=7e4bf9b5-877d-4ad1-9a09-6d973fcff699
http://wiki.mattgoyer.com/Wiki.jsp?page=Interviews

   Plain Text Attachment     [  Scan and Save to Computer       |   Save to Yahoo! Briefcase      ]


1).merge two height balanced binary trees to get another height
balanced
 binary tree.
--------------------------------------------------------------------------------------------
2).given an unsorted array of n integers, find that pair of integers
which gives the maximum sum.
--------------------------------------------------------------------------------------------
3) slight modification.(use heap)
 find the maximum sum giving combination of k integers.
--------------------------------------------------------------------------------------------
4)sudoku solver
--------------------------------------------------------------------------------------------
5)How do you find a loop in a linked list?

               1) ptr method
               2) Go on reversing the linked list.
                     Ifyou reach the head again, the list has a loop
--------------------------------------------------------------------------------------------
6) construct a n element binary tree from its inorder and preorder
traversals kept in two arrays A[n] and B[n].
{ u can get the roots of each subtree in preorder array. Then we can
Partion the inorder array into left and right subtrees. Thus this problem
can be solved recursively...}

--------------------------------------------------------------------------------------------
7)we are given the answers to a crossword puzzzle...we need to generate
the blocks...that is the question is to be framed..what datastructure
do u think should we use for this????(may be trie,linked list.??)
----------------------------------------------------------------------------------------------------
8)how can v reverse a sentence.its not string reversal
example;
given input "this is me"
the output should b "me is this"
{Use a stack !! first "push" every word in correct order.. then "pop"
them out... the resulting string will be in reverse order !}
----------------------------------------------------------------------------------------------------
9)def. of tree,graph,linked list.nd many more
----------------------------------------------------------------------------------------------------
10) How do you find a loop in a Binary tree in a most efficient way.
{ by maintaining flag variable in node data.if already traversed ,flag
value z true,otherwise false.
suppose recursive function access the already traversed node,then we
can conclude that this tree z havng loop.}
----------------------------------------------------------------------------------------------------
11) If 'n' is even do n=n/2
Else if 'n' is odd do n=3*n+1.
If you keep on doing above said operations 'n'will converge to 1 at
some point.
You are given a set of numbers (say 65 to 125.Give an efficient soln to
find out which number converges to 1 the quickest.
----------------------------------------------------------------------------------------------------
 12) sort an array having elements only 0 and 1 in O(n)time and sorting
should terminate immediately after array gets sorted.(1. find the first
occurence of
 1. now find the first occurence of 0.
2. when u are having two marker one at first 1 and other at first 0.
swap them.}
----------------------------------------------------------------------------------------------------
13)findout the median of two sorted arrays as if this is one sorted
array with O(1) space constraint.
----------------------------------------------------------------------------------------------------
14)how will you find out that a given binary tree is binary search
tree.
 (inorder traversal nd check 4 sorted nos.)

{  isBST(Node *node){
if(node == NULL)
return TRUE;
if (node->left->data > node->data )
return FALSE;
else
return isBST(node->left);
if(node->right->data < node->data)
return FALSE;
else
return isBST(node->right);
}
----------------------------------------------------------------------------------------------------
15) given two node pointers in a binary tree . find out the closest
common ancestor of the nodes.

{
     int postOrderToFindLCA(elem *root,elem a,elem b)
{
if(root==NULL) return 0;
if(root->left!=NULL)
left=postOrderToFindLCA(root->left);
if(root->right!=NULL)
right=postOrderToFindLCA(root->right);
if(right+left == 2)
{
printf("I am the LCA%d\n",root->id) ;
return 0;
}
if(root->id == a->id || root->id == b->id)
{
return 1;
}
return (left+right);
}
----------------------------------------------------------------------------------------------------
16. Algorithm to swap two words in a given sentence.
Constraint: You can use only one extra char variable
( reverse the whole sentence. then reverse it with delimiter ' '.)
----------------------------------------------------------------------------------------------------
17). Given the root of a binary tree, write a routine to find the depth
of the tree.
 depth ( Tree T)
{
If isnull(T) then return 0;
else return
max(depth(T->right),depth(T>left))+1
}
----------------------------------------------------------------------------------------------------
18)Given the head pointer of a singly linked list, print the contents
of the list in reverse order.
Constraints - O(1) space
 print(node head)
{
if ( head != null)
{
if(head->next == null)
printf("%d",head->element);

print(head->next);

printf("%d",head->element);
}
----------------------------------------------------------------------------------------------------
19) Algorithm to find the number of ones in the binary form of a given
number "n". An efficient method.
#include
main()
{
int x,count=0;
scanf ("%d",&x);
while (x!=0)
{
count++;
x=(x&(x-1));
}
printf (" %d ",count);
}
----------------------------------------------------------------------------------------------------
20)Given a string of length N, find whether there exits an even length
palindrome substring.
----------------------------------------------------------------------------------------------------
21) Given an array arr[a1 a2 ... an b1 b2 ...bn]
Arrange in order arr[a1 b1 a2 b2 .. an bn] in O(n)
----------------------------------------------------------------------------------------------------
22) Given N sets of integers( Assume suitable representation), Device
an algorithm to print the cross product of N sets, N known at runtime.
complexity?
----------------------------------------------------------------------------------------------------
23)Algo to compute determinant of an array[N][N]
------------------------------------------------------------------------------------------ ----------
24) Array of size N is given, N is even. In this array one entry is
repeated n/2 times and the remaining n/2 entries are unique. Write algo to
find the repeated value. Complexity?
----------------------------------------------------------------------------------------------------
25)Given an array which represents a tree. Find out the distance
between two elements. Distance between tree-nodes is length of their path
from one to other through root. Assume array is represented as heap.
----------------------------------------------------------------------------------------------------
26)Convert a tree into doubly linked list such that the elements in the
list are in order same as inorder traversal of tree.
----------------------------------------------------------------------------------------------------
27)write a program for Intersection of two sets for general data
structures in O(nlogn) complexity or if u can minimise the complexity lower
than that it would be great..
----------------------------------------------------------------------------------------------------
28) Can any one come up with generic solution for structurally unique
binary search trees if yu are give a set of numbers?
(http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtaln5.html )
----------------------------------------------------------------------------------------------------
29)Compute the minimum (min) or maximum (max) of two integers without
branching
int x;  // we want to find the min,max of x and y
int y;
int r;  // the result goes here
r = x - ((x - y) & -(x < y)); // max(x, y)
r = y + ((x - y) & -(x < y)); // min(x, y)
------------------------------------------------------------ ----------------------------------------
30)int v;      // we want to find the absolute value of v
int r;      // the result goes here

r = (v ^ (v >> (sizeof(int) * CHAR_BIT - 1))) -
   (v >> (sizeof(int) * CHAR_BIT - 1));
----------------------------------------------------------------------------------------------------
30)Compute the sign of an integer
int v;      // we want to find the sign of v
int sign;   // the result goes here
// CHAR_BIT is the number of bits per byte (normally 8).
sign = v >> (sizeof(int) * CHAR_BIT - 1); // if v < 0 then -1, else 0.
----------------------------------------------------------------------------------------------------
31)Determining if an integer is a power of 2
unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here
f = (v & (v - 1)) == 0;
Note that 0 is incorrectly considered a power of 2 here. To remedy
this, use:
f = !(v & (v - 1)) && v;
----------------------------------------------------------------------------------------------------
32)Reverse bits the obvious way
unsigned int v;           // reverse the bits in this
unsigned int t = v << 1;  // t will have the reversed bits of v
int i;
v >>= 1;
for (i = sizeof(v) * CHAR_BIT - 2; i; i--)
{
 t |= v & 1;
 t <<= 1;
 v >>= 1;
}
t |= v;
( good link-> http://graphics.stanford.edu/~seander/bithacks.html)
----------------------------------------------------------------------------------------------------
33) Reverse an N-bit quantity in parallel in 5 * lg(N) operations:

unsigned int v; // 32 bit word to reverse bit order

int const S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
int const B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF,
0x0000FFFF};

v = ((v >> S[0]) & B[0]) | ((v << S[0]) & ~B[0]); // swap odd and even
bits
v = ((v >> S[1]) & B[1]) | ((v << S[1]) & ~B[1]); // swap consecutive
pairs
v = ((v >> S[2]) & B[2]) | ((v << S[2]) & ~B[2]); // swap nibbles ...
v = ((v >> S[3]) & B[3]) | ((v << S[3]) & ~B[3]);
v = ((v >> S[4]) & B[4]) | ((v << S[4]) & ~B[4]);

The following variation is also O(lg(N)), however it requires more
operations to reverse v. Its virtue is in taking less memory by computing
the table entries on the fly.

unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2
unsigned int mask = ~0;
while ((s >>= 1) > 0)
{
 mask ^= (mask << s);
 v = ((v >> s) & mask) | ((v << s) & ~mask);
}

------------------------------------------------------------------------------------------------------
34)Compute modulus division by 1 << s without a division operator

const unsigned int n;          // numerator
const unsigned int s;
const unsigned int d = 1 << s; // So d will be one of: 1, 2, 4, 8, 16,
32, ...
unsigned int m;                // m will be n % d
m = n & (d - 1);
-------------------------------------------------------------------------------------------------------
35)largest sum of contiguous integer
-------------------------------------------------------------------------------------------------------
36)  Given an array of numbers,How can we find the most frequently
occuring element?Without using extra space...
-------------------------------------------------------------------------------------------------------
37)  If you had an infinite supply of water and a 5 quart and 3 quart
pail, how would you measure exactly 4 quarts?.learn general approach
-----------------------------------------------------------------------------------------------------
38)absolute value code(2 lines)
-----------------------------------------------------------------------------------------------------
39)Write a routine that prints out a 2-D array in spiral order(o(1)
space)
-----------------------------------------------------------------------------------------------------
40) A version of the "There are three persons X Y Z, one of which
always lies".. etc..
-----------------------------------------------------------------------------------------------------
41)An array of pointers to (very long) strings. Find pointers to the
(lexicographically) smallest and largest strings.
-----------------------------------------------------------------------------------------------------
42) Given a list of numbers ( fixed list) Now given any other list, how
can you efficiently find out if there is any element in the second list
that is an element of the first list (fixed list).

Read More

Longest common subsequence : Dynamic programming

m: A B C B D A B
yn: B D C A B A

The LCS is B C B A

For arbitrary inputs, it is NP-hard. For constant inputs, DP gives the solution in polynomial time ex: O(n^k). Also, there can be more than one LCSs and the solution for that is exponential time ex: O(k^n).

Here we maintain an LCS matrix of m*n size. Initially, for i= 0 or j = 0, LCSij = 0. Then we use the following optimal substructure.

LCSij = 0                                                    for i = 0 or j = 0
          = LCS[i-1,j-1] + 1                            for x[i] = y[j]
          = max(LCS[i-1,j],LCS[i , j-1])          for x[i] != y[j]

I thought of the following on my try which also works:


i

Below is an example from wiki:


    | 0 1 2 3 4 5 6 7
    |   M Z J A W X U
----|-----------------
0   | 0 0 0 0 0 0 0 0
1 X | 0 0 0 0 0 0 1 1
2 M | 0 1 1 1 1 1 1 1
3 J | 0 1 1 2 2 2 2 2
4 Y | 0 1 1 2 2 2 2 2
5 A | 0 1 1 2 3 3 3 3
6 U | 0 1 1 2 3 3 3 4
7 Z | 0 1 2 2 3 3 3 4
So the length of the longest subsequence is 4.


getLongestCommonSubsequence(x, y):
    int lcs[m,n] ;   //2 d array
    for i = 0 to m:
        lcs[i,0] = 0
    for j = 0 to n:
        lcs[0,j] = 0
    for i = 1 to m:
        for j = 1 to n:
            if x[i] = y[j]:
                lcs[i,j] = lcs[i-1,j-1] + 1
            else:
                lcs[i,j] = max(lcs[i-1,j], lcs[i,j-1])


After LCS matrix is calculated in O(n*m) time, we just need to trace back from LCS[n,m] location.


printLCS(lcs, x, y, i, j):
    if i = 0 or j = 0:
        return ""
    else:
        if x[i] = y[j]:
            return printLCS(lcs, x, y, i-1, j-1) + x[i]
        else:
            if lcs[i,j-1] > lcs[i-1,j]:
                return printLCS(lcs, x, y, i, j-1)
            else:
                return printLCS(lcs, x, y, i-1, j)


There can be more than one LCS of the same length. The above would print one of them in O(n+m) time. So by DP, we get one LCS in O(n*m) time.

Step by step example

	0	A	G	C	A	T
0	0	0	0	0	0	0
G	0
A	0
C	0

Read More

GCD and LCM

Finding the GCD
GCD for 60 and 40 is 20: 

60 = 40 * 1 + 20
40 = 20 * 2 + 0

LCM for 60 and 40 is 120:
60*40 / 20

Recursive solution for GCD

int gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)

Iterative solution for GCD

int gcd(a, b):
    while (b != 0): //swap a with b, and b with a%b
        temp = a%b
        a = b
        b = t
    return a

Finding the LCM
Method1 : Using GCD

int lcm(a, b):
    return (a*b)/gcd(a, b)

Method 2:
Solution: least common multiple (LCM) is the lowest value that is a multiple of both integers. That means LCM is divisible by both integers or the modulus of LCM divided by either integers is 0 (LCM % num = 0). Thus, we just need to start with a reasonable number and keep increasing that number until it is divisible by both integers. The number is then the LCM of the integers.

But where is the reasonable number to start out? Well, instead of starting out at 1, we can start out at the highest integer between the two integers. The reason is that a number that is less than either of those two integers can't be divisible by those integers. For example, if we are to find LCM of 2 and 3, then any number that is less than 3 is surely not the LCM. Thus, we can safely start our search at 3. Notice that one integer can be the LCM of another integer. That's why we start out at the higher number. For example, the LCM of 2 and 4 is 4. Here is the algorithm in C:

int lcm(int num1, int num2)
  {
    if (num1 % num2 == 0)
      return num1;

    if (num2 % num1 == 0)
      return num2;
      
    int n = (num1 <= num2) ? num2 : num1;
    
    for (; ; n++)
    {
      if(n % num1 == 0 && n % num2 == 0)
         return n;
    }
  }

Explanation: our function takes two integers as arguments and returns the LCM of those integers.

1. First, we take the modulus of the first integer (num1) and the second integer (num2). If num1 % num2 equals 0, we know num1 is the LCM because num1 is divisible by num1 and is the smallest number that is not less than num1 and num2. Similarly, if num2 % num1 equals 0 then num2 is the LCM.
2. When neither integer is the LCM, we find out which integer is greater and begin to find the LCM starting from that integer. That's exactly what the for loop does. For every iteration, we increase n by 1 until we find a number that divisible by both num1 and num2. This loop guarantees to find the solution. That's why we don't need any other return statement outside the loop. Nor we need a termination condition for the loop.

Read More

External Sorting - How do you sort a million 32-bit integers in 2MB RAM?

A million 32-bit integers is 4MB. We cannot fit them all in the given RAM size and we have to do external sorting. It is an open ended question which is interactive.

Let's assume that -

• The list of numbers is on disk (as we cannot fit them all in RAM).
  
• There is a sort function which sorts the given list effectively i.e. we do not have to worry about a particular sorting algorithm.
  
• There is lots of disk space. 
• As we are short on RAM, the time complexity is not a constraint. This is an important one.
  

I would:
- divide the list into manageable sizes (in this case, it would be 250,000 numbers of 1MB).
- sort the list, save it on the disk and continue with other list.
- then do an m-way merge on the sorted lists.

m-way (or n-way) merge:

If you have m lists, and every one is sorted, then from the beginning of the lists pick the smallest from one of the list, fetch the next element in that same list. Continue till all elements from all m lists are exhausted. Just like the 2-way merge in merge sort.

This particular m-way merge step is quite inefficient and for m lists containing n/m elements each, it results in O(m*n) time. This is where I realized that time complexity is not important. However, we can maintain a min-heap of the front elements of the m lists and can achieve a time of O(logm) for selecting the smallest - delete the smallest element from the min-heap, insert the next element into the min-heap, each operation takes O(logm) time. So the m-way (n-way) merge for m lists and n elements would take O(logm *n) time. Also, we can read a chunk of size (n/m*m) for each list into memory and so at any time, we have total of n/m elements in memory. 

Read More

maximum index of an array

Space for
200,000,000 integers : 800MB
256,000,000 integers : 1024MB
Integer.MAX_VALUE (2,147,483,647) : ~8600MB
Integer.MAX_VALUE/2 (1,073,741,823) : ~4300MB


//arrayindextest.java
class arrayindextest {
    public static void main(String[] args) {
        int[] a = new int[256000000]; //or 200000000
        System.out.println(a.length);
    }
}


-Xmx set max heap size flag
-Xms set min heap size flag

200,000,000 integers : 800MB
With new int[200000000]:
java -Xms32m -Xmx1024m arrayindextest
200000000

256,000,000 integers : 1024MB
With new int[256000000]:
java -Xms32m -Xmx1024m arrayindextest
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Integer.MAX_VALUE (2,147,483,647) : ~8600MB
With new int[Integer.MAX_VALUE]:
Exception in thread "main" java.lang.OutOfMemoryError: Requested array size exceeds VM limit

Integer.MAX_VALUE/2 (1,073,741,823) : ~4300MB
With new int[Integer.MAX_VALUE/2]:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

If setting the max heap size to 2048MB:
java -Xms32m -Xmx2048m arrayindextest
Error occurred during initialization of VM
Could not reserve enough space for object heap
Could not create the Java virtual machine.


Since array index is int (or anything that can be converted to int) and not long, one should be able to create an array of Integer.MAX_VALUE size IF one can "reserve enough space for object heap".

Read More

Missing integers

If you have a cheap mainstream commodity hardware consisting of a decent processor and 1GB RAM, how would you find a few (more than one) missing integers in a list saved on disk containing all of the unique 2^32 integers?

One approach is to use an array of boolean flags and marking them as true for present integers (index of the array denotes flag for the integer). Traversing the flags array again would give the missing integers.

However, 2^32 integers each of 4B require 16GB of space alone. A boolean array for 2^32 locations each of 1B would be 4GB. We can deal with the integers list by reading manageable chunks as we need it in memory only to set the flags i.e. we do not need it completely in memory. But, if we cannot save the flags completely in memory, we have to divide it to manageable parts and make numerous passes through the list which is tedious.

The trick for managing the flags array would be to use a bit as a flag and do bit wise operations for setting and getting the bits. Using bits as flags for 2^32 locations would require only 512MB (8 times less than boolean array).

For setting the nth bit in int x, we OR x with 2^n.


set bit 6
76543210
00001000 = x
01000000 = 2^6
01001000 = x | 2^6 //new x

setBit(x, pos)
    x = x | 2^pos


Unsetting the nth bit in x, we AND x with an operand with only the nth bit unset.


unsetBit(x, pos)
    x = x & (2^8 -1 - 2^pos)

unset bit 6
76543210
01001000 = x
11111111 = 2^8 -1 // all 1s
01000000 = 2^6
10111111 = (2^8 -1 - 2^6) //operand with nth bit unset
00001000 = x & (2^8 -1 - 2^6) //new x


One thing to note is that, ORing anything lesser than int would implicitly promote the operands to int. On using char (2B), which can be treated as unsigned, too many implicit conversions might result in an Out of Memory exception. 

For any number k and m bits for datatype used as flag (for signed or unsigned int, m = 31 or 32), appropriate location in the flags array is k/m and the appropriate bit within that location is k%m. I used m = 31 as Java does not have unsigned int.

Algorithm:

• Read manageable chunks of integers from the list 
• Populate the flags array using setbit() method for the read chunks
  
• While traversing the flags array, traverse each of the bits of the flag to find the missing integers (see below)
  

int m = 31 // bits per flag i.e. signed int
for (int i = 0; i < flags.length; i++):
    for (j = m-1; j >= 0; j--):
        if flags[i] & 2^j == 0:
            print i*m +j //missing


Note: In Java, we have to set the max / min Java heap size (-Xmx) at runtime and since array indexes are positive integers only, we can have an array of maximum size Integer.MAX_VALUE i.e. 2^31 -1 (this can different for other languages).

Read More

print combinations

All possible combinations of a 3 digit binary number are 2c1 * 2c1 * 2c1 = 8 (000, 001, 010, 011, 100, 101, 110, 111). Each digit can be 0 or 1 so 2c1. Below is the code for it.

Starting with 000, we get the next combination by incrementing the LSbs and carrying out the ripple effect with the for loop.


void printCombinations(int digits):
    char[] out = new char[digits]

    for (int i = 0; i < out.length; i++):
        out[i] = '0'

    while (true):
        print(out)
       
        int i
        for(i = out.length -1; i >= 0; i--):
            if (out[i] == '0'):
                out[i] = '1'
            else if (out[i] == '1'):
                out[i] = '0'
                continue
            break
       
        if (i == -1):
            break


If each digit can have more values (for decimal 0 to 9, or characters A B C ... Z), the if-else would change (better with a mapping function). There is a (intuitive, simple) recursive solution too but recursion is a overhead for large combinations.


printCombinations_Recursive (char[] out, int index):
    if (index == out.length):
        print(out)
        return
   
    for (int bit = 0; bit <= 1; bit++):
        out[index] = bit //(char) (bit +'0') or a mapping function
        printCombinations_Recursive(out, index + 1)

printRecursiveWrapper (int digits):
    char[] out = new char[digits]
    printCombinations_Recursive(out, 0)

Read More

Trie examples

I mentioned Tries before here and here. I thought of two more popular examples.

Google Suggestions (now in production) and Gmail autocomplete logic would be implemented as a Trie (prefix tree).

I could think of two ways this could be done using a Trie.

The first way is to DFS from the current prefix or node to get to all the possible words below. This approach is time-intensive due to its recursive nature and the user probably would not benefit when the Trie is large. Autocomplete features need to be quick as the user probably would have typed the next character by the time the logic would return results. The Gmail autocomplete Trie is client side and small. This approach should be enough.

The Google Suggest Trie is server-side and large. The DFS approach is time-intensive. Here is my take on it - the second way. For the Trie data structure of each node, a list for each node is required (or a set to avoid duplicates) which contains all the words formed while traversing it. While adding a word to the Trie, the list of every node lying on the path is updated with the remaining part of word. For example, if the Trie has 'anon', 'an', 'a', the list of node 'a' would contain 'non' and 'n' (as 'a-non' and 'a-n' are words but not 'no' as 'a-no' is not a word) and the words 'anon' and 'an' can be retrieved from node 'a'. The rough code is mostly same like the first post with slight changes shown below in blue. Although, this approach is space-intensive. For a word of length n, we save n-1 prefixes in Trie (for 'anon', we save 'non', 'on', 'n').


class trieNode:
    trieNode[26] children
    char c
    int countPrefix // words with prefix from root to current node
    int countWord // complete words for this current node
    List words //or set

void addWord(trieNode node, string word):
        //end of the word
        if (word = ""):
            node.countWord = node.countWord +1
            return

        //do stuff with current node
        node.countPrefix = node.countPrefix + 1
        node.words.add(word)
   
        //go to next node
        char first = firstChar(word)
        if (node.children[first] == null):
            node.children[first] = new trieNode()
   
        addWord(node.children[first], firstCharRemoved(word))


The disadvantage with Trie is that since it is a prefix data structure, a word can be looked up only through one of its prefixes. So, the only way to look up a word 'calendar' is through 'c', 'ca' etc. If it was a suffix data structure, a word 'calendar' can be looked up through any of its suffix like 'dar', 'len' etc. An example of suffix data structure would be something similar to autocomplete logic used in Mozilla Firefox's Location bar.


[Hat tip to my thoughts]


--


Another example is to find the distinct words from a text file. At first, I thought of a Hashmap which acts like a boolean array for the words as index. In which case, the time required is O(n) and space required is that of the distinct words. With Trie, the solution is better and elegant in terms of space required (time required is O(n)). In case of words 'anon', 'an', 'a', the Trie formed (''-a-n-o-n) would just need space for a-n-o-n. Thus, the advantages of Trie would show over a Hashmap when many words have overlapping prefixes. Once the Trie is formed, a DFS would print the distinct words as follows.


//do DFS on the trie
StringBuilder sb = new StringBuilder()
dfs(root, sb)


void dfs(trieNode node, StringBuilder sb):
    sb.append(node.c)
   
    if (node.countWord > 0):
        print(sb)
   
    for (trieNode child : node.children)
        if (child != null):
            dfs(child, sb)
   
    sb.length = sb.length -1


Read More

Scrabble algorithm

If you are playing scrabble and you have n letters, what are all the possible words that you can make from these n letters?

It looks as if it would involve permutations and combinations both of the letters or a union of permutations and combinations for n letters. Surprisingly, it is much simpler.

Below are the possible words for letters 'abc'. I have highlighted the patterns in them.

a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba

For n letters, it looks like we have to get permutations of n letters plus permutations of n-1 letters and so on till permutations of each letter which is O(nCn * n^n) + O(nCn-1 * n-1^n-1) + ... O(nC1 * 1^1). The time complexity is quite high.

I think I said simpler. :D 

All possible words for n letters can be obtained by using the permutations algorithm of n letters with a very simple mod. The changes are in blue.


permutation(char[] in):
    //initially, used[] set to false and depth is 0
    permuteWords(in, out, used, 0)

permuteWords(char[] in, buffer out, bool[] used, int depth):
    print out
    if depth = in.length:
        print out
        return
    for (int i = 0; i < in.length; i++):
        if used[i] = true:
            continue
        used[i] = true
        out.append(in[i])
       
        permuteWords(in, used, out, depth +1)
       
        out.length = out.length -1
        used[i] = false


Time complexity is the same as that of permutations O(n^n).

A better way is to have each word added to a list (the list would be created in permutation method and passed as parameter to permuteWords method) for extensions of the problem. 

Possible extensions to this scrabble problem are:

• Find the longest word. 
• Find the word with maximum points given a map of points to each letter.
• You have a dictionary, how would you use it to get the valid words? For this, I would assume that the dictionary has a function like boolean isValidWord(String s) which would indicate if a particular word is valid or not. Here is another interesting thought with the dictionary extension which requires a trie structure. I could use a dictionary, to see if I can bust out of permuting further as mostly not all permutations are going to be valid words. For example, if you have a dictionary implemented as a trie with a function boolean hasPrefix(String s) or hasPrefix(char c) and letters 'aabc' and suppose that the dictionary does not have a trieNode structure a-a, you do not have to permute further for the unused characters 'bc'. Below is the changed code that I came up with (not tested). 
  

Set getValidWordsPermutation(char[] in):
    Set validWords = new HashSet();
    //initially, used[] set to false and depth is 0
    permuteWords(in, out, used, 0, validWords);
    return validWords;

permuteWords(char[] in, buffer out, bool[] used, int depth, Set validWords):
    // if the current prefix is not present in the dictionary, then do not permute further with the rest of the unused letters
    if !dict.hasPrefix(out): //or dict.hasPrefix(out[out.length()])
        return
   
    //if current prefix is a word, add to the set
    if dict.isValidWord(out):
        validWords.add(out)

    if depth = in.length:
        return

    for (int i = 0; i < in.length; i++):
        if used[i] = true:
            continue
        used[i] = true
        out.append(in[i])
       
        permuteWords(in, used, out, depth +1, validWords)
       
        out.length = out.length -1
        used[i] = false


Using the dictionary, only those trieNodes forming valid words possible from the n letters are traversed in the dictionary trie [O(|V|+|E|) time] and not all permutations [O(n^n) time]. If all permutations are valid words OR if there is no such hasPrefix(String s) function for trie, then it takes O(n^n) time - which is better than O(nCn * n^n) + O(nCn-1 * n-1^n-1) + ... O(nC1 * 1^1). 

Read More

Permutations and Combinations of string

Permutations of string:

For a string of length n, there are n! permutations. For string abcd, there are 24 permutations. We would have a wrapper permutation method which takes the string and calls the recursive permute method. The basic idea is that the permutations of string abc are a + permutations of string bc, b + permutations of string ac and so on. The permute method uses a bool[] used to indicate which characters of the string are already used in the buffer out (to avoid repetitions). The variable depth is used to indicate how many characters of the string in are used in the out buffer. When depth would be equal to length of string in, we print the permutation and return.


permutation(char[] in):
    //initially, used[] set to false and depth is 0
    permute(in, out, used, 0)

permute(char[] in, buffer out, bool[] used, int depth):
    if depth = in.length:
        print out
        return
    for (int i = 0; i < in.length; i++):
        if used[i] = true:
            continue
        used[i] = true
        out.append(in[i])
       
        permute(in, used, out, depth +1)
       
        out.length = out.length -1
        used[i] = false


Time efficiency is O(n^n).


Combinations of string:

For a string of length n, there are nCn + nCn-1 + ... + nC1 combinations. For string abc, there are 1 + 3 + 3 = 7 combinations. We would have a wrapper combination method which takes the string and calls the recursive combine method. The basic idea is that the combinations of string abc are a, a + combinations of string bc and so on. We put the character in the buffer, print it and combine from the next character (i +1) as start for the next combine call. For string ab, it would print a, ab, b in that order. Since the if block just returns when start = in.length, we can optimize the code by calling the combine method in the for loop only when i < in.length -1.


combination(char[] in):
    //initially, start is 0
    combine(in, out, 0)
   
combine(char[] in, buffer out, start):
    if start = in.length:
        return
    for (int i = start; i < in.length; i++):
        out.append(in[i])
        print out
       
        combine(in, out, i +1)
       
        out.length = out.length -1


Time efficiency is O(n^n).

Read More

Tries

Trie (pronounced as try even though it stands for tree and retrieval) is a prefix tree data structure. You can read more on it on topcoder and wiki.

Trie mostly has a root node as an empty string ("") and each node has 26 child pointers letters (A to Z) at least. As we add words to it, the trie grows. Here is an example of how a trie looks (from www.danvk.org) after adding a few words to it. Note that the complete words are double rounded.

It is mainly used for longest prefix (ex: IP matching) and for dictionaries pairs. For dictionary it has advantages like spell-checking, other nearest words etc.

Usually, the trie node needs to have the children pointers at the least and it can have more data members as per the problem.


class trieNode {
    trieNode[26] children
    char c //
    int countPrefix // words with prefix from root to current node
    int countWord // complete words for this current node
    meaning // pointer to meanings of this node's word (dictionary)
}

At the minimum, we need the below functions. Depending upon the problem, we add more data members, change the functions.

initialize(trieNode)
addWord(trieNode, word) //called as addWord(root, word)


Efficiency for a building a trie is O(n) for n strings as we have to add all n strings to the trie. For finding a string in a trie, it takes O(l) worst case where l is the length of the string.

Let's take a problem where we want to find the "longest prefix of a given list of strings" for given percentage of strings (i.e longest prefix for 50% of given strings). We would first form the trie with the addWord(root, word) function and then use longestPrefix().

Once the trie is formed, the problem becomes quite simple (like finding the max from a list of numbers). We maintain currPath (path from root to current node i.e. current prefix) and longestPrefix (longest prefix so far). From node's countPrefix and root's countPrefix, we calculate the node's percentage. Based on these two conditions, we change longestPrefix accordingly as we traverse the whole tree by DFS. Note that we first go deep into the tree and then check for conditions as ancestor nodes within the longestPrefix have the same prefixCount (or greater but we prefer longer prefix than greater prefixCount).

class trieNode:
    trieNode[26] children
    char c
    int countPrefix
    int countWord

    addWord(trieNode node, string word) {
        //we are at end of the word
        if (word = ""):
            node.countWord = node.countWord +1
            return

        //do stuff with current node
        node.countPrefix = node.countPrefix + 1
       
        //go to next node 
        char first = firstChar(word)
        if (node.children[first] == null):
            node.children[first] = new trieNode()
       
        addWord(node.children[first], firstCharRemoved(word))
    }

    addWord(trieNode root, List l) {
        for string s in l:
            addWord(root, s)
    }

    string longestPrefix(trieNode root, int percent) {
        StringBuffer currPath = new StringBuffer()
        StringBuffer longestPrefix = new StringBuffer()
        dfs(root, percent, currPath, longestPrefix)
        return longestPrefix.toString()
    }

    dfs(trieNode node, int percent, StringBuffer currPath, StringBuffer longestPrefix) {
        // append node char
        currPath.append(node.c)

        // go as deep as possible as ancestors have the same prefixCount
        // as the child within the longestPrefix
        for trieNode tn in children:
             dfs(tn, percent, currPath, longestPrefix)

        if (node.countPrefix/countPrefixForRoot *100 >= percent):
            if (currPath.length() > longestPrefix.length()):
                longestPrefix.setLength(0)
                longestPrefix.append(currPath)

        // drop last node char
        currPath.deleteCharAt(currPath.length() -1)
    }

}


Longest Prefix problem needs O(n) time to build the trie for n strings. Then it dwindles down to DFS with (O(|V| + |E|) time to find the longest prefix.

Read More

superstring

Some code for superstring given two strings. It assumes that first string is longer than second string. If the lengths of the strings first and second are m and n, it takes O(mn) time (as m >= n, the other two loops run for O(n^2) time). There are three loops, first loop looks for second string within the first string, second loop looks for the second string before the first string and third loop looks for after. A list of results is maintained from which the string which is least lengthy and lexicographically smallest is returned as the superstring. I am not sure if this is the best way.


string getSuperString(char[] first, char[] second):
    list results
    int i, j
   
    // abcdefgh
    // abc -->|
    for i = 0 to first.length-1 :
        for j = 0 to second.length-1 && (i+second.length <= first.length) :
            if second[j] != first[i+j] :
                break
        j--
        if j == second.length-1 : //inner for did not break
            results.add(first) // best case

    //     abcdefgh
    // <--abc
    for i = 1 to second.length-1 :
        for j = i to second.length-1 :
            if second[j] != first[j-i] :
                break
        j--
        if j == second.length-1 : // inner for loop did not break
            results.add(
                second[0..i] + //before
                second [i..second.length-i] + //matched part
                first[j..first.length-j] //after
            )
   
    // abcdefgh
    //       abc -->
    for i = second.length-2 to 0 :
        for j = 0 to i :
            if second[j] != first[first.length-1 -i+j] :
                break
        j--
        if j == i : //inner for did not break
            results.add(
                first[0..first.length-2 -i+j] + //before
                second[0..j] + //matched part
                second[j..second.length-1] //after
            )
   
    results.add(first + second)
    results.add(second + first)
   
    //find string that is least lengthy and lexicographically smallest
    string superstring = results.get(0)
    for curr in results :
        if curr.length <= superstring.length :
            if curr < superstring :
                superstring = curr
   
    return superstring



The second and third loop explained below.

Second loop:

    abcdefgh
<--abcd


for i = 1 to 3
    for j = i to 3
        print i, j, (j-i)


i    j (second)     j-i (first)
-----------------------------------
1    1, 2, 3        0, 1, 2
2    2, 3           0, 1
3    3              0

    012
    abcdefgh
<--abcd
    123

     01
     abcdefgh
<--abcd
     23

      0
      abcdefgh
<--abcd
      3



Third loop:


abcdefgh
     abcd -->


for i = 4-2 to 0
    for j = 0 to i
        print i, j, (8-1 -i+j)


i    j (second)    8-1 -i+j (first)
----------------------------------------
2    0, 1, 2       5, 6, 7
1    0, 1          6, 7
0    0             7

     567
abcdefgh
     abcd -->
     012

      67
abcdefgh
      abcd -->
      01

       7
abcdefgh
       abcd -->
       0

Read More

Find the distinct words from a text file

The data structure of the trie and its addWord() method remains the same.


class trieNode:
    trieNode[26] children
    char c
    int countPrefix // words with prefix from root to current node
    int countWord // complete words for this current node

void addWord(trieNode node, string word):
        //end of the word
        if (word = ""):
            node.countWord = node.countWord +1
            return

        //do stuff with current node
        node.countPrefix = node.countPrefix + 1
       
        //go to next node
        char first = firstChar(word)
        if (node.children[first] == null):
            node.children[first] = new trieNode()
   
        addWord(node.children[first], firstCharRemoved(word))


Another example is to find the distinct words from a text file. At first, I thought of a Hashmap which acts like a boolean array for the words as index. In which case, the time required is O(n) and space required is that of the distinct words. With Trie, the solution is better and elegant in terms of space required, time required is O(length). In case of words 'anon', 'an', 'a', the Trie formed (''-a-n-o-n) would just need space for a-n-o-n. Thus, the advantages of Trie would show over a Hashmap when many words have overlapping prefixes. Once the Trie is formed, a DFS would print the distinct words as follows.


//do DFS on the trie
StringBuilder sb = new StringBuilder()
dfs(root, sb)


void dfs(trieNode node, StringBuilder sb):
    sb.append(node.c)
   
    if (node.countWord > 0):
        print(sb)
   
    for (trieNode child : node.children)
        if (child != null):
            dfs(child, sb)
   
    sb.length = sb.length -1

Read More

DFS and BFS on trees, with and without recurssion

BFS (Breath First Search) with and without recurssion 

DFS with Recursion and without recursion

Read More

Remove duplicates from the sorted array

Problem 

 Remove duplicates from the sorted array

Example
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5] -> [1, 2, 3, 4, 5]

Method 1- using 3 pointers

//using 3 pointers
fixDuplicatesInSortedArray(Integer[] a):
    start = 0
    end = 0
    destination = 0

    while(start < a.length):
        while(end < a.length && a[end] == a[start]):
            end++
        end--
       
        //copy the distinct element
        a[destination] = a[start]
        destination++
       
        start = end + 1
        end = start

    //null out the rest
    while destination < a.length:
        a[destination] = null

    return

Method 2 - using 2 pointers

//using 2 pointers
fixDuplicatesInSortedArray(Integer[] a):
    prev = 0
    curr = 1
   
    while curr < a.length():
        while curr < a.length && a[curr] == c[prev]:
            curr++
        if curr == a.length() break
       
        prev++
        a[prev] = a[curr]
        curr++
   
    //null out the rest
    prev++
    while prev < a.length:
        a[prev] = null
   
    return

Time complexity - O(n) in both cases.

Thanks.

Read More

print all word combinations from phone number

Print all words combinations from phone number.
ex: 111-1111 -> AAA-AAAA, AAA-AAAB ... CCC-CCCC

char charkeyMap(int digit, int position)
ex:
charkeyMap(1, 0) = 'A'
charkeyMap(1, 1) = 'B'
charkeyMap(1, 2) = 'C'


void printCombinations(int[] in):
    char[] out = new char[in.length]
   
    //first combination ex: 111-1111 -> AAA-AAAA
    for(int i = in.length -1; i >= 0; i--):
        out[i] = charkeyMap(in[i], 0)

    int i
    while (true):
        out.print()
        i = in.length - 1;
       
        while (true):
            //if A then B
            if out[i] == charkeyMap(in[i], 0):
                out[i] = charkeyMap(in[i], 1)
                break
           
            //if B then C
            if out[i] == charkeyMap(in[i], 1):
                out[i] = charkeyMap(in[i], 2)
                break
           
            //if C then A and let it loop for the adjacent digit
            if out[i] == charkeyMap(in[i], 2):
                out[i] = charkeyMap(in[i], 0)
                //let it loop
           
            i--
            if i < 0 break
       
        if i < 0 break

Read More

String matching

The naive brute force approach:

It is very simple to code but there are little things to look for (as least I have to) with respect to optimization. The outer loop runs for text, the inner loop runs for pattern with one more condition -  i+ len(pattern) <= len(text).


int bruteForce (text, pattern)
    for (i =0; i < len(text); i++):
        for (j = 0; j < len(pattern) && i+ len(pattern) <= len(text); j++): //instead of i+j < len(text)
            if text[i+j] != pattern[j]:
                break;
        if (j==len(pattern)) return i; //match found
    return -1 //match not found



With i+j < len(text) (2+0 < 3), the inside loop runs this the last, even though not required i.e. i=2 is run.
 
012    i
aab    len(text)= 3
  ax   len(pattern)= 2
  01   j

With i+ len(pattern) <= len(text) (1+2 <= 3), the inside loop runs this the last i.e. i=2 is not run.
 
012   i
aab   len(text)= 3
 ax   len(pattern)= 2
 01   j
 

Update: A simpler way is to run the outer loop for condition: i <= len(text) - len(pattern)

Read More

Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

Problem

Sort a binary array - array containing 0s and 1s in 1 pass. This is also called two color sort.

Example

Input - Binary unsorted array
A = {0,1,1,0,0,1};

Output - binary sorted array
B = {0,0,0,1,1,1}

Solution

This is similar to quicksort partition algorithm. Though normal sorting takes O(n log n) time, but we have to just partition 0 from 1, and hence it should only take time of partitioning - O(n). Lets see how?

We take low at index 0 of array, high at the of the array. Now we will follow this pseudocode:

Pseudocode:

low = 0; 
high = arr.length - 1;

while (low < high) {
    while (arr[low] == 0) {
        low ++;
    }
    while (arr[high] == 1) {
        high --;
    }
    if (arr[low] > arr[high] ) {
        swap arr[low], arr[high]
    }
}

c implementation

int main()
{
 int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
 int N = 18;
 int *low, *high;

 low = arr;//low points to start of arr
 high = arr + N;//high points to end of arr
 while(low <= high)
 {
  while( (low < high) && (*low == 0) )
   low ++;

  while( (low < high) && (*high== 1) )
   high--;

  if( low < high)
  {
   int temp = *low ;
   *low = *high;
   *high = temp;
   low ++;
   high--;
  }
 }
 for(int i=0;i<N;i++)
  printf("%d ",arr[i]);

 return 0;
}

Time complexity:
Since we have to examine each of n input elements, we can't improve on O(n). Also, since the algorithm requires O(1) memory, you can't improve on that either (there's nothing asymptotically better than O(1)).

But it is still better than comparison sorts like quicksort, merge sort. Though the below pseudocode will look like partition method in quicksort, which was also O(n) algorithm.


Thanks.

Read More