Thursday, December 29, 2011

Saving a Binary Search Tree to a File

Describe an algorithm to save a Binary Search Tree (BST) to a file in terms of run-time and disk space complexity. You must be able to restore to the exact original BST using the saved format.

Hint:
Remember the big three tree traversal algorithm? Yes, it’s pre-order, in-order, and post-order traversal. Only one of them is useful for storing a BST.
Assume we have the following BST:

    _30_
   /    \   
  20    40
 /     /  \
10    35  50

In-order traversal
If we do an in-order traversal, we will output 10 20 30 35 40 50. There is no way of telling how the original BST structure looks like, as the following unbalanced BST is one of the possible BST sets from the output 10 20 30 35 40 50.

Post-order traversal:
If we do a post-order traversal, we will output the leaf nodes before its parent node. Specifically, we will output 10 20 35 50 40 30 using post-order traversal. Imagine we’re reading the nodes to construct the tree back. See the problem that we are reading the leaf nodes before its parent? There’s too much trouble to create the child nodes before its parent. Remember that the BST insertion algorithm works by traversing the tree from the root to the correct leaf to insert.
Pre-order traversal:
Pre-order traversal is the perfect algorithm for making a copy of a BST. The output of a pre-order traversal of the BST above is 30 20 10 40 35 50. Please note the following important observation:

A node’s parent is always output before itself.

Therefore, when we read the BST back from the file, we are always able to create the parent node before creating its child nodes. The code for writing a BST to a file is exactly the same as pre-order traversal.

A Binary Search Tree (BST) is useful for storing phone book records in a memory limited device, such as a cell phone. The records are always maintained in sorted order, inserting and deleting a record takes O(lg n) time (slower than linked list, but much better than array).

Reading a BST from a file:
The question now is, how would you reconstruct a BST back from the file? Assume that we have the following pre-order traversal output of the BST earlier: 30 20 10 40 35 50.
Hint:
When we encounter a new node to insert, we should always place it into the first empty space which it will fit using a pre-order traversal. How do we determine the first empty space which a node will fit in? We can use the ordinary BST insertion algorithm, but the run-time complexity will be O(n lg n), since inserting a node takes O(lg n) time. Not efficient enough!
Solution:
Remember my post: Determine if a Binary Tree is a Binary Search Tree (BST)?
We use the same idea here. We pass the valid range of the values from the parent node to its child nodes. When we are about to insert a node, we will check if the insert value is in the valid range. If it is, this is the right space to insert. If it is not, we will try the next empty space. Reconstructing the whole BST from a file will take only O(n) time.

void readBSTHelper(int min, int max, int &insertVal,
                   BinaryTree *&p, ifstream &fin) {
  if (insertVal > min && insertVal < max) {
    int val = insertVal;
    p = new BinaryTree(val);
    if (fin >> insertVal) {
      readBSTHelper(min, val, insertVal, p->left, fin);
      readBSTHelper(val, max, insertVal, p->right, fin);
    }
  }
}
 
void readBST(BinaryTree *&root, ifstream &fin) {
  int val;
  fin >> val;
  readBSTHelper(INT_MIN, INT_MAX, val, root, fin);
}

Further thoughts:
How about storing a binary tree (not BST) to a file? Does the algorithm above works? Why and why not?

Friday, December 23, 2011

Determine if a Binary Tree is a Binary Search Tree (BST)

Source

Write a function isBST(BinaryTree *node) to verify if a given binary tree is a Binary Search Tree (BST) or not.

I have seen this question being asked over again and again at Google, Microsoft, and Amazon‘s interviews, you name it… If you can only prepare one binary tree question for your interview, this is the question you absolutely must know how to answer correctly!
First, you must understand the difference between Binary Tree and Binary Search Tree (BST). Binary tree is a tree data structure in which each node has at most two child nodes. A binary search tree (BST) is based on binary tree, but with the following additional properties:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

This question is a very good interview question, because it really tests your understanding of the definition of BST. Most people will fall to this first trap, and gives the following algorithm:

Assume that the current node’s value is k. Then for each node, check if the left node’s value is less than k and the right node’s value is greater than k. If all of the nodes satisfy this property, then it is a BST.

It sounds correct and convincing, but look at this counter example below: A sample tree which we name it as binary tree (1).

    10
   /  \
  5   15     -------- binary tree (1)
     /  \
    6    20

