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