implement procedure find(N,X) that returns 1 if there exists a sensor at height X and returns 0 otherwise.

Animal behavior researchers would like to get information on animal movements in a valley. They have placed N motion sensors along a straight line crossing the valley at various heights. For 0 <= i <= N-1, the i-th sensor's height is h_i (0 <= h_i <= 1 000 000 000). No two sensors are on the same height.
Since the line is on a valley, the heights of sensors satisfy these constraints:

• there is an integer k (0 <= k <= N-1), such that the k-th sensor has the minimum height,
• for all 0 <= i < k, h_i > h_i+1, and
• for all k <= i < N-1, h_i < h_i+1.

However, because the sensor installation team forgot to measure the sensors' heights, the value of k, and all the heights h_i's are not known.
You would like to find if there is a sensor at height X. This seems to be hopelessly impossible, but you recall that each sensor has a height meter and can report its height. To minimize the power usage, you would like to make only a small number of height queries.

Implement

You have to implement procedure find(N,X) that returns 1 if there exists a sensor at height X and returns 0 otherwise. Your procedure can call a procedure query(i) to get h_i. However, you can make at most 50 calls, for each run of procedure find.
Note: In a single run, the sample grader, provided with the prototype, may perform many calls to find in one run. While the sample grader uses the same heights for all calls, the real grader may use different heights between each call to procedure find. Therefore, you should not assume that two different calls to procedure find share the same height information.

Example

Suppose that N=4 and the height of each sensor is:

sensor	height
0	10
1	7
2	9
3	15

Note that in this case, k=1. The following are the return values from procedure query:

calls	returns
query(0)	10
query(1)	7
query(2)	9
query(3)	15

The correct implementation of procedure find, when called by the grader, should return as in the following table.

calls	returns
find(4,10)	1
find(4,2)	0
find(4,9)	1
find(4,15)	1
find(4,100)	0

find the maximum sum of temperatures of K consecutive days

Thailand is a tropical country. Thai people usually say that Thailand has 3 seasons: Hot Summer, Hotter Summer, and Hottest Summer. It especially feels very hot when you have many consecutive days with high temperatures.
You are planning a K-day trip to Thailand. Since you would like to experience the real Thai Summer, you want your stay to be as hot as possible.
You are given a list of forecasted temperatures of N consecutive days. You would like to find the maximum sum of temperatures of K consecutive days. It is guaranteed that 1 <= K <= N.

Implement 

You are to implement procedure maxk(N,T,K) that returns the maximum sum of temperatures of any K consecutive days, where N is the number of days and T is an array of positive integers where T[i], for 0 <= i < N, is the temperature of day i.

Example

Suppose that N=6, K=3 and T = 10 50 30 20 5 1.

There are 4 possible 3-day trips, starting from day 0, day 1, day 2, and day 3; and their sum of temperatures are 90, 100, 55, and 26. Therefore, procedure maxk should return 100.

Subtasks

Subtask 1

• N <= 1 000, 0 < T[i] <= 1 000

Subtask 2

• N <= 1 000 000, 0 < T[i] <= 1 000

you have to encode the data into a sequence of alphabets, transmit the encoded data, and decode it to obtain the original integer data.

You would like to transmit integer data through a special channel, i.e., this channel only supports transmission of alphabets a - z. In order to do so, you have to encode the data into a sequence of alphabets, transmit the encoded data, and decode it to obtain the original integer data.
The overall process is shown in the following figure.

       You have to implement:

• Procedure encode(N,D) that encodes the data, where N denotes the length of data and D is an array of integers representing the data, where D[i] is the i-th integer in the data. (0 <= D[i] <= 255.) This procedure must call procedure send_data(c) for each character c in the sequence to transmit the encoded data. Each encoded character c must be lowercase English alphabets, i.e., alphabets a - z.
  
  Procedure decode(M) that decodes the data, where M denotes the length of the encoded data. To read the encoded data as a sequence of characters, this procedure must call procedure read_data() for each character in the sequence. It may call read_data for at most M times. To output the decoded data, it must call procedure output_data(y) for each integer y in the decoded data.
  
   Follow Up
  

  Subtask 1

• N <= 100 and 0 <= D[i] <= 25.
• The encoded data should not contain more than 100N characters, i.e., encode may not call send_data more than 100N times.

        Subtask 2