It’s obvious that this is not a valid BST, since (6) could never be on the right of (10).
Based on BST’s definition, we can then easily devise a brute-force solution:

Assume that the current node’s value is k. Then for each node, check if all nodes of left subtree contain values that are less than k. Also check if all nodes of right subtree contain values that are greater than k. If all of the nodes satisfy this property, then it must be a BST.

Below is the brute force code (though inefficient, but works):

bool isSubTreeLessThan(BinaryTree *p, int val) {
  if (!p) return true;
  return (p->data < val &&
          isSubTreeLessThan(p->left, val) &&
          isSubTreeLessThan(p->right, val));
}
 
bool isSubTreeGreaterThan(BinaryTree *p, int val) {
  if (!p) return true;
  return (p->data > val &&
          isSubTreeGreaterThan(p->left, val) &&
          isSubTreeGreaterThan(p->right, val));
}
 
bool isBSTBruteForce(BinaryTree *p) {
  if (!p) return true;
  return isSubTreeLessThan(p->left, p->data) &&
         isSubTreeGreaterThan(p->right, p->data) &&
         isBSTBruteForce(p->left) &&
         isBSTBruteForce(p->right);
}

Solution:
Here is the much better solution. Instead of examining all nodes of both subtrees in each pass, we only need to examine two nodes in each pass.
Refer back to the binary tree (1) above. As we traverse down the tree from node (10) to right node (15), we know for sure that the right node’s value fall between 10 and +INFINITY. Then, as we traverse further down from node (15) to left node (6), we know for sure that the left node’s value fall between 10 and 15. And since (6) does not satisfy the above requirement, we can quickly determine it is not a valid BST. All we need to do is to pass down the low and high limits from node to node! Once we figure out this algorithm, it is easy to code.

bool isBSTHelper(BinaryTree *p, int low, int high) {
  if (!p) return true;
  if (low < p->data && p->data < high)
    return isBSTHelper(p->left, low, p->data) &&
           isBSTHelper(p->right, p->data, high);
  else
    return false;
}
 
bool isBST(BinaryTree *root) {
  // INT_MIN and INT_MAX are defined in C++'s <climits> library
  return isBSTHelper(root, INT_MIN, INT_MAX);
}

This algorithm runs in O(N) time, where N is the number of nodes of the binary tree. It also uses O(1) space (neglecting the stack space used by calling function recursively).
Alternative Solution:
Another solution is to do an in-order traversal of the binary tree, and verify that the previous value (can be passed into the recursive function as reference) is less than the current value. This works because when you do an in-order traversal on a BST, the elements must be strictly in increasing order. This method also runs in O(N) time and O(1) space.

bool isBSTInOrderHelper(BinaryTree *p, int& prev) {
  if (!p) return true;
  return (isBSTInOrderHelper(p->left, prev) &&
          (p->data > prev) && (prev = p->data) &&
          isBSTInOrderHelper(p->right, prev));
}
 
bool isBSTInOrder(BinaryTree *root) {
  int prev = INT_MIN;
  return isBSTInOrderHelper(root, prev);
}
 

Part 2: How inheritance, encapsulation and polymorphism work in C++

Source

What if we try something even more complicatedBACK TO TOC

The thing is that you can’t. Lets say we try to create even more complicated hierarchy by changing class D from our previous example to inherit from class C.

This will immediately create ambiguous inheritance and the compiler will not hesitate to tell you that this is what happened. This is because now class X will have all members of classes A and C twice. Once it will have it via A-C-F-X branch and once via A-C-D-G-X branch. It will not tell you that there’s a problem immediately. Instead, once you will try to reference one of the members of X inherited from either A or C, g++ will tell you that it has two variations of the same member/method and that it does not know which one of them to call.
This what would be g++ output if you try to compile this file.

main.cc: In function 'int main()':
main.cc:110: error: request for member 'set_a' is ambiguous
main.cc:29: error: candidates are: virtual void A::set_a(int)
main.cc:29: error:                 virtual void A::set_a(int)

All this because I was trying to do x.set_a( 20 ); in line 110.

Few words about C++ constructorsBACK TO TOC

