How to delete a node in the singly link list ?

Given a pointer to a node in a singly linked list, how do you delete the node ?
A simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires pointer to the head node which contradicts the problem statement.
Fast solution is to copy the data from the next node to the node to be deleted and delete the next node. Something like following.

    struct node *temp  = node_ptr->next;
   node_ptr->data  = temp->data;
   node_ptr->next  = temp->next;
   free(temp);

In java, the code would look something like this :

1	public void deleteNode(Node node){

2	Node temp = node.next;

3	node.data = temp.data;

4	node.next = temp.next;

5	//do nothing with temp and let the garbage collector remove it

6

}

Continue

Vertical sum of binary tree

Find vertical sum of given binary tree.

Example:

Code:

     1
   / \
 2     3
/ \   / \
4   5 6   7

The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4
Vertical-2: nodes-2 => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3 => vertical sum is 3
Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7

We can do an inorder traversal and hash the column. We call Traverse(root, 0) which means the root is at column 0. As we are doing our traversal, we can hash the column and increase its value by T.data. A rough sketch of my function looks like this -

Traverse(Tree T, int column)
{
if(T==NULL) return;
Traverse(T.left, column-1);
Hash(column) += T.data;
Traverse(T.right, column+1);
}

Traverse(root, 0);
Print Hash

Continue

Card shuffle

Write a program to shuffle an pack of cards in the most efficient way. This question can be asked in several flavors.
Knuth Shuffle / Fisher-Yates Shuffle(Modified version by Durstenfeld) algorithm is the answer to all the trick questions. So how does this algorithm work ?
Fisher and Yates’ original method was designed to be implemented using pencil and paper, with a precomputed table of random numbers as the source of randomness. Modern approach suggested by – Richard Durstenfeld is as follows:
To shuffle an array a of n elements:

for i from n - 1 downto 1 do
        j ← random integer with 0 ≤ j ≤ i
        exchange a[j] and a[i]

Reduced time complexity to O(n), compared to O(n²) for the naive implementation. A sample java implementation :

01	import java.util.Random;

02

03	static Random rng = new Random();

04	public static void shuffle(int[] array) {

05	// i is the number of items remaining to be shuffled.

06	for (int i = array.length; i > 1; i--) {

07	// Pick a random element to swap with the i-th element.

08	int j = rng.nextInt(i); // 0 <= j <= i-1 (0-based array)

09	// Swap array elements.

10	int tmp = array[j];

11	array[j] = array[i-1];

12	array[i-1] = tmp;

13

}

14

}

Continue

How to connect database with C and CPP ?

I got this tutorial from one site its very helpful hence shared here..... :)

This tutorial show coding how to connect with a database in C++….

This are actual guides

Note:


Quote
Before I start just to introduce some SQL commands and stuff. For starter you had some back grounds on it….

SQL (Structured Query Language) is a fourth-generation language (4GL) that is used to define, manipulate, and control an RDBMS (relational database management system).

DML sublanguage is concerned with commands that can perform operations on data in tables.It provides four commands for data manipulation:

SELECT command retrieves data for queries.

INSERT command adds new rows into a database table.

UPDATE command changes the values of data items in a database table.

DELETE command removes rows from a database table.


And let’s start….

ODBC (Open Database Connectivity)

• A standard interface for connecting from C++ to relational databases
• It allows individual providers to implement and extend the standard with their own ODBC drivers

Here are procedures or rather steps used in the industry in C++ coding for connecting to a database

Steps of the ODBC

• Include Header Files
• Open a Connection to a Database
• Choose an ODBC Driver
• Query the Database
• Creating an ODBC Statement Object
• Executing a Query and Returning an ODBCResultSet Object
• Extracting Data from an ODBCResultSet
• Closing the ODBCResultSet and ODBCStatement
• Importance of closing the connection



Okey, this are actual steps how I connect to a database…definitely I used Oracle database, but I don’t want to further say what version it is. LOL


1. Include the Header Files
# include statements at the beginning of your programs:
#include
#include
#include

2. Open a Connection to a Database
Set the environment handle:
SQLAllocHandle(SQL_HANDLE_ENV, SQL_NULL_HANDLE, &hdlEnv);

Set ODBC Driver version:
SQLSetEnvAttr(hdlEnv,SQL_ATTR_ODBC_VERSION,(void*)SQL_OV_ODBC30);

Set the connection handle:
SQLAllocHandle(SQL_HANDLE_DBC, hdlEnv, &hdlConn);

Connect to the database:
SQLConnect(hdlConn, (SQLCHAR*)dsnName,SQL_NTS,(SQLCHAR*)userID,SQL_NTS, (SQLCHAR*)passwd, SQL_NTS);

3. Choose Driver
•DSN – Data Source Name
•Open the GUI ODBC Administrator (ODBCConfig)
•Choose the appropriate ODBC driver
•Provide a meaningful name to the DSN
•Specify the server and the host string (host string is required if the server is running on a different machine)

4. Query the Database
Querying the database involves the following steps:

–Creating a Statement
SQLAllocHandle(SQL_HANDLE_STMT, hdlDbc, &hdlStmt);
It allocates the memory for the statement handle. The database handle obtained during connection phase is passed as the second argument.

– Executing a Query
SQLExecDirect(hdlStmt, stmt, SQL_NTS);
It executes the query, which is passed in as SQLCHAR* in the second argument.

5. Extract the Data out of the Executed Query

SQLGetData(hStmt,colNum,type,retVal,buffLength,&cbData);
It extracts data from table as void* data and places it in retVal

colNum refers to the column number provided in the SELECT statement in SQLExecDirect()

Type is one of the standard ODBC data types
example: DT_STRING à for a string data type
DT_DOUBLE à for a double data type

buffLength is the estimated size of the expected data

cbData is the actual size of the data

6. Traverse Through the Results
SQLFetch(hStmt);
Fetches the next record

hStmt is the statement handle obtained using SQLAllocHandle
If a record is available, It returns SQL_SUCCEEDED

7. Close the Statement and the Connection
SQLFreeHandle(SQL_HANDLE_STMT, hdlStmt);
It closes and de-allocates the memory reserved for the statement handle

SQLFreeHandle(SQL_HANDLE_DBC, hdlConn);
It disconnects and de-allocates the memory reserved for the connection handle

SQLFreeHandle(SQL_HANDLE_ENV, hdlEnv);
It de-allocates the memory occupied by the environment handle


For further escalate the whole steps here a sample program

//Header files:

#include
#include
#include
...
....

//Declaration:

SQLHandle hdlEnv, hdlConn, hdlStmt, hdlDbc
char* stmt = "SELECT * from NutHead"; //SQL statement NutHead is the Table name

//for example
char *dsnName = “COLLECTOR”  name of your program or what ever…..
char* userID = "eXceed";
char* passwd = "hole";
char* retVal[256];
unsigned int cbData;

SQLAllocHandle(SQL_HANDLE_ENV, SQL_NULL_HANDLE, &hdlEnv);
SQLSetEnvAttr(hdlEnv,SQL_ATTR_ODBC_VERSION,(void*)SQL_OV_ODBC30);
SQLAllocHandle(SQL_HANDLE_DBC, hdlEnv, &hdlConn);
SQLConnect(hdlConn, (SQLCHAR*)dsnName,SQL_NTS,(SQLCHAR*)userID,SQL_NTS, (SQLCHAR*)passwd, SQL_NTS);
SQLAllocHandle(SQL_HANDLE_STMT, hdlDbc, &hdlStmt);
SQLExecDirect(hdlStmt, (SQLCHAR*)stmt, SQL_NTS);


