Technical Questions in the second round



Download 466,44 Kb.
Page4/6
Date conversion09.08.2018
Size466,44 Kb.
1   2   3   4   5   6

| | | |

. . -- . .



| |

. -- . -- . -- .

7)

. -- . -- . -- .



| |

. -- . -- . . -- . -- .

| | | | | |

. . -- . -- . -- . .

| | | |

. . -- . -- . -- . .



| | | | | |

. -- . -- . . -- . -- .

| |

. -- . -- . -- .


8)

. -- . -- . -- . -- . -- . -- .

| |

. . -- . -- . -- . -- .



| | | |

. . -- . -- . -- . -- . .

| | | | | |

. . -- . -- . -- . -- . . .

| | | | | | | |

. . -- . -- . -- . -- . -- . -- . -- .

| | | | | | | |

. . -- . -- . -- . -- . -- . -- . -- .

| | | | | | | |

. -- . -- . -- . -- . -- . -- . -- .

| | | | | |

. . . -- . -- . -- .

| | | |

. . -- . -- . -- .



| |

. -- . -- . -- .

Basic pattern:

.

|



. -- . -- . -- . -- .

| |


. .

| |


. .

| |


. -- . -- . -- .
9)

. -- .


| |

. -- . -- . -- .

| | |

. -- . -- . -- .



| |

. -- .
10) . -- .

over and over the same square | |

still area = 1 . -- .


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

,------------------------.

| Problem 4: Superstring |

`------------------------'


The Problem

~~~~~~~~~~~

A scientist working the swampy, mosquito-infested jungles of

Sumatra has made an interesting find. She has recovered fragments of

the gene code of a long-extinct animal, the Blarky, each fragment

consisting of a string of molecules. The Blarky's genetic code is much

like ours, with each molecule represented by a letter, except that all

26 letters are used, unlike our code that uses only the four letters,

A, T, C and G to code the molecules in the gene.
Unfortunately, no single sample is guaranteed to be the entire

genetic code of the Blarky, though it is known that every sample

contains a string of consecutive molecules in the actual code. To

reconstruct the final genetic code, our scientist relies on a

well-known principle in genetics that states that the best

approximation of a genetic code from its fragments is obtained by

finding the shortest sequence of molecules that contains all the known

fragments. For example, if the fragments gyy, segyy and

puse are available, then the best guess at the code is

pusegyy.
Write a program that, given gene fragments, obtains the best

approximation. The input consists of n+1 lines when there are n

gene fragments. The first line has a single integer, which is the

number of fragments. All other lines have a single sequence of

letters, there being no space between letters. The sequence on each

line represents a different gene fragment obtained by the scientist.

The output should be the genetic code as guessed from these fragments.

Each fragment is at most 20 molecules long, and there are at most 100

fragments with the scientist. ... 38 marks


In short

~~~~~~~~


You are given some strings, and you are expected to find the shortest

string that contains all the other given strings, i.e. the shortest

superstring.
My approach

~~~~~~~~~~~

NP-hard, and can be mapped to finding the Hamiltonian path. Hence

approximate solutions (within 91% of my exact ones) are given full

credit.
Winner1 algo

~~~~~~~~~~~~

(GREEDY) At any stage, find the pair of strings giving the maximum overlap

on merging in the best possible manner. Merge them, and proceed. At the

end, the string left is the approximate answer.
Winner2 algo

~~~~~~~~~~~~

Sort the strings in descending order of length. Pick the longest and

copy it in the final string. Take the next one.Insert it as follows.

If the final string is "abcdef" and the string to be inserted is

a. "pqr" . Final becomes "abcdefpqr".

2. "def". Final remains the same.

3. "defd". Final becomes "abcdefd"

4. "fabc". Form two strings "fabcdef" and "abcdefabc" and Final

becomes the shorter of two.

Keep on inserting strings in the descending order. Its a NP hard

problem. No polynomial time algo exists for it. Our algorithm works

for fairly large number of cases.
Winner3 algo

~~~~~~~~~~~~

Just removed strings that were already present
Test cases

~~~~~~~~~~

1. all overlaps are zot

: any algo will work


2. aaaaa aaabbb aaabbb bbbccc

: two strings identical


3. aaaaa aaaab aabac baaab aabaab

: general arbit


4. cdefghi abcdef hijklm efghij

: two possibilities exist, which do you choose ?


5. raman mantra uma

: greedy does not work:

greedy takes raman+mantra = ramantra, and then uma: ramantrauma

you should take mantra+raman = mantraman, and then umantraman


6. abcd abef cdab efab
7. hello hell llama lotus shell ellot

: one string is a substring of another


8. finger oafing german muffin codger
9. life feels silli
10. with all the might of the earth rama lifted his bow and in just

one stroke fired twenty types of arrows which made all around him

stop to think about his powers

: to check exhaustive searches


11. who holds the hell torch is none other than the guy who lives here

or there and doth not know fear


12. abcdef defab fababc babc labcd gabcde gfab bcdfab ababef cdlab gbcd bcdg
13. csea prog contest is the worst thing that took place ever
14. sc re w t he gu y w ho do es an ex ha us ti ve se ar ch so th at he

lo ok s fo r be tt er so lu ti on s


15. abab abbc bbcad dacca aabdba abdbabd abadbabdbdbabad adbdbdabadba abdbab

adbbad adbabdad adbadb adbadb adbbdaba dabdbad dbadbadabb dbadab dba

: general arbit
************************************************************************************************
PROBLEM 4:
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)

. -- . -- .

| |

. . -- . -- .



| | | |

. -- . -- . -- . -- .

| | | |

. . -- . .



| |

. -- . -- . -- .

7)

. -- . -- . -- .



| |

. -- . -- . . -- . -- .

| | | | | |

. . -- . -- . -- . .

| | | |

. . -- . -- . -- . .



| | | | | |

. -- . -- . . -- . -- .

| |

. -- . -- . -- .


8)

. -- . -- . -- . -- . -- . -- .

| |

. . -- . -- . -- . -- .



| | | |

. . -- . -- . -- . -- . .

| | | | | |

. . -- . -- . -- . -- . . .

| | | | | | | |

. . -- . -- . -- . -- . -- . -- . -- .

| | | | | | | |

. . -- . -- . -- . -- . -- . -- . -- .

| | | | | | | |

. -- . -- . -- . -- . -- . -- . -- .

| | | | | |

. . . -- . -- . -- .

| | | |

. . -- . -- . -- .



| |

. -- . -- . -- .

Basic pattern:

.

|



. -- . -- . -- . -- .

| |


. .

| |


. .

| |


. -- . -- . -- .
9)

. -- .


| |

. -- . -- . -- .

| | |

. -- . -- . -- .



| |

. -- .
10) . -- .

over and over the same square | |

still area = 1 . -- .


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

,------------------------.

| Problem 4: Superstring |

`------------------------'