I guess you know what constructors are good for. In light of what we’ve seen, you may ask yourself, who is building all those virtual methods tables and who writes right pointer into the object.
Obviously compiler builds all the virtual methods tables. And constructor is the one who fills in the right virtual methods table. And this is another reason why you cannot call constructor directly – you don’t want to mess up with virtual methods tables.

ConclusionBACK TO TOC

For now, I think we had some very nice insight of what’s going on inside of the objects you create. Hope you find it useful. In case you have something to say, please leave comments here or send me emails to alex@alexonlinux.com.

Part 1: How inheritance, encapsulation and polymorphism work in C++

Source

How inheritance, encapsulation and polymorphism work in C++

Posted on September 18, 2008, 6:15 pm, by Alexander Sandler, under Programming Articles.

Introduction
Encapsulation
How methods work
How overloading works
How mangling solves the problem
Structure and size of the object
How inheritance and polymorphism work
How basic polymorphism works
How multiple inheritance works
Difference between different casting types
Polymorphism and multiple inheritance
What if we try something even more complicated
Few words about C++ constructors
Conclusion

IntroductionBACK TO TOC

Inheritance, encapsulation and polymorphism are undoubtedly the cornerstones of OOP/OOD in general and C++ in particular.
When programming C, it is very easy to remember how things work. You know that when you add an int variable to a structure it mostly grows by four bytes. You know that long is either four or eight bytes long depending on the architecture you’re working with.
Things are less obvious when moving to C++. OOP brings more abstractions to the program. As a result you are no longer sure if a+b sums two numbers or calls some overloaded operator method that concatenates contents of two files together.
In this article, I would like to give you a short insight into what’s going on behind the scenes. In particular we’ll see how the three whales of OOP work in C++.
Things that I am going to show in this article may differ from compiler to compiler. I will talk mostly about g++ (version 4.2.3). Note however, that same ideas apply everywhere.

EncapsulationBACK TO TOC

As you know, encapsulation is a principle by which same entity, the object, encapsulates data and methods that manipulate the data. You may be surprised to find out that underneath, class methods are just plain functions.

How methods workBACK TO TOC

In C++ there’s one fundamental difference between plain functions and class methods. Class methods receive one additional argument and that is the pointer to the object whose data the method is expected to manipulate. I.e. first argument to a method is pointer to this.
To speed things up, C++ developers used single CPU register (ECX/RCX on x86/x86_64) to pass pointer to this, instead of passing it via stack as if it was a regular function argument (no longer true in x86_64).
Otherwise, objects know nothing about methods that operate on them.

How overloading worksBACK TO TOC

Another thing that we have to take care of in C++ is how to distinguish between some_function() and some_class::some_function(). Or between some_class::some_function( int ) and some_class::some_function() I.e. what’s the difference between two methods with the same name that receive different number and type of arguments? What is the difference between method and function that has same name?
Obviously, out of linker, compiler and preprocessor, linker is the one that should be aware of the above difference. This is because we may have some_function() in some distant object file. Linker is the component that should find this distant function and interconnect the call to the function and the actual function. Linker uses function name as a unique identifier of the function.
To make things work, g++ and any other modern compiler, mangles the name of the method/function and makes sure that:

Mangled method name includes name of the class it belongs to (if it belongs to any class).
Mangled method name includes number and type of arguments method receives.
Mangled method name includes namespace it belongs to.

With these three, some_class::some_function() and some_function() will have totally different mangled name. See the following code sample.

01namespace some_namespace
02{
03    class some_class
04    {
05    public:
06        some_class() { }
07        void some_method() { }
08    };
09};
10 
11class some_class
12{
13public:
14    some_class() { }
15    void some_method() { }
16};
17 
18void some_method()
19{
20    int a;
21}

g++ will turn:

void some_class::some_method() into _ZN10some_class11some_methodEv
void some_namespace::some_class::some_method() into _ZN14some_namespace10some_class11some_methodEv
void some_method() into _Z11some_methodv

Adding integer argument to void some_method() will turn it from _Z11some_methodv to _Z11some_methodi.

How mangling solves the problemBACK TO TOC

So when you create two methods with same name, but with different arguments, compiler turns them into two functions with different names. Later, when linker links the code together it doesn’t know that these are two methods of the same class. From linkers standpoint, these are two different functions.

Structure and size of the objectBACK TO TOC

