1. What is the BEST-WORST case time to add and remove elements from a queue that has been implemented with the help of 2 stacks.
2. There are 4 people in a closed room and you are waiting outside to enter into the room. You can enter only when one of them opens the door. The probability that somebody will open the door is 1/2. Now what is the probability that the door will be opened so that you can go inside?
3. Given an integer array A[], what preprocessing you need to do so that when given i and j such that i <= j, you can tell in O(1) time the number of elements in the array having values between and including i and j.
4. Processing times for 5 processes were given. You need to find out the minimum average waiting time the processes have to wait in order to get executed if TWO PROCESSORS are given.
5. The following figure has many squares. Remove only 4 sticks so that there are only 9 squares possible. The figure was like squares arranged in 3x3 form.
6. How many regions (open or closed) can n straight lines give at the maximum?
7. A C++ code was given and was asked to debug. The bug was, an array of a derived class object was declared. Base class pointer was made to point to the array. But to traverse the array, base_ptr++ was done which gives wrong output.
8. A graph is given. You need to design a data structure with minimum space complexity such that it does the follows
--> Finds whether nodes u and v have a path in between them in O(1) time.
--> Finds whether there is a path of length l between u and v in O(l) time.
9. There are 2 tables with 16 and 60 tuples respectively. Column A in table 1 is its primary key, whereas Column A in table 2 is the foreign key referring to table 1. Now find out the Minimum and Maximum number of tuples that are possible due to a natural join.
10. A SQL query was given and was asked to find out what it does.
11. Employee(Company Name, Employee name, Salary) is a table. You need to find out the company with maximum number of employees.
12. Find out what this function does.
int foo(int n) {
int t,count=0;
t=n;
while(n)
{
count=count+1;
n=(n-1)&t;
}
return count;
}
13. Given a graph's shortest path algorithm, how can you make use of it to find the second shortest path?
14. What does the following function return?
int foo(int n) {
int d = n, s = n;
while (d) {
d = floor(d/2);
s -= d;
}
return s;
}
15. A number of steps are there. You can go to step n either from step n-1 or from step n-2. In how many ways can you go to step n?
Section 2: (30 min)
1. Integer has been represented in linked list. Eg. 7541 has been represented as 7->5->4->1 with 4 nodes each having a digit. Given 2 such linked lists, you need to compute the sum of them.
2. Given a binary tree, you need to find out the diameter. Diameter is defined as the number of edges in the longest path that may exist between any 2 nodes of the tree.
2. There are 4 people in a closed room and you are waiting outside to enter into the room. You can enter only when one of them opens the door. The probability that somebody will open the door is 1/2. Now what is the probability that the door will be opened so that you can go inside?
3. Given an integer array A[], what preprocessing you need to do so that when given i and j such that i <= j, you can tell in O(1) time the number of elements in the array having values between and including i and j.
4. Processing times for 5 processes were given. You need to find out the minimum average waiting time the processes have to wait in order to get executed if TWO PROCESSORS are given.
5. The following figure has many squares. Remove only 4 sticks so that there are only 9 squares possible. The figure was like squares arranged in 3x3 form.
6. How many regions (open or closed) can n straight lines give at the maximum?
7. A C++ code was given and was asked to debug. The bug was, an array of a derived class object was declared. Base class pointer was made to point to the array. But to traverse the array, base_ptr++ was done which gives wrong output.
8. A graph is given. You need to design a data structure with minimum space complexity such that it does the follows
--> Finds whether nodes u and v have a path in between them in O(1) time.
--> Finds whether there is a path of length l between u and v in O(l) time.
9. There are 2 tables with 16 and 60 tuples respectively. Column A in table 1 is its primary key, whereas Column A in table 2 is the foreign key referring to table 1. Now find out the Minimum and Maximum number of tuples that are possible due to a natural join.
10. A SQL query was given and was asked to find out what it does.
11. Employee(Company Name, Employee name, Salary) is a table. You need to find out the company with maximum number of employees.
12. Find out what this function does.
int foo(int n) {
int t,count=0;
t=n;
while(n)
{
count=count+1;
n=(n-1)&t;
}
return count;
}
13. Given a graph's shortest path algorithm, how can you make use of it to find the second shortest path?
14. What does the following function return?
int foo(int n) {
int d = n, s = n;
while (d) {
d = floor(d/2);
s -= d;
}
return s;
}
15. A number of steps are there. You can go to step n either from step n-1 or from step n-2. In how many ways can you go to step n?
Section 2: (30 min)
1. Integer has been represented in linked list. Eg. 7541 has been represented as 7->5->4->1 with 4 nodes each having a digit. Given 2 such linked lists, you need to compute the sum of them.
2. Given a binary tree, you need to find out the diameter. Diameter is defined as the number of edges in the longest path that may exist between any 2 nodes of the tree.
No comments:
Post a Comment