The Problem

~~~~~~~~~~~

A scientist working the swampy, mosquito-infested jungles of

Sumatra has made an interesting find. She has recovered fragments of

the gene code of a long-extinct animal, the Blarky, each fragment

consisting of a string of molecules. The Blarky's genetic code is much

like ours, with each molecule represented by a letter, except that all

26 letters are used, unlike our code that uses only the four letters,

A, T, C and G to code the molecules in the gene.
Unfortunately, no single sample is guaranteed to be the entire

genetic code of the Blarky, though it is known that every sample

contains a string of consecutive molecules in the actual code. To

reconstruct the final genetic code, our scientist relies on a

well-known principle in genetics that states that the best

approximation of a genetic code from its fragments is obtained by

finding the shortest sequence of molecules that contains all the known

fragments. For example, if the fragments gyy, segyy and

puse are available, then the best guess at the code is

pusegyy.
Write a program that, given gene fragments, obtains the best

approximation. The input consists of n+1 lines when there are n

gene fragments. The first line has a single integer, which is the

number of fragments. All other lines have a single sequence of

letters, there being no space between letters. The sequence on each

line represents a different gene fragment obtained by the scientist.

The output should be the genetic code as guessed from these fragments.

Each fragment is at most 20 molecules long, and there are at most 100

fragments with the scientist. ... 38 marks


In short

~~~~~~~~


You are given some strings, and you are expected to find the shortest

string that contains all the other given strings, i.e. the shortest

superstring.
My approach

~~~~~~~~~~~

NP-hard, and can be mapped to finding the Hamiltonian path. Hence

approximate solutions (within 91% of my exact ones) are given full

credit.
Winner1 algo

~~~~~~~~~~~~