//Initialize the database connection

while(SQLFetch(hdlStmt) == SQL_SUCCEEDED)
{
SQLGetData(hdlStmt,0,DT_STRING,retVal,256,&cbData);
std::cout << retVal << std::endl;
}
SQLFreeHandle(SQL_HANDLE_STMT, hdlStmt);
SQLFreeHandle(SQL_HANDLE_DBC, hdlConn);
SQLFreeHandle(SQL_HANDLE_ENV, hdlEnv); //End the connecti

Continue

How to Rebuild a binary tree from Inorder and Preorder traversals ?

This is a well known problem where given any two traversals of a tree such as inorder & preorder or inorder & postorder or inorder & levelorder traversals we need to rebuild the tree.

The following procedure demonstrates on how to rebuild tree from given inorder and preorder traversals of a binary tree:

• Preorder traversal visits Node, left subtree, right subtree recursively
• Inorder traversal visits left subtree, node, right subtree recursively
• Since we know that the first node in Preorder is its root, we can easily locate the root node in the inorder traversal and hence we can obtain left subtree and right subtree from the inorder traversal recursively

Consider the following example:

Preorder Traversal: 1 2 4 8 9 10 11 5 3 6 7

Inorder Traversal: 8 4 10 9 11 2 5 1 6 3 7

Iteration 1:

Root – {1}

Left Subtree – {8,4,10,9,11,2,5}

Right Subtree – {6,3,7}

Iteration 2:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}

Root – {3} Left Subtree – {6} Right Subtree – {7}

Iteration 3:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}		Root – {3} Left Subtree – {6} Right Subtree – {7}
Root – {4} Left Subtree – {8} Right Subtree – {10,9,11}	Done	Done

Iteration 4:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}			Root – {3} Left Subtree – {6} Right Subtree – {7}
Root – {4} Left Subtree – {8} Right Subtree – {10,9,11}		Done	Done
Done	R – {9} Left ST – {10} Right ST-{11}	Done	Done

The following are the two versions of programming solutions even though both are based on above mentioned algorithm:

• Creating left preorder, left inorder, right preorder, right inorder lists at every iteration to construct tree.
• Passing index of preorder and inorder traversals and using the same input list to construct tree.

Continue

O(1) stack operations.

Design a datastructure to implement a stack such that ALL of push(), pop() and getMax() functions work in O(1) time. You have infinite memory at your disposal.
Also note that function getMax() just returns the element with maximum value in the stack and NOT delete it from the stack like what pop() does.

Insight : compress the information using diff

PUSH :
if stack empty
push(elem)
push(elem)
else
min = pop()
push(elem-min)
push(min)

POP :
min = pop()
elem = pop()
if elem is -ve
   push(min-elem) // earlier min  
    return min
else
   push(min)
    return elem + min 

MIN :
min = pop()
push(min)
return min 

O(n+1) space and  constant operations for pop push min !! 

Continue

A memory Q here..

In file1.c
we have static int i = 5;
and int *ptr = &i;

now value of ptr is written in some file say abc.txt

now file2.c (another program) opens abc.txt
read the value

and print the value loacted at dat adress say
what will be the o/p????


example i = 5;
ptr = &i; ptr has now 0xABFF

0xABFF is written in abc.txt

file2.c opens the abc.txt and read the value 0xABFF

now print the value present at this address
waht it will print????



ANSWER:

A program has nothing to do with RAM but an address space available to it. That is, total amount of memory it can index (on 32 bit systems 2^32). Program is written at the lower level to hold addresses (any of these 2^32 minus some reserved for kernel) within this range irrespective of the amount of RAM you have. Program assume it has and can have whole addresses only for itself. OS and CPU help to map this wide range of addresses to the amount of available RAM in your computer. Thus, the address your pointer holds is an address in this address space (called virtual address).

Even if the same program runs twice your pointer may not be the same (with same value) next time due to various environmental (and your program logic) reasons.

There are programs that store addresses of objects in virtual memory and the links between these objects to a file. But prior to writing they change these addresses to file offsets (thinking now this file to be memory.) Converting memory pointers (addresses) to file offsets and fro is termed 'pointer swizzling.' These programs are in general called 'object stores', and object-oriented databases are on genre of object stores.

The variable being static makes no difference, the code produced by your program may be relinkable and reloadable (relocatable code.)

Continue

Write a C program to insert nodes into a linked list in a sorted fashion

The solution is to iterate down the list looking for the correct place to insert the new node. That could be the end of the list, or a point just before a node which is larger than the new node.

Note that we assume the memory for the new node has already been allocated and a pointer to that memory is being passed to this function.



