Lunatic Server Solutions Interview Report
- 0of 0 votes
AnswersIn this problem you have to write a program to check if two given binary trees are structurally equivalent.
- PriyaDarad May 22, 2012 in United States
Two trees are structurally equivalent if they are both null or if the left and right children of one are
structurally equivalent to the RESPECTIVE children of the other. In other words, when you draw the trees
on paper, they should LOOK alike (ignoring the values at the nodes).
The input to the program is a number N followed by N lines of input. Each line consists of a sequence of
positive numbers terminated by -1. There will be no duplicate numbers in any of the lines.
Construct a binary search tree with the input in the second line and use this as the basis-tree. For each of the
remaining N-1 lines, construct a binary search tree and compare against the basis tree for equivalence. If the
trees are equivalent, print YES else print NO. Also print the depth difference between the two trees (ie, depth
of the bigger tree minus the depth of the smaller tree). Both these for a given tree pair must be on one line
separated by a space. The answers for the different pairs must be on separate lines.
Sample Input/Output
Input
5
1 3 2 4 -1
4 1 2 3 -1
3 2 1 4 -1
4 3 2 1 -1
1 3 4 2 -1
Output
NO 1
NO 0
NO 1
YES 0
(Note that the depth difference will be zero if the trees are equivalent.)| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Developer Program Engineer - 0of 0 votes
AnswersConsider a service counter. People waiting for service form a queue. At the start, the queue is empty and
- PriyaDarad May 22, 2012 in United States
time is 0. The service time per person is 3 minutes.
The input to the program consists of an integer N followed by a sequence of integers indicating the arrival
time (in minutes) of the customers. These times are given as offset from the start of the simulation, so that an
input of 44 means 44 minutes from the start of simulation. The sequence of input numbers is terminated by
the number -1.
Your program must simulate the queue and print out the following:
1. The number of customers waiting in the queue at time = N minutes from the start of simulation.
2. The arrival times of the customers in the queue at that time, in increasing order.
Each integer must be separated by a space. Terminate your output with a newline character.
For doing the computation, you can assume that if the counter is expected to be vacant at time t, the first
person in the queue will be scheduled for service, before the counting is done for time t.
You must use the queue data structure to solve this problem.
Sample Input/Output
Input
9 0 2 5 6 6 8 10 -1
Output
2 6 8| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Developer Program Engineer Data Structures