X

# Level - 3  Questions

View By:

Q1 PONY

Discord is in trouble for causing discord, so he is trying to escape from Equestria. He's arrived at the port, and he doesn't care what boat he gets on, he just wants to get out. He can see the boat schedule, where he sees that N boats are arriving today,

boat 1 arrives any time within a_1 minutes

boat 2 arrives any time within a_2 minutes

...

boat N arrives any time within a_N minutes (uniform distribution)

Tell discord the expected number of minutes he needs to wait for a boat to arrive.

For example If n=3 , and there arriving times are 49,50,51 respectively then expected number of minutes would be 12.495000 . Thats all I know .

Q2 Log parser

Each time a visitor requests a page from our website, our webserver writes a log entry recoding the visitor's identity and the kind of page requested. Entries are written in chronological order to a plain-text file, with one entry per line. The format of each entry is:

user-id page-type-id

User IDs are arbitrary strings that uniquely represent a given user; if a user visits multiple pages, each log entry will have the same user ID. Page type IDs are arbitrary strings that uniquely represent a given kind of page on our site, such as the homepage, a product detail pages, or the shopping cart. Tons of users visit our website, but there are only a few dozen types of pages.

Q3 Staves

You want to create a staff to use in your martial arts training, and it has to meet some specific requirements.
1. You want it to be composed of two smaller staves of equal length so that you can either use it as a single staff or as two smaller ones.

2. You want the full sized staff's center of gravity to be exactly in the middle of the staff.

You have a very, very long branch from which you can cut the pieces for your staff. The mass of the branch varies significantly throughout it, so you use just any two pieces of the same length. Given a description of the mass throughout the branch, determine the longest staff you can make, then return three integers on a single line, the first two indicatin...

Q4 Given a 2-D MxN matrix having each value as difficulty for the block

Given a 2-D MxN matrix having each value as difficulty for the block. A frog is starting from a point Matrix[0][0] and will have to reach Matrix[M-1][N-1]. It can jump any step in one go [ 1, 2, ..... M-1] horizontally OR [ 1,2,3,.... N-1] vertically Each difficulty value is positive. Write code to give path trace for frog. Two structure to use -

struct node { int x; int y; struct node *next; };

struct path { int difficulty; struct node *pathlink; }

Ex matrix - 4X4 matrix

7 9 2 11 13 23 1 3 14 11 20 6 22 44 3 15

Minimum difficulty = 7 (a[0][0])+ 2(a[0][2]) +3(a[3][2])+15(a[3][3]) = 27 Path trace will have = 7->2->3->15

Q5 N-2 Problem

You are given 2 machines. There are N jobs you have to perform. Job i takes Ai time to perform on machine A and Bi time to perform on machine B. Each job should be done either on machine A or B. The jobs should be performed in order. Given the arrays A and B and an integer K, find the minimum time required to complete the jobs, given that you cannot do more than K jobs on the same machine continuously. This can be done in O(N K)space and time. This can be improved to O(N K) time and O(N ) space and further to O(N logN ) time.

Q6 Convert a doubly linked list to a Binary Search Tree

Given a sorted doubly linked list, create a BST which is balanced and not skewed.

Q7 Given a preorder and a postorder traversal, construct the tree.

Given a preorder and postorder traversal of a Binary Tree, construct the tree using these two traversals.

Q8 Destroy cities

Byteland consists of N cities numbered 1..N. There are M roads connecting some pairs of cities. There are two army divisions, A and B, which protect the kingdom. Each city is either protected by army division A or by army division B.

You are the ruler of an enemy kingdom and have devised a plan to destroy Byteland. Your plan is to destroy all the roads in Byteland disrupting all communication. If you attack any road, the armies from both the cities that the road connects comes for its defense. You realize that your attack will fail if there are soldiers from both armies A and B defending any road.

So you decide that before carrying out this plan, you will attack some of the cities and defeat the army located in the city to make ...