(GREEDY) At any stage, find the pair of strings giving the maximum overlap

on merging in the best possible manner. Merge them, and proceed. At the

end, the string left is the approximate answer.
Winner2 algo

~~~~~~~~~~~~

Sort the strings in descending order of length. Pick the longest and

copy it in the final string. Take the next one.Insert it as follows.

If the final string is "abcdef" and the string to be inserted is

a. "pqr" . Final becomes "abcdefpqr".

2. "def". Final remains the same.

3. "defd". Final becomes "abcdefd"

4. "fabc". Form two strings "fabcdef" and "abcdefabc" and Final

becomes the shorter of two.

Keep on inserting strings in the descending order. Its a NP hard

problem. No polynomial time algo exists for it. Our algorithm works

for fairly large number of cases.
Winner3 algo

~~~~~~~~~~~~

Just removed strings that were already present
Test cases

~~~~~~~~~~

1. all overlaps are zot

: any algo will work


2. aaaaa aaabbb aaabbb bbbccc

: two strings identical


3. aaaaa aaaab aabac baaab aabaab

: general arbit


4. cdefghi abcdef hijklm efghij

: two possibilities exist, which do you choose ?


5. raman mantra uma

: greedy does not work:

greedy takes raman+mantra = ramantra, and then uma: ramantrauma

you should take mantra+raman = mantraman, and then umantraman


6. abcd abef cdab efab
7. hello hell llama lotus shell ellot

: one string is a substring of another


8. finger oafing german muffin codger
9. life feels silli
10. with all the might of the earth rama lifted his bow and in just

one stroke fired twenty types of arrows which made all around him

stop to think about his powers

: to check exhaustive searches


11. who holds the hell torch is none other than the guy who lives here

or there and doth not know fear


12. abcdef defab fababc babc labcd gabcde gfab bcdfab ababef cdlab gbcd bcdg
13. csea prog contest is the worst thing that took place ever
14. sc re w t he gu y w ho do es an ex ha us ti ve se ar ch so th at he

lo ok s fo r be tt er so lu ti on s


15. abab abbc bbcad dacca aabdba abdbabd abadbabdbdbabad adbdbdabadba abdbab

adbbad adbabdad adbadb adbadb adbbdaba dabdbad dbadbadabb dbadab dba

: general arbit

************************************************************************************************

PROBLEM 5:
1. You are given an array of positive integers. you want to check whether there is a triplet(a,b,c) such that a + b = c

--------------------------------------------------------------------------------

2.Given a number n & a prime p(< n) consider the binomial coefficients C(n,0) , C(n,1) , C(n,2), ... ,C(n,n) one wants to find out how many coefficients are not divisible by p. (try for a log(n) algo.)

--------------------------------------------------------------------------------

3.A chess board (NxN) is given. you want to place knights such that no attack each other & no 2 control the same position. |--|--|--|--|--|--|--| | A| | | | | | B| |--|--|--|--|--|--|--| | | |a | | *| | | |--|--|--|--|--|--|--| | | | | | | | b| |--|--|--|--|--|--|--| in the above grid the 2 knights(position marked A & a) are attacking each other & the 2 knights (position marked B & b ) control the same position( marked Bp addresses baahar bo chummi header iitians mail mankars sendits.sh slocat.sh time xaa xab xac xad xae xaf xag xah xai xaj xak xal xam xan ); you have to give the maximum no. of knights that u can place.

--------------------------------------------------------------------------------

4.Given a string one wants to find out the shortest even palindrome starting from the first index. e.g 1.aabbaa now there are 2 even palindromes(starting from the 1st index) aa & aabbaa. thus the answer is aa. 2.abb although bb is a palindrome but it doesn't start from 1st index thus answer -1.

************************************************************************************************