You probably already know that C++ class and good old C structures are nearly the same thing. Perhaps the only difference is that all class members are private unless specified otherwise. On the contrary, all structure members are public.
When looking at the memory layout of the object, it is very similar to C structure.

Differences begin when you add virtual methods. Once you add virtual methods to the class, compiler will create virtual methods table for the class. Then it will place pointer to the table in the beginning of each instance of this class.

Object vs. structure and virtual methods table

So, bear in mind that once your class has virtual methods, each object of this class will be four or eight bytes (depends on whether you have 64-bit support or not) bigger.
Actually, pointer to the virtual methods table does not have to be at the beginning of the object. It is just handy to keep it at the beginning, so g++ and most of the modern compilers do it this way.
Adding virtual methods to the class will also increase amount of RAM your program consumes and its size on your hard drive.

How inheritance and polymorphism workBACK TO TOC

Lets say we have two classes. A and B. Class B inherits from class A.

01#include <iostream>
02 
03using namespace std;
04 
05class A
06{
07public:
08    A() { a_member = 0; }
09    int a_member;
10};
11 
12class B : public A
13{
14public:
15    B() : A() { b_member = 0; };
16    int b_member;
17};
18 
19int main()
20{
21    A *a = new B;
22    a->a_member = 10;
23 
24    return 0;
25}

The interesting thing to notice here is that a actually points to instance of class B. When dereferencing a_member, we’re actually dereferencing a_member that defined in class A, but belongs to class B (via inheritance). To make this happen, compiler has to make sure that common part of both classes (a_member in our case) located at the same offset in the object.

Now what if we have some virtual methods.

How basic polymorphism worksBACK TO TOC

Let’s change our example a bit and add some virtual methods.

01#include <iostream>
02 
03using namespace std;
04 
05class A
06{
07public:
08    A() { a_member = 0; }
09    virtual int reset() { a_member = 0; }
10    void set_a_member( int a ) { a_member = a; }
11    int get_a_member() { return a_member; }
12protected:
13    int a_member;
14};
15 
16class B : public A
17{
18public:
19    B() : A() { b_member = 0; };
20    virtual int reset() { a_member = b_member = 0; }
21    virtual void some_virtual_method() { }
22    void set_b_member(int b ) { b_member = b; }
23    int get_b_member() { return b_member; }
24protected:
25    int b_member;
26};
27 
28int main()
29{
30    B *b = new B;
31    A *a = b;
32 
33    b->set_b_member( 20 );
34    b->set_a_member( 10 );
35 
36    a->reset();
37 
38    cout << b->get_a_member() << " " << b->get_b_member() <<
39        endl;
40 
41    return 0;
42}

If you compile and run this program it will obviously print “0 0″. But how, you may ask. After all we did a->reset(). Without our understanding of polymorphism we could think that we’re calling method that belongs to class A.
The reason it works is because when compiler sees code that dereferences pointer to A it expects certain internal object structure and when it dereferences pointer to B it expects different object structure. Let us take a look at both of them.

Classes A and B with virtual methods tables

However even more important here is the structure of the virtual methods tables of both classes.

It is because of the virtual methods table structure compilers knows what virtual method to call. When it generates the code that dereferences pointer to A, it expects that first method in the virtual methods table of the object will be pointer to right reset() routine. It doesn’t really care if the pointer actually points to B object. It will call first method of the virtual methods table anyway.

How multiple inheritance worksBACK TO TOC

Multiple inheritance makes things much more complicated. The problem is that when class C inherits from both A and B, we should have both members of class A and class B in the instance of class C.

01#include <iostream>
02 
03using namespace std;
04 
05class A
06{
07public:
08    A() { a_member = 0; }
09protected:
10    int a_member;
11};
12 
13class B
14{
15public:
16    B() { b_member = 0; }
17protected:
18    int b_member;
19};
20 
21class C : public A, public B
22{
23public:
24    C() : A(), B() { c_member = 0; }
25protected:
26    int c_member;
27};
28 
29int main()
30{
31    C c;
32 
33    A *a1 = &c;
34    B *b1 = &c;
35 
36    A *a2 = reinterpret_cast<A *>( &c );
37    B *b2 = reinterpret_cast<B *>( &c );
38 
39    printf( "%p %p %p\n", &c, a1, b1 );
40    printf( "%p %p %p\n", &c, a2, b2 );
41 
42    return 0;
43}

