1. Convert a binary tree to pre-order doubly link list without using extra memory .

(you can only use constant amount of memory)

2. Write a function which checks a given Binary Tree is BST or not.

prototype:-

int isBST(Tree * root)

3. Draw memory-map for C program.

4. Suppose you are a station master and you know the schedule of arrival and departure of trains passing through that station for a particular day .You need to find the minimum number of platforms required to fulfill this task.

Eg:-

Trains arrival departure

T1 9:00 9:30

T2 9:15 10:00

T3 9:45 10:10

(consider time line to be 00:00 hours to 23:55).Here at 9:20 there will be two trains at the station , So we need at least two platform for this schedule.

Ans :- 2

Eg:-

Trains arrival departure

T1 9:00 9:30

T2 9:15 10:00

T3 9:20 9:25

(consider )

Here at 9:21 there will be three trains at the station , So we need at least three platform for this schedule.

Ans :- 3

Eg:-

Trains arrival departure

T1 9:00 9:30

T2 9:10 9:15

T3 9:20 9:25

(consider )

At any point of time at max two trains will be at the station.

Ans :- 2

Note :-

Trains arrival departure

T1 9:00 9:30

T2 9:30 10:00

In this case both the trains can use the same platform

Ans : 1

5. Consider a tree

struct tree{

int data,

struct tree *lchild, *rchild, *parent ;

}Tree;

(Here parent pointer of a node points to it's parent node)

Given two leaf nodes find the least-common-ancestor

of them.

prototype:

Tree* lca(Tree *leaf1, Tree *leaf2

6. Given an array every element is repeating odd number of times

except one number.

Find the number which is being repeated even

no of times.

7. Given a string remove multiple spaces except one.

(Similar like html)

Eg. input :- " hi dost how are you "

output:- "hi dost how are you"

8. A pirate ship captures a treasure of 1000 golden coins.

The treasure has to be split among the 5 pirates: 1, 2, 3, 4, and 5 in order of rank.

The pirates have the following important characteristics:

* Infinitely smart.

* Bloodthirsty.

* Greedy.

Starting with pirate 5 they can make a proposal how to split up the treasure.

This proposal can either be accepted or the pirate is thrown overboard.

A proposal is accepted if and only if a majority of the pirates agrees on it.

What proposal should pirate 5 make?

Sol:- http://www.puzzlesite.nl/teasers/index_us.html#pirate_treasure

9. There is a link-list having structure

struct LinkList{

struct LinkList *next, *sortedNext;

int data;

}

Initially sorted Next pointer points to null and next points

to the next pointer as in simple link list.

Manipulate the pointers such that sortedNext pointer of each

node points to the sorted-next node

(It´s the first node in

right side when link-list is sorted).

10. Find all pythagorean tripletes in a given array of integers.

11. Explain some problems with multi-threading and implement a lock if a section of code is shared by two different processes.

## 0 comments:

## Post a Comment