PROBLEM 6:
C-on-test ~~~~~~~~~ Brought to you by CSEA, IITB in association with VERITAS software. ==================================================================
You are Dunce E. Dumdum, freshie at IIT Bombay, Powai - 400076. Having cracked a cool 3567 rank in IIT JEE after 5 years of concentrated mugging, you think that the future is bright and a gentle smile plays on your lips as you look around at the verdant green campus and the hallowed halls of learning. Little do you know what a dark, gloomy future awaits you. So here's already PROBLEM 1: Credits: 10 ~~~~~~~~~~ Filled with the enthusiasm and excitement of hostel life, you are exploring your new home when suddenly you bump into what appears to be a wall. Closer examination reveals the "wall" to be actually a gigantic, disgruntled and unshaven SENIOR. You politely say "Hi!". SENIOR just grunts in reply. You are about to continue when suddenly SENIOR booms out "Hey FRESHIE!". The plaster is still falling off the ceiling as you turn back with trembling legs. So starts a nice interactive session with SENIOR. One-way intros over, SENIOR starts asking more technical questions. Your slowly losing that gentle smile on your lips as the questions get livelier. But here comes a question which puts the g.s. back where it belongs: SENIOR says, " I will give you a number (N). Find positive integers `x' and `y' so that x^y + y^x = N, and the sum (x + y) is maximum." So your job is to find such x and y. Input: The integer N in a line by itself. Output: The values of x and y in the format x y on a line by themselves, separated by a blank. Any order of x and y is ok.

--------------------------------------------------------------------------------

PROBLEM 2: Credits: 20 ~~~~~~~~~~ After many such encounters of the SENIOR kind, finally you feel that things are in order and the gentle smile, though mellowed with bitter experience, is still there. But a week's over, and so is your stock of undies, which number 7 (seven). You have realised that now you need to wash them! (Becoz Mommy insists that you wear a clean pair of undies every day.) But now you have had a taste of an IITian's life: too many things to do, too less time. So following Mommy's advice, you decide to plan out things. You know your routine now, so you know exactly what days you will be able to do the washing and what days you won't. You decide 2 things: 1> Since the number of undies is 7 (seven), the washing dates can atmost be separated by 7. Thus, if you wash on the 15th, you have to wash on or before the 22nd. 2> Since basically you are a lethargic bum, you decide that you will wash only if you have atleast 2 dirty undies to wash. Thus the dates must be separated by atleast 3. (So you have to wash on or after 18th, if you wash on the 15th) Since, as mentioned above, you are a lethargic bum, you want to find out the MINIMUM number of days you need to have a fresh undie every day to wear. You also know the number of days you have to spend, and the possible washing days. Input: The total number of days(N) on the first line. The total number of washing days(M) on the second line. The dates of the washing days, M of them, one on each line. NOTE: The dates are numbered from 0 to (N-1). Assume that you start out with a fresh set of undies BEFORE 0th day, (i.e the -1th day), so you need to wash on or before 6th, but but not before the 2nd day. Output: The minimum number of days you need to do the washing. Just the number, on a line by itself. Output -1 if it is impossible to schedule washing days subject to the conditions. Sample Input: 10 4 0 3 6 9 Sample Output: 1 (Since you can wash on the 6th This was an error earlier). length of input > strings? could be at max 100000.

--------------------------------------------------------------------------------

PROBLEM 3: Credits: 30 ~~~~~~~~~~ Now you have finally drained the bitter cup: you have realised that life in IITB is not all that rosy, and only by mutual co-operation and work-sharing (read cogging) can help you thru the troubled times. Particularly when you are trying to crack math problems. You have a long list of math problems.You and other fellow sufferers decide to handle it together. Each math problem takes you or your friends 1 man-hour to crack. But there's a catch: there are some problems that can be done only if some previous problems are done. You decide (as Mommy advices) to prioratize the problems. For problems A and B, for which A appears in the list before B, there are two possibilities: 1> If A has lower or equal priority than B, then 2 students can simultaneously work on problems A and B, to decrease the number of man-hours. 2> If A has higher priority than B, then A has to be completed before B. Now since this is a common cause, you have a huge number of freshies who can work on the problems, so there's no constraint on the number of problems being tackled at the same time, as long as the above two conditions are met. As mentioned above, you are a lethargic bum, and so are your friends, so you want to decide what's the MINIMUM number of man-hours to solve all the problems. Input: The total number of problems (N) on the first line. The priorities you assigned to the problems in the list, one after the other, on separate lines, as they appear in the list. Thus there are N more lines after the first one, each having a priority value, an integer. Output: The minimum number of man-hours needed to solve all the problems in the list. Just the number. Note that a higher priority problem can be done before a lower priority job, even if it comes later in the list. THUS: IF A comes before B in the list and B has higher priority than A, then B can be done before A, or with A simultaneously. BUT if B has lower priority than A, then B HAS to be completed before A. Sample Input: 10 1 1 2 3 1 4 1 2 1 5 Sample Output: 3 (1,1,2,3,4,5) are done first, (1,1,2) are done next, (1) last. Therefore the answer is 3

--------------------------------------------------------------------------------

PROBLEM 4: Credits: 50 ~~~~~~~~~~ Return of the SENIORS. SENIORS strike back. Now your Hostel elections are round the corner. The SENIOR who's standing for G.Sec is unfortunately your wingmate, and so he wants you to go door to door canvassing for him. But lethargic bum that you are, you crib incessantly, and whine and say that Mommy forbids you from such hard work and to concentrate on your studies. So rather than listen to your whines, the SENIOR relents and gives you a list of `N' room numbers you have to visit in order, and tells you that you can visit any `k' of them. You are ecstatic. But again that lethargic bum in you tells you that you would like to minimize your travelling. So you decide to pick a `k' subsequence of room numbers so the the total consecutive absolute differences in room numbers is minimized. Input: N,k -- on the first line, the two numbers separated by a comma. Then the room numbers, N of them, one on a line. Output: The minimum total sum of consecutive absolute differences, just the number, on a line by itself. Sample Input: 7,3 67 35 89 37 100 36 4 Sample Output: 3 (By choosing 35,37, 36. Thus 3 = |35 - 37| + |37 - 36|).

--------------------------------------------------------------------------------

PROBLEM 5: Credits: 40 ~~~~~~~~~~ Your roommate is in the Civil engg. dept. His project consists of setting hanging a heavy plane metal sheet from cables attached to the roof. Bad. Theorem 4.7.18 in the Green book says that to minimize tensile strain( DUH...) you have to have 4 (four) points from which the metal sheet is hung. So that means that these 4 points must be coplanar. WORSE. Your roomie, having got JEE rank 4754, is worse than you. Since your JEE is nearly 1000 more than his, he thinks you are GOD, and turns to you for help. He tells you that there are `N' points in 3D space which represent the ends of the cables. He also tells you that all these points have non-negative integer co-ordinates. Since you have a huge ego (rank 3500+ is GREAT, you feel) you have to find 4 coplanar points, given that there ARE 4 coplanar points in the data.The gentle smile replaced by a frown, you set to work. Input: The number of points `N' on the first line. The co-ordinates of the points, in the format x,y,z -- separated by commas, on the next N lines. NOTE: The points are numbered from indices 0 to (N-1), as they appear in the list. Output: The indices of 1 set of 4 points, in the format: i j k l where i, j, k, l represent the indices of the points. Sample Input: 5 2,0,0 0,2,0 1,1,1 1,1,0 0,0,2 Output: 0 1 3 4 (the plane is (x + y + z) = 2).