Once we cast pointer to class C into class B, we cannot keep the value of the pointer as is because first fields in the object occupied by fields defined in class A (a_member). Therefore, when we do casting we have to do a very special kind of casting – the one that changes the actual value of the pointer.
If you compile and run above code snippet, you will see that all the values are the same except for b1, which should be 4 bytes bigger than other values.

This is what (C style casting in our case) casting does – it increments the value of the pointer to make sure that it points to the beginning of the, inherited from B, part of the object.
In case you wonder what other types of casting will do, here is a short description.

Difference between different casting typesBACK TO TOC

There are five types of casting in C++.

reinterpret_cast<>()
static_cast<>()
dynamic_cast<>()
const_cast<>()
C style cast.

I guess you know already what const_cast<>() does. Also, it is only a compile time casting. C style cast is same as static_cast<>(). This leaves us with three types of casting.

reinterpret_cast<>()
static_cast<>()
dynamic_cast<>()

From the above example we learn that reinterpret_cast<>() does nothing to the pointer value and leaves it as is.
static_cast<>() and dynamic_cast<>() both modify value of the pointer. The difference between two is that the later relies on RTTI to see if the casting is legal – it looks inside the object to see if it truly belongs to the type we’re trying to cast from. static_cast<>() on the other hand, simply increments the value of the pointer.

Polymorphism and multiple inheritanceBACK TO TOC

Things getting even more complicated when we have virtual methods in each one of the classes A, B and C that we already met. Let’s add following virtual methods to the classes.

virtual void set_a( int new_a ) { a_member = new_a; }

To class A.

virtual void set_b( int new_b ) { b_member = new_b; }

To class B and

virtual void set_c( int new_c ) { c_member = new_c; }

To class C.

Dual inheritance with virtual methods table

You could have assumed that even in this case class C objects will have only one virtual tables methods, but this is not true. When you static_cast class C object into class B object, class B object must have its own virtual tables method. If we want to use same casting method as with regular objects (that is adding few bytes to the pointer to reach right portion of the object), then we have no choice but to place another virtual tables method in the middle of the object.

As a result, you can have many different virtual methods tables for the same class. The above diagram shows very simple case of inheritance and the truth is that it does not get more complicated than this. Take a look at the following, more complex, class hierarchy.

It may surprise you, but structure of the class X object will be quiet simple. In our previous example inheritance hierarchy had two branches. This one has three:

A-C-F-X
D-G-X
B-E-H-X

All end up with X of course. They are a little longer than in our previous example, but there is nothing special about them. The structure of the object will be the following:

Structure of derivative of the hierarchy

As a rule of thumb, g++ (and friends) calculates the branches that lead to the target class, class X in our case. Next it creates a virtual methods table for each branch and places all virtual methods from all classes in the branch into virtual methods table. This includes pointer to virtual methods of the class itself.
If we project this rule onto our last example. A-C-F-X branch virtual methods table will include pointers to virtual methods from classes A, C, F and X. Same with other two branches.

When should static_cast, dynamic_cast and reinterpret_cast be used?

Source

static_cast is the first cast you should attempt to use. It does things like implicit conversions between types (such as int to float, or pointer to void*), and it can also call explicit conversion functions (or implicit ones). In many cases, explicitly stating static_cast isn't necessary, but it's important to note that the T(something) syntax is equivalent to (T)something and should be avoided (more on that later). A T(something, something_else) is safe, however, and guaranteed to call the constructor.
static_cast can also cast through inheritance hierarchies. It is unecessary when casting upwards (towards a base class), but when casting downwards it can be used as long as it doesn't cast through virtual inheritance. It does not do checking, however, and it is undefined behavior to static_cast down a hierarchy to a type that isn't actually the type of the object.

const_cast can be used to remove or add const to a variable; no other C++ cast is capable of removing it (not even reinterpret_cast). It is important to note that using it is only undefined if the orginial variable is const; if you use it to take the const of a reference to something that wasn't declared with const, it is safe. This can be useful when overloading member functions based on const, for instance. It can also be used to add const to an object, such as to call a member function overload.
const_cast also works similarly on volatile, though that's less common .

