X

# Algorithm  Questions

View By:

Q1 Facebook Programming Challenge - Bar Problem - N friends are playing a game

N friends are playing a game. Each of them has a list of numbers in front of himself.

Each of N friends chooses a number from his list and reports it to the game administrator. Then the game administrator sorts the reported numbers and shouts the K-th largest number.

You want to know the count all possible numbers that the game administrator can shout.

Input Format:

First line of the input contain an integer T, the number of testcases. Then follow T testcases. For each test case the input is of the following format.

In the first line there are two numbers N and K. In each of next N lines there is an integer a_i followed by a_i integers, ith line describes the list for ith person.

All the numbers ...

A group of N high school students wants to play a basketball game. To divide themselves into two teams they first rank all the players in the following way:

Players with a higher shot percentage are rated higher than players with a lower shot percentage. If two players have the same shot percentage, the taller player is rated higher.

Luckily there are no two players with both the same shot percentage and height so they are able to order themselves in an unambiguous way. Based on that ordering each player is assigned a draft number from the range [1..N], where the highest-rated player gets the number 1, the second highest-rated gets the number 2, and so on. Now the first team contains all the players with the odd draft numbers and ...

Q3 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 .

Q4 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.

Q5 Find elements that sum to a given value in a balanced BST

Find two elements in balanced BST which sums to a given a value. Constraints Time O(n) and space O(logn).
``````          6
3         8

1    4    7      12
``````

sum = 16 o/p should be 4 and 12

Q6 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...

Q7 URL Detection

MS Word has the inbuilt logic to detect the url when user writes to any document. MS Word application detects the url typed by user and hyperlinks it. Write a code to:

1) Detect url assuming that MS Word engine streams the characters to your function BOOL DetectURL(UCHAR chUserCharEntry) 2) Once #1 is completed then execute the url from IE

Q8 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

Q9 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.

Q10 Octa to Decimal Conversion

eg 12 in octa is 10 in deci