--------------------------------------------------------------------------------

PROBLEM 6: Credits: 50 ~~~~~~~~~~ DANIYA time!!! Work time also for you lethargic bum. The gentle smile on your face is conspicuous by its absence. Finally DANDIYA day comes. Out of the small number of girls in IIT, an even smaller number has arrived. SENIORS being SENIORS, get priority and pairs are formed. You, poor sod, don't have a partner, and have to do the dirty work of arranging publix in circles. The (lucky) boys have already formed the outer circle. The girls have formed the inner one. Your newly elected G.Sec (your wingmate, remember?) puts you to work. The girls being ladies, stay where they are. So you have to rotate the outer circle of boys so as to match them with the girls they have paired up with, or decide if it can't be done. To avoid choas, you would like to have the smallest number of movements.To add to your problems, some guys won't mind dancing with some girls apart from their partners. Input: Two strings of characters of equal length, each on a separate line. You have to find the least index of the character in the second line where the 0th character in the first string should go, so that the two strings match. The characters are numbered from 0 to (length - 1). In short: If a(0) a(1) ... a(n-1) b(0) b(1) ... b(n-1) are the two strings, then find the minimum 'k' so that a(i) = b(k + i (mod n)); for all i = 0, 1, 2,.. (n-1); NOTE: Output -1 if such a 'k' does not exist. Output: The index 'k' as specified above, just the number, on a single line. NOTE: Output -1 if such a 'k' does not exist. Sample Input: aabaa abaaa Sample Output: 4 (Since the 0th character of the first string, a, matches with the 4th character of the second string, so that if you take the 0th character to the 4th character the first string matches with the second.) Epilogue: After spending 4 years in IIT Bombay, Powai-400076, you permanently lose that gentle smile from your lips forever, but atleast learn the value and importance of hard work, so that you are no longer a lethargic bum.