dynamic_cast is almost exclusively used for handling polymorphism. You can cast a pointer or reference to any polymorphic type to any other class type (a polymorphic type has at least one virtual function, declared or inherited). You don't have to use it to cast downwards, you can cast sideways or even up another chain. The dynamic_cast will seek out the desired object and return it if possible. If it can't, it will return NULL in the case of a pointer, or throw std::bad_cast in the case of a reference.
dynamic_cast has some limitations, though. It doesn't work if there are multiple objects of the same type in the inheritance hierarchy (the so-called 'dreaded diamond') and you aren't using virtual inheritance. It also can only go through public inheritance - it will always fail to travel through protected or private inheritance. This is rarely an issue, however, as such forms of inheritance are rare.

reinterpret_cast is the most dangerous cast, and should be used very sparingly. It turns one type directly into another - such as casting the value from one pointer to another, or storing a pointer in an int, or all sorts of other nasty things. Largely, the only guarantee you get with reinterpret_cast is that if you cast the result back to the original type, you will get the same value. Other than that, you're on your own. reinterpret_cast cannot do all sorts of conversions; in fact it is relatively limited. It should almost never be used (even interfacing with C code using void* can be done with static_cast).

C casts are casts using (type)object or type(object). A C-style cast is defined as the first of the following which succeeds:

const_cast
static_cast
static_cast, then const_cast
reinterpret_cast
reinterpret_cast, then const_cast

It can therefore be used as a replacement for other casts in some instances, but can be extremely dangerous because of the ability to devolve into a reinterpret_cast, and the latter should be preferred when explicit casting is needed, unless you are sure static_cast will succeed or reinterpret_cast will fail. Even then, consider the longer, more explicit option.
C-style casts also ignore access control when performing a static_cast, which means that they have the ability to perform an operation that no other cast can. This is mostly a kludge, though, and in my mind is just another reason to avoid C-style casts.
I hope this helps!

Finding all unique triplets that sums to zero

Source

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the set which gives the sum of zero.
For example, given set S = {-1 0 1 2 -1 -4},
One possible solution set is:
(-1, 0, 1)
(-1, 2, -1)
Note that (0, 1, -1) is not part of the solution above, because (0, 1, -1) is the duplicate of (-1, 0, 1). Same with (-1, -1, 2).
For a set S, there is probably no “the” solution, another solution could be:
(0, 1, -1)
(2, -1, -1)

This is also known as the 3sum problem. The 3sum problem is the extension of the problem below:

Given a set S of n integers, find all pairs of integers of a and b in S such that a + b = k?

The above problem can be solved in O(n) time, assuming that the set S is already sorted. By using two index first and last, each pointing to the first and last element, we look at the element pointed by first, which we call A. We know that we need to find B = k – A, the complement of A. If the element pointed by last is less than B, we know that the choice is to increment pointer first by one step. Similarly, if the element pointed by last is greater than B, we decrement pointer last by one step. We are progressively refining the sum step by step. Since each step we move a pointer one step, there are at most n steps, which gives the complexity of O(n).
By incorporating the solution above, we can solve the 3sum problem in O(n^2) time, which is a straight forward extension.

set<vector<int> > find_triplets(vector<int> arr) {
  sort(arr.begin(), arr.end());
  set<vector<int> > triplets;
  vector<int> triplet(3);
  int n = arr.size();
  for (int i = 0;i < n; i++) {
    int j = i + 1;
    int k = n - 1;
    while (j < k) {
      int sum_two = arr[i] + arr[j];
      if (sum_two + arr[k] < 0) {
        j++;
      } else if (sum_two + arr[k] > 0) {
        k--;
      } else {
        triplet[0] = arr[i];
        triplet[1] = arr[j];
        triplet[2] = arr[k];
        triplets.insert(triplet);
        j++;
        k--;
      }
    }
  }
  return triplets;
}

Note that a set is chosen to store the triplets, because we are only interested in unique triplets. Since the set S is already sorted, and we don’t look back as it progresses forward, we can guarantee there will be no duplicate triplets (Even though the set might have duplicate elements.)

Friday, December 16, 2011

Maximum Length Bitonic Subarray

Source

