Technical Questions in the second round

Download 466,44 Kb.
 Page 3/6 Date conversion 09.08.2018 Size 466,44 Kb.
 Write a program that plays "Cows and bulls". The user thinks of a number less than 10000, with no two digits identical (like 1234. numbers like 0875 are allowed. But 5456 and 3922 are not because it contains 2 indentical digits). The program starts by guessing a number. The user gives the number of hits and misses. A hit is a number in the right place and a miss is a number in the wrong place. e.g If the the number you thought is 4273 the feedback for 2135 is 0 hit 2 miss 0913 is 1 hit 0 miss 4217 is 2 hit 1 miss Your program should use the feedback provided by the user for the next guess and keep guessing after every feedback till it gets the right number. A good program will get the number in about 7 guesses (on an average). -------------------------------------------------------------------------------- Algo : 5) Cows and bulls. This requires some explaining because nobody got it. But actually its not that difficult. You create an array of all possible numbers. Guess one randomly from that list. Based on the feedback reduce your list eliminating the numbers that can't satisfy the feedback. Guess again from the new list. You will hit the right number in 5 to 7 trys. -------------------------------------------------------------------------------- 6) Knapsack problem. A Sack is given with a specified volume. And a set of bags are given, each with a specified mass and volume. You have to fill the sack using some of bags such that the total volume of chosen bags is less than or equal to the volume of the sack and their total mass is maximum. Input: Input will be read from a file called "bags.dat". It will contain the number of bags, the volume of the sack, followed by the volume and the mass of the bags. eg. 6 100 10 2 50 10 20 5 40 9 30 5 35 8 Output: Output should be printed on the screen. It will be the number of all the bags to be used. For the given example it will be, 3,4,6 -------------------------------------------------------------------------------- Algo : 6) Knapsack problem. This is a straight forward algorithm. Try all possible combinations that satisfy the given volume constraint and choose the one with the maximum mass. -------------------------------------------------------------------------------- 7) Zigzag An n by m matrix with all its elements between 1 to 4 is given. The left top element(1,1) is 1 and right bottom element(m,n) is 4. You have to find out a continuous zigzag path connecting these two elements, such that, 1)small parts of the zigzag are lines connecting two elements. 2)The numbers in the zigzag path should read 1-2-3-4-1-2-3-4... 3)The zigzag must touch all squares. Assume a solution exists. Example : Given: Solution should be: ;1 3 1 2 ;1 3 1-2 |/ \| | 2 1 4 3 2 1 4 3 / \ / 2 3 4 3 2-3 4 3 / /| 4 1 2 4; 4-1-2 4; Input: input should be read from a file called "matrix.dat". The file contains, row no. column no. elements. eg. 4 4 1 3 1 2........ Output: Output should be printed on the screen. Program should print out the row and column numbers of the elements in the order they are visited. eg. (1,1) (2,1) (1,2) (2,3) ..... -------------------------------------------------------------------------------- Algo : 7) Zigzag. Many people used brute force algorithms. Their code didn't work for a matrix of order 8. One way to do this is to maintain a list of all possible ins and outs for every square. Using the ins of the neigbouring nodes decrease the possible outs for every square. Then use the neighbouring outs to decrease the ins of every square. Do this a few times and you will get very near the solution. Then do a few check and you can get it. -------------------------------------------------------------------------------- 8) Partitioning You have "n" numbers having values from 1 to n. You have to write a code to partition it into "m" groups such that sum of numbers in each group is equal to n*(n+1)/(2*m). Assume that numbers n and m are such that n*(n+1)/(2*m) is an integer. Your program should print out the numbers in each group. Or if it is not possible to partition the numbers into m groups, then print out that its not possible. Example : n=20 and m=3 Group 1 : 1,8,11,13,18,19 Group 2 : 2,5,12,14,17,20 Group 3 : 3,4,6,7,9,10,15,16 Input: Two integers n,m. Output: Print out to the screen the numbers in each group in a differnt line. Testing: We will run atleast 5 test cases for this problem. So if you cannot write a generalised code which will take care of all n and m, you can try to write codes based on specific conditions. -------------------------------------------------------------------------------- Algo : 8) Partition. An algo which worked very well, was to start by adding the number n(the largest number) to group 1. Then add the next largest number ( n-1 in this case) , and check whether your sum in that group is greater than n(n+1)/(2m). If it is greater, than take out the number and then add the next greatest number and so on till you get the sum equal to n(n+1)/(2m). For the next group, start out similarly, add the largest of the remaining numbers to the group, and keep adding the next largest, till you get the sum. -------------------------------------------------------------------------------- ********************************************************************************************* PROBLEM 2: C-on-test - Intra-IIT Round Brought to you by CSEA, IITB in association with VERITAS software. -------------------------------------------------------------------------------- Problem 1. ~~~~~~~~~~ With Election fever on its high and politicians running short on time you have write an program which they can use to call junta to come forward and vote... The program should print Come-Sure-Come on a line by itself just once. No leading or trailing spaces. The output is case sensitive i.e. come-sure-come would be regarded as incorrect. As an concerned citizen of this country you should do your bit towards it. Ask yourself, Do you want an elected government or are you apathetic ? -------------------------------------------------------------------------------- Problem 2. ~~~~~~~~~~ Elections over, mps' elected, the auction house set and the horse-trading is on. All the mp's are seated in a circle. Each belongs to either the H front or the T front of the regional faction of the secular group of the leftist liberal democratic anti-communalist pro-poor progressive party of India. In the center of the circle is THE ONE of the current polity Akal Bechari Bhaggayi (ABB). His aim is to convert all the mp's to either H or T group. But mps' being mps', having had years of experience are not so easy. They always go in pairs (so they can use each other as excuse later). In each step ABB can ask any 2 adjacent mp's to toggle their loyalty. Time however is of the essence. Everyone wants a piece of the action and if ABB doesnot convert fast he will be out of center stage. This is where you come into the picture. You being the brilliant students from IITB can surely use your skills to help him out. Help ABB figure out the minimum number of steps required to achieve his aim. You will be given a string consisting of H's and T's as input on a single line. The size of the input is bounded above by 1600. Consider the input string to be the Circle listed out clockwise from some point. You have to output the number of steps it will take ABB to convert all mp's to one type. The number is to be printed on a line by itself. No leading or trailing data. If it is not possible to do the conversion then output -1. Sample Input: HTTH ~~~~~~~~~~~~~ Sample Output: 1 (for above example. Either pair of T's or H's ********************************************************************************************* PROBLEM 3: | Problem 0: Helloworld | `-----------------------' The Problem ~~~~~~~~~~~ (Freebie) Write a program to print the sentence, Hello world on the screen. There is one space between the two words, and a newline after World. The program should then input an integer, add 10 to it and print the sum on the screen, followed by a newline. Note: You need to submit this program first to register yourself. .. 2 marks In Short ~~~~~~~~ int main() { int x; printf("Hello world\n"); scanf("%d", &x); printf("%d\n", x+10); } Comments ~~~~~~~~ This program tests the editor, compiler, submission script, mail, printf, scanf, +, and just about everything else. In addition, it registers the person by creating his program and score directories. Some smart IITian tried out int *x; scanf("%d", x); printf("%d\n", *x+10); which promptly crashed, leaving him wondering why. Someone else (actually, me) did "Hello World" (caps W) and got incorrect. My fault, actually. I forgot to lowercase it before checking. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ,-----------------------. | Problem 1: Monontonic | `-----------------------' The Problem ~~~~~~~~~~~ An IITian student, having forgotten to attend his last Physics lab, has to now cook up a graph for the lab report. He has a moth-eaten journal from ten years ago of the same lab, in which the readings are there, but not in the same order that they were taken down from the experiments. Each reading has an x-value which runs from 1 from to the number of readings, and a y-value, which may be any positive integer. However, only the latter is visible for each reading, in the old report. The student knows that the final graph is a sine wave. With a couple of hours left for submission, he decides that the closest he can get to that is to plot a ``zigzag graph''. He will rearrange the readings in such a way that when a line is drawn between successive readings on the graph, a zigzag pattern is obtained, with every point being at a local maxima or minima of the graph. There may be more than one reading with the same y-value, but if they are placed adjacent, the lab instructor will spot the student's ploy immediately and have him repeat the experiment. Hence, he wants to avoid an arrangement in which this happens. Write a program that given a sequence of readings, determines whether they suit the student's requirements or not. The input consists of n+1 lines, with a single integer on each, when there are n readings. The first number is the number of readings, i.e. n, and the remaining numbers are the y-values of the readings, given in no particular order. The output should be the word ``no'' in lowercase letters, if the readings can't help the hapless student, or the required sequence, if they can. In the latter case, the readings, in the correct order, should be output as a single integer on each line. Hence, for an n-reading problem, for which a ``good'' rearrangement exists, the answer will consist of n lines. There will be at most 500 readings, with y-values in [0,10]. ... 15 marks In Short ~~~~~~~~ We define a monontonic sequence as one which strictly increases and decreases alternately, starting with either increase or decrease. Given a sequence of numbers, find a monontonic permutation if you can, or print "no" if you can't. My approach ~~~~~~~~~~~ If the number with the maximum number of occurrences occurs more than N/2 times, then it's not possible to find a sequence. Otherwise alternately output numbers on either side of this most frequent number. The problem would become more interesting if we insist that the final sequence has to have increasing magnitude. Alternatively, (due to sami), one might use divide and conquer, knowing that an odd length sequence may *have* to start with an increase or a decrease, but an even length sequence, on reversing, starts with the other kind of change. Therefore we can have a merge sort like algo with the merging step optionally reversing one or both the even-length (power of 2) sequences and concatenating. Winner1 algo ~~~~~~~~~~~~ (GREEDY) Sort the numbers in decreasing order and split the sequence in half. Now, construct the final sequence by taking alternate elements from the two halves. There will be 4 possible ways of doing this. Consider all of them. Winner2 algo ~~~~~~~~~~~~ Sort the list in increasing order . Let this be b1,b2,....,bn Form two lists as follows. b1,b4,b2,b5,b3,b6 and b4,b1,b5,b2,b6,b3 for even n ( here n=6) b1,b5,b2,b6,b3,b7,b4 and b4,b1,b5,b2,b6,b3,b7 for odd n ( here n=7) If in both lists there are consecutive equals then solution not possible else print that list in which no equal consecutive are present. Winner3 algo ~~~~~~~~~~~~ Sort Even 2n nos if a(n)=a(2n) no else pick a(n) a(2n) a(n-1) a(2n-1) ..... Odd 2n+1 nos : if a(n)=a(n+1) no else pick a(n) a(2n+1) a(n-1) a(2n) .... and place a(n+1) appropriately if it fits (End beginning or centre) Test cases ~~~~~~~~~~ yes: 1 2 3 yes: 1 2 2 3 yes: 3 2 2 1 yes: 2 1 3 2 yes: 2 3 1 2 yes: 2 2 1 3 yes: 1 3 2 2 no : 1 2 2 2 3 yes: 3 2 2 2 3 yes: 1 2 2 2 1 yes: 3 3 3 6 6 6 yes: 6 4 6 4 6 4 6 yes: 1 2 2 2 2 2 4 5 6 7 no : 1 2 2 2 2 2 4 5 6 yes: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 yes: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 no : 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 no : 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 no : 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 yes: 3 3 3 3 3 4 4 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 4 4 4 4 3 3 3 3 3 3 3 3 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 4 4 4 4 3 3 3 3 3 3 3 4 4 4 3 3 3 3 3 3 3 3 3 3 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ,-------------------------. | Problem 2: Setsplitting | `-------------------------' The Problem ~~~~~~~~~~~ Bheeshma looked grimly at Krishna and said, ``You must decide, O Yadava, whom you will give your armies to. They cannot remain neutral in the great war that will take place.'' ``But I love both the Pandavas and Kauravas. If I give, I give equally, or I do not give at all.'', replied Krishna, petulantly. Bhishma beamed. ``That is as easily done as winning a game of Snakes and Ladders with Shakuni at your side. Just give Yudhistira half your men, and Duryodhana the other half.'', he said. ``Not so, Pitamaha! My army is comprised of many akshauhinis and the men of an akshauhini fight together. So, I have to give an entire akshauhini to either brother, and not parts of it. Unfortunately, each akshauhini has a different number of soldiers, and the math I learnt at my Gurukul is inadequate to help me figure out how to distribute the akshauhinis. What do I do?'', wailed Krishna. Bheeshma looked on, nonplussed. This was going to be a tougher nut to crack than that fisherman chap so many years ago.... Write a program that given the number of soldiers in each of Krishna's akshauhinis determines whether he will send his soldiers to war or not. The input consists of n+1 lines, for n akshauhinis, the first line containing a single integer which is the number of akshauhinis and every other line containing a single integer which is the number of soldiers in the corresponding akshauhini. The output should be the word ``no'' on a line, if there is no equitable distribution possible. If there is, then output the distribution in the following manner: for each akshauhini that goes to the Pandavas, print a +, followed by a space, and the number of soldiers in that akshauhini. For the Kauravas, substitute the + with a -. Each number (with its appropriate sign) should appear on a line by itself. There are at most 100 akshauhinis, with 0 to 100 soldiers in each, inclusive. ... 20 marks In Short ~~~~~~~~ You're given a sequence of numbers, you're supposed to insert +'s and -'s in between so that it evaluates to zero. i.e. find a subset of sum S/2, where S is the sum of all numbers (assumed positive). The numbers are given to be N in number and bounded by M. For example ~~~~~~~~~~~ 1 2 3 4 : + 1 - 2 - 3 + 4 or - 1 + 2 + 3 - 4 1 2 3 10 : no My approach O(MN^2) ~~~~~~~~~~~~~~~~~~~ Have an array of size M*N which marks all the sums that can be made out of the N numbers. For example, 0 can be formed by taking no number in a set. x1 can be formed. x2 and x1+x2 can be formed. i.e. for each number xi, go through the array sj and mark xi+sj as formable. In the end, check if the S/2'th element of the array is marked. For finding the sequence, the entire sequence need not be stored for each array element, a pointer is sufficient. For example, s[0] = 0, s[x1] = 0, s[x2] = 0, s[x1+x2] = x1, ... so that by following s[S/2] down to 0, the set can be obtained. Winner1 algo ~~~~~~~~~~~~ (BRANCH AND BOUND) Recursively enumerate all the subsets of {1,..,N}, where N=#inputs. Whenever the running sum of a subset exceeds half the total sum, abandon that path. Winner2 algo ~~~~~~~~~~~~ We used Brute force. Let the list be a1,a2,..,ai,...,an. Initially i=1 and av[1]=(a1+a2+.....+an)/2. Prob: pick some numbers in ai to an such that total is equal to av[i]. step: If we can include ai solve the prob with av[i+1]=av[i]-ai and i=i+1. If we can't include ai solve prob with av[i+1]= av[i] and i=i+1. If i>end : Solution not possible for that combination. If at any stage num[i] is -ve : Sol not possible for that combination. If at any stage num[i]=0 : Sol found. If solution is not found for a1 then solution not possible. Winner3 algo ~~~~~~~~~~~~ Greedy: Sort Pick the largest as long as feasable Feasable when fits and required no > least no. Test Cases ~~~~~~~~~~ yes: 1 2 3 4 5 6 7 no : 6 5 4 1 2 3 yes: 1 2 2 3 no : 2 4 6 10 no : 4 1 16 2 7 yes: 0 no : 2 1 1 1 1 2 2 1 2 2 yes: 1 2 1 1 1 1 2 2 2 1 2 2 yes: 1 1 1 1 1 1 yes: 70 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 yes: 11 19 33 48 7 8 yes: 50 40 10 10 1 1 1 1 1 1 1 1 1 1 yes: 40 27 91 54 67 9 36 40 61 92 30 11 61 0 34 8 32 84 39 73 37 52 71 86 48 35 72 4 31 8 49 47 56 95 48 20 87 72 31 10 30 83 77 5 89 34 68 36 19 10 96 95 43 49 22 95 12 60 11 93 15 72 72 69 73 26 90 96 24 78 1 0 95 0 60 23 88 69 52 34 37 16 45 14 93 41 90 5 52 51 56 69 46 29 28 90 12 5 81 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ,------------------. | Problem 3: Areas | `------------------' The Problem ~~~~~~~~~~~ Star Date 6876.21. The known Universe is under the control of Earth. To facilitate easy patrolling, all of Earth's dominion has been mapped onto a two-dimensional grid of squares. The grid is described by equidistant points, with each pair of adjacent points being joined by lines. Each square in the grid is a colony of Earth, and any spaceship must travel only along the lines of the grid. Recently, a renegade band of Klatchians have been making furtive raids on our colonies. A Klatchian ship materialises at some point on the grid and drops its crew there. The crew travels from point to point in some random order, and after some time returns to the point where they started so that the ship can pick them up again. During this journey, they may revisit points and travel lines they have already gone through. All the colonies circumscribed by the travel line of the Klatchians are laid to waste. Earth Patrol has managed to capture an abandoned ship used in such a raid that contains only a log mentioning the details of the crew's trip along the grid lines. Each line of the log contains a letter, ( n, s, w, e), which gives the direction of travel (north, south, west, east) and a number that denotes the number of lines travelled in that direction. For example, the log, ( s 1 w 1 n 1 e 1 ) is a trip that destroys exactly one square, while ( s 2 w 2 n 2 e 2 ) destroys 4. A longer sequence, with a diagram describing the travel is attached at the end. Write a program that given the details of a Klatchian trip finds out how many colonies have been destroyed. The input is as specified above in the example, and the output should be an integer with no spaces before or after it, and succeeded by a newline, that gives the number of colonies. There are at most 200 lines of input, with the number on any line not exceeding 200. ... 25 marks In Short ~~~~~~~~ A particle moves on a grid in an arbitrary manner, but finishing at the starting point. What's the area of the boundary of the region it encloses? My approach ~~~~~~~~~~~ Find a point outside and floodfill, by doing a DFS on the outside region. Winner1 algo ~~~~~~~~~~~~ (O(M^3) ALGO) The alien travels along some M lines, say. Extend all these lines in both directions. This gives rise to some grid of rectangles. For every rectangle in this grid, find out if it is bounded on all 4 sides by line segments from the alien's path (standard test for point inclusion in a convex figure). If yes, add this rectangle's area to the current area. Others have not submitted algos ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Test Cases ~~~~~~~~~~ 1) 4, e 1, n 1, w 1, s 1 . -- . Area = 1 | | . -- . 2) 4, n 1, w 1, e 1, s 1 . -- . Area = 0 | . 3) . -- . | | . . -- . | | . -- . -- . 4) . -- . -- . | | . . -- . | | . . -- . -- . | | . -- . -- . -- . 5) . -- . | | . -- . -- . | | . -- . 6) . -- . -- . | | . . -- . -- . | | | | . -- . -- . -- . -- .

The database is protected by copyright ©sckool.org 2016
send message

Main page