***********************************************************************************************

SIEMENS INFO :
THIS PAPER CONSISTS 6 PARTS. all are multiple choice q's

1)general

2)c/unix

3)c++/motif

4)database

5)x-windows

6)ms-windows

we have written q's not acc. to each part.total 50. q's. time is

sufficient.

if u have basic idea about all of the u can easily answer the paper.

paper

------


1)which of following operator can't be overloaded.

a)== b)++ c)?! d)<=

2)#include

main()


{

printf("Hello World");

}

the program prints Hello World without changing main() the o/p should



be

intialisation

Hello World

Desruct


the changes should be

a)iostream operator<<(iostream os, char*s)

os<<'intialisation'<<(Hello World)<

b) c) d)none of the above

3)CDPATH shell variable is in(c-shell)

a) b) c) d)

4) term stickily bit is related to a)kernel

b)undeletable file

c) d)none

5)semaphore variable is different from ordinary variable by

6)swap(int x,y)

{

int temp;



temp=x;

x=y;


y=temp;

}

main()



{

int x=2;y=3;

swap(x,y);

}

after calling swap ,what are yhe values x&y?



7) static variable will be visible in

a)fn. in which they are defined

b)module " " " "

c)all the program

d)none

8)unix system is



a)multi processing

b)multi processing ,multiuser

c)multi processing ,multiuser,multitasking

d)multiuser,multitasking

9)x.25 protocol encapsulates the follwing layers

a)network

b)datalink

c)physical

d)all of the above

e)none of the above

10)TCP/IP can work on

a)ethernet

b)tokenring

c)a&b


d)none

11)a node has the ip address 138.50.10.7 and 138.50.10.9.But it is

transmitting data from node1 to node2only. The reason may be

a)a node cannot have more than one address

b)class A should have second octet different

c)classB " " " " "

d)a,b,c

12) the OSI layer from bottom to top



13)for an application which exceeds 64k the memory model should be

a)medium


b)huge

c)large


d)none

14)the condition required for dead lock in unix sustem is

15)set-user-id is related to (in unix)

16) bourne shell has

a)history record

b)

c)



d)

17)wrong statement about c++

a)code removably

b)encapsulation of data and code

c)program easy maintenance

d)program runs faster

18)struct base {int a,b;

base();


int virtual function1();

}

struct derv1:base{



int b,c,d;

derv1()


int virtual function1();

}

struct derv2 : base



{int a,e;

}

base::base()



{

a=2;b=3;


}

derv1::derv1(){

b=5;

c=10;d=11;}



base::function1()

{return(100);

}

derv1::function1()



{

return(200);

}

main()


base ba;

derv1 d1,d2;

printf("%d %d",d1.a,d1.b)

o/p is


a)a=2;b=3;

b)a=3; b=2;

c)a=5; b=10;

d)none


19) for the above program answer the following q's

main()


base da;

derv1 d1;

derv2 d2;

printf("%d %d %d",da.function1(),d1.function1(),d2.function1());

o/p is

a)100,200,200;



b)200,100,200;

c)200,200,100;

d)none

20)struct {



int x;

int y;


}abc;

you can not access x by the following

1)abc-- x;

2)abc[0]-- x;

abc.x;

(abc)-- x;



a)1,2,3

b)2&3


c)1&2

d)1,3,4


21) automatic variables are destroyed after fn. ends because

a)stored in swap

b)stored in stack and poped out after fn. returns

c)stored in data area

d)stored in disk

22) relation between x-application and x-server (x-win)

23)UIL(user interface language) (x-win)

24)which is right in ms-windows

a)application has single qvalue system has multiple qvalue

b) " multiple " " single "

c)" " " multiple "

d)none


25)widget in x-windows is

26)gadget in x_windows is

27)variable DESTDIR in make program is accessed as

a)$(DESTDIR)

b)${DESTDIR}

c)DESTDIR

d)DESTDIR

28)the keystroke mouse entrie are interpreted in ms windows as

a)interrupt

b)message

c)event

d)none of the above



29)link between program and out side world (ms -win)

