X

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

The beauty of a number X is the number of 1s in the binary representation of X.

Two players are plaing a game. There is number n written on a black board. The game is played as following:

Each time a player chooses an integer number (0 <= k) so that 2^k is less than n and (n-2^k) has as much beauty as n. Next he removes n from blackboard and writes n-2^k instead. The player that can not continue the game (there is no such k that satisfies the constrains) looses the game.

The First player starts the game and they play in turns alternatively. Knowing that both two players play optimally you have to specify the winner.

Input:

First line of the Input contains an integer T, the number of testcase. 0 <= T...

Q5 Game playing problem

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 in all the lists are uniq...

Q6 Decode messages encoded with Substitution Cipher

Your task is to decode messages that are encoded with substitution ciphers. In a substitution cipher, all occurrences of a character are replaced by a different character. For example, in a cipher that replaces "a" with "d" and "b" with "e", the message "abb" is encoded as "dee".

The exact character mappings that are used in the substitution ciphers will not be known to you. However, the dictionary of words that were used will be given. You will be given multiple encoded messages to decode (one per line) and they may use different substitution ciphers. The same substitution cipher is used on all of the words in a particular message.

For each scrambled message in the input, your program should output a line with the input line, f...

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

Q8 GenerateTrue

Given a number x, less than 100. How will you generate true with probability x/100. So if x = 65, how will you generate true with probability 65/100. You can represent true by 1 and false by 0.

Q9 Sort array of 3 distinct integers

Sort an array that contains multiple occurrences of 3 integers (1,2,3).

For example input: 121221123323

output: 111122222333

Q10 Find a matrix of 3x3 such that each row, column and diagonal forms a valid word in the dictionary

You are given a list of 3 letter words, as a Dictionary. You need to find a matrix of 3x3 such that each row, column and diagonal in the matrix forms a valid word in the dictionary.