Sort in odd increasing even decreasing linked list

In the given linked list, odd numbered nodes are in increasing order and even numbered nodes are in decreasing order. How it can be sorted in increasing order?

Solution is very easy and is in linear time.

Given linked list

a1->a2->a3->......an

a1, a3, a5... are in increasing order.
a2, a4, a6... are in decreasing order.

First step is to get the linked list of odd numbered nodes only.
Means a1->a3->a5->...
This can be done in O(n)

Similar for even numbered nodes, a2->a4->.... This is again in linear time.
Now reverse the a2->a4-> list. It can be done in O(n).

Merge it with a1->a3->... It also has linear complexity.

And you will get a sorted linked list in linear time. 

Deletion of arbitrary node in the linked list

Given any node in a liked list without start pointer, how will you delete that node?
And what problem(s) will arise?

Solution is swap content of it with the next node (pointed by next pointer). And delete next node instead.
Problem will arise when this will be a terminal node (node with null next pointer). It will free a memory location that is longer used and still pointed by a node of linked list.

Yahoo interview questions

Yahoo visited our campus on 26th Oct. 2010. Its selection process consists of
1. Written Objective Test
2. Coding Round
3. 2 Technical Interviews
4. 1 HR Interview

Written Objective is pretty simple. One can easily get through with sound knowledge of Data structures, Algorithms, Operating Systems, Database Management Systems and little bit Discrete Mathematics.

In coding round, two problems were given which were simple if you are a regular programmer.
First one is to implement GREP without using any API/Library that supports such functionality.

Second one was level order traversal of a binary search tree. It concerned with finding sum at each level of tree that stores integers at each node.

Technical round were not that tough.

Questions are:

In first round:

1. Print linked list in reverse order using a recursive function. A code is to be written.
2. Given any node of a linked list (but not the start node), how that node can be deleted. And what problems can be faced later?
3. Two blind people are sitting near a table top. On table, there are n head faced coins and n tail faced coins. How they can distribute such that each one have equal number of heads and tails?
4. Solve f(n) = f(n-2)+2 and f(n) = f(n/2)+2 and similar RRs.

In second round:

1. Given a linked list, odd numbered nodes are in increasing order and even numbered nodes are in decreasing order. How can linked list be sorted in increasing order?
Solution is pretty simple and is in linear time.

2. How map (in C++) guarantees search in O(logn) in worst case?

Questions are quite easy.
Still I was unable to answer few one. Solution to someone I will post in my next blog.

Technical Interview

It is a hurdle which everyone has to cross to get technical position in the company. However, when it comes to a software company, it is much more of fun for techies.

What makes it different from an ordinary interview? Ordinary interview means interviewer(s) throw(s) questions on you and you reciprocate it with your answer.
Does it mean that there is no question from interviewer to interviewee? No.
Definitely there are questions. But how these questions are different from ordinary interview?

Here questions are technical one. They not only scan your technical knowledge but your other aspects.
These questions are meant for conversation as well.

At the outset, you will come to know the problem. That is "what to be done?".
And you have to discover the solution? That is it.
Perhaps not.

It is more than just "proposing a solution".


Solution is to be discussed and loud thinking is encouraged here.
The "road to the solution" is much more important than its destination.
Therefore it is conversation and discussion rather a conventional interview.
To interviewer, it is the only way to judge the candidate. However, he/she is restrained to ask any personal question which are also necessary to check the suitability of the candidate.

Hence, instead of transforming yourself into problem solving mode, you need the best of  both world. Means of technical and as well as of so called normal human being.
Candidate has to prove his both facets.
But the focus is still on the technical part but instead of solution, interviewer is much more interested in the path through which you walk towards to the solution and if that is scintillating then it is the right path you have chosen.

logn Search in rotated sorted array

Lets have a sorted array like 1 2 3 4 5 6 7 8 9. Lets rotate it arbitrary number of times. It is like 5 6 7 8 9 1 2 3 4.

Now, can element still be searched in O(lgn) time?

Limit crossed

Everyone is revered.
You will find this problem pretty interesting. Computer has some limitation on the size of number and your requirement has reached to that limit. So write a program (essentially in C/C++) which add, multiply, subtract and divide any arbitrarily large integer.

Inside or Outside?

How will you know that you are inside in a building of a polygon? Consider also concave polygon as well.

Tree b is the subset of Tree a

Given a node of a tree

typedef struct node

{

int info;

struct node *left,*right;

}
node;

Given the function prototype is

 bool isSubset(node *a,node *b);

Write the C code to implement the function.

Counting set bits

Can you suggest the way to count the bits that are set in the number?

Find the maximum of three

Though it may appear very trivial, but what is now so special about finding maximum of 3 numbers is that no comparison or relational operator is to be used. See if you can go for it.

C: What is the use of stderr?

In the C, error or other messages can be displayed by using printf or by using file stdout. Then what is the need of stderr? Why it is so special to display error using stderr file pointer?

Removing ab patterns

Given a string of containing alphabets. Task is to remove ab patterns in linear time using inline algorithm.

e.g. cdaabbcd gives the output cdcd after the execution of the algorithm.

Rotating triads of a linked list

Given a linked list a>b>c>d>e>f. We need to rotate each triad. e.g. c>b>a>f>e>d. However data is so large that its movement is a costly operation in terms of memory as well as time. Write a C code to preform the task.

Tries

Tries is a data structure used to show some keys in the tree rather than in the string array. List some advantages and how it can be compressed.

Dynamic Link library Problem : Microsoft technical interview question

Consider a DLL containing a substantial number of functions. Few functions from it are shipped. It is given that which function call which one. Design an algorithm to remove unused function from the DLL. Means main objective is to detect unused function.

Few C puzzles

1. What's the difference between the 
following two C statements?
  const char *p;
  char* const p; 

2. Write a C function which does the addition of two integers
without using the '+' or '-' operator. 

3. The following is the macro implementation of the famous, Triple xor
swap.
  #define SWAP(a,b) ((a) ^= (b) ^= (a) ^= (b))

What are the potential problems with the above macro?
 

Welcome to this blog

Hello friends

This is the blog for the fun purpose to discuss technical stuff related to Computer Science. If you have any query/answer, do not hesitate to post here. However, please adhere to the few good rules.
These are
1. Use decent language
2. Do not annoy anyone.
3. Respond properly
4. Do not comment unnecessarily

And it is being loaded