a)device driver and hardware disk

b)application and device driver

c)application and hardware device

d)none

30)ms -windows is



a)multitasking

b) c) d)


31)dynimic scoping is

32) after logout the process still runs in the background by giving

the command

a)nohop


b)

33)process dies out but still waita

a)exit

b)wakeup


c)zombie

d)steep


34)in dynamic memory allocation we use

a)doubly linked list

b)circularly linked

c)B trees

d)L trees

e)none


35)to find the key of search the data structure is

a)hask key

b)trees

c)linked lists



d)records

36)data base

--------------------------

--------------------------------

employ_code salary employ_code leave

---------------------------

----------------------------------

from to
--------------------------------------

1236 1500 1238 --- ---

1237 2000 1238 --- ---

1238 2500 1237 ---

-----


1237 --- ---

1237 --- ---

1237 --- ---

-------------------------- --------------------------------------

select employ_code,employ_data ,leave

the number of rows in the o/p

a)18

b)6


c)7

d)3


37)DBMS

38)read about SQL,db

39)which is true

a)bridge connects dissimiler LANand protocol insensitive

b)router " " " " "

c)gateway " " " " "

d)none of the above

40)read types of tree traversals.

41)42)43) simple programs on pointers in c
_____________________________________________________________________
BEST OF LUCK
This is sisl paper given in iit kanpur. enjoy this.
All are multiple choice questions.60 questions to be answered in 60 mins.

Distribution of questions:

---10 questions from data structures and some general topics.

-----10 questions from Unix and C.

--7Questions from Data base.

----Remaining from Windows(x windows,MS Windows etc..)

The distribution is not exact.Only approximate.

Totally there are six sections as below:

1.General

2.Unix and c

3.RDBMS

4.C++/object oriented



TCP/IP

6not remembered.

The questions are as follows:

RDBMS-----

1.What is RDBMS...Def

2.Two tables are given.In 1st table 2 columns are there.one

isEmployee no,second is salary.In second table 3 columns are there,one is

employee no,second is date,3rd is salary.

Select employee no,from table1,table 2.

How many records it will contain?.(This is somewhat difficult).


3.What is transaction?

TCP/IP:


1.X.25 protocol belongs to which layer.

2,Order all the 7 layers in sequence


3,One node has 2 IP address but data goes through only one link.What is the

reason?


4,Router,Bridge,Gateway....Which one of these can not connect

two different LANS and is protocol sensitive.

5,Client sends server---reqest or demand or -----Choices

are given.

Another section...

1.main(argc,argv)

{

if(argc<1)



printf("error");

else


exit(0);

}

If this program is compiled without giving any argument ,what it will print.



2.What are the static variables...def

3.What is Dynamic allocation ?

4.Dead lock condition...What may be the condition for it.

5.Semaphore variable?..def

> 6.Most

************************************************************************************************

TISL

part 1
it consists of number series.In some institutes alphabetical series is



given instead of number series.Iam having number series so iam sending

that.Please go through tha alphabetical tests also.


1. 19,24,20,25,21,26,? ans:22

2. 11,14,12,15,13,16,? ans: 14

3. 10,2,8,2,6,2,? a:4

4. 8,9,11,14,,18,23,? a:29

5. 25,25,22,22,19,19,? a:16

6. 14,2,12,4,10,6,? a:8

7. 7,16,9,15,11,14,? a:13

8. 40,42,39,44,38,46,? a:37

9. 3,18,4,24,5,30,? a:6

10. 18,20,22,20,28,20,? a:22

11. 18,20,10,12,4,6? a:0

12. 7,6,8,5,3,7,? a:4

13 9,18,21,25,20,? a:30

14 3,3,4,8,10,36,? a:33

15.30,28,25,20,34,28,? a:21

16. 4,8,16,32,64,128,? a:256

17. 8,16,24,32,40,48,? a:56
18. 13,11,14,12,15,13,? a:16

19. 6,18,36,108,216,648,? a:1296

20. 4,4,8,8,16,16,? a:32

21. 2,6,18,54,162,486,? a:1458

22. 4,20,35,49,62,74,? a:85

23. 10,18,15,23,20,28,? a:25

24. 4,10,8,14,12,18,? a:16

25 10,15,12,17,14,10,? a:16


1   2   3   4   5   6


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

    Main page