// Special case code for the head end
void linkedListInsertSorted(struct node** headReference, struct node* newNode)
{
// Special case for the head end
if (*headReference == NULL || (*headReference)->data >= newNode->data)
{
newNode->next = *headReference;
*headReference = newNode;
}
else
{
// Locate the node before which the insertion is to happen!
struct node* current = *headReference;
while (current->next!=NULL && current->next->data <>data)
{
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}


Continue

What is the difference between the stack and the heap? Where are the different types of variables of a program stored in memory?

When a program is loaded into memory, it is organized into three areas of memory, called segments: the text segment, stack segment, and the heap segment. The text segment (sometimes also called the code segment) is where the compiled code of the program itself resides. This is the machine language representation of the program steps to be carried out, including all functions making up the program, both user defined and system.

The remaining two areas of system memory is where storage may be allocated by the compiler for data storage. The stack is where memory is allocated for automatic variables within functions. A stack is a Last In First Out (LIFO) storage device where new storage is allocated and deallocated at only one "end", called the Top of the stack. When a program begins executing in the function main(), space is allocated on the stack for all variables declared within main(). If main() calls a function, func(), additional storage is allocated for the variables in func() at the top of the stack. Notice that the parameters passed by main() to func() are also stored on the stack. If func() were to call any additional functions, storage would be allocated at the new Top of stack. When func() returns, storage for its local variables is deallocated, and the Top of the stack returns to its old position. If main() were to call another function, storage would be allocated for that function at the Top. The memory allocated in the stack area is used and reused during program execution. It should be clear that memory allocated in this area will contain garbage values left over from previous usage.

The heap segment provides more stable storage of data for a program; memory allocated in the heap remains in existence for the duration of a program. Therefore, global variables (storage class external), and static variables are allocated on the heap. The memory allocated in the heap area, if initialized to zero at program start, remains zero until the program makes use of it. Thus, the heap area need not contain garbage.

Continue

How the compiler make difference between C and C++?

Most compilers recognized the file type by looking at the file extension.

You might also be able to force the compiler to ignore the file type by supplying compiler switch. In MS VC++ 6, for example, the MSCRT defines a macro, __cplusplus. If you undefine that macro, then the compiler will treat your code as C code. You don't define the __cplusplus macro. It is defined by the compiler when compiling a C++ source. In MSVC6 there's a switch for the compiler, /Tc, that forces a C compilation instead of C++.

Continue

What are the general steps in compilation?

1. Lexical analysis.
2. Syntactic analysis.
3. Sematic analysis.
4. Pre-optimization of internal representation.
5. Code generation.
6. Post optimization.

Continue

What are the different types of linkages?

Linkage is used to determine what makes the same name declared in different scopes refer to the same thing. An object only ever has one name, but in many cases we would like to be able to refer to the same object from different scopes. A typical example is the wish to be able to call printf() from several different places in a program, even if those places are not all in the same source file.

The Standard warns that declarations which refer to the same thing must all have compatible type, or the behaviour of the program will be undefined. Except for the use of the storage class specifier, the declarations must be identical.


The three different types of linkage are:


* external linkage
* internal linkage
* no linkage



In an entire program, built up perhaps from a number of source files and libraries, if a name has external linkage, then every instance of a that name refers to the same object throughout the program. For something which has internal linkage, it is only within a given source code file that instances of the same name will refer to the same thing. Finally, names with no linkage refer to separate things.

Linkage and definitions

Every data object or function that is actually used in a program (except as the operand of a sizeof operator) must have one and only one corresponding definition. This "exactly one" rule means that for objects with external linkage there must be exactly one definition in the whole program; for things with internal linkage (confined to one source code file) there must be exactly one definition in the file where it is declared; for things with no linkage, whose declaration is always a definition, there is exactly one definition as well.


The three types of accessibility that you will want of data objects or functions are:


* Throughout the entire program,
* Restricted to one source file,
* Restricted to one function (or perhaps a single compound statement).



For the three cases above, you will want external linkage, internal linkage, and no linkage respectively. The external linkage declarations would be prefixed with extern, the internal linkage declarations with static.



#include

// External linkage.
extern int var1;

// Definitions with external linkage.
extern int var2 = 0;

// Internal linkage:
static int var3;

// Function with external linkage
void f1(int a){}

// Function can only be invoked by name from within this file.
static int f2(int a1, int a2)
{
return(a1 * a2);
}

Continue

Write a C program to swap two variables without using a temporary variable

This questions is asked almost always in every interview.

The best way to swap two variables is to use a temporary variable.


int a,b,t;

t = a;
a = b;
b = t;




There is no way better than this as you will find out soon. There are a few slick expressions that do swap variables without using temporary storage. But they come with their own set of problems.


Method1 (The XOR trick)


a ^= b ^= a ^= b;


Although the code above works fine for most of the cases, it tries to modify variable 'a' two times between sequence points, so the behavior is undefined. What this means is it wont work in all the cases. This will also not work for floating-point values. Also, think of a scenario where you have written your code like this



swap(int *a, int *b)
{
*a ^= *b ^= *a ^= *b;
}


Now, if suppose, by mistake, your code passes the pointer to the same variable to this function. Guess what happens? Since Xor'ing an element with itself sets the variable to zero, this routine will end up setting the variable to zero (ideally it should have swapped the variable with itself). This scenario is quite possible in sorting algorithms which sometimes try to swap a variable with itself (maybe due to some small, but not so fatal coding error). One solution to this problem is to check if the numbers to be swapped are already equal to each other.


swap(int *a, int *b)
{
if(*a!=*b)
{
*a ^= *b ^= *a ^= *b;
}
}




Method2

This method is also quite popular


a=a+b;
b=a-b;
a=a-b;


But, note that here also, if a and b are big and their addition is bigger than the size of an int, even this might end up giving you wrong results.



Method3

One can also swap two variables using a macro. However, it would be required to pass the type of the variable to the macro. Also, there is an interesting problem using macros. Suppose you have a swap macro which looks something like this


#define swap(type,a,b) type temp;temp=a;a=b;b=temp;



Now, think what happens if you pass in something like this


swap(int,temp,a) //You have a variable called "temp" (which is quite possible).



This is how it gets replaced by the macro


int temp;
temp=temp;
temp=b;
b=temp;


Which means it sets the value of "b" to both the variables!. It never swapped them! Scary, isn't it?


So the moral of the story is, dont try to be smart when writing code to swap variables. Use a temporary variable. Its not only fool proof, but also easier to understand and maintain.

Continue

How can I sort things that are too large to bring into memory?

A sorting program that sorts items that are on secondary storage (disk or tape) rather than primary storage (memory) is called an external sort. Exactly how to sort large data depends on what is meant by ?too large to fit in memory.? If the items to be sorted are themselves too large to fit in memory (such as images), but there aren?t many items, you can keep in memory only the sort key and a value indicating the data?s location on disk. After the key/value pairs are sorted, the data is rearranged on disk into the correct order. If ?too large to fit in memory? means that there are too many items to fit into memory at one time, the data can be sorted in groups that will fit into memory, and then the resulting files can be merged. A sort such as a radix sort can also be used as an external sort, by making each bucket in the sort a file. Even the quick sort can be an external sort. The data can be partitioned by writing it to two smaller files. When the partitions are small enough to fit, they are sorted in memory and concatenated to form the sorted file.

Continue

What is the difference between Merge Sort and Quick sort?

Both Merge-sort and Quick-sort have same time complexity i.e. O(nlogn). In merge sort the file a[1:n] was divided at its midpoint into sub-arrays which are independently sorted and later merged. Whereas, in quick sort the division into two sub-arrays is made so that the sorted sub-arrays do not need to be merged latter.

Continue

What is heap sort?

A Heap is an almost complete binary tree.In this tree, if the maximum level is i, then, upto the (i-1)th level should be complete. At level i, the number of nodes can be less than or equal to 2^i. If the number of nodes is less than 2^i, then the nodes in that level should be completely filled, only from left to right.

The property of an ascending heap is that, the root is the lowest and given any other node i, that node should be less than its left child and its right child. In a descending heap, the root should be the highest and given any other node i, that node should be greater than its left child and right child.

To sort the elements, one should create the heap first. Once the heap is created, the root has the highest value. Now we need to sort the elements in ascending order. The root can not be exchanged with the nth element so that the item in the nth position is sorted. Now, sort the remaining (n-1) elements. This can be achieved by reconstructing the heap for (n-1) elements.

A highly simplified pseudocode is given below


heapsort()
{
n = array(); // Convert the tree into an array.
makeheap(n); // Construct the initial heap.

for(i=n; i>=2; i--)
{
swap(s[1],s[i]);
heapsize--;
keepheap(i);
}
}

makeheap(n)
{
heapsize=n;
for(i=n/2; i>=1; i--)
keepheap(i);
}

keepheap(i)
{
l = 2*i;
r = 2*i + 1;

p = s[l];
q = s[r];
t = s[i];

if(l<=heapsize && p->value > t->value)
largest = l;
else
largest = i;

m = s[largest];

if(r<=heapsize && q->value > m->value)
largest = r;

if(largest != i)
{
swap(s[i], s[largest]);
keepheap(largest);
}
}


Continue

Can we do a Binary search on a linked list?

Great C datastructure question!

The answer is ofcourse, you can write a C program to do this. But, the question is, do you really think it will be as efficient as a C program which does a binary search on an array?

Think hard, real hard.

Do you know what exactly makes the binary search on an array so fast and efficient? Its the ability to access any element in the array in constant time. This is what makes it so fast. You can get to the middle of the array just by saying array[middle]!. Now, can you do the same with a linked list? The answer is No. You will have to write your own, possibly inefficient algorithm to get the value of the middle node of a linked list. In a linked list, you loosse the ability to get the value of any node in a constant time.

One solution to the inefficiency of getting the middle of the linked list during a binary search is to have the first node contain one additional pointer that points to the node in the middle. Decide at the first node if you need to check the first or the second half of the linked list. Continue doing that with each half-list.

Continue

How do you reverse a linked list without using any C pointers?

One way is to reverse the data in the nodes without changing the pointers themselves. One can also create a new linked list which is the reverse of the original linked list. A simple C program can do that for you. Please note that you would still use the "next" pointer fields to traverse through the linked list (So in effect, you are using the pointers, but you are not changing them when reversing the linked list).

Continue

Demystifying SQL Joins

A SQL JOIN clause combines records from two or more tables in a database. It creates a set that can be saved as a table or used as is. A JOIN is a means for combining fields from two tables by using values common to each. ANSI standard SQL specifies four types of JOINs: INNER, OUTER, LEFT, and RIGHT. In special cases, a table (base table, view, or joined table) can JOIN to itself in a self-join.

All subsequent explanations on join types in this article make use of the following two tables. The rows in these tables serve to illustrate the effect of different types of joins and join-predicates. In the following tables, Department.DepartmentID is the primary key, while Employee.DepartmentID is a foreign key.

Note: The "Marketing" Department currently has no listed employees. Also, employee "John" has not been assigned to any Department yet.

Inner join

An inner join is the most common join operation used in applications, and represents the default join-type. Inner join creates a new result table by combining column values of two tables (A and B) based upon the join-predicate.

SQL specifies two different syntactical ways to express joins: "explicit join notation" and "implicit join notation".

The "explicit join notation" uses the JOIN keyword to specify the table to join, and the ON keyword to specify the predicates for the join, as in the following example:

SELECT *
FROM   employee
      INNER JOIN department
         ON employee.DepartmentID = department.DepartmentID

The "implicit join notation" simply lists the tables for joining (in the FROM clause of the SELECT statement), using commas to separate them. Thus, it specifies a cross-join, and the WHERE clause may apply additional filter-predicates (which function comparably to the join-predicates in the explicit notation).

The following example shows a query which is equivalent to the one from the previous example, but this time written using the implicit join notation:

SELECT *
FROM   employee, department
WHERE  employee.DepartmentID = department.DepartmentID

The queries given in the examples above will join the Employee and Department tables using the DepartmentID column of both tables. Where the DepartmentID of these tables match (i.e. the join-predicate is satisfied), the query will combine the LastName, DepartmentID and DepartmentName columns from the two tables into a result row. Where the DepartmentID does not match, no result row is generated. Thus the result of the execution of either of the two queries above will be:

Thus the result of the execution of either of the two queries above will be:

Outer joins

An outer join does not require each record in the two joined tables to have a matching record. The joined table retains each record—even if no other matching record exists. Outer joins subdivide further into left outer joins, right outer joins, and full outer joins, depending on which table(s) one retains the rows from (left, right, or both).

(In this case left and right refer to the two sides of the JOIN keyword.)

No implicit join-notation for outer joins exists in standard SQL.

Left outer join

The result of a left outer join (or simply left join) for table A and B always contains all records of the "left" table (A), even if the join-condition does not find any matching record in the "right" table (B). This means that if the ON clause matches 0 (zero) records in B, the join will still return a row in the result—but with NULL in each column from B. This means that a left outer join returns all the values from the left table, plus matched values from the right table (or NULL in case of no matching join predicate). If the left table returns one row and the right table returns more than one matching row for it, the values in the left table will be repeated for each distinct row on the right table.

For example, this allows us to find an employee’s department, but still shows the employee(s) even when they have not been assigned to a department (contrary to the inner-join example above, where unassigned employees are excluded from the result).

Example of a left outer join, with the additional result row italicized:

SELECT *
FROM   employee  LEFT OUTER JOIN department
         ON employee.DepartmentID = department.DepartmentID

Right outer joins

A right outer join (or right join) closely resembles a left outer join, except with the treatment of the tables reversed. Every row from the "right" table (B) will appear in the joined table at least once. If no matching row from the "left" table (A) exists, NULL will appear in columns from A for those records that have no match in B.

A right outer join returns all the values from the right table and matched values from the left table (NULL in case of no matching join predicate).

For example, this allows us to find each employee and his or her department, but still show departments that have no employees.

Example right outer join, with the additional result row italicized:

SELECT *
FROM   employee RIGHT OUTER JOIN department
         ON employee.DepartmentID = department.DepartmentID

In practice, explicit right outer joins are rarely used, since they can always be replaced with left outer joins (with the table order switched) and provide no additional functionality. The result above is produced also with a left outer join:

SELECT *
FROM   department LEFT OUTER JOIN employee
         ON employee.DepartmentID = department.DepartmentID

Continue

Majority element in linear time.

A majority element in an array A, of size N is an element that appears more than N/2 times (and hence there is atmost
one such element)
Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:
I/P : 3 3 4 2 4 4 2 4 4
O/P : 4
I/P : 3 3 4 2 4 4 2 4
O/P : NONE

Obvious answer is create a binary search tree. When you get one element insert it. If the element exists increase count by one in the node. After insertion traverse the tree for the required element!

But the real and smart answer is something else.

A Linear Time Majority Vote Algorithm (linear time)

Scan the array elements, while scanning elements maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.
When we move the pointer forward over an element e:
* If the counter is 0, we set the current candidate to e and we set the counter to 1.
* If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.
But if you must confirm that the chosen element is indeed the majority element, you must take one more linear pass through the data to do it.

Continue

What is cycle stealing?

We encounter cycle stealing in the context of Direct Memory Access (DMA). Either the DMA controller can use the data bus when the CPU does not need it, or it may force the CPU to temporarily suspend operation. The latter technique is called cycle stealing. Note that cycle stealing can be done only at specific break points in an instruction cycle.

Continue

What is thrashing?

If the number of frames allocated to a low-priority process falls below the minimum number required by the computer architecture, we must suspend that process' execution. We should then page out its remaining pages, freeing all its allocated frames. This provision introduces a swap-in, swap-out level of intermediate CPU scheduling.


In fact, look at any process that does not have "enough" frames. Although it is technically possible to reduce the number of allocated frames to the minimum, there is some (larger) number of pages in active use. If the process does not have this number of frames, it will quickly page fault. At this point, it must replace some page. However, since all its pages are in active use, it must replace a page that will be needed again right away. Consequently, it quickly faults again, and again, and again. The process continues to fault, replacing pages for which it then faults and brings back in right away.

This high paging activity is called thrashing. A process is thrashing if it is spending more time paging than executing.

Continue

What are turnaround time and response time?

Turnaround time is the interval between the submission of a job and its completion. Response time is the interval between submission of a request, and the first response to that request.

Continue

What is Belady's anomaly?

Usually, on increasing the number of frames allocated to a process' virtual memory, the process execution is faster, because fewer page faults occur. Sometimes, the reverse happens, i.e., the execution time increases even when more frames are allocated to the process. This is known as the Belady's Anomaly. This is true for certain page reference patterns. This is also called the FIFO anomaly.

Continue

What is an AVL tree?

AVL trees are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has O(log n) height and hence O(log n) worst case search and insertion times. However, ordinary binary search trees have a bad worst case. When sorted data is inserted, the binary search tree is very unbalanced, essentially more of a linear list, with O(n) height and thus O(n) worst case insertion and lookup times. AVL trees overcome this problem.

An AVL tree is a binary search tree in which every node is height balanced, that is, the difference in the heights of its two subtrees is at most 1. The balance factor of a node is the height of its right subtree minus the height of its left subtree (right minus left!). An equivalent definition, then, for an AVL tree is that it is a binary search tree in which each node has a balance factor of -1, 0, or +1. Note that a balance factor of -1 means that the subtree is left-heavy, and a balance factor of +1 means that the subtree is right-heavy. Each node is associated with a Balancing factor.


Balance factor of each node = height of right subtree at that node - height of left subtree at that node.



Please be aware that we are talking about the height of the subtrees and not the weigths of the subtrees. This is a very important point. We are talking about the height!.


Here is some recursive, working! C code that sets the Balance factor for all nodes starting from the root....


#include

typedef struct node
{
int value;
int visited;
int bf;
struct node *right;
struct node *left;
}mynode;

mynode *root;

mynode *add_node(int value);
void levelOrderTraversal(mynode *root);
int setbf(mynode *p);


// The main function
int main(int argc, char* argv[])
{
root = NULL;

// Construct the tree..
add_node(5);
add_node(1);
add_node(-20);
add_node(100);
add_node(23);
add_node(67);
add_node(13);

// Set the balance factors
setbf(root);

printf("\n\n\nLEVEL ORDER TRAVERSAL\n\n");
levelOrderTraversal(root);
getch();
}

// Function to add a new node to the tree...
mynode *add_node(int value)
{
mynode *prev, *cur, *temp;

temp = (mynode *) malloc(sizeof(mynode));
temp->value = value;
temp->visited = 0;
temp->bf = 0;
temp->right = NULL;
temp->left = NULL;

if(root==NULL)
{
//printf("\nCreating the root..\n");
root = temp;
return;
}

prev=NULL;
cur=root;

while(cur!=NULL)
{
prev=cur;
cur=(valuevalue)?cur->left:cur->right;
}

if(value <>value)
prev->left=temp;
else
prev->right=temp;

return(temp);

}


// Recursive function to set the balancing factor
// of each node starting from the root!
int setbf(mynode *p)
{
int templ, tempr;
int count;
count = 1;

if(p == NULL)
{
return(0);
}
else
{
templ = setbf(p->left);
tempr = setbf(p->right);

if(templ < tempr)
count = count + tempr;
else
count = count + templ;
}

// Set the nodes balancing factor.
printf("\nNode = [%3d], Left sub-tree height = [%1d], Right sub-tree height = [%1d], BF = [%1d]\n",
p->value, templ, tempr, (tempr - templ));
p->bf = tempr - templ;
return(count);
}



// Level order traversal..
void levelOrderTraversal(mynode *root)
{
mynode *queue[100] = {(mynode *)0};
int size = 0;
int queue_pointer = 0;

while(root)
{
printf("\n[%3d] (BF : %3d) ", root->value, root->bf);

if(root->left)
{
queue[size++] = root->left;
}

if(root->right)
{
queue[size++] = root->right;
}

root = queue[queue_pointer++];
}
}


And here is the output...


Node = [-20], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [ 1], Left sub-tree height = [1], Right sub-tree height = [0], BF = [-1]
Node = [ 13], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [ 67], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [ 23], Left sub-tree height = [1], Right sub-tree height = [1], BF = [0]
Node = [100], Left sub-tree height = [2], Right sub-tree height = [0], BF = [-2]
Node = [ 5], Left sub-tree height = [2], Right sub-tree height = [3], BF = [1]


LEVEL ORDER TRAVERSAL

[ 5] (BF : 1)
[ 1] (BF : -1)
[100] (BF : -2)
[-20] (BF : 0)
[ 23] (BF : 0)
[ 13] (BF : 0)
[ 67] (BF : 0)




Here is the tree which we were dealing with above


5
1 100
-20 23
13 67




After insertion, the tree might have to be readjusted as needed in order to maintain it as an AVL tree. A node with balance factor -2 or 2 is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees, possibly stored at nodes. If, due to an instertion or deletion, the tree becomes unbalanced, a corresponding left rotation or a right rotation is performed on that tree at a particular node. A balance factor > 1 requires a left rotation (i.e. the right subtree is heavier than the left subtree) and a balance factor < -1 requires a right rotation (i.e. the left subtree is heavier than the right subtree).


Here is some pseudo code to demonstrate the two types of rotations...


Left rotation


BEFORE

0 (par)

0 0 (p)

0 0 (tmp)

0 0 0 0
(a) (b)



Here we left rotate the tree around node p



tmp = p->right;
p->right = tmp->left;
tmp->left = p;

if(par)
{
if(p is the left child of par)
{
par->left=tmp;
}
else
{
par->right=tmp;
}
}
else
{
root=tmp;
}

// Reclaculate the balance factors
setbf(root);




AFTER
0 (par)

0 0
(tmp)

0 0
(p) (b)

0 0
(a)

0 0






Right rotation


BEFORE

0 (par)

0 0 (p)

0 (tmp) 0

0 0 0 0
(a) (b)



Here we right rotate the tree around node p


tmp = p->left;
p->left = tmp->right;
tmp->right = p;

if(par)
{
if(p is the left child of par)
{
par->left=tmp;
}
else
{
par->right=tmp;
}
}
else
{
root=tmp;
}

// Recalculate the balancing factors...
setbf(root);




AFTER

0 (par)

0 0 (tmp)

0 0
(a) (p)

0 0
(b)

0 0




**

Continue

Write a C program to free the nodes of a linked list

Before looking at the answer, try writing a simple C program (with a for loop) to do this. Quite a few people get this wrong.


This is the wrong way to do it


struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = listptr->next)
{
free(listptr);
}


If you are thinking why the above piece of code is wrong, note that once you free the listptr node, you cannot do something like listptr = listptr->next!. Since listptr is already freed, using it to get listptr->next is illegal and can cause unpredictable results!



This is the right way to do it


struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = nextptr)
{
nextptr = listptr->next;
free(listptr);
}
head = NULL;