Given an array A[0 ... n-1] containing n positive integers, a subarray A[i ... j] is bitonic if there is a k with i <= k <= j such that A[i] <= A[i + 1] ... <= A[k] >= A[k + 1] >= .. A[j - 1] > = A[j]. Write a function that takes an array as argument and returns the length of the maximum length bitonic subarray.
Expected time complexity of the solution is O(n)
Simple Examples
1) A[] = {12, 4, 78, 90, 45, 23}, the maximum length bitonic subarray is {4, 78, 90, 45, 23} which is of length 5.
2) A[] = {20, 4, 1, 2, 3, 4, 2, 10}, the maximum length bitonic subarray is {1, 2, 3, 4, 2} which is of length 5.
Extreme Examples
1) A[] = {10}, the single element is bitnoic, so output is 1.
2) A[] = {10, 20, 30, 40}, the complete array itself is bitonic, so output is 4.
3) A[] = {40, 30, 20, 10}, the complete array itself is bitonic, so output is 4.
Solution
Let us consider the array {12, 4, 78, 90, 45, 23} to understand the soultion.
1) Construct an auxiliary array inc[] from left to right such that inc[i] contains length of the nondecreaing subarray ending at arr[i].
For for A[] = {12, 4, 78, 90, 45, 23}, inc[] is {1, 1, 2, 3, 1, 1}
2) Construct another array dec[] from right to left such that dec[i] contains length of nonincreasing subarray starting at arr[i].
For A[] = {12, 4, 78, 90, 45, 23}, dec[] is {2, 1, 1, 3, 2, 1}.
3) Once we have the inc[] and dec[] arrays, all we need to do is find the maximum value of (inc[i] + dec[i] – 1).
For {12, 4, 78, 90, 45, 23}, the max value of (inc[i] + dec[i] – 1) is 5 for i = 3.

#include<stdio.h>
#include<stdlib.h>
 
int bitonic(int arr[], int n)
{
    int i;
    int *inc = new int[n];
    int *dec = new int[n];
    int max;
    inc[0] = 1; // The length of increasing sequence ending at first index is 1
    dec[n-1] = 1; // The length of increasing sequence starting at first index is 1
 
    // Step 1) Construct increasing sequence array
    for(i = 1; i < n; i++)
    {
        if (arr[i] > arr[i-1])
            inc[i] = inc[i-1] + 1;
        else
            inc[i] = 1;
    }
 
    // Step 2) Construct decreasing sequence array
    for (i = n-2; i >= 0; i--)
    {
        if (arr[i] > arr[i+1])
            dec[i] = dec[i+1] + 1;
        else
            dec[i] = 1;
    }
 
    // Step 3) Find the length of maximum length bitonic sequence
    max = inc[0] + dec[0] - 1;
    for (i = 1; i < n; i++)
    {
        if (inc[i] + dec[i] - 1 > max)
        {
            max = inc[i] + dec[i] - 1;
        }
    }
 
    // free dynamically allocated memory
    delete [] inc;
    delete [] dec;
 
    return max;
}
 
/* Driver program to test above function */
int main()
{
    int arr[] = {12, 4, 78, 90, 45, 23};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("\n Length of max length Bitnoic Subarray is %d", bitonic(arr, n));
    getchar();
    return 0;
}

Time Complexity: O(n)
Auxiliary Space: O(n)

tHe puZZlingG wOrlD

Thursday, December 29, 2011

Saving a Binary Search Tree to a File

Friday, December 23, 2011

Determine if a Binary Tree is a Binary Search Tree (BST)

Part 2: How inheritance, encapsulation and polymorphism work in C++

Source

What if we try something even more complicatedBACK TO TOC

Few words about C++ constructorsBACK TO TOC

ConclusionBACK TO TOC

Part 1: How inheritance, encapsulation and polymorphism work in C++

How inheritance, encapsulation and polymorphism work in C++

Table of contents

IntroductionBACK TO TOC

EncapsulationBACK TO TOC

How methods workBACK TO TOC

How overloading worksBACK TO TOC

How mangling solves the problemBACK TO TOC

Structure and size of the objectBACK TO TOC

How inheritance and polymorphism workBACK TO TOC

How basic polymorphism worksBACK TO TOC

How multiple inheritance worksBACK TO TOC

Difference between different casting typesBACK TO TOC

Polymorphism and multiple inheritanceBACK TO TOC

When should static_cast, dynamic_cast and reinterpret_cast be used?

Finding all unique triplets that sums to zero

Friday, December 16, 2011

Maximum Length Bitonic Subarray