INTERVIEW QUESTIONS

Cognizant Interview questions C/C++

2015-04-03T04:12:00.001-07:00

Hi Guys,
Its been Long have updated my blog. I have attended an Interview at Cognizant on 28th March 2015 at Powai (Mumbai) for "C" Developer position.

I was contacted by the HR. Interview consisted of 2 Technical rounds. One with a Sr developer and other with Manager and another Senior developer.

I can recollect some of the question asked to me. Here are those...

1) How do we allocate dynamic memory in C. (write the syntax of malloc)
2) How do we free it ?.
3) How does free understand how much memory to free as we just pass a pointer to it.
4) Return type of free.
==> First interview had these question and he asked me to design a solution to a problem. He was quite helpful. I had already told that I don't have much hands-on with IPC.

5) How to allocate 1 bit to a variable.
6) Go to the 3rd last node of a list.
7) What are zombies ?
8) How to identify the zombies in Linux.
9) What does fork do ?
10) Whether to use fork or system calls ?
11) How to create a daemon process ?
12) What is a race condition.
13) He asked about thread local memory. (I wasn't quite sure what he exactly meant)

Know thy Complexities !!

2013-10-27T23:34:00.002-07:00

Know Thy Complexities!

Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them. Over the last few years, I've interviewed at several Silicon Valley startups, and also some bigger companies, like Yahoo, eBay, LinkedIn, and Google, and each time that I prepared for an interview, I thought to msyelf "Why oh why hasn't someone created a nice Big-O cheat sheet?". So, to save all of you fine folks a ton of time, I went ahead and created one. Enjoy!

`Good`	`Fair`	`Poor`

Searching

Algorithm	Data Structure	Time Complexity		Space Complexity
		Average	Worst	Worst
Depth First Search (DFS)	Graph of \|V\| vertices and \|E\| edges	`-`	`O(\|E\| + \|V\|)`	`O(\|V\|)`
Breadth First Search (BFS)	Graph of \|V\| vertices and \|E\| edges	`-`	`O(\|E\| + \|V\|)`	`O(\|V\|)`
Binary search	Sorted array of n elements	`O(log(n))`	`O(log(n))`	`O(1)`
Linear (Brute Force)	Array	`O(n)`	`O(n)`	`O(1)`
Shortest path by Dijkstra, using a Min-heap as priority queue	Graph with \|V\| vertices and \|E\| edges	`O((\|V\| + \|E\|) log \|V\|)`	`O((\|V\| + \|E\|) log \|V\|)`	`O(\|V\|)`
Shortest path by Dijkstra, using an unsorted array as priority queue	Graph with \|V\| vertices and \|E\| edges	`O(\|V\|^2)`	`O(\|V\|^2)`	`O(\|V\|)`
Shortest path by Bellman-Ford	Graph with \|V\| vertices and \|E\| edges	`O(\|V\|\|E\|)`	`O(\|V\|\|E\|)`	`O(\|V\|)`

Sorting

Algorithm	Data Structure	Time Complexity			Worst Case Auxiliary Space Complexity
		Best	Average	Worst	Worst
Quicksort	Array	`O(n log(n))`	`O(n log(n))`	`O(n^2)`	`O(n)`
Mergesort	Array	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(n)`
Heapsort	Array	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(1)`
Bubble Sort	Array	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Insertion Sort	Array	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Select Sort	Array	`O(n^2)`	`O(n^2)`	`O(n^2)`	`O(1)`
Bucket Sort	Array	`O(n+k)`	`O(n+k)`	`O(n^2)`	`O(nk)`
Radix Sort	Array	`O(nk)`	`O(nk)`	`O(nk)`	`O(n+k)`

Data Structures

Data Structure	Time Complexity								Space Complexity
	Average				Worst				Worst
	Indexing	Search	Insertion	Deletion	Indexing	Search	Insertion	Deletion
Basic Array	`O(1)`	`O(n)`	`-`	`-`	`O(1)`	`O(n)`	`-`	`-`	`O(n)`
Dynamic Array	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Singly-Linked List	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Doubly-Linked List	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Skip List	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n log(n))`
Hash Table	`-`	`O(1)`	`O(1)`	`O(1)`	`-`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Binary Search Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Cartresian Tree	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`-`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
B-Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
Red-Black Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
Splay Tree	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
AVL Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`

Heaps

<!-- heapify

Heaps	Time Complexity
	Heapify	Find Max	Extract Max	Increase Key	Insert	Delete	Merge
Linked List (sorted)	`-`

O(1)
O(1)
O(n)
O(n)
O(1)
O(m+n)