After doing this, make sure you also set the head pointer to NULL!

Continue

How do you reverse a linked list without using any C pointers?

One way is to reverse the data in the nodes without changing the pointers themselves. One can also create a new linked list which is the reverse of the original linked list. A simple C program can do that for you. Please note that you would still use the "next" pointer fields to traverse through the linked list (So in effect, you are using the pointers, but you are not changing them when reversing the linked list).

Continue

25 Horses.

You have 25 horses. You have 5 tracks to race on. We need to find 3 fastest horses. How many minimum races required to find that ? We have no stop-watch. Horses run at same speed.

Now this puzzle is deceptive if you are not careful enough.

Solution :

Divide the set of 25 horses into 5 non-overlapping sets of 5 horses each.
Have a race each for all the horses in eachset.
This makes it a total of 5 races, one for each set.

Now, have a race for the winners of each of the previous 5 races.
This makes it a total of 6 races.
But this step is tricky. We need to use the following logic
to identify horses for this race.

Observe the position of each horse in the 6th race and correspondingly
number the sets. i.e. the set of the winner of 6th race will be said to be set no. 1
while the set of the loser of the 6th race will be said to be set no. 5.

Now, possible candidates for the first three positions :
1. No horse from set 4 or set 5.
2. No horse from set 3, except for 1st Rank from this group.
3. No horse from set 2, except for 1st and 2nd Rank from this group
4. No horse from set 1, except for 1st, 2nd and 3rd Rank from this group