• N <= 100.
• The encoded data should not contain more than 100N characters, i.e., encode may not call send_data more than 100N times.

        Subtask 3 (40 points)

• N <= 100.
• The encoded message should not contain more than 2N characters, i.e., encode may not call send_data more than 2N times.

You need to write a program that calculates the advanced edit distance of two given words.

The edit distance of two strings S and T is the minimum number of edit operations that need to be done to transform S into T . The valid edit operations are:
• Insert a single character at any position.
• Modify an existing character.
• Remove an existing character.
For example, the edit distance of “pantera” and “aorta” is 5, because the following chain of
edits is valid (and there is no shorter chain):
“pantera” >>> “antera” >>> “aotera” >>> “aoera” >>> “aora” >>> “aorta”.
We define the advanced edit distance in a similar way, but adding the swap of two adjacent characters as an extra valid operation. With this setting, the advanced edit distance of “pantera” and “aorta” is 4:
“pantera” >>> “antera” >>> “antra” >>> “aotra” >>> “aorta”.

You need to write a program that calculates the advanced edit distance of two given words.

In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. We have to do it in O(1) extra space.

Transpose Algorithm 

Basically, we are converting rows into columns. E.g. a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should be changed to a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4.

a1 b1 c1 (i=1)

a2 b2 c2 (i=2)

a3 b3 c3 (i=3)

a4 b4 c4 (i= 4)

So we should write the array as a1 a2 a3 a4 b1 b2 b3 b4........, only this time, we are writiing column wise.

The program is recursive. The variable i is the number of groups

#include

#define SIZE 12 //multiple of 3

void arrange(int arr[], int n, int i)

{

if(i == 1)

{

arr[1] = arr[n];

arr[2] = arr[n <<1]

return;

}

int a = arr[i - 1];

int b = arr[n + i - 1];

int c = arr[2*n + i - 1];

arrange(arr, n, i - 1);

int x = 3 * (i - 1);

arr[x] = a;

arr[x + 1] = b;

arr[x + 2] = c;

}

int main()

{

int n = SIZE;

int a[SIZE], i;

printf("\nEnter %d numbers", SIZE);

for(i = 0; i <>

scanf("%d", a + i);

if(n != 0 && n % 3 == 0)arrange(a, n/3, n/3);

for(i = 0; i <n;i++)
printf(a[i]);

printf("\n");

}

Given a root and a node of a BST tree, write a function which print all the nodes which are a 'k' distance from the given nodes in sorted order. (distance can be upwards and downwards)

Given a function getInorderSuccessor which takes a BST (Binary Search Tree) as it's parameter. Every node has an extra pointer "next" , which is intialized to null, fill next with node pointers which represent Inorder Successor.

Design a Architecture of Online Movie Booking System . Find the possible issues and Idea to Resolve them. How do you optimize the Performance against all these issues.

We are interested to find out the number of Distinct customer visited at-least p distinct pages within exactly T days.

Suppose, Amazon have a Logging system Like This:
They Track all logs daily basis, stored in separate log file.Log contains a collection of tuples of Customer ID and Page ID. The length of Customer ID and Page ID is L1 and L2. Suppose We have a log of D-days , and size of each log fine can be Order of n , where n be the number of customer.
In a most generalized situation, you can assume that a customer can visit the same page multiple times in a day or any number of days.
We are interested to find out the number of Distinct customer visited at-least p distinct pages within exactly T days.
Propose a Data Structure to be use to solve this problem efficiently . Design an Algorithm to solve this problem and Find out the complexity of the algorithm.

how many heaps can be created with complete binary tree of n nodes

Alex is curious about data structures. He is working on binary trees recently and particularly interested in complete binary trees.
A complete binary tree satisfies that all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

Alex defines his own complete binary tree: each node has a weight, while father's is always less than or equal to its sons'. He names this complete binary tree as minimum heap.

Now he wants to know: With N nodes weighted from 1 to N (each appears once), how many heaps can be created. The answer (represented by Q) may be very large, so please output a number P while P = Q mod M.

Followed Up:
Consider a complete binary tree of height n, where each edge is a one Ohm resistor. Suppose all the
leaves of the tree are tied together. Approximately how much is the effective resistance from the root to thisbunch of leaves for very large n?

(a) Exponential in n
(b) Cubic in n
(c) Linear in n
(d) Logarithmic in n
(e) Of the order square root of n