Linked List (unsorted)
-
O(n)
O(n)
O(1)
O(1)
O(1)
O(1)
Binary Heap
O(n)
O(1)
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(m+n)
Binomial Heap
-
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
Fibonacci Heap
-
O(1)
O(log(n))*
O(1)*
O(1)
O(log(n))*
O(1)

Graphs

Node / Edge Management	Storage	Add Vertex	Add Edge	Remove Vertex	Remove Edge	Query
Adjacency list	`O(\|V\|+\|E\|)`	`O(1)`	`O(1)`	`O(\|V\| + \|E\|)`	`O(\|E\|)`	`O(\|V\|)`
Incidence list	`O(\|V\|+\|E\|)`	`O(1)`	`O(1)`	`O(\|E\|)`	`O(\|E\|)`	`O(\|E\|)`
Adjacency matrix	`O(\|V\|^2)`	`O(\|V\|^2)`	`O(1)`	`O(\|V\|^2)`	`O(1)`	`O(1)`
Incidence matrix	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|E\|)`

Notation for asymptotic growth

letter	bound	growth
(theta) Θ	upper and lower, tight^[1]	equal^[2]
(big-oh) O	upper, tightness unknown	less than or equal^[3]
(small-oh) o	upper, not tight	less than
(big omega) Ω	lower, tightness unknown	greater than or equal
(small omega) ω	lower, not tight	greater than

[1] Big O is the upper bound, while Omega is the lower bound. Theta requires both Big O and Omega, so that's why it's referred to as a tight bound (it must be both the upper and lower bound). For example, an algorithm taking Omega(n log n) takes at least n log n time but has no upper limit. An algorithm taking Theta(n log n) is far preferential since it takes AT LEAST n log n (Omega n log n) and NO MORE THAN n log n (Big O n log n).^SO

[2] f(x)=Θ(g(n)) means f (the running time of the algorithm) grows exactly like g when n (input size) gets larger. In other words, the growth rate of f(x) is asymptotically proportional to g(n).

[3] Same thing. Here the growth rate is no faster than g(n). big-oh is the most useful because represents the worst-case behavior.

In short, if algorithm is __ then its performance is __

algorithm	performance
o(n)	< n
O(n)	≤ n
Θ(n)	= n
Ω(n)	≥ n
ω(n)	> n

Big-O Complexity Chart

-->

"Query end" state in Mysql

2013-08-23T00:59:00.002-07:00

"Query end" state in MySql appears to consume a lot of time which becomes a bottleneck for insert operations.

I had written a stored Procedure in Mysql which implements a cursor to iterate over the rows of a table. This cursor worked well on my machine but it took a lot of time in the live environment (POC setup).

Initial culprit seemed to be the hardware but after analysing the procedure with "show processlist", I found that every insert would used to get stuck at query insert state.

Incase any of you guys come across similar issue, you can edit your my.cnf file (I think my.ini for windows) and change this

innodb_flush_log_at_trx_commit = 1
to
innodb_flush_log_at_trx_commit = 0 or innodb_flush_log_at_trx_commit = 2.

This will drastically improve the performance but it also prohibits the innodb engine to serve ACID properties.

After reading some forums I found that the above parameter can be changed if you are ready to incur a loss of one statement in case of system crash(not Mysql) or power failure.

What is 1000000007 ?

2013-07-29T01:17:00.000-07:00

Hello Guys,

As a newbie on online Coding contests, I was initially fed-up with 1000000007.I hardly understood the logic behind it.

Some guys give an hint that "its the first 10 digit prime..", so what ?
There were 2 questions in my mind.
1) Why only a prime.
2) Why not 2nd or 3rd prime

Instantly I got an partial answer from myself for the first question, A prime because we need (ans % Prime) as the actual answer, so the o/p should be unique.

But, there was a lot behind that word Prime in this case (Explained later)

The 2nd question what still open, but lately I understood that 1000000007 is easy to represent as 10^9+7. Any greater Prime would have served the purpose but this was easy to write. Infact some times we find the 2nd 10 digit prime which is again easy to represent 1000000009.

This would have been very well understood by everyone now.

Coming to the actual point.

All of us might have noticed that 1000000007 comes only when our answers are expected to be very large, more commonly when we implement combinations n(c,k) or nCk.

The combination formula is n!/(r!(n-r)!).

We are asked mod operation with 1000000007 for 2 reasons,
1) Obviously, so as to restrict our answer to 10 digit and
2) Help us with large multiplications and divisions.

Did u read Division ? yes !!!

We must know that (%) is distributive over multiplication,addition etc, but not over division.
So, how to do large divisions ?

There`s a theorem known as "Fermat's little theorem".
It say`s that (A/B) % MOD = ((A % MOD)*(B^(MOD-2) % MOD))%MOD (You can refer wiki for actual theorem)

Now, we can see that, Fermat's theorem essentially convert all our division to multiplication.So we can use our mod (%) operation.

If you have any issues/queries, please comment the same... I will try my best to answer it.

Techgig Monthend challenge : Foreign Trip : Level Easy

2013-07-28T23:09:00.003-07:00

Problem Statement

A company organizes two foreign trips for its employees yearly. Aim of the trip is to increase interaction among the employees of the company and hence company wants each of his employee to see new people on the trip and not even a single person with whom he has worked in past. Therefore it is a rule in company that in any of the trips, all the employees should be new to each other and no two of them should have worked together in past.

Given the work history of each employee (which people he has worked with sometimes in past), you have to tell whether all of the employees can be accommodated within trips without violating the above rule or not. Each employee is given a unique integer ID by which they are recognized. You can also assume that each employee has worked with at least one other employee in past.

Note: No employee can be in both trips and every employee must be part of one trip.

Examples

Example:

i) Suppose the work history is given as follows: {(1,2),(2,3),(3,4)}; then it is possible to accommodate all the four employees in two trips (one trip consisting of employees 1& 3 and other having employees 2 & 4). Neither of the two employees in the same trip have worked together in past.

ii) Suppose the work history is given as {(1,2),(1,3),(2,3)} then there is no way possible to have two trips satisfying the company rule and accommodating all the employees.

==========================================================================

This is an old Question on Techgig, but lets discuss it as we are finding it difficult to approach the problem.

Well, I had solved this question few months back and scored just 90. Unable to 100 (Maybe I am missing a corner case, not sure though).

I can`t recollect the exact thought process of mine towards this problem but I will explain the final approach used by me.