So now we have 6 candidates for top 3 positions. However, we know that the winner
of set 1 is the fastest horse in the whole group of 25 sets.

So now we have 5 candidates for the second and third position.
What better way to find out who’s who than to have a race of these 5 horses. Race them and this will solve our
problem in just 7 races.

Continue

Find two numbers in an array whose sum =X

Find if the sum of two elements in an array sum up to b (a number) with complexity of O(n)?

Input – Array : 1,2,3,4,5,6,7,8 and the sum is : 6

Output would be : {1,5} {2,4}

Solution : Here is the idea is to start from the first element of the array and keep a hashtable to store the potential pairs. We will check if sum – (a[i]) already exists in the Hashtable. If yes, we have a pair (a[i], value from hashtable) as the pair with the sum. If no, we store a[i] in the hashtable.

Here is a little dry run of array a= {1,2,3,4,5,6,7,8} and sum = 6.

6 – 1 = 5 — found in Hashtable H ? No – store it in H. H will contain (1)

6 –2 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2)

6 –3 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2, 3)

6 –4 = 2 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in H) – (4,2)

6 –5 = 1 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in H) – (5,1)

Why Hashtable ? because the lookup is always O(1) in a hashtable.

Continue

Find Duplicates from m + n elements in an array

Given an array of m+n elements in the range 1 to n ie(m elements are repeated). Find the duplicate elements.
Time Complexity: O(m+n)
Space Complexity: O(m)