As per the question, they are giving us the set of employees who have worked with each other. So lets keep a mapping of the employees who have worked with each other.

Then, if an employee has worked with someone, check for all combinations of employee such that the intersection should not be marked as "1" (i.e worked with each other)

Here is the code : (Fetches only 90)

#include
#include

char* emp_violating(int input1,char* input2)
{
int i=0,j=0,k=0;
int a=0,b=0;
int map[input1+1][input1+1];
int cnt[input1+1];
for(i=0;i<=input1;i++)
{ for(j=0;j<=input1;j++)
map[i][j]=0;
cnt[i]=0;
}
while(1)
{
while(*input2 != '(')
{input2++;}
input2++;
while(*input2>='0' && *input2<='9') /*For more than 1 digit numbers*/
{
a=a*10 + (int)*input2++ - '0';
}
while(*input2 != ',')
input2++;
input2++;
while(*input2>='0' && *input2<='9') /*For more than 1 digit numbers*/
{
b=b*10 + (int)*input2++ - '0';
}
map[a][b]=1;map[b][a]=1; /*Mark that both guys have been with each other*/
cnt[a]++;cnt[b]++; /*Increment the count to identify that they have been to a picnic. This can also just set to be dirty*/
input2++;
if(*input2!=',')
break;
a=0;b=0;
}

for(i=1;i<=input1;i++)
{
if(cnt[i]>1)
{
for(j=1;j<=input1;j++)
{
for(k=j+1;k
{
if(map[i][j]==1 && map[i][k]==1)
{
if(map[j][k]==1) return "no";
}
}
}
}
}
return "yes";
}

int main() /*Driver*/
{
char *a="(10,2),(2,3),(3,4)";
printf("%s\n",emp_violating(10,a));
return 0;
}

Techgig July contest : Musical Pillow : Level (Medium)

2013-07-15T02:52:00.001-07:00

Problem Statement

In a family party, people are playing the musical pillow game in which people sit in a circle. Starting from the first person, they transfer the pillow to the person to their left. For simplicity, we’ll assume that people are assigned an integer tag from 1 to n(which is the total number of people) in the clockwise manner, so that during the game pillow is passed in the increasing sequence of. When game starts, a song is played and the person with the pillow at the end of the song, is eliminated and game starts again till there is only one person is left, which is declared as the winner of the game.

You are give total number of people playing the game and the duration of the song in seconds. If game starts with pillow being put on a table & person1 (person with tag number 1)picking it up(at the end of first second [time], pillow will be with person1) and each person takes one second to transfer the pillow to the next person, you have to tell which person (tag number) which will win the game.

Examples

Example 1: Let there are 5 people and duration of the song is 2 seconds(every second person present in the clockwise manner will be eliminated) then people will be eliminated in the following order: 2,4,1, 5 and person with tag 3 will be the winner.

Example 2: If there are 11 people in the beginning of the game, and song duration is 4 seconds then people will be eliminated in following order: 4,8,1,6,11, 7, 3,2,5, 10 and winner will be the person with tag no. 9.

==============================================================================

Dont know why they called it as a medium level problem after that Bitonic problem (Easy level) which ruined a couple of days of my life.. :(

Lets come to the problem, its a very easy problem to solve. A new programmer would face only one problem i.e to start the loop from first position when we reach the end of our sequence.

Here`s the logic :

i) First we declare an array with the number of persons (input1) and fill it with 0.

ii) Then, as the games starts and a person gets out, that position is to be marked as 1. Because while the next round this position needs to be ignored as the person is already out.

ii) Continue till only a single person remains.

The tricky point here is, how to traverse through the loop. The answer to this is, just maintain a flag which is updated only when we encounter a 0 at that position in the array else just move on until flag becomes equal to input2. In case, we reach the end of array, start from 1 again without resetting the flag.

If you have doubts or you want the source code for reference the comment below with your email address.

EDIT: Just learnt to find that this is called as "Josephus Problem" and a recursive solution can be written for it.

Techgig May contest : Partition problem : Level Easy

2013-07-08T05:46:00.002-07:00

Problem Statement

You are given a set of positive integers. your task is to solve partition problem.

Lets define the partition problem.

Partition problem is the task of deciding whether a given multiset of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the elements in S1 equals the sum of the elements in S2.

Example 1:
array[] = {1, 5, 11, 5}
Output: Yes
This array can be divided into to subsets {1, 5, 5} and {11} these two have equal sum.

Example 2:
array[] = {1, 5, 3}
Output: No
This array cant be divided into two subsets of equal sum.

===============================================================================

The level set was easy but this was really a nice question, took half hour to code it.. :P

Well, Most of us get the answer just by reading the question... "Divide the array such that sum of each partition is equal", but as soon we we try to write the code, out mind keeps wondering "how the hell do I implement this ?"

I thought for some time and then realized that, The worst case of forming the partitions for N element is; One partition of 0 elements and the other of N elements, but this wont help us.

Now lets move forward in the same line. One partition of N-1 elements and the other of 1 element.This is our first step.

This can be easily achieved with a for loop. But, the problem is, there are many different ways for selection 2 partitions each of N-1 and 1 elements respectively. To be precise they are N ways.

First thing to be taken care of is to cover all the N ways. Next, every time the partition should be increase and decrease respectively keeping in mind all the cases.

Here is the code,

#include
#include

char* partition(int input1[])
{
int i=0,n,total=0,loop,round,s1=0;
while(input1[i]>-1)
{
if(input1[i]==0)return "Invalid";
total+=input1[i++];
}
n=i;
round=0;
while(round < N)
{
loop=round;
for(i=0;i<=round-1;i++)
s1=s1+input1[i];
while(loop < round)
{
s1=s1+input1[loop];
if(s1==(total-s1))return "Yes";
s1=s1-input1[loop];
loop++;
}
s1=0;
round++;
}
return "No";
}

Let me know if you have any doubts.

Techgig June contest : Disks in a Pile : Level (Easy)

2013-07-08T04:18:00.000-07:00

Problem Statement

Rahul is playing a very interesting game. He has N disks ( each of equal radius).

Every disk has a distinct number out of 1 to N associated with it. Disks are placed one over other in a single pile.

Rahul wants to sort this pile of disk in increasing order from top to bottom. But he has a very very special method of doing this. In a single step he can only choose one disk out of the pile and he can only put it at the top.

Rahul wants to sort his pile of disks in minimum number of possible steps. So help Rahul in doing so. So don't have to show the actual steps just answer the minimum number of possible steps to sort the pile so that that Rahul can check whether he is doing his work right or wrong

===============================================================================

This was a very easy question, but Some of us found it difficult.

Here goes the explanation,

If you write it down on a paper then you will notice that We first track the highest numbered disk and then just move the disks with the decreasing number on top of it.

For example lets take 3 4 5 1 2 as the numbering.

Here, since 5 is the highest number I will move only 2 and then 1 on top of it, so the ans comes as 2.

There are two steps to solve this problem
1) First find the max element. then,
2) Find (P) the number of elements before the max element which are in increasing order. Total-1-P is the ans.

This logic fetches 100 ont Techgig.

If anyone wants the code then just give a comment.

Techgig July contest : Bitonic Sequence : Level(Easy)

2013-07-08T01:05:00.001-07:00

Problem Statement

You are given an array A[] containing n positive integers. Lets define Bitonic subsequence. A subsequence of array A[] is called Bitonic if it is first strictly increasing and then strictly decreasing. Your task is to find the length of largest bitonic subsequence given an array.

Note- A sequence sorted in increasing order is considered as Bitonic with decreasing part as empty. Similarly, A sequence sorted in decreasing order is also considered as bitonic with increasing part as empty

How many of you guys have got the solution for this problem ?

Well, I have got the logic which work perfect but unfortunately It doesn`t fetch 100 on the Techgig compiler. The problem is not with my Code/Loigc but the problem is Techgig`s definition for Bitonic subsequence. Which can be found here

Techgig say that the sequence should be strictly increasing and then decreasing where as it can be either way and that too in circular fashion.

If you refer the previous link we can see that

3 5 8 9 7 4 2 1

5 8 9 7 4 2 1 3

both are bitonic such that 2nd sequence can be converted to first by a circular shift.

Lets, come to the basic question on Techgig and see how to implement a logic for it.

I am considering a sequence for example given below.

9,10,1,3,5,8,2,1,7,5,3,1

Here starts the actual logic :-

As we want an subsequence which is first increasing and then decreasing let find the increasing numbers.

We will be going number by number.

step 1 : Consider 9, It is the first number so directly put it into a list(Array)

9 (List)

step 2: next is 10, since 10 is greater and 9, put it into same list

9,10

step 3: 1, since 1 is less than 10 and we are searching for increasing number, we will create a new list

9,10

At this point, If we had any numbers less then 1 in the previous list then those needed to be first i inserted in the new list and then 1. But we didnt have any here

step 4: Once we have more than 1 list, every new number has to be checked with the last number of that list and if the new number is greater then it has to be appended to that list. The next number is 3,first check in the previous list if 3 is greater than the last number if it. In our case we have 10 as the last number so we need not append 3.

Now, 3 is greater than 1, so just append it.

9,10

1,3

Repeat the above steps, we get

9,10

1,3,5,8

1,2

1,7

1,5

1,3

These are the various lists which we get. Now we can see here that 2nd list has the largest length. But that wont help us, because it may happen the there is not decreasing subsequence for it or may be some other list has a decreasing sequence of greater length.

Hence, once these lists are formed we perform a similar process for decreasing lists.

The important thing to keep in mind is the position(in input1[]) of last number in our lists.Because, we need to find the decreasing sequence only after that position.

For example, lest take our first list 9,10 and try to find the various decreasing sequences for it.

step 1 :1

step 2: 1

step 3: 1

step 4: 1

step 5: 1

3,2

5,2

8,2

step 6: 1

3,2,1

5,2,1

8,2,1

step 7: 1 (Important)

3,2,1

5,2,1

8,2,1

8,7

step 8: 1 (Important)

3,2,1

5,2,1

8,2,1

8,7,5,3,1

Now, we can see that for increasing order 9,10; we have a decreasing order 8,7,5,3,1 of length 5, so 5+2=7 is the length of this Bitonic.

Similarly, we can find the decreasing sequences for other lsit`s generated in part I and check the largest length.

Hope this was helpful. There may be other logic for the implementation but this was my own from scratch.

Also, this can be modified for the circular sequence.

If anyone want the code for this just put a comment below, and I would share the same.

How to delete a node in the singly link list ?

2010-06-30T11:01:00.000-07:00

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 }

Vertical sum of binary tree

2010-06-30T10:59:00.000-07:00

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

Card shuffle

2010-06-30T10:57:00.000-07:00

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 }

How to connect database with C and CPP ?

2010-05-08T12:21:00.000-07:00

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

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

2010-04-08T10:37:00.000-07:00

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

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

R – {9}

Left ST – {10}

Right ST-{11}

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.

O(1) stack operations.

2010-04-08T10:36:00.000-07:00

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 !!

A memory Q here..

2010-03-28T11:08:00.000-07:00

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.)

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

2010-03-28T09:41:00.001-07:00

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;
   }
}

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

2010-03-28T09:39:00.000-07:00

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.

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

2010-03-28T09:38:00.001-07:00

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++.

What are the general steps in compilation?

2010-03-28T09:37:00.000-07:00

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

What are the different types of linkages?

2010-03-28T09:36:00.002-07:00

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);
}

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

2010-03-28T09:36:00.001-07:00

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.

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

2010-03-28T09:34:00.000-07:00

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.

What is the difference between Merge Sort and Quick sort?

2010-03-28T09:32:00.001-07:00

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.

What is heap sort?

2010-03-28T09:31:00.000-07:00

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);
   }
}