Solution :

Since we know there are 1 to n elements, we can sort the array in O(n).
The first n elements will be the unique values and n to m will be the duplicates.
This is O(n+m) && no extra space required.

for (int i = 0; i < array.Length; i++)
{
if (array[i] != i + 1)
{
int t = array[array[i]-1];
array[array[i]-1] = array[i];
array[i] = t;
}
}

Continue

Small Algo

Write an algorithm to find whether a given number is a multiple of 3 or not without using modulo or division operation.

Ans: Convert the number to a string, thereby getting the decimal digits separately. Read those digits once by one and add all of them. If the sum is more than 10, repeat the procedure. Once the sum is less than 10, if it is 0, 3, 6 or 9, then the original number is divisible by 3.

Continue

Array Question

In an integer array all numbers occur exactly twice except for a single number which occurs exactly once..give an O(n) algorithm to find the number occurring only once.

Ans: Do bitwise XOR of all numbers. The result will be the number that occurs only once. The result in each position is the different number if the two bits are different, and 0 if they are the same.

public class Xor
{
public static void main(String args[])
{
int[] arr= {1,1,2,2,3,4,4,5,5};
int xOR = arr[0] ;
for(int i =1 ;i< arr.length; i++)
{
xOR = xOR ^ arr[i];
System.out.println( arr[i] + " —- " + xOR);
}
System.out.println(xOR);
}
}

Continue

Find an element in a sorted 2D Array.

You have a [n * n] array which is sorted both row wise and column wise. How do you find an element in this array in O(n) time ?

Solution: 1

1. Start from left bottom most cell.
2. If query is larger move right .
3. If query is smaller move up.
4. If you can’t move right or up and haven’t found the query yet, it means that the query does not exist.

Applying binary search for Rows and column may furthur reduce the complexity,,,

Continue

Maximum sub-sequence…

Question : Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.
Eg.
i) 3 2 7 10 should return 13 (sum of 3 and 10)
ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)

The idea is to use Dynamic Programming and store the intermediate “good” sums in an auxiliary array. The right way is to define an array B[n] whose j-th element B[j] represents the best sum that has A[j] as the last element.

A simplistic java code looks like this :

public class maxSkip
{
public static void main(String args[])
{
.... int[] a = {3,2,5,10,7};
.... int j,mx=0;
.... int len = a.length;
.... int[] b = new int[len];

....b[0] = a[0]; if(len==1) mx = b[0];
....b[1] = a[1]; if(len==2) mx = max(b[0],b[1]);
....b[2] = a[2]+b[0]; if(len==3) mx = max(b[1],b[2]);

.... for(j = 3 ; j< len; j++)
.... {
........ b[j] = max(a[j]+b[j-2] , a[j] + b[j-3]);
.... }
.... mx= max(b[j-2], b[j-1]);
.... System.out.println("Max subsequence : " + mx);
}
public static int max(int a, int b)
{
......return(a>b?a:b);
}
}

Continue

Max contiguous sub-sequence.

This problem is called Maximum contiguous sub sequence sum problem.
Given an array which can contain both positive and negative numbers, find the maximum contiguous sub sequence sum.
For example in an array = {2, -3, 4, -5, 6, -3, 8}, it should return 11.

Algo :

Take the array, {2, -3, 4, -5, 6, -3, 8}
Compute the partial sums up to place i for all i, {2, -1, 3, -2, 4, 1, 9}
Subtract from each element the minimum that occurs earlier (or 0), {2, -1, 4, -1, 6, 3, 11}
Take the maximum, 11

Code:

public class maxSubSeq
{
public static void main(String args[])
{
....int[] a = {2,-3,4,-5,6,-3,8};
....int[] p = new int[a.length];
....//Compute partial sums
....for(int i = 0; i ....{
....if(i==0)
.......p[i] = a[i] ;
....else
.......p[i] = a[i] + p[i-1];
....}
....//Substract from each element in p, the minimum that occur
....//earlier (or 0)
....int min=0;
....for(int i=0; i< p.length; i++)
....{
....if(i==0)
....{
....if(p[i] > 0)
........min = 0;
....else
........min = p[i];

..... p[i] = p[i] - min;
...}
....else
... {
....if(p[i] < min)
.......min = p[i];
....... p[i] = p[i] - min;
}
}

//Maximum of the resulting p would be the maximum subsequence
java.util.Arrays.sort(p);
System.out.println("The maximum subsequence - " + p[p.length-1]);
}

}

Continue

N stack 1 Array

Implement N stacks using constant sized array(space). Until the array is completely filled, I should be able to push elements to any one of the N stacks.(i.e.)Do not reserve space for the stacks. And I should also be able to pop elements from any stack.

Sounds very tricky. The idea is :

Keep an array S of N pointer, where each S_i.top will point to the top of the corresponding stack. And one global pointer gptr, which points to the next free location in the array. Now follow the steps:

Now implement Push(stackToPush) and pop(StackToPop) as follows :

Push(x, Si) //pushing x in Stack Si.
{
if(gptr > sizeof(Arr))
{
// To Be Added -- explained below
}
Arr[gptr].data = x;
Arr[gprt].prev = Si.top;
Si.top = gptr;
gptr++;
}


Pop(Si)
{
T data = Arr[Si.top].data; //T is data type
Si.top = Arr[Si.top].prev;
return data;
}

I would suggest that you try a very detailed dry-run with a little visual aid for this.

Continue

Inorder successor ?

This is one of the nasty ones, if you don’t fully understand what “Inorder successor” is. The inorder successor is the next value in an inorder traversal of a binary search tree. So how do you find the inorder successor for the node U ?

Algorithm : If node U has a right sub-tree, then the successor is the left most descendent of the right sub-tree. Otherwise, find the first ancestor that has node U in the left sub-tree.

Pseudocode :

if(node->right)
if( ! node->right->left)
return node->right;
else
{
tmp = node->right->left;
while(tmp->left)
tmp = tmp->left;
return tmp;
}

Continue

Reverse a Singly Linked List.

Reverse a singly linked list :

public void reverse()
{
Node current = head;
head = null ; //set head to null
while(current != null)
{
Node save = current;
//Interchange the pointers
current = current.next;
save.next = head;
head = save;
}
}

Continue

Chasing Dogs.

There are four dogs, each at a corner of a large square.
Each of the dogs begins chasing the dog clockwise from it.
All of the dogs run at the same speed. All continuously
adjust their direction so that they are always heading
straight toward their clockwise neighbor. How long does it
take for the dogs to catch each other? Where does this
happen?

Solution :

To make things easy, let’s say the square is 1 mile on each
side, and the dogs are genetically enhanced greyhounds that
run exactly 1 mile per minute. Pretend you’re a flea riding on
the back of Dog 1. You’ve got a tiny radar gun that tells you how
fast things are moving, relative to your own frame of reference
(which is to say, Dog l’s frame of reference, since you’re holding
tight to Dog l’s back with five of your legs and pointing the
radar gun with the sixth). Dog 1 is chasing Dog 2, who is
chasing Dog 3, who is chasing Dog 4, who in turn is chasing
Dog 1. At the start of the chase, you aim the radar gun at Dog
4 (who’s chasing you). It informs you that Dog 4 is
approaching at a speed of 1 mile per minute.
A little while later, you try the radar gun again. What
does the gun read now? By this point, all the dogs have
moved a little, all are a bit closer to each other, and all have
shifted direction just slightly in order to be tracking their
respective target dogs. The four dogs still form a perfect
square. Each dog is still chasing its target dog at 1 mile per
minute, and each target dog is still moving at right angles to
the chaser. Because the target dog’s motion is still at right
angles, each chasing dog gains on its target dog at the full
running speed. That means your radar gun must say that Dog
4 is still gaining on you at 1 mile per minute.
Your radar gun will report that Dog 4 is approaching at
that speed throughout the chase. This talk of fleas and radar
guns is just a colorful way of illustrating what the puzzle
specifies, that the dogs perpetually gain on their targets at
constant speed.
It makes no difference that your frame of reference
(read: dog) is itself moving relative to the other dogs or the
ground. One frame of reference is as good as any other. (If
they give you a hard time about that, tell ‘em Einstein said
so.) The only thing that matters is that Dog 4 approaches you
at constant speed. Since Dog 4 is a mile away from you at the
outset and approaches at an unvarying 1 mile per minute,
Dog 4 will necessarily smack into you at the end of a minute.
Fleas riding on the other dogs’ backs will come to similar
conclusions. All the dogs will plow into each other one
minute after the start.
Where does this happen? The dogs’ motions are
entirely symmetrical. It would be strange if the dogs ended
up two counties to the west. Nothing is "pulling" them to
the west. Whatever happens must preserve the symmetry of
the original situation. Given that the dogs meet, the collision
has to be right in the middle of the square.

Continue

Sorting Array of 0’s and 1’s

You are given an Array of N size. It contains 0 and 1 only. You have to arrange all 0s before all 1s (In the program you can’t travel more than once. Minimum complexity desired).

Idea : Move a pointer left, from the front, until it encounters a 1
Move a pointer right, from the end, until it encounters a 0
Swap the elements at the two pointers (if they haven’t crossed)
Repeat this for entire array – this is inplace and single pass.

Code :

public class swap01
{
public static void main(String arg[])
{
int[] a = {0,1,1,0,0,1,1,1,0};
int l =0;
int r= a.length-1;
while(l {
if(a[l] == 0)
{
l++;
}
else if(a[r] == 1)
{
r–;
}
else {
swap(a,l,r);
l++;
r–;
}
}
for(int i=0;i System.out.print(a[i] + ",");
}
private static void swap(int[] a, int l, int r)
{
int tmp = a[l];
a[l] = a[r];
a[r]=tmp;
}
}

Continue

Remove Duplicates from a String.

Given a string of ASCII characters, write the write a program to remove the duplicate elements present in them. For example, if the given string is "Potato", then, the output has to be "Pota". Additional constraint is, the algorithm has to be in-place( no extra data structures allowed)

Idea for an O(n) solution :

Let’s start with ['a','b','a','c','a','a','d','b','c']
[i:j:'a','b','a','c','a','a','d','b','c'] – [0,0,0,0] (character map for a,b,c,d)
1st charcter is an ‘a’, it’s not in the map, so we add it and increment i&j
['a',i:j:'b','a','c','a','a','d','b','c'] – [1,0,0,0]
2nd character is ‘b’, same procedure as before
['a','b',i:j:'a','c','a','a','d','b','c'] – [1,1,0,0]
third character is an ‘a’, this is already in the map, so we clear the spot, and increment only i
['a','b',j:0,i:'c','a','a','d','b','c'] – [1,1,0,0]
fourth character is ‘c’, which is not in the map; since i and j are different we add ‘c’ to the map, move it to position j, clear position i and increment i and j.
['a','b','c',j:0,i:'a','a','d','b','c'] – [1,1,1,0]
fifth and sixth character are handled like the third
['a','b','c',j:0,0,0,i:'d','b','c'] – [1,1,1,0]
seventh character is ‘d’, which is not in the map, so we handle it like the fourth one.
['a','b','c','d',j:0,0,0,i:'b','c'] – [1,1,1,1]
last two are like third case.
['a','b','c','d',j:0,0,0,0,0]:i – [1,1,1,1]
i has incremented beyond the range of the array so we’re done. We have j unique characters starting from position 0.
Code :

public static void main(String[] args) {
char[] a = {‘a’,'b’,'a’,'c’,'a’,'a’,'d’,'b’,'c’};
boolean[] ascii = new boolean[256];
int j=0;
for(int i=0;i<255;i++){
ascii[i] = false;
}
for(int i=0; i {
if(ascii[a[i]] == false)
{
ascii[a[i]] = true;
a[j] = a[i];
if (i != j)
{
a[i] = ‘0′;
}
j++;
i++;
}
else if (ascii[a[i]] == true)
{
a[j]=’0′;
a[i]=’0′;
i++;
}
}

Continue

Loop in Singly Linked List.

I am sure you must know answer to this by now. Nevertheless, its very easy to miss the most valid answers to this which is the lesser known “Tortoise and Hare Algorithm”

Solution with – O(n) time complexity

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

This solution is "Floyd’s Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".

function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}

Continue

Lowest Common Ancestor in a Binary Search Tree.

Given the values of two nodes in a binary search tree, we need to find the lowest common ancestor. You may assume that both values already exist in the tree.

I/P : 4 and 14

O/P : 8 (Here the common ancestors of 4 and 14, are {8,20}. Of {8,20}, the lowest one is 8).

Algorithm:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 <>

    private static int LCA(Node root, int x, int y){

       /* If we have reached a leaf node then LCA doesn't exist

          If root->data is equal to any of the inputs then input is

          not valid. For example 20, 22 in the given figure */

       if(root==null || root.data==x || root.data==y){

           return -1;

       }

       /* If any of the input nodes is child of the current node

       we have reached the LCA. For example, in the above figure

       if we want to calculate LCA of 12 and 14, recursion should

       terminate when we reach 8*/

       if(root.right != null && (root.right.data==x || root.right.data ==y)){

           return root.data;

       }

       if(root.left != null && (root.left.data==x || root.left.data ==y)){

           return root.data;

       }



       if(root.data > x && root.data < y){

           return root.data;

       }

       if(root.data > x && root.data > y)

       {

           return LCA(root.left, x,y);

       }

       if(root.data < x && root.data < y){

           return LCA(root.right,x,y);

       }

       return -1;

   }

Continue

Merge Two Sorted Arrays.

Problem : There are two sorted arrays A1 and A2. Array A1 is full where as array A2 is partially empty and number of empty slots are just enough to accommodate all elements of A1. Write a program to merge the two sorted arrays to fill the array A2. You cannot use any additional memory and expected run time is O(n).

Solution: The trick to solving this problem is to start filling the destination array from the back with the largest elements. You will end up with a merged and sorted destination array.

Code:

public class MergeSortedArrays {

   public static void main(String[] args) {

       int[] a = new int[] {3,6,10,12,56};

       int[] b = new int[8] ;

       b[0] = 9;

       b[1] =11;

       b[2] =36;

       //after this b looks like {9,11,36,0,0,0,0,0}

       // with enough space to accommodate 'a'

       //0 indicating a free space.

       int i = a.length-1; //a's length

       int k = b.length-1; //b's length

       //Starting point to the empty slots.

       int j = findCount(b) - 1;

       for(; k>0; k--) {

           if(j<0)

               break;



           if(a[i] > b[j])

           {

               b[k] = a[i];

               i--;

           }

           else

           {

               b[k] = b[j];

               j--;

           }

           print(b);

       }

       //Copy the leftovers which are already sorted.

       while(k>=0){

               b[k--] = a[i--];



       }

      print(b); //Final array is printed.

   }

   //Purely a debug method

   private static void print(int[] b){

       for(int x=0;x           System.out.print(b[x] + ", ");



       System.out.println("");

   }

   private static int findCount(int[] b)

   {   int i=0;

       while (b[i] != 0){

          i++;

       }

       return i;

   }

}

Continue

Merge Sorted Linked Lists.

Given two sorted Linked Lists, we need to merge them into the third list in sorted order. Complexity – O(n)

Solution :

   public Node mergeList(Node a, Node b){
       Node result = null;
       if(a==null)
           return b;
       if(b==null)
           return a;

       if(a.data <= b.data){
           result =a;
           result.next = mergeList(a.next,b);
       }
       else
       {
           result =b;
           result.next = mergeList(b.next,a);
       }
       return result;
   }

Continue

MaxHeap and MinHeap Implementations in Java

Sometimes a code-segment is worth a thousand words. Understanding the MaxHeap and MinHeaps using Java code is very easy. Here is an implementation of both.

MaxHeap :

package bst;

import java.util.ArrayList;

import java.util.List;

public class BinaryHeap {

   //ArrayList to hold the heap

    List h = new ArrayList();

   public BinaryHeap(){



   }

   //Constructs the heap - heapify

    public BinaryHeap(int[] e) {

       for(int i=0; i<e.length;i++)

       {

           add(e[i]);

       }

   }

   private int intGet(int key){

       return new Integer(h.get(key).toString()).intValue();

   }

   public void add(int key){

       h.add(null);

       int k = h.size()-1;

       while (k>0){

           int parent = (k-1)/2;

           int parentValue = new Integer(h.get(parent).toString()).intValue();

           //MaxHeap -

           //for minheap - if(key > parentValue)

            if(key <= parentValue){

               break;

           }

           h.set(k,parentValue);

           k=parent;

       }

       h.set(k,key);

   }

   public int getMax()

   {

       return new Integer(h.get(0).toString()).intValue();

   }

   public void percolateUp(int k, int key){

       if(h.isEmpty())

           return ;



       while(k < h.size() /2){

           int child = 2*k + 1; //left child

            if(child < h.size() -1 &&

              (new Integer(h.get(child).toString()).intValue() <

               new Integer(h.get(child+1).toString()).intValue()    )){

               child++;

           }

           if(key >= new Integer(h.get(child).toString()).intValue()){

               break;

           }

           h.set(k,new Integer(h.get(child).toString()).intValue());

           k=child;

       }

       h.set(k,key);

   }

   public int remove()

   {

       int removeNode = new Integer(h.get(0).toString()).intValue();

       int lastNode = new Integer(h.remove(h.size()-1).toString()).intValue();

       percolateUp(0,lastNode);

       return removeNode;

   }

   public boolean isEmpty()

   {

       return h.isEmpty();

   }



   public static void main(String[] args) {

       BinaryHeap heap = new BinaryHeap(new int[] {2,5,1});

       while(!heap.isEmpty()){

           System.out.println(heap.remove());

       }



   }

}

MinHeap :

package bst;

import java.util.*;



public class MinHeap<E extends Comparable<E>> {

 List<E> h = new ArrayList<E>();



 public MinHeap() {

 }



 public MinHeap(E[] keys) {

   for (E key : keys) {

     h.add(key);

   }

   for (int k = h.size() / 2 - 1; k >= 0; k--) {

     percolateDown(k, h.get(k));

   }

 }



 public void add(E node) {

   h.add(null);

   int k = h.size() - 1;

   while (k > 0) {

     int parent = (k - 1) / 2;

     E p = h.get(parent);

     if (node.compareTo(p) >= 0) {

       break;

     }

     h.set(k, p);

     k = parent;

   }

   h.set(k, node);

 }



 public E remove() {

   E removedNode = h.get(0);

   E lastNode = h.remove(h.size() - 1);

   percolateDown(0, lastNode);

   return removedNode;

 }



 public E min() {

   return h.get(0);

 }



 public boolean isEmpty() {

   return h.isEmpty();

 }



 void percolateDown(int k, E node) {

   if (h.isEmpty()) {

     return;

   }

   while (k < h.size() / 2) {

     int child = 2 * k + 1;

     if (child < h.size() - 1 && h.get(child).compareTo(h.get(child + 1)) > 0) {

       child++;

     }

     if (node.compareTo(h.get(child)) <= 0) {

       break;

     }

     h.set(k, h.get(child));

     k = child;

   }

   h.set(k, node);

 }



 // Usage example

  public static void main(String[] args) {

   MinHeap<Integer> heap = new MinHeap<Integer>(new Integer[] { 2, 5, 1, 3 });

   // print keys in sorted order

    while (!heap.isEmpty()) {

     System.out.println(heap.remove());

   }

 }

}

Continue