PROBLEM 1:
n
non-negative integers and (n-1) arithmetic operators from the set
(+,-,*) are
given on a single line as follows:
<num1><num2>...<numn><op1><op2>...<opn-1>
Write a
program to evaluate the expression
formed left to right as:
<mun1><op1><mun2><op2>...<mun(n-1)><op(n-1)><mun(n)>
In the above
mun1 is obtained by reversing the digits of num1,
mun2 by
reversing the digits of num2 and so on.
Thus 241 56 * has to be evaluated as 142 * 65.
Input:-
The input
will consist of 2 lines, each terminated by EOLN.
Line 1: n,
the number of integers
Line 2: a
sequence of n integers( with reversed digits)followed by
(n-1)
arithmetic operators.
There is
exactly one space separating any two items on the second line
(integers or
operators), and there are no leading spaces either.
The range of
values for 'n' is from 2 to 10.
The
operators used are '+' meaning addition.
'-' meaning subtraction.
'*' meaning multiplication.
Output:-
Your output
must be an integer without any leading zeroes and with a
sign only if
the result is negative.The output must be terminated
by an EOLN.
Examples:-
Input:-
3
12 03 123 + +
Output:-
372
{note: 21 + 30 + 321 = 372 }
Input:-
4
54 0 50 94 * + -
Output:-
-44
{note: 45 * 0 = 0; 0 + 05 =5; 5 - 49 = -44 }
Input:
3
21 3 5 + *
Output:
75
{ note: 12 + 3 = 15; 15 * 5 = 75 }
PROBLEM 2:
Given a line
of variable declarations like in Pascal programs, you
have to
identify the type of a variable. The input to your program
will consist
of Pascal language like variable declaration, terminated
by EOLN.
e.g.
int1,int2,int3,int4 : integer;
The line
following such an input will contain a variable name.
e.g. int4
Your program
should identify the type of the variable, and print the
variable
name followed by its type terminated by EOLN.
For example,
in the above case , the output is
int4 integer
integer if the type of the variable is integer,
real if the type of the variable is real,
char if the type of the variable is char,
boolean if the type of the variable is boolean,
undefined if the variable is not any of the above type
or is not
declared.
Note that
all the strings that you output must be in lower-case as
shown above.
There can be one or more spaces between the variable name
and the type
name in your output.
A variable
will be at the most 8 (eight) characters long, and the
maximum
number of variables declared in such an input is limited to 50.
Your program
should not make any assumptions regarding the number of
spaces
separating items on the line. There may be 0 or more leading
blanks,
trailing blanks and 0 or more spaces before or after any
variable
name, comma, colon or type name. The declarations of the
variables
will be given in the lower-case only.
Examples
--------
Input:
abc, boy, int1 : boolean;
boy
Output:
boy
boolean
Input:-
cat,
myreal,bigreal: real;
dog
Output:-
dog
undefined
Input:-
x1, y2,
none : text ;
y2
Output:-
y2
undefined
PROBLEM 3:
A pack of 52
playing cards has four suites ( Hearts, Spades, Clubs
and Diamonds
) with 13 cards in each suite. A card is represented by
a letter
{h,s,c or d} denoting each of the four suites(Hearts, Spades,
Clubs and
Diamonds) respectively. The letter is immediately followed
by a number
from 1 to 13 denoting the particular card in that suite.
Thus, the
Four of Hearts is represented by h4, Ten of Spades by s10.
and so on.
A
"4-sequence" is a set of four cards of the same suite in consecutive
order, e.g.
{c10,c11,c12,c13}. Wrap-around sequences like
{d11,d12,d13,d1},
{d13,d1,d2,d3} etc. are not valid. A "3-trail" is a
set of three
cards of the same number but belonging to different
suites,
e.g.
{c6,h6,s6}, {d1,c1,s1}, etc.
Given a set
of 13 distinct cards you have to determine if the given
set contains
a 4-sequence or a 3-trail. Assume that the given set will
contain a
single 4-sequence or a single 3-trail or neither. That is, it
will not
contain both.
The input
consists of the 13 cards on one line, each card represented
as explained
above. Each "card" is separated from the other by a single
space. There
are no leading spaces before the first card and no
trailing
spaces after
the last card.
Output
Specification:
----------------------
If the input
set contains a 4-sequence, output the cards that form the
4-sequence
in increasing order of the card numbers separated by one or
more spaces
terminated by an EOLN.
If the input
set contains a 3-trail, output the cards that form the
3-trail in
the order of {h,s,c,d} separated by one or more spaces
terminated by
an EOLN.
If the input
set contains neither of the two, then output "none" on a
line. The
output must be in lower-case letters only.
Sample Input
And Output:
-------------------------
Input:
h1 d7 s2 d8
d3 h13 d12 h11 d5 d6 h2 s1 h10
Output:
d5 d6 d7 d8
Input:
h1 h2 h10
h11 h13 s1 s2 d1 d3 d5 d6 d7 d12
Output:
h1 s1 d1
Input:
h12 d7 s2 c1
d1 h13 d2 h11 d5 d6 h9 s11 c2
Output:
s2 c2 d2
Input:
s1 h2 s3 h4
s5 h6 s7 h8 s9 h10 c11 d12 c13
Output:
none
PROBLEM 4:
Write a program
for maintaining the appointments of patients in
different
departments
of a hospital. Assume that each patient has a unique
integer-
identifier(id)
and so also every department. A patient can seek
appointments
to one or
more departments and is also allowed to cancel an appointment
from
any
department. The program should be able to list out at any time the
number
of patients
who have valid appointments with a given department or the
number
of
departments with which a given patient has appointments.
INPUT
------
The input to
your program is a sequence of commands each command on a
separate
line. There
are four commands as follows:
1) S
patient-id department-id
Example
S 3013 1023
(Patient
with id 3013 is seeking appointment from department with id
1023)
2) C
patient-id department-id
Example:
C 10293 0112
(Patient
with id 10293 is cancelling his appointment from department
with id
0112)
3) D
department-id
Example
D 23
Output
-------
Print the
total number of patients who have valid appointments with the
department
having the id 23. Cancelled appointments should not be
counted.
Terminate
your output by an EOLN. If there are no appointments for the
department then
your program must output 0 followed by an EOLN. The
output
must not
have any sign and there should be no leading zeroes in the
output.
4) P
patient-id
Example:
P 101
Print the
total number of departments with which the patient with id
101 has
valid
appointments. Cancelled appointments should not be counted.
Terminate
your output
by an EOLN. If the patient does not have any valid
appointment
with any
department then your program must output 0 followed by an
EOLN.
The output
must not have any sign and there should be no leading zeroes
in
the output.
Your program
must be capable of handling any number of departments and
any
number of
patients. You may assume that there are no receding blanks
before
the command
character and that erroneous input will not be given to
your
program.
Each command line is terminated by EOLN and the input is
terminated
by an EOF.
EXAMPLES
---------
S 100 200
S 100 201
S 100 203
S 101 203
S 101 240
C 100 200
S 101 207
C 101 240
P 100
D 203
D 200
S 100 200
S 101 231
D 200
S 102 245
D 203
P 104
PROBLEM 5:
Write a
program to merge two linked lists.
INPUT
------
The input to
the program will be two lines, each terminated by EOLN.
Line 1 :
sequence of integers for the first list
Line 2 :
sequence of integers for the second list
The integers
appearing on each of the lines may not be in ascending
order.
So you must
arrange the integers on a line as a linked list in
non-decreasing
order. Once
a line of input is read, the integers on that line must be
output
as an
ordered list of numbers on the same line terminated by an EOLN.
After
obtaining two ordered linked lists, you must merge them such that
there
are no
duplicate elements in the resultant list and the new list has
elements
in a
non-decreasing order.
The elements
in the new list must be printed on the same line
terminated
by
EOLN.
The elements
in the input list will be integers and
duplicate integers
will
not be provided
on a line of input.
OUTPUT
------
The output
of your program must consist of three lines, each terminated
by EOLN.
Line 1 :
elements of the first list in ascending order.
Line 2 :
elements of the second list in ascending order.
Line 3 :
elements of the merged list in ascending order.
In case the
output list is empty, output an EOLN.
EXAMPLES
--------
Input :
20 10 5 13 30
5 2 10 9
Output :
5 10 13 20 30
2 5 9 10
2 5 9 10 13 20 30
PLEASE NOTE
------------
The words
'Input:' and 'Output:' are not a part of the inputs and
outputs.
Do not
attempt to input or output these words using your program.
Assume
that the
input values are all correct. Do not do any input validation
and
do not
output anything other than what is defined in the output
specification
otherwise
the grader will fail to check your program properly.
PROBLEM 6:
Write a
program to maintain the current stock of machine parts of a
workshop. A
part is
identified by a 10 character part-id. The production and
consumption
of
parts take
place within the workshop. You may assume that over
consumption
is
allowed(
that is, the stock can go negative also).
INPUT &
OUTPUT
--------------
The input to
your program is a sequence of action commands each command
on a
separate
line.
The four
commands are as follows:
1) Production of a part( command is P )
P SCR1110810 1500
This implies
that 1500 units of the part with id SCR1110810 have been
produced.
( Note that
a part entry has to be created if one with this part-id
does not
already
exist).
2) Consumption of a part( command is C )
C NPN1012136 2000
2000 units
of the part with part-id NPN1012136 have been consumed.
( Note that
a part entry has to be created if one with this part-id
does not
already
exist).
3) To output
the number of parts whose stock is less than the given
number
( command is
L )
L 100
This
requires your program to output the number of parts with stock
less than
100. Your
output should be an integer ( greater than or equal to zero )
without any
sign or leading zeroes.
Terminate
your output by an EOLN.
4) To output
the number of times the stock of the given part has gone
from >=0 to negative.
( command is F )
F NPN1012136
This
requires your program to output the number of times the stock of
the part
with part-id
NPN1012136 has gone from >=0 to negative. Your output
should be
an integer (
greater than or equal to zero ) without any sign or any
leading
zeroes.
Terminate your output by an EOLN.
If the stock
has never become negative, you must output a 0 terminated
by an
EOLN.
In the above
assume that there is exactly 1 blank between the command
(P, C or F )
and the part-id. Your program must be capable of handling
any number
of parts. Assume that there are no leading spaces before
the command
character.
PROBLEM 7:
Write a
program that will generate a specified number of fibonacci
numbers.
The first
two numbers in the fibonacci number series are always 1. Each
succeeding number in the series is such that its value
is equal to the
sum
of its
preceding two numbers.
Input:-
The program
should accept an integer indicating the number of elements
to be
generated in the series. The input number will be a natural
number.
Output:-
The output
of the program should contain the required number of
elements
of the
fibonacci series. The numbers in the series must be separated
by a space.
Examples:-
1. Input:
5
Output:-
1 1 2 3 5
2. Input:
7
Output:-
1 1 2 3 5 8 13
3. Input:
2
Output:-
1 1
PROBLEM 8:
A set can be
implemented using arrays. Write a program to implement the
basic set
operations on sets of the following
specifications
The set may
hold maximum of 100 elements. The elements of the sets
are
integers.
The
operations to be performed on these sets are
1.
Intersection denoted by the letter I
intersection of sets A and B yields a
set whose elements
are both in A and B
2.
Difference denoted by the letter D
A difference B yields a set whose
elements are the
elements of A not in B
The elements
in a set will be given as a sequence of integers on a line
EOLN will
mark the end of the sequence.
The input
consists of 3 lines
line 1:
elements of set A
line 2:
elements of set B
line 3: set
operator( I or D )
The output
should consist of the result ofoperation
A
<operator> B
The elements
of the resultant set must be output on
a line
separated by
blanks and without any leading zeroes. The line must be
terminated
by an EOLN.
Note : The
elements of the input sets will be given in non-decreasing
order.
The elements
in the output must also be in non-decreasing order.
Sample Input
and Output:
Input:
0 23 456 765 1000 5678 7654 8001 10000
23 234 543
765 1235 10000 12347
I
Output:
23
765 10000
Input:
-10 0 15 25 125
-15 -10 0 20
D
Output:
15 25 125
PROBLEM 9:
Given a set
of vertical and a set of horizontal line segments, in the
format
specified below, write a Pascal program to find the total
number of
crossings amongst the line segments.
( See figure
below ).
|
|
|
|
-----|----------|---------------
|
|
|
|
|
-----|---------------------
|
|
|
|
|
-----|----------------
|
Input :-
The input to
your program will be as follows:
line 1: an
integer m {number of horizontal line
segments}
line 2: an
integer n {number of vertical line
segments}
line 3: x11
x12 y1 x21 x22 y2 ...xm1 xm2 ym
{3m integers specifying the horizontal
lines}
line 4: y11
y12 x1 y21 y22 x2 ... yn1 yn2 xn
{3n integers specifying the vertical lines}
In line3,
three integers define a line segment
Example:-
x11 x12 and y1 define a horizontal line segment with
endpoint co-ordinates (x11, y1) and (x12, y1).
Similarly in
line 4, y11 y12 and x1 define a vertical line segment
with endpoint co-ordinates (x1, y11) and
(x1, y12).
Assume that
the maximum number of horizontal line segments is 20.
Similarly
the maximum number of vertical line segments is 20.
Note: If two line segments merely touch each
other and do not
cross then it is not a valid crossing.
For example the following are not valid
crossings.
|
--------+----------- |
| |-----------
| | |
| |
| | _____________
| | |
| +------------- |
| |
|
Examples :-
Input:
3
2
1 10 3 30 2
5 4 20 6
10 1 5 25 30
100
Output:
3
Input:
1
1
10 20 10
20 15 15
Output:
0
PROBLEM 10:
N numbers,
starting from 1, are placed around a circular table.
Starting
from 1 every Kth number around the table is removed. This
process is
continued until all the numbers are removed from the table.
For example
If N = 10 and K = 3 the order in which numbers removed are
1 4 7 10 5 9
6 3 8 2
Write a
program which prints out the sequence of numbers in the same
order as
removed for any given N and K.
Input:-
Two numbers
N and K given on a single line terminated by an EOLN.
Example:-
Input:-
10
3
Output:-
1 4 7 10 5 9 6 3 8 2
Hint: Use
circular linked list.
PROBLEM 11:
Write a
Pascal program to build a number triangle. Given 4 integers,
the number
triangle is built as follows:
A11
A12 A13 A14
Root members of the number triangle of
height 4
+
+ +
A21
A22 A23 A21 = A11+A12, A22 = A12+A13, A23 =
A13+A14
+ +
A31 A32 A31 = A21+A22, A32 = A22+A23
+
A41 A41 = A31+A32
Given a
number, search for the number from root and starting from root,
print in
increasing order all the levels at which the number is found.
If the
number is not found in the triangle, print 0.
Level of the
root is 1.
The three
lines of input to your program are
1) The first
line will be an integer h giving the height of the
triangle.
2) The
second line will have h integers which are the root members
of the triangle.
3) The last
line contains the number to be searched.
The output
of your program will be the levels at which the number
to be
searched occurs in the triangle, one per line. Output the
level(s)
without any leading zeroes. If the number does not occur,
print 0.
Terminate your output by an EOLN. Assume that the maximum
height of
the triangle is 10. In case the number occurs more than once
at
a level,
that level number should be output only once.
Input:-
4
1 2 3 4
8
Output:-
3
Triangle is
as follows:
1 2 3 4
Level 1
3
5 7 Level 2
8
12 Level 3 ( 8 is at this
level )
20 Level 4
Input:-
5
4 2 1 1 1
4
Output:-
1
3
PROBLEM 12:
Write a
Pascal program to search a line of text for a pattern. The
pattern is
of the form X+Y*Z where X, Y and Z are
distinct
characters.
The + and * are interpreted as follows,
X*Y Zero or more occurrence(s) of X followed by
Y
X+Y 1 or more occurrence(s) of X followed by Y.
Thus k+j
kj, kkj, kkkj, kkkkj etc
k*j j, kj, kkj, kkkj
etc
The input to
your program will be two lines of text each terminated
by an EOLN.
The first line is a line of text of maximum 80 characters.
The second
line contains the pattern to be searched in the first line.
The output
of your program should be the position in the first line
at which the
matching pattern occurs ( ie. the matching pattern begins
at that
position - the first character in the line has position 1).
If the
pattern is not found, output a zero. The output should not
contain any
leading zeroes. Terminate your output by an EOLN.
In case the
entire pattern is found at more than one position, output
the last
position. The position output should be such that we do not
get a
matching pattern in the immediately preceding position.
Input:-
this is not a major issue.
s+u*e
Output:-
22
The pattern
is always of the form X+Y*Z.
u is at
position 24. "sue" matches the pattern.
But
"ssue" also matches. So the position is 22
and not 23.
Input:-
astro astonish assume atomic attribute
static
a+s*t
Output:-
42
Here , there
are a lot of matches.
But the
"at" in "static" is the last one to match.
PROBLEM 13:
A
"saddle point" of a matrix A is defined as the element A[i,j] such
that A[i,j]
is the smallest element in row "i" of the matrix and
the largest
element in column "j" of the matrix.
Given a 9x9
matrix whose elements are non-negative integers, you have
to output
its saddle point if it exists or -1 (minus one) if the
saddle point
does not exist. The saddle point if it exists, is
always
unique.
Assume that
the rows and the columns of the matrix are numbered
from 1 to 9.
The input consists of the 9x9 matrix ie. there are 9 lines
with 9
integers on each line.
If the given
matrix has a saddle point, you have to output three
integers on
a line terminated by EOLN. The three integers, in order,
are the
saddle point, the row index and the column index of the
saddle
point.
Integer
numbers on the same line must be output separated by blanks
and without
any leading zeroes. If the given matrix does not have a
saddle
point, you must output -1 on a line terminated by EOLN.
Input:-
2 3
4 5 6 7 8
9 10
4 5
6 7 8 9 10
11 12
8 9
10 11 12 13 14 15
16
2 3
4 5 6 7 8
9 10
3 5
6 7 8 9 10
11 12
2 3
4 5 6 7 8
9 10
7 5
6 7 8 9 10
11 12
2 3
4 5 6 7 8
9 10
6 3
4 5 6 7 8
9 10
Output:-
8 3 1
In the above
matrix, the integer 8 at position [3,1] is the saddle
point, as
per the definition of the saddle point given above.
PROBLEM 14:
Given an
input text which resembles a Pascal program segment, write
a program to
output the maximum degree of nesting of the
"begin"
-- "end" keywords.
The first
line of input consists of an integer denoting the number
of lines of
text to follow. The text will contain a Pascal program
segment
which will have an arbitrary degree of nesting of begin-end
statements.
You may
assume that every "begin" will have a corresponding "end"
and that the
keywords "begin" and "end" will always be in lower
case
letters.
The output
of your program should be an integer denoting the maximum
degree of
begin-end nesting found in the text. Terminate your output
by an EOLN.
The ouput integer should not have any leading zeroes.
Input:-
var i, j : integer;
begin
while (i<10) do begin
if j=10 then begin
j := succ(j);
i := pred(k)
end;
if true then begin flag
:= false end
end;
if j=7 then begin
j := j+1;
i := i+j
end
end
Output:-
3
PROBLEM 15:
Given a
piece of text, find the frequency distribution of word lengths
(ie. how
many words have one letter, how many have two letters,...).
Find the
word-length having the highest frequency and print that
word-length
followed by its occurrence count. In
case two or more
word-
lengths have
the highest frequency, print the largest word-length and
its
occurrence
count.
A
"word" is made up of alphanumeric characters and delimited by white-
spaces or
period( ie. full stop ).
The first
line of input specifies the number of lines of text to follow
( say N ).
Each word in the piece of text can be assumed to be smaller
than
15
characters. Your output will be two integers as above, separated by
one or
more spaces
with no leading zeroes and terminated by an EOLN.
Example:-
Input:
2
This is
a sample text. The text has sentences and sentences have
words.
Some words
are small. Some words are big.
Output:
4 6
PROBLEM 16:
In this
problem you have to find out a path between two points in a
maze.
The maze is
represented here as a 7x7 matrix containing the elements
0, 1, 2 and
3. The '0's are part of the path from the starting point
represented
by a '2' to the ending point represented by a '3'. The '1's
represent
blocks in the maze. There is a unique path from '2' to '3'
and it
always
exists and there are no dead-ends and no branches in the path.
The
elements '2'
and '3' occur only once in the matrix. Assume that the
rows and the
columns of
the matrix are numbered from 1 to 7.
The input
consists of 7 lines, each line containing 7 integers, thus
forming
the 7x7
matrix.
The output
should consist of a sequence of lines, each line containing
a pair
of integers
which are the row and column indices of the elements in the
path
from the
starting point '2' to the ending point '3' in the order of the
traversal,
including the indices for the '2' and the '3'. Integers on
the same
line must be
output separated by blanks and without any leading zeroes.
Sample Input
& Output:
Input:
1 0 1 1 1 1
2
0 1 0 1 1 0
1
0 1 1 0 0 1
1
1 0 1 1 1 1
1
1 1 0 0 1 1
1
1 1 1 1 0 1
1
1 1 1 1 1 0
3
Output:
1 7
2 6
3 5
3 4
2 3
1 2
2 1
3 1
4 2
5 3
5 4
6 5
7 6
7 7
Explanation:
The indices
for the starting point '2' are (1,7) and the ending point
are
(7,7). The
rest are the indices of the '0's that form the path from the
'2' to the
'3' in the order of traversal ie. after the '2' at (1,7),
the
next element
in the path is the '0' at (2,6), followed by the '0' at
(3,5),
followed by the '0' at (3,4) and so on till the '3' at (7,7).
PROBLEM 17:
Consider a
shop 'Linked List Electronics ' which allows its customers
to
purchase
items on credit. (The payment can be made later.) They are
planning
to automate their record-keeping for such
customers. They have less
than 100
customers.They
want a progrm as per the following desciption
Whenever a
customer purchases an item the operator will enter a line of
input
purchase name item_name
-----------------------
You may
assume that only the last name of the customer is given as one
word.
Also the
item name can be assumed to be a single word.
Whenever the
customer pays up another line of the form
payment-name item-name
----------------------
is entered.
For multiple
payments and purchases;multiple lines will be entered with
one
entry per
line .
The end of
input will be indicated by a line containing just the word
'stop'.
After that a
seperate line of input will specify a customer name.The
program
should output
the items purchased by the customer which are not yet
paid for.
The output
should be alphabetically ordered and all items in one line.
If their are
no pending items ,output "nothing".Assume maximum length
of a word
to be 50
characters.
SAMPLE
INPUT:
purchase wilson vcr
purchase wilson radio
purchase graey tv
payment wilson radio
purchase wilson tv
stop
wilson
SAMPLE
OUTPUT:
tv vcr
NOTE : YOU
MUST USE LINKED LISTS.
PROBLEM 18:
An anagram
of the word x is the word formed by the characters of the
word x
with each
letter being used only those many times as in word x.For
example
post,opst,tops
are some anagrams of the word 'stop'.
Input to the
program will be the word (less than 8 char.s) terminated
by eoln.
Output of
the program should be the list of all anagrams of the input
word;
alphabetically
sorted with one word per line.The upper case letters are
lower
than the
lower case letters.Terminate the last word also with eoln.
SAMPLE
INPUT:
tea
OUTPUT: aet
ate
eat
eta
tae
tea
PROBLEM 19:
Write a program to accept a finite set of
alphabets and all its
nonempty
subsets in
lexicographic order.The set of alphabetic symbols will have
at
most eight
chars.Note that the no. of such non-empty subsets is equal
to
(2^n -
1),where n is the no. of elements in the given set.
For
example;given a set {a,b,c},the list of its non-empty subsets is
{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}.
Input Format
:The input will consist of two lines.
First line
indicating the no. of elements in the input set say n .
Second will
have a string of n non-blank alphabetical characters
forming a
set.
Note that
the characters themselves will be given in alphabetical
order.
Output
Format:The output must list each of the required subsets on a
seperate
line (ie.the
no. of lines in the output must be equal to the no. of
non-empty
subsets of
the given set.) The characters in each line ,also the
subsets
themselves
should be in alphabetical order.
SAMPLE
INPUT: 3
abc
OUTPUT: a
ab
abc
ac
b
bc
c
PROBLEM 20:
Consider a teller counter in a bank.There are
two clerks handling the
job.
Each of them can handle any transaction at
the counter. Mr.Fast takes
5 minutes per transaction irrespective of the
type of transaction.
Mr.Slow needs 8 minutes per transaction. The
bank is planning to
improve
customer satisfaction and wants to know the
varios statistical
parameters
of its performance. The follwing is
specification of one of the
programs.
Implement it using the Que data stucture.
The input to the program consists of a
sequence of positive integers
terminated by the number -1. The input
numbers indicate the arrival
pattern
of customers.
Assume that the start of the program is at
time 0.The first no.
indicates
how many minutes from the arrival of the
first customer the second
customer
arrives , and so on.
You have to
simulate the service to the customers at the teller
counter.
Assume that
the customer will go to the earliest available counter for
his work.
However ;if both counters are free ; then preference is given
to
Mr.Fast. The
order of service is strictly in the order of arrival.
The input is
a table of number of people waiting for service at every
minute.
You need to
print this for the first 21 minutes from 0 to 20
(inclusive).
For each
minute one line of input is required containing the time and
the no. of
people waiting for service.The two items are seperated by a
single
space. For
the same purpose,you can assume that a customer arriving at
time t
is in the
que at time t,if no counter is free at that time.
SAMPLE
INPUT: OUTPUT:
0 0 0
0 1 0
1 2 1
2 3 1
2 4 1
8 5 0
-1 6 0
|
|
|
|
16
0
--------------------------------------------------------------------------------
MGPT - Problem
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1
A railway network system
is spread across many
islands.
There are N (N <= 50) stations in all,
identified by numbers
from 1 to N. Railway lines interconnect the
stations. On
a
given line a train can travel in any direction between
the stations connected by
that line. Every
island has
atleast two stations and atleast one
line.
The network has the following properties:
* If two stations are on the same island,
then it is pos-
sible
to travel between them by
rail. It may be necessary
to go through several lines and
intermediate stations, for
this purpose.
* If two stations are on two different
islands, then there
is
no railway route to go from one to the other. That is,
there are no lines connecting stations on
different islands.
The input to the program will be
1) 2 integers N and M representing
the number of stations
and the number of lines respectively
2) M lines representing the different
railway-lines. Each
line
will have two
numbers representing the two stations
connected by that line.
3) An integer Z
4) Z lines each having the numbers of two
stations
The program should output
1) The number of islands in the network,
followed by a new-
line.
(Hint : The number of islands is equal to the number
of different trees in the spanning forest
of the railway
network.)
2) For each of the Z lines in (4) above
print YES or NO on
separate
lines depending on whether the two stations are in
one-island or not. Hint: Check if they
are on the same span-
ning
tree. There are different ways
to do this. One possi-
ble approach is sketched below.
For each of the Z lines, take one end
point and do a traver-
sal
from that vertex. If during this traversal, you visit
the other vertex, then the two vertices
are in the same
spanning tree.
.........
Sample input
8 6
1 2
3 1
5 7
1 4
7 8
6 8
4
1 5
5 6
3 2
7 8
Sample output
2
NO
YES
YES
YES
------------------------------------------------------------------------------
2
Construct a binary search tree based
on a set of keys
given
as input. The criteria to be met by each node is:
info(left(node)) < info(node)
<= info(right(node)). Inser-
tion
of new nodes are to be
done as discussed in class
(ie, only as a leaf of an existing node).
After the tree is
constructed, you have to
rotate the tree to
right or
left
by one step and then print out the pre-order traversal
of the tree.
The input will consist of a number N
(< 50) followed by a
sequence
of N integers, all in
one line. These N numbers
will be the keys to construct the tree.
After this there
will
be a single word (either
left or right) on a
separate line. This is the instruction as
to which way the
tree is to be rotated.
The output from the program will be
the pre-order traver-
sal
of the resulting tree. All keys
are to be printed in a
single line, separated by spaces.
If the desired rotation cannot be
performed, ignore the
command
and do pre-order
traversal of the
tree con-
structed from the input.
...........
Sample Input/Output:
Input: 6 1 2 4 3 5 6
left
Output: 2 1 4 3 5 6
Input: 4 4 3 5 6
right
Output: 3 4 5 6
------------------------------------------------------------------------------
3
Implement a
variation of the Quick Sort algorithm as given below.
X is an
array of N integers to be sorted.
The array is
partitioned using an element, say X[J], as the pivot such
that
after
partitioning, all elements in the array
at positions less than J
are less
than X[J] and all elements in the array at positions greater
than J are
greater than X[J]. This is done recursively on each of the
two
partitions,
till all the partitions contain one element -- which
means the
array is sorted.
The
partitioning works as follows. The partitioning procedure gives
the position
J.
Let LB and
UB be the lower and upper bound of the
subarray
respectively.
Here, the
pivot element A is the middle element of the subarray
ie. the
element at position (LB+UB)/2.
Two
pointers, DOWN and UP, are initialized to the upper and lower
bounds
of the
subarray respectively. At any point during execution, each
element in a
position greater than UP is greater than or equal to A;
and each
element in a position lesser than DOWN is lesser than or equal
to A. The
two pointers UP and DOWN are moved towards each other as
follows:
Step 1:
repeatedly increase the pointer DOWN by one position until
X[DOWN] >
A.
After DOWN
is increased each time, if X[DOWN] < X[DOWN - 1], swap
X[DOWN]
and X[DOWN -
1].
Step 2:
repeatedly decrease the pointer UP by
one position until
X[UP]
<= A.
After UP is
decreased each time, if X[UP] > X[UP + 1], swap X[UP] and
X[UP + 1].
Step 3: If
UP > DOWN, swap X[DOWN] and X[UP].
If X[DOWN]
< X[DOWN - 1], swap X[DOWN] and X[DOWN - 1].
If X[UP]
> X[UP + 1], swap X[UP] and X[UP + 1].
The above
steps are repeated till UP <= DOWN. The position UP is the
position J
required.
--------------------
Input
Specification:
--------------------
The input
will be a single line containig an integer N, followed by N
integers.
Assume N < 50.
---------------------
Output
Specification:
---------------------
You have to
print out the contents of the array X each time
partitioning
is done. The output should be on a single line containing
the array
elements separated by a space.
-------
Example
-------
Input:
8 25 57 48
37 12 92 86 33
Output: Explanation:
25 12 33 37
48 57 92 86 sort(0,7) up = 3
X[down] = 48 X[up] =
37
12 25 33 37
48 57 92 86 sort(0,2) up = 0
X[down] = 25 X[up] =
12
12 25 33 37
48 57 92 86 sort(1,2) up = 1
X[down] = 33 X[up] =
25
12 25 33 37
48 57 86 92 sort(4,7) up = 5
X[down] = 86 X[up] =
57
12 25 33 37
48 57 86 92 sort(6,7) up = 6
X[down] = 92 X[up] =
86
------------------------------------------------------------------------------
4
Write a
program to differentiate a linear expression with respect to
a variable X
(having power not more than one) given
a set of
formulae for
differentiation. The expression
will have no variable
other than
X.
The set of formulae to be used are :
expression derivative
---------- ----------
X 1
k 0
u + v der(u) +
der(v)
u - v der(u) -
der(v)
k * u k *
der(u)
where :
u and v are
expressions involving X,constants and the
binary
operators +,- and *;
k is a
single-digit constant:this always precedes the
expression
involving X in the case of '*' operator;
der denotes
'derivative with respect to X'.
Expressions
of the following form will NOT be given :
1) (X+2) *
(X+3) i.e. resulting in power of X more
than one.
2) 20*X i.e. constants with more than one
digit.
3) X*3 i.e. constants on the R.H.S. of
'*'.
4) (3+5) *
X i.e. an expression on the L.H.S.
of '*'.
........
Input :
The expression to be differentiated is given
in the
form of a
binary expression tree whose leaves are either the
variable X
or constants and the internal nodes
are the
operators
+,- or *.
The input consists of a sequence of one or
more lines.
Each line contains a string followed by an
operator, X or
a constant.
The string is a sequence of zero or more L's and
R's enclosed
within a pair of brackets and is separated from
the
operator, X or the constant by a single space.
The first line contains an empty string ()
which means
that the
item following it is to be
inserted at the root.
For the
remaining input lines, you have
to move to
the
correct position
in the tree using the string of L's and
R's. An 'L'
in the string means that you have to move to the
left branch
of the present node. Similarly, an 'R' indicates
moving to
the right branch of the present node. The input is
terminated
by EOF.
Process :
Based on the input, construct a binary
tree denoting
the expression. The derivation formulae given at the beginning
can be
applied to this tree in a recursive manner to
compute the
differentiated expression.
For example,
a subtree
* *
/
\ becomes /
\
2
X 2 1
The resulting tree will not have any variables
and
can be
evaluated as a simple arithmetic expression, to yield
a single
number.
Output:
This must be
an integer whose value is the derivative of
the given
expression. Terminate this by a newline.
Note that
the Sample Input given below represents
the
expression
(5 * (X+2)) - (3*X)
for which
the derivative is 2.
........
Sample
Input:
() -
(L) *
(R) *
(LL) 5
(LR) +
(LRL) X
(LRR) 2
(RL) 3
(RR) X
Sample
Output :
2
------------------------------------------------------------------------------
5
In
this problem, you
are given the
probabilities of
occurrence of a sequence of tokens. You
are required to con-
struct a suitable encoding of the input
token to efficiently
represent these tokens while storing. In this problem, each
token
will be represented
by only one
character. The
detailed algorithm is given below.
Construct a binary tree
using the probability
sequence, as follows.
For example, consider the tokens: A, B,
C, D, E and F, and
the
respective probabilities of occurrence: 40, 30, 10,
10, 6, and 4. We represent probabilities
as an
integer in
the range 0 to 100.
Represent these as
single tree-nodes consisting
of the
token-name and the probability. It is useful to store these
nodes in an array as shown in the
figure.
Scan the array and find the lowest two
probabilities. These
will
be E and F, at positions 4 and 5 (assuming A is at
zero).
Combine these nodes into a binary tree,
by creating a new
parent
node and marking
these nodes as its children. The
node with smaller array index, will
form the left subtree
and the other will be the right subtree.
Array: 0 1 2
3 4 5
| | | |
/ \ |
| | | |
/ \ |
A B C D
E F NULL
Replace the array entry which has
smaller array index with
the
new parent of this subtree and delete the other entry
(mark it with NULL). Now the array will contain: 40, 30,
10,
10 and 10.
Repeating the above process once more,
we get to combine two
of
the 10 nodes. In case of a tie,
we choose the first in
the array. Thus we will combine
nodes C and D to
create
another subtree. This resulting tree will replace the node
C and the node D will be marked as NULL.
Array: 0 1 2
3 4 5
| | / \ |
/ \ |
| | / \
| / \
|
A B C D
NULL E F
NULL
Repeat the process, till the array
has only one
element
remaining. The final tree is as follows:
Array: 0 1 2
3 4 5
/\ | | | | |
/ \ | |
| | |
/ \ NULL NULL
NULL NULL NULL
A /\
/ \
/ \
B / \
/ \
/ \
/\ /\
/ \ / \
/ \ / \
C D E F
......
Input: The input consists of one line
giving the number of
tokens N(< 100), followed by N lines
each containing a token
name and a probability.
Output: Traverse the tree and print out
the depth of
each leaf node, left-to-right.
Some part of the code for solving this
problem will be given
to you in the grader. This is also
reproduced below for your
information in planning the rest of the
code.
The code given to you implements the
output part of
the
solution, ie. printing the
depths of the leaf nodes from
left to right. This code should not be changed, and should
be
included in your program file as "prob1.h". Please note
that the tree-node structure is also
defined in this file.
You must use this same structure.
........
Sample Input:
6
A
40
B
30
C
10
D
10
E
6
F
4
Output:
1 2 4 4 4 4
--------------------------------------------------------------------------------
6
Multi-way
Search tree
---------------------
Write a program to construct a multi-way
search tree of order 5
using a set of numbers as input. The ordering
to be used is
descending order. The basic approach to
insertion of a key (say,
k) is similar to construction of binary
search trees.
for each node (from the root onwards)
if the node has space insert the key
there at a suitable place.
else find a position i such that, key
k(i-1) > k and ki < k.
then continue the search with the
ith subtree. If the
subtree is empty, create node
structure there.
The input will consist of a number N (> 0)
followed by N numbers.
The different numbers will be on separate
lines. The program
must, for each number read-in, print out the
number of nodes (not
keys!) in the tree after insertion of the
number into the tree. You
can assume that there will be no duplicate
numbers in the input.
All output must be on one line.
.........
Sample Input:
-------------
10
1001
231
134
2356
347
455
678
745
1010
444
Sample Output:
--------------
1 1 1 1 2 2 2 2 3 4
--------------------------------------------------------------------------------
7
Write a
program to generate a boolean OR of two digital signals.
A signal has
two states, a high state and a low state.
It is given
as an array of positive integers in ascending order.
Each pair of
integer indicates the range of the signal in a high
state. The
array size will be even, so that the signal starts with a
low state
and ends with a low state.
A signal
3 4 5 9 10
11
would look
like
______ __________________
______
____________| |____| |____|
|____________________
3 4 5 9 10 11
So given two
signals
3 4 5 9 10
11
1 2 6 12 13
14
______ __________________
______
____________| |____| |____|
|____________________
3 4 5 9 10 11
______ ____________________________ ______
__| |___________________| |____| |_____
1
2 6 12 13
14
The boolean
OR is
1 2 3 4 5 12
13 14
______
______
_________________________________
______
__| |____|
|____|
|____| |_____
1
2 3 4 5 12 13
14
.......
The input
will be two signals each with exactly five high states
So each
signal would be ten positive integers seperated by a space.
A number
would not be duplicated in the same signal. A number used
in the first
signal would not be used in the second signal.
Output
should be a signal which is the boolean OR of the two input
signals.
.........
Sample Input
2 5 6 10 20
23 38 45 51 52
1 4 7 9 14
19 21 24 30 31
Output
1 5 6 10 14
19 20 24 30 31 38 45 51 52
3 4
5
12 13 14
------------------------------------------------------------------------
8
Write a
program to create a linked list of numbers in
sorted(ascending)
order and then to delete some
specified
elements from the list.
Input/Output
Specification: Input to your program is a
positive
integer N on a line followed by N numbers in the next
line. You
have to build the sorted list for these
N numbers.
Next line in the input is another positive
integer M
followed by M integers in the next line. These
M integers
are a subset of N integers given earlier. You
must delete
these elements from the linked list. Next line
in the input
is a positive integer K. Your program should
print the
Kth element of the sorted list.
Example:
Input: 8
2 5 9 2 3 1 8 4
2
2 5
5
Output: 8
Note : You
must use linked list in your program. If you don;t
use your will not be awarded any marks
even grader gives
you any marks.
-------------------------------------------------------------------------------
9
Round Robin
Scheduling Problem - Problem Statement
One of the scheduling techniques
that multitasking operating systems
use
to allocate the CPU amongst running processes
is the Round Robin
Scheduling
Technique.
Write a
program in C to simulate the technique as described below.
In this technique, the running
processes are arranged in a queue and
are
scheduled
sequentially, each for a time-slice of fixed duration. If a
process
is unable to
finish in the given time-slice, it is
suspended and
placed at
the
end of the
queue and next process in the queue is scheduled. When a
process
finishes
execution, it is removed from the queue.
........
If a process finishes execution
before exhausting the given
time-slice,
the remaining time in the time-slice is used
to create the time-slice
for the
next process
in the queue. If the total time of the simulation finishes
while a
process is
executing, the time for which the process ran in that time
slice is
deducted
from the time entry of the process and the process is retained
as the
first
process of the queue.
Input
Specification
The input to
the program will be an integer(<num>), indicating the
number of
processes in
the queue, followed by <num> pairs of integers (<pid>
<time>),
with the
first integer specifying the process id and the second integer
specifying
the number of time units required by the process to complete
execution.
These pairs will be followed by an
integer (<len>), indicating the
number of
time units making up one time-slice in the schedule.
The total
duration of the simulation (<total>) (in time units) is
specified as
the last
integer. Each line in the input is
terminated by a newline.
Input
Structure:
<num>
<pid>
<time>
<pid>
<time>
...
<len>
<total>
Output
Specification
The output of the program should be
a series of integer pairs denoting
the state of
the processes in the queue, with the first integer
indicating
the
process-id
and the second integer indicating the remaining time of the
process.
Each pair
should be on a separate line.
If there are no processes remaining
in the queue, output a pair of
zeros(0 0),
separated by a space, terminated by a newline.
Note
This problem
has to be solved using a linked list.
Marks will be
deducted if
on post exam
inspection, it is found that a linked list has not been
used.
Example
Input
5
1 5
2 4
3 1
4 5
5 2
2
10
Output
1 2
2 2
4 3
-----------------------------------------------------------------------------
****THE END****
From
c9913023@adithya.ncb.ernet.in Fri Dec 17 13:53:14 1999
Date: Fri,
17 Dec 1999 13:52:35 +0531 (IST)
From:
Prashantha-S <c9913023@adithya.ncb.ernet.in>
MGPT EVAL 10 FIRST BATCH
------------------------
You have to visulise a game in which cartoon
characters are hopping
in a square
grids. Characters are hopping from one grid to other and
if two
characters happen to hop in same grid
at the same instant,
then they
are out from the game. when the game stops, print out the
number of
characters left behind.
It should be noted that that at the most 20 characters
are allowed
to make hop and they can make a maximum of 20 hops.
As the
characters hop new characters keep on adding.
The behaviour of the characters are defined as follows:
For each
character inputs should be : t,x,y,n,hi.
t---->time
at which characters are joining the game.
x---->X-coordinate
to which the character is placed in the begining.
y---->Y-coordinate
to which the character is placed in the begining.
n---->Number
of hopping that the characters will make.
hi--->
its a string which will take input as follows:
fi------> the no of +ve Y coordinates
the character will move.
bi------> the no of -ve Y coordinates
the character will move.
ri------> the no of +ve X coordinates
the character will move.
li------> the no of -ve X coordinates
the character will move.
As a sample to
interpret hi [ie fi,bi,ri,li]
\ /
\ /
\ |
\ |
f5------> 5 unit along +ve Y Axis.
b9------> 9 unit along -ve Y Axis.
r1------> 1 unit along +ve X Axis.
l6------> 6 unit along -ve X Axis.
Your input
should start with a integer N which will determine the No.
of character
that are to be taken in the event, followed by
cartoon
behaviour as described above. ie
t,x,y,n,hi
Your output
should print out the number of cartoon left behind
after the
game is up.
========================================================================
--------------------------------------------------------------------------------
7
** 'An
introduction to Algorithms - A creative approach' -- Udi Manber
**
---------------------------------------------------------------------------------------------------------------------------------------------------------------
Maze
Problem:
Conside a n x n matrix . This
represents a maze. The input is
a set of
pairs of numbers each denoting the obstacles in the maze. Find
a path from
the starting point(0,0) to thetarget point( n-1,n-1)
without
meeting any
of the obstacles. Also, find the shortest path.
Input:
(3,2) (6,6) (7,0) ( 2,8) (5,9) (8,4)
(2,4) (0,8) (1,3) (6,3)
(9,3) (1,9)
3,0) (3,7) (4,2) (7,8) (2,2) (4,5) (5,6) (10,5) (6,2)
(6,10) (4,0)
(7,5) (7,9) (8,1) (5,7) (4,4) (8,7) (9,2) (10,9) (2,6)
Skyline
problem:
Given the exact locaitons and shapes
of several rectangular
buildings in
a city, draw the skyline(in two dimensions) of these
buildings,
eliminating hidden lines.
The inputs
are in the form (Li,Hi,Ri) where Li,Ri are the Left and
Right x coordinates of the building resp., HI
isthe height.
A skyline is
a list of x coordinates and heights connecting them in
order from
left to right.
Input :
(1,11,5)
(2,6,7) (3,13,9) (12,7,16) (14,3,25) (19,18,22) (23,13,29)
(24,4,28)
Output:
1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0
--
-- - - - --
- -- -
The
underlined numbers are the heights.
Extended
problem :
Consider the buildings to have roofs
which are at 45-degree
angles to
the buildings(each building is a rectangle with a triangle
on top).
Draw the skyline for these.
Suppose there are two skylines. One
is projected on to a blue
screen.
Another is superimposed on it and projected in red colour.
Draw the
skyline which is purple in colour. In other words, draw the
interseciton
of the two skylines.
Knapsack
problem:
Given an integer K and n item of
different sizes such that
the ith item
has an integer size ki, find a subset of the items whose
sizes sum to
exactly K, or determine that no such subset exists.
Input :
2 ,3 ,5, 6
Try for K=4
K=8 ...
Stuttering
subsequence problem:
Given two sequences A,B, find the
maximal value of i such
that B
raised to i is a subsequence of A.
Kth smallest
element:
Given a sequence of n elements and
an integer k such that
1 <= k
<= n , find the kth smallest element.
Line
segments problem:
Given a set of horizontal and
vertical line segments
(coordinates
given), find the points of intersection of these lines.
* Given a
tree's root node, make an exact copy of the tree and return
the new
root.
* Given a
tree's root node, build a mirror image of it and return the
new root.
* Given
a forest of trees, construct a single
equivalent binary tree
from
them.Eg.:
Input:
1 A
2 B
2 C
2 D
3 E
1 F
2 G
3 I
3 J
2 H
The numbers
correspond to the level of the node.
A F
/ | \ / \
B C D G H
| / \
E
I J
Preorder : A
B C D E F G I J H
Output Tree:
A
/ \
/ \
B
F
\
/
C
G
\
/ \
D I
H
/
\
E
J
Inorder : B
C E D A I J G H F
Try this!
* Construct
a tree with the given input and evaluate the arithmetic
expression.
The leaf nodes of the trees are numbers whereas the other
nodes are
operators.
eg:
*
/ \
+ -
/ \ / \
2 3 4 5
This is
equivalent to (2+3) * (4-5) = -5
(Output)
* Travelling
Salesperson Problem:
A salesperson must start at a
specified city, visit each of
the n-1
other cities exactly once, and then return to the initial city.
The cost of
going from city i to city j is C[i,j]. The objective is to
find a route
through the cities that minimises the total cost.
::::::::::::::
matplacing.c
::::::::::::::
/* eval
prob.Superimposing one matrix on another and finding the
result.
A matrix(say a) is superimposed on another
matrix(say b) such that
the middle element of a is placed on an
element(say position(i,j) of
b.The sum of the products of elements of a
and b(except the product
of the element(i,j) of b with the middle
element of a)is placed at
(i,j) of the resultant matrix.This process
repeats for each and
every
of b.The resultant matrix is o/p.
(e.g.)
i/p: 5 (matrix b)
1 2 1 2 3
1 0 0 3 1
3 4 1 0 2
2 1 2 1 3
0 0 2 4 1
3
(matrix a)
1 1 0
0 1 1
1 0 1
o/p: 2 2 5 4 3
5 7 10 7 5
6 6 2 10 5
4 11 10 7 6
2 5 7 4 4
------------------------------code------------------------------------*/
#include<stdio.h>
struct
element{
int flag,val;
};
int m,n;
void
arrange(struct element a[][50],int b[][50]){
int s=(n-1)/2,i,j,k=0,l;
for(i=s;i<s+m;i++){
l=0;
for(j=s;j<s+m;j++){
a[i][j].flag=1;
a[i][j].val=b[k][l++];
}
k++;
}
}
int
place(struct element a[][50],int b[][50],int i,int j){
int s=(n-1)/2,k,l,u=0,v,sum=0;
for(k=i-s;k<i-s+n;k++){
v=0;
for(l=j-s;l<j-s+n;l++){
if(k==i
&& l==j) /* do nothing */ ;
else
if(a[k][l].flag)
sum=sum+(a[k][l].val)*b[u][v];
v++;
}
u++;
}
return sum;
}
main(){
struct element mat1[50][50];
int
mat2[50][50],temp[50][50],res[50][50],i,j,s;
for(i=0;i<50;i++)
for(j=0;j<50;j++){
mat1[i][j].flag=0;
mat1[i][j].val=-1;
}
printf("size of first matrix:
");
scanf("%d",&m);
printf("enter first matrix:\n");
for(i=0;i<m;i++)
for(j=0;j<m;j++)
scanf("%d",&temp[i][j]);
printf("size of second matrix:
");
scanf("%d",&n);
printf("enter second
matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&mat2[i][j]);
/*printf("before arrange:\n");
for(i=0;i<m;i++){
for(j=0;j<m;j++)
printf("%d
",mat1[i][j].val);
printf("\n");
}*/
arrange(mat1,temp);
/*printf("after
arrange:\n");
for(i=0;i<m+2;i++){
for(j=0;j<m+2;j++)
printf("%d
",mat1[i][j].val);
printf("\n");
}*/
s=(n-1)/2;
for(i=0;i<m;i++)
for(j=0;j<m;j++)
res[i][j]=place(mat1,mat2,i+s,j+s);
for(i=0;i<m;i++){
for(j=0;j<m;j++)
printf("%d
",res[i][j]);
printf("\n");
}
}
::::::::::::::
patcount.c
::::::::::::::
/* to count
the no.of times a pattern string appears in a 2-D matrix,
horizontally,vertically,or diagonally from
top to bottom.The i/p
consists of m,n(size of the matrix),and
then the matrix itself.The
next line consists of the pattern string
which is to be searched in
the matrix.The o/p consists of the no.of
times the pattern string
appeared in the matrix
horizontally,vertically,or diagonally.
i/p:
4 4
isti
siti
isis
otsa
is
o/p:
7
---------------------------------code---------------------------------*/
#include<stdio.h>
#include<string.h>
char
mat[10][10],str[10];
int
m,n,l,cnt=0;
void
horizontal(int i){
int j;
for(j=0;j<=n-l;j++)
if(!strncmp(&mat[i][j],str,l))
cnt++;
}
void
vertical(int j){
int i,r,s,flag;
for(i=0;i<=m-l;i++){
s=0;
for(r=i;r<i+l;r++){
if(mat[r][j]!=str[s++]){
flag=0;
break;
}
else flag=1;
}
if(flag) cnt++;
}
}
void
rightdiag(int i,int j){
int r,s,t,u,v,flag;
for(r=i,s=j;s<=n-l;r++,s++){
t=0;
for(u=r,v=s;u<r+l;u++,v++){
if(mat[u][v]!=str[t++]){
flag=0;
break;
}
else flag=1;
}
if(flag) cnt++;
}
}
void
leftdiag(int i,int j){
int r,s,t,u,v,flag;
for(r=i,s=j;s>=l-1;r++,s--){
t=0;
for(u=r,v=s;u<r+l;u++,v--){
if(mat[u][v]!=str[t++]){
flag=0;
break;
}
else flag=1;
}
if(flag) cnt++;
}
}
main(){
int i,j;
printf("enter matrix
size(row,col): ");
scanf("%d%d",&m,&n);
printf("enter the
matrix:\n");
for(i=0;i<m;i++) scanf("%s",mat[i]);
printf("enter the string:
");
scanf("%s",str);
l=strlen(str);
for(i=0;i<m;i++) horizontal(i);
for(j=0;j<n;j++) vertical(j);
for(j=n-l+1,i=0;i<=m-l+1;){
rightdiag(i,j);
if(j==0) i++;
else j--;
}
for(j=l-1,i=0;i<=m-l+1;){
leftdiag(i,j);
if(j==n-1) i++;
else j++;
}
printf("%s is found %d
times\n",str,cnt);
}
::::::::::::::
perm.c
::::::::::::::
/*
permutations of a given string
i/p:
abc
o/p:
abc
acb
bac
bca
cba
cab
*/
/*-------------------------code---------------------------------------*/
#include<stdio.h>
#include<string.h>
int l;
permute(char
*str,int i){
char *inter,temp;
int s,k,j;
inter=(char*)malloc(100*sizeof(char));
strcpy(inter,&str[i]);
if(strlen(inter)==2){
printf("%s\n",str);
for(s=0;s<l-2;s++)
printf("%c",str[s]);
printf("%c%c\n",str[l-1],str[l-2]);
return 0;
}
for(j=i;j<l;j++){
k=0;
for(s=i;s<l;s++)
str[s]=inter[k++];
temp=str[i];str[i]=str[j];str[j]=temp;
permute(str,i+1);
}
}/* end
permute */
main(){
char
*str=(char*)malloc(100*sizeof(char));
printf("Original string
is:\n");
gets(str);l=strlen(str);
printf("Permuted combinations
are:\n");
if(l==1)
{printf("%s\n",str);return 0;}
permute(str,0);
}
::::::::::::::
setop.c
::::::::::::::
/* eval
problem. set operations.
i/p: 3 lines containing tne no. and
elements of a set.
The next 4 lines contain
the set operations to be performed.
(eg.) 6 1 2 3 4 5 6
4 1 5 6 7
3 1 4 5
A*B
A+B
B*C
A-C
o/p: 4 lines giving the the no. of
elements in the resultant set due
to each operation
(eg.) 3
7
2
3 */
/*-----------------------------code-----------------------------------*/
#include<stdio.h>
#include<string.h>
int
A[30],B[30],C[30],nA,nB,nC;
int
inter(int a[],int b[],int na,int nb){
int cnt=0,i,j;
for(i=0;i<na;i++)
for(j=0;j<nb;j++)
if(a[i]==b[j]){
cnt++;
break;
}
return cnt;
}
void
eval(char *str){
int *a,*b,na,nb,res;
switch(str[0]){
case
'A':a=A;na=nA;break;
case
'B':a=B;na=nB;break;
case
'C':a=C;na=nC;break;
}
switch(str[2]){
case
'A':b=A;nb=nA;break;
case
'B':b=B;nb=nB;break;
case 'C':b=C;nb=nC;break;
}
switch(str[1]){
case
'*':res=inter(a,b,na,nb);break;
case
'+':res=nA+nB-inter(a,b,na,nb);break;
case
'-':res=nA-inter(a,b,na,nb);break;
}
printf("%d\n",res);
}
main(){
int i;char str[3];
scanf("%d",&nA);
for(i=0;i<nA;i++) scanf("%d",&A[i]);
scanf("%d",&nB);
for(i=0;i<nB;i++)
scanf("%d",&B[i]);
scanf("%d",&nC);
for(i=0;i<nC;i++)
scanf("%d",&C[i]);
for(i=0;i<4;i++){
scanf("%s",str);
eval(str);
}
}
/* 1mgpt question */
/* OR signal handling */
/* 2nd method */
#include
<stdio.h>
main()
{
int
num[2][100],sig[3][500],i,j,x,max,n;
printf("\n\n\t\tinput no. of
elements of row [ even no. ]:");
scanf("%d",&n);
for(i=0;i<2;i++)
for(j=0;j<n;j++)
scanf("%d",&num[i][j]);
max=num[0][n-1] >
num[1][n-1] ? num[0][n-1] : num[1][n-1] ;
for(i=0;i<2;i++)
for(j=0;j<n;j+=2)
for(x=num[i][j];x<num[i][j+1];x++)
sig[i][x]=1;
for(i=1;i<=max;i++)
sig[2][i]=sig[0][i]
|| sig[1][i] ;
for(i=0;i<2;i++)
for(j=0;j<n;j+=2)
for(x=num[i][j];x<num[i][j+1];x++)
sig[i][x]=1;
for(i=0;i<=max;i++)
if (
sig[2][i] )
{
printf("%d
",i);
for(++i;i<=max
&& sig[2][i] ;i++);
printf("%d
",i);
}
printf("\n");
}
/* 1mgpt question */
/* STRING MANUPULATION UNDER
CONDITION +,.,*,?,//,A CHARECTER
REPLACEMENT OF WORD */
#include
<stdio.h>
main()
{
char str1[20][20],str2[20],f1;
int i,j,k,l,x=0,y=0;
while( (str1[x][y]=getchar())!='\n'
)
{
if ( isspace(str1[x][0])
)
continue;
else if (
isspace(str1[x][y]) )
{
str1[x][y]='\0'; ++x ; y=-1; }
++y;
}
str1[x][y]='\0';
gets(str2);
for (i=0;i<=x;i++,printf("
"))
for (j=0;str1[i][j];j++)
{
for(k=0,l=j;str2[k];k++,l++)
if
(str2[k]=='+' && isalpha(str1[i][l]) )
f1='t';
else
if (str2[k]=='*' && isalnum(str1[i][l]) )
f1='t';
else
if (str2[k]=='?' && isdigit(str1[i][l]) )
f1='t';
else
if (str2[k]=='\\' && str2[k+1]=='\\' && \
!isalnum(str1[i][l])
&& str2[k+2]==str1[i][l] )
{
f1='t'; k+=2; }
else
if (str2[k]=='.'&& !isdigit(str1[i][l]) )
f1='t';
else
if ( str2[k]==str1[i][l] )
f1='t';
else
{ f1='f'; break; }
if ( f1=='t'
)
j=l-1;
else
printf("%c",str1[i][j]);
}
printf("\n");
}
/* pgdst-mgpt question */
/* matrix manupulation */
/* if input (3*3) is 1 2 3 4 5
6 7 8 9 */
/* then output 1 4 2 3 5 7 8 6
9 */
#include
<stdio.h>
main()
{
int
i,j,num[10][10],m,n,c;
/* ..............INPUT...................*/
printf("\n\n\t\tINPUT
ROW & COLUMN :");
scanf("%d
%d",&m,&n);
printf("\n\n\t\tINPUT
MATRIX ELEMENT :\n");
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d",&num[i][j]);
/* ..........PROCESSING.............. */
i=0;j=-1;c=0;
while(c <
m*n)
{
if ( i>=m )
{++j;i=m-1;}
for(++j; j<n && i>=0
&& c<m*n ;--i,++j,++c)
printf("%d ",num[i][j]);
if (j>=n)
{++i;j=n-1;}
for(++i; j>=0 && i<m
&& c<m*n ;--j,++i,++c)
printf("%d
",num[i][j]);
}
}
/*************************************************************
The game of
LIFE takes place on a 2d array of cells,each of
which may
contain an organism . Let occ(i) be the no. of cells
adjacent to
cell i that are occupied by an org.. ,is obtained from
the previous
generation appling the following rules:
I. An org..
in cell i survive to the next generation if
2<=occ(i)<=3; otherwise it dies.
II. An org..
born in empty cell i if 2<=occ(i)<=3; otherwise it
remains empty
Write a
prg.. that reads initial config.. of occupied cells and prints
a series of
gene.. . Note that the prg.. must maintain two copies of
the config..
,since all changes occur simultaneously.
****************************************************************/
#include
<stdio.h>
main()
{
char org[100][100];
int i,j,n;
printf("\n\n\t\tInput n for n*n
matrix :");
scanf("%d",&n);
fflush(stdin);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%c
",&org[i][j]);
printf("j=%d
%c\n",j,org[i][j]);
}
for(i=0;i<n;i++)
for(printf("\n"),j=0;n>j;j++)
printf("%c
",org[i][j]);
}
/* canceld mgpt question */
/* lucky no. calculation on
name */
/* 1>=word<=3 : a=1.....z=26 */
/* output : for each word
& total word sum in single digit */
#include
<stdio.h>
main()
{
char str[3][20];
int i=0,j=0,sum[4]={0};
while(i<=2 &&
(str[i][j]=getchar())!='\n')
{
if (isspace(str[i][0]))
continue;
else if
(isspace(str[i][j]))
{ ++i;j=-1;
}
else if (
isalpha(str[i][j]) )
sum[i]+=(toupper(str[i][j])-'A')+1;
++j;
}
if ( i>2 ) --i;
for(j=0;j<=i;sum[3]+=sum[j],++j)
for(;sum[j]>9;sum[j]=sum[j]/10+sum[j]%10);
for(;sum[3]>9;sum[3]=sum[3]/10+sum[3]%10);
for(j=0;j<=i;++j)
if(sum[j]>0) printf("%d ",sum[j]);
if(sum[3]>0) printf("%d\n",sum[3]);
}
/* mock mgpt question */
/* reverse a word starting
with r/R */
include
<stdio.h>
main()
{
int i,x,y;
char s[100],c;
gets(s);
for(i=0;s[i];i++)
if((s[0]=='r'||s[0]=='R')||(!isalpha(s[i])&&\
(s[i+1]=='r'||s[i+1]=='R')))
{
if (
(s[0]=='r'||s[0]=='R')&&isalpha(s[1])) --i;
for(x=++i;isalpha(s[i]);++i);
for(y=--i;y>x;--y,++x)
{
c=s[x];s[x]=s[y];s[y]=c; }
}
puts(s);
}
/* 3rd mgpt question no 1 of
string substitution */
/* replace a specified word
wth given word */
#include
<stdio.h>
main()
{
char str[100],str1[20],str2[20];
int i,j,x,flag;
printf ( "\n\tInput string to be substituted \n");
gets(str1);
printf ( "\n\tInput substitution string \n");
gets(str2);
printf ( "\n\n\tInput sentence \n");
gets(str);
printf("\n\n\t\t\tOutput...............\n");
for(i=0;str[i];++i)
{
for(j=0,x=i,flag=0;str1[j]
&& flag==0 ;++x,++j)
if
( str[j]!=str1[x] )
flag=1;
if ( flag==1
)
{
printf("%s",str2);
i=x-1;
}
else
printf("%c",str[i]);
}
printf("\n\n\n");
}
/* 2nd mgpt question */
/* stack question----- */
/* a book-keeper making a book
rack.if he throws a book which
weight is greater
than/equal to previous(just) then thrown
book is fall down with
some other book equal to its weight
the output is total no
of in rack & its total weight
input is weight of book
terminated by -1 */
main()
{
int i,j,x,n[100];
for(i=0,scanf("%d",&n[i]);n[i]!=-1;scanf("%d",&n[++i]))
{
if ( i>0 &&
n[i]>=n[i-1] )
{
x=n[i]-n[i-1];
for(i-=2;(x-n[i])>=0&&i>=0;x-=n[i--]);
}
}
for(x=0,j=0;j<i;j++) x+=n[j];
printf("%d %d\n",i,x);
}
/* 3rd mgpt
question no. 2 */
/* Input :-
begin
var x
var y
y 10
x 5
begin
y 20
var z
z 10
j 10
print y
print x
end
print y
end */
/* Output :-
ERR
20
5
10 */
#include
<stdio.h>
main()
{
int i=-1,j,f,val[50]={0};
char order[50][20];
do
{
scanf("%s",order[++i]);
if (
strcmp(order[0],"begin"))
break;
else if (
!strcmp(order[i],"end"))
{
for(j=i-1,f=0;j>=0
&& f==0;--j)
if
( !strcmp(order[j],"begin"))
f=1;
if ( f==1 )
i=j;
}
else if (
strcmp(order[i],"begin"))
{
if (
!strcmp(order[i],"var"))
scanf("%s",order[i]);
else if (
!strcmp(order[i],"print"))
{
scanf("%s",order[i]);
for(j=i-1,f=0;j>=0
&& f==0;j--)
if
( !strcmp(order[i],order[j]))
f=1;
if
( f==1 )
printf("%d\n",val[++j]);
else
printf("ERR\n");
}
else
{
for(j=i-1,f=0;j>=0
&& f==0;j--)
if
( !strcmp(order[i],order[j]))
f=1;
if
( f==1 )
scanf("%d",&val[i]);
else
printf("ERR\n");
}
}
fflush(stdin);
}while(i>=0);
}
/* Input : n ( no. of set) then n pairs of no. */
/* Output :- related set */
/* eg:-
input:- 5
1 4,4 8,7 11,15 20,4 13
output:-
1 4 7 8 11 13
15 20 */
#include
<stdio.h>
main()
{
int
i,j,k,l,n,m[20],num[20][20],x,f,f1;
for(scanf("%d",&n),i=0;i<n;i++)
for(j=0;j<2;j++)
scanf("%d",&num[i][j]);
for (i=0;i<n;i++)
m[i]=2;
for(i=0;i<n;i++,f1=0)
{
for(j=i+1;j<n;j++)
for(k=0,f=0;k<m[i]
&& f==0;k++)
for(l=0;l<2
&& f==0;l++)
if
( num[i][k]==num[j][l] )
{
f1=f=1;
if
( l==0 )
for
(x=0;x<m[i]&&num[i][x]<=num[j][1];x++);
else
for
(x=0;x<m[i]&&num[i][x]<=num[j][0];x++);
for
(k=x,x=m[i]++;x>k;x--)
num[i][x]=num[i][x-1];
if
( l==0 )
num[i][k]=num[j][1];
else
num[i][k]=num[j][0];
for(x=j;x<n-1;x++)
for(l=0;l<2;l++)
num[x][l]=num[x+1][l];
--j;--n;
}
if ( f1==1 )
i=-1;
}
for(i=0;i<n;i++,printf("\n"))
for(j=0;j<m[i];j++)
printf("%d
",num[i][j]);
}
/* Pascal Series */
# include
<stdio.h>
int
arr[100][1000];
addarr(int
i)
{
int j,k=0;
if(!i)
arr[i][0]=1;
else
for(j=i-1;k<i+1;(!k)?(arr[i][k]=1):\
((k==i)?(arr[i][k]=1):(arr[i][k]=arr[j][k-1]+arr[j][k])),k++);
}
main()
{
int N,i,j;
scanf("%d",&N);
if(N>1)
{
for(i=0; i<=N;
addarr(i),i++);
printf("1
\n");
for(i=2;i<N+1;i++,printf("\n"))
for(j=0;j<i+1;printf("%d
",arr[i][j++]));
}
}
/* to print
all the possible combinations of the digits for the letters
such that
the foll. puzzle holds
I IS
+AM +IT
--- ---
OK OK
/*----------------------------code------------------------------------*/
#include<stdio.h>
main(){
int i,a,m,o,k,s,t,cou;
/* s+t=i+m;a=2i;(s+t)%10=k;a:
2,4,6,8*/
for(i=1;i<=4;i++)
for(s=0;s<=9;s++)
for(t=0;t<=9;t++)
for(m=0;m<=9;m++){
a=2*i;o=(i+m)/10+a;k=(i+m)%10;
if((s!=i
&& s!=a && s!=m && s!=t && s!=o &&
s!=k)&&(t!=i && t!=a
&&
t!=m && t!=o && t!=k)&&(m!=i && m!=a &&
m!=o && m!=k)&&(a!=i && a!=o
&&
a!=k)&&(s+t==i+m)){
printf("set%d:\n\n",++cou);printf(" %d\n+%d%d\n---\n
%d%d\n\n",i,a,m,o,k);printf("\n\n
%d%d\n+%d%d\n---\n %d%d\n\n\n\n",i,s,i,t,o,k);}
}
}
/* skyline
Skyline
problem:
Given the exact locaitons and shapes
of several rectangular
buildings in
a city, draw the skyline(in two dimensions) of these
buildings,
eliminating hidden lines.
The inputs
are in the form (Li,Hi,Ri) where Li,Ri are the Left and
Right x coordinates of the building resp., HI
isthe height.
A skyline is
a list of x coordinates and heights connecting them in
order from
left to right.
Input :
(1,11,5)
(2,6,7) (3,13,9) (12,7,16) (14,3,25) (19,18,22) (23,13,29)
(24,4,28)
Output:
1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0
--
-- - - - --
- -- -
The
underlined numbers are the heights. */
/*----------------------------code------------------------------------*/
#include<stdio.h>
#include<stdlib.h>
struct
nodetype{
int left,height,right;
struct nodetype *next;
};
typedef
struct nodetype *nodeptr;
nodeptr
getnode(){
return((nodeptr)malloc(sizeof(struct
nodetype)));
}
nodeptr
makelist(int l,int h,int r){
nodeptr p;
p=getnode();
p->left=l;p->height=h;p->right=r;p->next=NULL;
return p;
}
void main()
{
nodeptr list,p,q,r,t,newnode=NULL;
int xl,h,xr,temp,temph,flag;
scanf("%d%d%d",&xl,&h,&xr);
list=makelist(xl,h,xr);
while(scanf("%d%d%d",&xl,&h,&xr)!=EOF)
{
q=makelist(xl,h,xr);
for(p=list;p &&(!((p->left
<= q->left)&&(q->left <=
p->right)));p=p->next)
r=p;
if(!p)
{
newnode=makelist(r->right,0,q->left);
r->next=newnode;
newnode->next=q;
}
else
{
while(p)
{
flag=0;
if(!((p->left
<= q->right)&&(q->right <= p->right)))
{
if(q->height
< p->height) /* neglect */;
else
{
if((p->left
< q->left)&&(q->left < p->right))
{
temp=p->right;p->right=q->left;
newnode=makelist(p->right,q->height,temp);
newnode->next=p->next;p->next=newnode;p=newnode;
}
else
p->height=q->height;
}
}
else{
if(q->height
< p->height) /* neglect */;
else
{
if((p->left
< q->left)&&(q->left < p->right))
{
temp=p->right;p->right=q->left;
newnode=makelist(q->right,p->height,temp);
p->next=q;q->next=newnode;
}
else
{
temp=p->right;temph=p->height;p->right=q->right;p->height=q->height;
newnode=makelist(p->right,temph,temp);
p->next=newnode;
}
}
flag=1;
}
if(flag)
break;
r=p;p=p->next;
}
if(!p)
{
newnode=makelist(r->right,q->height,q->right);
r->next=newnode;
}
}
for(p=list;p;)
{
if((p->next)&&(p->height
== (p->next)->height))
{p->right=(p->next)->right;t=p->next;p->next=t->next;free(t);}
else
p=p->next;
}
}
for(p=list;p;p=p->next)
{printf("%d %d ",p->left,p->height);r=p;}
printf("%d
0\n",r->right);
}
/* assn.
no.10 in '98 batch
i/p line is
terminated by a '.'
o/p line is
terminated by a '\n'
i/p: this is
a test . or this is a test.
o/p: test a
is this */
#include<stdio.h>
#include<string.h>
main(){
char str[200][200],*tok;
int i=0,j,flag=0;
scanf("%s",str[i]);
for(j=0;str[i][j]!='\0';j++) ;
while(str[i][j-1]!='.')
{
scanf("%s",str[++i]);
j=strlen(str[i]);
}
tok=strtok(str[i--],".");
if(tok)
{
printf("%s",tok);
flag=1;
}
while(i>=0)
{
if(flag) printf("
");
flag=0;
printf("%s",str[i--]);
if(i>=0)
printf(" ");
}
printf("\n");
}
/* Given
radius,to print no. of integer coordinates that lie within the
circle*/
#include<stdio.h>
#include<math.h>
main(){
float r;
int x,y,count=0;
printf("Input radius:
"),scanf("%f",&r);
for(x=ceil(-r);x<=floor(r);x++)
for(y=ceil(-r);y<=floor(r);y++)
if(x*x + y*y
< r*r) count++;
printf("No. of integer
co-ordinates that lie within the circle is
%d\n",count);
}
::::::::::::::
ass.c
::::::::::::::
#include
<stdio.h>
struct tree
{
char name[20];
struct tree *left;
struct tree *right;
};
typedef
struct tree* node;
node
makenode(char name1[20])
{
node temp;
temp=(node)malloc(sizeof(struct
tree));
strcpy(temp->name,name1);
temp->left=NULL;
temp->right=NULL;
return temp;
}
void
insert(node temp,node temp1,char name1[20])
{
int i;
node prev;
prev=temp;
for(i=1; i < strlen(name1)-1;
i++)
{
if(name1[i]=='L')
{
prev=temp;
temp=temp->left;
}
else if(name1[i]=='R')
{
prev=temp;
temp=temp->right;
}
}
if(name1[i-1]=='L')
prev->left=temp1;
else
prev->right=temp1;
}
void
inorder(node temp)
{
if(temp)
{
if(temp->left==NULL
&& temp->right==NULL)
printf("%s
", temp->name);
inorder(temp->left);
inorder(temp->right);
}
else
return;
}
node
search(node temp,char string[20])
{
node temp1,temp2;
if(temp)
{
if(strcmp(temp->name,string)==0)
return temp;
else
temp1=search(temp->left,string);
if(temp1)
return temp1;
else
temp2=search(temp->right,string);
if(temp2)
return
temp2;
else
return NULL;
}
else
return NULL;
}
main()
{
node root,temp,temp1,temp2;
char str1[20],str2[20],str3[20];
int num,n;
int i,j,k,flag;
root=NULL;
scanf("%s%s", str1,str2);
if(root==NULL)
{
root=(node)malloc(sizeof(struct
tree));
strcpy(root->name,str2);
root->left=NULL;
root->right=NULL;
}
while(1)
{
scanf("%s%s",
str1,str2);
if(strcmp(str1,"END")==0)
break;
else
{
temp =
makenode(str2);
insert(root,temp,str1);
}
}
scanf("%d",&num);
for(i=0; i<num; i++)
{
temp2=root;
scanf("%d",&n);
for(j=0; j<n; j++)
{
scanf("%s",
str3);
if(str3[0]=='!')
flag=1;
else
flag=0;
if(flag==1)
{
temp1=search(temp2,&str3[1]);
temp2=temp1->left;
}
else
{
temp1=search(temp2,&str3[0]);
temp2=temp1->right;
}
}
inorder(temp2);
printf("\n");
}
}
::::::::::::::
avl.c
::::::::::::::
#include
<stdio.h>
typedef
struct tree
{
int Num;
int Rh, Lh;
struct tree *Right, *Left;
}*Node;
main()
{
int n;
Node Head = NULL;
while(1)
{
scanf("%d",
&n);
if ( n == -1 )
break;
Insert(&Head, n);
}
puts("Inorder");
Inorder(Head);
printf("\n");
puts("Preorder");
Preorder(Head);
printf("\n");
}
Insert(Node
*temp, int n)
{
Node q,p;
int max, flag=0;
if ( !(*temp) )
{
(*temp) = (Node)
malloc(sizeof(struct tree));
(*temp)->Right
= (*temp)->Left = NULL;
(*temp)->Num = n;
(*temp)->Rh =
(*temp)->Lh = 0;
}
else
{
if ( (*temp)->Num
> n )
{
Insert(&((*temp)->Left),
n);
(*temp)->Lh
= Max((*temp)->Left)+1;
flag=Check((*temp));
if(flag)
{
p=(*temp);
q=(*temp)->Left;
if(q->Rh
> q->Lh)
{
Leftrotate(&q);
Set(p);
}
Rightrotate(&(*temp));
Set(&(*temp));
}
}
else
{
Insert(&((*temp)->Right),
n);
(*temp)->Rh
= Max((*temp)->Right)+1;
flag=Check((*temp));
if(flag)
{
p=(*temp);
q=(*temp)->Right;
if(q->Lh
> q->Rh)
{
Rightrotate(&q);
Set(p);
}
Leftrotate(&(*temp));
Set(&(*temp));
}
}
}
}
int
Check(Node temp)
{
int flag=0;
if ( abs((temp->Rh) -
(temp->Lh)) > 1 )
flag=1;
return flag;
}
Max(Node
temp)
{
if ( temp )
return (temp->Rh >
temp->Lh)?temp->Rh:temp->Lh;
else
return -1;
}
Inorder(Node
temp)
{
if (temp)
{
Inorder(temp->Left);
printf("%d
",temp->Num);
Inorder(temp->Right);
}
}
Preorder(Node
temp)
{
if (temp)
{
printf("%d
",temp->Num);
Preorder(temp->Left);
Preorder(temp->Right);
}
}
Leftrotate(Node
*temp)
{
Node p;
p=(*temp)->Right;
(*temp)->Right=p->Left;
p->Left=(*temp);
(*temp)=p;
}
Rightrotate(Node
*temp)
{
Node p;
p=(*temp)->Left;
(*temp)->Left=p->Right;
p->Right=(*temp);
(*temp)=p;
}
Set(Node
*temp)
{
if(*temp)
{
Set(&(*temp)->Left);
(*temp)->Lh=Max((*temp)->Left)
+ 1;
Set
(&(*temp)->Right);
(*temp)->Rh=Max((*temp)->Right)
+ 1;
}
}
::::::::::::::
btree.c
::::::::::::::
#include
<stdio.h>
struct
nodetype{
struct nodetype *left;
struct nodetype *right;
int ele;
};
typedef
struct nodetype *node;
node tree;
int
element[8] = { 68, 80, 25, 40, 12, 32, 72, 92 };
node
create_node(int ele)
{
node p;
p = (node)malloc(sizeof(struct nodetype));
p->ele = ele;
p->left = p->right = NULL;
return(p);
}
void
itrate_insert( node p )
{
node q, f;
if( tree != NULL)
{
q = tree;
while( q != NULL)
{
f = q;
if(p->ele < q->ele)
q = q->left;
else
q = q->right;
}
if( f->ele > p->ele)
f->left = p;
else
f->right = p;
}
else
tree = p;
}
void
recursive_insert(node p, node father)
{
if( p->ele < father->ele)
{
if( father->left != NULL )
recursive_insert(p,
father->left);
else
father->left = p;
}
else
{
if( father->right != NULL)
recursive_insert(p,
father->right);
else
father->right = p;
}
}
void
inorder_traverse(node p)
{
if(p != NULL)
{
inorder_traverse(p->left);
printf("NODE:%d ELEMENT = %d\n", p, p->ele);
inorder_traverse(p->right);
}
}
void
preorder_traverse(node p)
{
if(p != NULL)
{
printf("NODE:%d ELEMENT = %d\n", p, p->ele);
preorder_traverse(p->left);
preorder_traverse(p->right);
}
}
void
postorder_traverse(node p)
{
if(p != NULL)
{
postorder_traverse(p->left);
postorder_traverse(p->right);
printf("NODE:%d ELEMENT = %d\n", p, p->ele);
}
}
main()
{
int i;
node p;
tree = NULL;
/*
for(i = 0; i < 8; i++)
{
p = create_node(element[i]);
itrate_insert( p );
}
*/
tree = create_node(element[0]);
for( i = 1; i < 8; i++ )
{
p = create_node(element[i]);
recursive_insert(p, tree);
}
printf("PRE ORDER\n");
preorder_traverse(tree);
printf("IN ORDER\n");
inorder_traverse(tree);
printf("POST ORDER\n");
postorder_traverse(tree);
free(tree);
}
::::::::::::::
bubble.c
::::::::::::::
struct
bubble
{
int tcr, eNo, id,ht, sz ;
}b[100];
main()
{
int i,j,k,l,dec,inc,simtime,noevents,mid ,
max,time=0;
scanf("%d %d %d %d
",&dec,&inc,&simtime,&noevents);
printf("Input---\n");
printf("%d %d %d
%d\n",dec,inc,simtime,noevents);
for(i=0;i<noevents;i++)
{
scanf("%d %d %d ",&b[i].tcr, &b[i].eNo, &b[i].id);
if(b[i].eNo == 0)
scanf("%d %d ", &b[i].ht, &b[i].sz);
}
for(i=0;i<noevents;i++)
printf("%d %d %d %d %d\n",b[i].tcr, b[i].eNo, b[i].id,
b[i].ht,
b[i].sz);
while(time < simtime)
{
for(i=0; i<noevents ; i++)
{
if(b[i].tcr <
simtime)
{
if(b[i].eNo ==0)
{
b[i].ht -= dec;
b[i].sz += inc;
}
else if(b[i].eNo ==1)
{
for(j=0; j< noevents;j++)
if(b[j].id
== b[i].id) /* need be checked ?? */
{
b[j].sz=0;
break;
}
}
}
}
time++;
}
/* If Height
is less than 0 make all elements of the bub zero */
for(i=0; i< noevents ;i++)
if(b[i].ht <= 0)
b[i].tcr = b[i].eNo = b[i].id = b[i].ht = b[i].sz = 0;
max = b[0].sz;
for(i=1; i< noevents ;i++)
{
if(b[i].sz > max)
{
max= b[i].sz;
mid = i;
}
}
printf("\n\n Output %d %d %d\n", b[mid].id , b[mid].ht,
b[mid].sz);
}
::::::::::::::
family.c
::::::::::::::
#include<stdio.h>
typedef
struct node{
char *name;
struct node *left,*right;
}*nodeptr;
nodeptr
root,temp,find;
int flag=0;
nodeptr
creat(char *name)
{
nodeptr new;
new=(nodeptr)malloc(sizeof(struct
node));
new->name=(char
*)malloc(20*sizeof(char));
new->left=NULL;
new->right=NULL;
strcpy(new->name,name);
return new;
}
void
insert(nodeptr temp,nodeptr new)
{
if(temp->left==NULL)
{
temp->left=new;
return;
}
else
{
temp->right=new;
return;
}
}
search(nodeptr
temp,char *name)
{
if(temp&&flag!=1)
{
if(strcmp(temp->name,name))
{
search(temp->left,name);
if(flag!=1)
search(temp->right,name);
else
return;
}
else
{
flag=1;
find=temp;
return;
}
}
else
return;
}
main()
{
nodeptr new;
char *name;
int num,i,fg;
name=(char
*)malloc(20*sizeof(char));
scanf("%s",name);
if(strcmp(name,"END"))
{
new=creat(name);
root=new;
while(strcmp(name,"END"))
{
scanf("%d",&num);
temp=root;
flag=0;
search(temp,name);
for(i=0;i<num;i++)
{
scanf("%s",name);
new=creat(name);
insert(find,new);
}
scanf("%s",name);
}
}
scanf("%d",&num);
for(i=0;i<num;i++)
{
scanf("%s",name);
temp=root;
find=NULL;
flag=0;
search(temp,name);
scanf("%s",name);
flag=0;
if(find&&strcmp(find->name,name))
search(find,name);
if(flag==1)
printf("YES\n");
else
printf("NO\n");
}
}
::::::::::::::
height.c
::::::::::::::
#include
<stdio.h>
#include
<stdlib.h>
typedef
struct tree {
int element;
struct tree *left;
struct tree *right;
int lh, rh;
} *node;
node head,
root;
int max(node
temp)
{
if(temp->rh > temp->lh)
return temp->rh;
else
return temp->lh;
}
node
create(int element)
{
node temp;
temp = (node) malloc (sizeof(struct
tree));
temp->element = element;
temp->rh = temp->lh = 0;
temp->right = temp->left =
NULL;
return temp;
}
int
insert(node temp, int element)
{
node hold;
int result;
if(!temp)
return 0;
if(temp->element < element)
{
if(temp->right)
{
result =
insert(temp->right, element);
temp->rh
= max(temp->right)+1;
}
else
{
hold =
create(element);
temp->right
= hold;
temp->rh
= max(hold)+1;
result = 1;
}
}
else
{
if(temp->left)
{
result =
insert(temp->left, element);
temp->lh
= max(temp->left)+1;
}
else
{
hold =
create(element);
temp->left
= hold;
temp->lh
= max(hold)+1;
result = 1;
}
}
return
result;
}
void
preorder(node head)
{
if(head)
{
printf("element = %d,left hight
= %d, right hight = %d\n",
head->element,
head->lh, head->rh);
preorder(head->left);
preorder(head->right);
}
}
void
postorder(node head)
{
if(head)
{
preorder(head->left);
preorder(head->right);
printf("element = %d,left hight
= %d, right hight = %d\n",
head->element,
head->lh, head->rh);
}
}
int main()
{
int data=0, i, j, k;
node temp;
scanf("%d", &data);
root = create(data);
for(;data != -1;)
{
scanf("%d",
&data);
if(data == -1)break;
i = insert(root, data);
if(!i)break;
}
preorder(root);
postorder(root);
}
::::::::::::::
rotatio.c
::::::::::::::
/*
You have to
construct a binary search tree and perform either a left
or a right
rotation ONCE, as directed.
Input to the
program will consist of an integer N, followed by N
integers,
which have
to be used to construct the binary search tree.
This will be
followed by an instruction "left" or "right" and you have
to
rotate the
tree accordingly, once.
After that,
you have to output the preorder traversal of the tree.
If the
requested rotation cannot be performed, ignore the instruction
and directly
print the preorder traversal of the tree.
Input:
------
5 1 2 5 6 4
left
Output:
-------
2 1 5 4 6
/* file:
ds/sep10_mock.c */
/* Mock MGPT
conducted on Sep 10, 1998 */
/* given a
BST and either "left" or "right" perform ONE rotation */
/*
accordingly, and then print the preorder traversal of the tree */
/* PGDST
'98, NCST Bangalore */
#include
<stdio.h>
#define
LT(a,b) ((a)<(b))
typedef
struct n_type
{
int info;
struct n_type *left, *right;
} node;
node *root;
node
*getnode(void);
node
*insert(node *, int);
void
preorder(node *);
void
leftrotate(void);
void
rightrotate(void);
int
main(void)
{
int a,b,c,x,y,z,n;
char dir[10]={'\0'};
node *p;
root=NULL;
scanf ("%d",&n);
for (x=0; x<n; x++)
{
scanf
("%d",&a);
root=insert(root,a);
} /** "for" to
construct BST **/
scanf ("%s",dir);
if (!(strcmp(dir,"left"))
&& root->right)
leftrotate();
else if
(!(strcmp(dir,"right")) && root->left)
rightrotate();
preorder(root);
printf ("\n");
return 0;
}
/** end of "main" **/
node
*getnode(void)
{
node *p;
p=(node *)malloc(sizeof(node));
p->left=p->right=NULL;
return p;
}
/** end of "getnode" **/
node
*insert(node *root, int data)
{
if (!root)
{
root=(node *)malloc(sizeof(node));
root->info=data;
root->left=root->right=NULL;
}
else if (LT(data,root->info))
root->left=insert(root->left,data);
else
root->right=insert(root->right,data);
return root;
}
/** end of "insert"
**/
void
preorder(node *root)
{
if (root)
{
printf ("%d ",root->info);
preorder(root->left);
preorder(root->right);
}
}
/** end of preorder **/
void
leftrotate(void)
{
node *o_root, *newroot, *lst, *n;
o_root=newroot=lst=(node
*)malloc(sizeof(node));
o_root=root;
newroot=o_root->right;
lst=newroot->left;
newroot->left=o_root;
o_root->right=lst;
root=newroot;
return;
}
/** end of "leftrotate" **/
void
rightrotate(void)
{
node *o_root, *newroot, *rst, *n;
o_root=newroot=rst=(node
*)malloc(sizeof(node));
o_root=root;
newroot=o_root->left;
rst=newroot->right;
o_root->left=rst;
newroot->right=o_root;
root=newroot;
return;
}
/** end of "rightrotate" **/
::::::::::::::
shell.c
::::::::::::::
#include<stdio.h>
#define MAX
25
char
tname[MAX][MAX]={NULL}, tdest[MAX][MAX]={NULL};
int
tno[MAX]={0};
int main()
{
int i=0,n=0,span =0,done ,temp;
char ndest[MAX], tstr[MAX];
while(1)
{
scanf("%s",&tname[i]);
if(strcmp(tname[i],"-1")==0)
break;
scanf("%s",&tdest[i]);
scanf("%d",&tno[i]);
i++;
}
n=i;
scanf("%s",ndest);
span = n/2;
while(1)
{
done = 1;
while(done)
{
done = 0;
for(i=0;(i+span)<n;i++)
if(tno[i]>tno[i+span])
{
temp =
tno[i];
tno[i]
= tno[i+span];
tno[i+span]
= temp;
strcpy(tstr,tname[i]);
strcpy(tname[i],tname[i+span]);
strcpy(tname[i+span],tstr);
strcpy(tstr,tdest[i]);
strcpy(tdest[i],tdest[i+span]);
strcpy(tdest[i+span],tstr);
done = 1;
}
}
printf("%s\n",tname[0]);
span = span -2;
if(span<=0) break;
}
if(span+2 != 1)
{
span = 1;
done = 1;
while(done)
{
done = 0;
for(i=0;(i+span)<n;i++)
if(tno[i]>tno[i+span])
{
temp =
tno[i];
tno[i]
= tno[i+span];
tno[i+span] = temp;
strcpy(tstr,tname[i]);
strcpy(tname[i],tname[i+span]);
strcpy(tname[i+span],tstr);
strcpy(tstr,tdest[i]);
strcpy(tdest[i],tdest[i+span]);
strcpy(tdest[i+span],tstr);
done = 1;
}
}
printf("%s\n",tname[0]);
}
for(i=0;i<n;i++)
if(strcmp(tdest[i],ndest)==0)
printf("%s ",tname[i]);
printf("\n");
}
#include<stdio.h>
main()
{
int
i,j,m,n,gen,count,count1;
char
arr[100][100], arr1[100][100];
printf("Enter
a no:\n");
scanf("%d",
&n);
printf("Enter characters: \n");
for(i=0;i<n;i++)
{
getchar();
for(j=0;j<n;j++)
scanf("%c",
&arr[i][j]);
}
printf("Enter a no:\n");
scanf("%d", &gen);
count=count1=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
arr1[i][j]=arr[i][j];
for(m=0;m<gen;m++)
{
for(i=1;i<=n-2;i++)
{
for(j=1;j<=n-2;j++)
{
count=0;
if( arr[i+1][j]=='#') count ++;
if( arr[i-1][j]=='#') count ++;
if( arr[i][j+1]=='#') count ++;
if( arr[i][j-1]=='#') count ++;
if( arr[i+1][j+1]=='#') count ++;
if( arr[i-1][j-1]=='#') count ++;
if( arr[i+1][j-1]=='#') count ++;
if( arr[i-1][j+1]=='#') count ++;
if(count==3&&arr[i][j]=='.')
arr1[i][j]='#';
else
if((count>3)||(count <2))
arr1[i][j]='.';
else
arr1[i][j]=arr[i][j];
}
}
for(i=1;i<n;i++)
for(j=1;j<n;j++)
arr[i][j]=arr1[i][j];
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%c",arr1[i][j]);
printf("\n");
}
}
********************************************************************************
From:
"R.K.V.S.Raman" <raman@adithya.ncb.ernet.in>
given the listing of preorder and
inorder traversals of a
binary
tree
construct a binary tree and print its post order
the input will be a follows
i/p
n (number of integers (nodes & leaves)
pro1 pro2 pro3 .... pron
ino1 ino2 ino3 .... inon
o/p
poo1 poo2 poo3 .... poon
sample
i/p
7
1 2 4 5 3 6 7
4 2 5 1 6 3 7
o/p
4 5 2 6 7 3 1
P.S : it is
a binary tree and not a binary search tree so no rule of
inserting
holds on the value of the integer. construct it from mgpt
point
of view. you
need not send me the program ,just send me the algo
--------------------------------------------------------------------------------
Prob1(Max.
20 Marks)
Write a
program that takes a positive long integer, generates two
integers
one by
concatenating the digits in the odd places and the other by
concatenating
the digits in the even places[from left to right]. Add
the
two numbers
generated to get a sum total. Add the digits in this total
to
get
the final
sum. Print the sum.
The input to
the program will be as follows.
<the number>
The output should be in the following
format.
<the final sum>
Example
input:
12345678
The two
numbers generated should be:
1357
2468
Sum
total: 1357+2468 = 3825
Answer :
3+8+2+5= 18
Expected
output for the example input:
18
Prob2:(Max.
25 Marks)
Remember
Roman numerals??
I=1
IV=4
V=5
X=10
XI=11
XV=15
L=50
C=100
D=500
M=1000
How about
counting in Roman?? Lets go!
Write a
program that takes as input a positive decimal number and gives
as
output the
number of (X)s, (V)s and (I)s that occur through the series
of
Roman
numerals starting from 1 to that number given as input, and
prints
them in that
order.
The input to
the program will be as follows.
<positive decimal number>
The output should be in the following
format.
< number
of X's>
<number
of V's>
<number
of I's>
Example
input:
12
## So your
task is to find out the number of (I)s,(V)s etc from this
series:
I,II,III,IV,V,VI,VII,VIII,IX,X,XI,XII
## As we
see, the number of Is is 17, the number
of Vs is 5, the
number
of Xs is 4.
Expected
output to the example input:
4
5
17
Prob3:(Max.
Marks 30)
Write a
program that finds the largest contiguous sum of an array of
numbers
given as input to your program. The program should first accept
the
number of
elements in the array as the input. Then it should accept the
elements of
the array. The output should be the largest contiguous
sum{for
further
clarification see example output}
The input to
the program will be as follows.(Each on a separate line).
<number of elements in the
array>
<element 0>
<element 1>
.
.
<element n-1>
The output should be in the following
format.(Each on separate
line).
<The largest contiguous sum>
Example
input:
8
100
-200
-300
40
400
-90
999
234
##So here
the number of elements in the array is 8. The elements are
the
next 8
numbers given as input. So here it is clear that the largest
##contiguous
sum is the sum of the elements 40,400,-90,999,234
Expected
output to example input:
1583
Prob4(Max.
Marks 40):
Given the
order of a square matrix and the elements as inputs, write a
program that
calculates the largest sum possible along a row, a column
or
a
diagonal.
The output is the largest sum out of all
these possible
combinations.
The first input to your program will be the order of the
square
matrix.
Then the
elements will be fed in the row major order. i.e. all the
columns
of a row are
to be completely filled before proceeding on to the
next row.
Caveat: Mind
you, the diagonals can be not only from Right hand top to
Left Hand
Bottom and from Left Hand top to Right hand bottom but also
along the
subsidiary diagonals.
e.g Consider
the matrix
1
2 -3
-2
4 9
-5
9 8
column/row sums are easily understood but for the
consideration of the
diagonal
sums ..
-5; -2 + 9;
1+4+8; 2+9; -3;
1; 2 + (-2); -3 + 4+(-5); 9+9;
8;
The input to
the program will be as follows.(Each on a separate line).
<order of the square matrix>
<element [0][0]>
<element [0][1]>
.
.
<element [0][n-1]>
<element [1][0]>
<element [1][1]>
.
.
<element [1][n-1]
.
.
<element [n-1][0]>
<element [n-1][1]>
.
.
<element [n-1][n-1]
The output should be in the following
format.(Each on separate
line).
<the largest sum>
Sample input
for the above matrix problem:
3
1
2
3
-2
4
9
-5
9
8
##Here
calculate all the possible sums along rows e.g. 1+2+3, etc ,
along
columns e.g.
(-3)+9+8 etc, and along diagonals 9+9 etc. The output
##should be
the maximum of all these.
Expected
output to the example input:
18
Prob5(Max.
Marks 45)
Write a
program to list all the permutations possible for a given input
string. The
characters fed to the program will be from the sets a-z and
A-Z
only. Note
that 'a' and 'A' are different(case-sensitive).
The input to
the program will be as follows.
<a string of characters>
The output
should be in the following format.
<all
possible permetuations each on a separate line>
Example:
<sample
input>
abca
##Give all
the permutations of this string as the output
<expected
output>
abca
abac
acba
acab
aabc
aacb
baca
baac
bcaa
caba
caab
cbaa
Prob6(Max.
Marks 40)
The input to
your program will be a string of letters which symbolize
the
nodes of a
binary tree[refer Notes]. The order of appearance of the
letters is
the pre-order traversal[refer Notes] of the tree. A 0(zero)
in
the string
specifies that the relevant child is null. Your
program
should then accept two letters as input and give as output the
path from
the first to the second.
The input to
the program will be as follows.
<string representing the tree >
<string of exactly two letters
representing the two nodes>
The output
should be in the following format.
<String representing the path from
first node to second node>
The input to
your program will be of the form:
ABDF000E00C0G00
DG
the sample
tree for this example string is as below..
A
/ \
B C
/ \ / \
D E 0 G
/
\ / \ / \
F
0 0 0 0 0
/ \
0
0
the output
for this problem should be:
DBACG
Notes:
1) Tree: A
tree is a data structure in which there is one root
node(e.g. A
in the above
example) and from each node sprout one or more
branches(e.g.
AB, AC) leading to one or more nodes(B & C).
All the
nodes in the tree except the root node can be null(e.g. F has
two
null
children). A null node cannot have
children.
2) Binary
tree : A tree in which each node has only two children.
3) Pre-order
Traversal : Here the tree is traversed such that the left
child of a
node and its progeny is completely traversed before
traversing
the children
of its right node.
e.g. After
specifying the children of A i.e. B & C we go on to specify
the
children of
B(the left child) before we specify the children of C(right
node).
Prob7(Max.
Marks 35)
Your program
should accept an input character string
of any number of
words. The
program should generate an encoded character strings
according to
the following encoding scheme.
Generate the encoded bit stream in the
form of a character array as
follows.
example:
given string
"ABC"
i) To encode, two bits are used as a
count value to represent
contiguous
similar bits in the given code i.e
00 bits for single bit
01 bits for two contiguous similar
bits
10 bits for three contiguous similar
bits
11 bits for four contiguous similiar
bits
For the
above example string "ABC"
A B C
Input
code 01000001 01000010 01000011
Output
code
000001110000001 For A
000001110001000 For B
000001110011 For C
Catenate the
above encoded bit sequence and group it by 8 bit as a
character
and it must be stored in a character array.
Prob8(Max.
Marks 65)
Suppose that
we are programming in a parallel processing environment in
which
instructions can be executed concurrently. Consider for example,
the
statements
p = x + y
q = x * y
r = q - p
Two
statements may be executed concurrently, if the order of their
serial
execution is
irrelevant. For instance, statements 1 and 2 above can be
executed in
either order - 1 first and then 2, or 2 first and then 1 -
with the
same result. However, we must execute statement 1 before
statement 3
because
statement 3 uses the value p
computed by statement 1, or to
put
it another
way, a variable (p) on the right side of the statement 3
appears
on the left
statement 1.
Conditions
known as Bernstein's conditions, have been formulated that
can
be used to
determine whether two statements can be
executed
concurrently.
Before stating these conditions, we must define two sets
of
variables for each statement. A statement's write set
consist of the
variables whose values are changed (written) when the statement
executes
and a
statement's read set consists of
the variables whose values
are
unchanged
(read) when the statement executes. For a simple assignment
statement, the write set is the variable on the left side of the
statement,
and the read
set is the set of variables that appear on the right side
of
the statement. The write set of statement 1
contains the variable p
while
that
of statement
3 contains the variable r. Similarly, the read set of the
statement 1
consists of the variables x and y while
that of statement
3
contains
the
variable p and q.
The intersection of two sets consists of the elements that
belong to
both
the sets.
For example, the intersection of the
read sets of the
statements 1
and 2
contains the variables x and y. While
the intersection of the
read
sets of
statements 1 and 3 is empty.
We can now
give Bernstein's conditions for
concurrent execution. Two
statements S1 and S2
can be executed concurrently if
they satisfy
the
following
conditions :
* The
intersections of S1's read set and S2's write set is empty.
* The
intersections of S2's read set and S1's write set is empty.
* The
intersections of S1's write set and S2's write set is empty.
Example :
For the previous example, the sets are
:
Read set
of statement 1: {x, y}
Write set of
statement 1: {p}
Read set
of statement 2: {x, y}
Write set of
statement 2: {q}
Read set
of statement 3: {q, p}
Write set of
statement 3: {r}
Intersection
of 1's read set and 2's write set : {}
Intersection
of 2's read set and 1's write set : {}
Intersection
of 1's write set and 2's write set : {}
Intersection
of 1's read set and 3's write set : {}
Intersection
of 3's read set and 1's write set : {p}
(Failure)
Intersection
of 1's write set and 3's write set : {}
Intersection
of 2's read set and 3's write set : {}
Intersection
of 3's read set and 2's write set : {q}
(Failure)
Intersection
of 3's write set and 2's write set : {}
Therefore,
we see that statements 1 and 2 can be
executed
concurrently,
but the
statements 1 and 3 and statements 2 and 3 cannot be executed
concurrently.
Write a
program that prompts the user to enter
3 assignment statements
that
are read as character strings. Assume
that the statements are
correct C
statements. The program should then
build the read and
write
sets for each statement and uses Bernstein's conditions
to test
whether
the
statements can be executed
concurrently.
The program
prints the following (see example given below):
The
intersection set specified by Bernstein's conditions.
A message as
to whether the statements can be
executed concurrently
(
yes-.can be
executed concurrently. no - cannot be
executed
concurrently)
Example
input:
<first
equation >
<second
equation>
<third
equation>
Note:
i) All the mathematical operators have their usual meanings.
ii) If the intersection set is null you
must output the string
"empty"(without
quotes)
Output
format:
<Intersection
of 1's read set and 2's write set as a
string>
<Intersection
of 2's read set and 1's write set as a
string>
<Intersection
of 1's write set and 2's write set as a
string>
<Intersection
of 1's read set and 3's write set as a
string>
<Intersection
of 3's read set and 1's write set as a
string>
<Intersection
of 1's write set and 3's write set as a
string>
<Intersection
of 2's read set and 3's write set as a
string>
<Intersection
of 3's read set and 2's write set as a
string>
<Intersection
of 2's write set and 3's write set as a
string>
<Output
message in yes/no stating whether 1 and 2 can be executed
concurrently>
<Output
message in yes/no stating whether 1 and 3 can be executed
concurrently>
<Output
message in yes/no stating whether 2 and 3 can be executed
concurrently>
--------------------------------------------------------------------------------
PROBLEM 1:
n
non-negative integers and (n-1) arithmetic operators from the set
(+,-,*) are
given on a single line as follows:
<num1><num2>...<numn><op1><op2>...<opn-1>
Write a
program to evaluate the expression
formed left to right as:
<mun1><op1><mun2><op2>...<mun(n-1)><op(n-1)><mun(n)>
In the above
mun1 is obtained by reversing the digits of num1,
mun2 by
reversing the digits of num2 and so on.
Thus 241 56 * has to be evaluated as 142 * 65.
Input:-
The input
will consist of 2 lines, each terminated by EOLN.
Line 1: n,
the number of integers
Line 2: a
sequence of n integers( with reversed digits)followed by
(n-1)
arithmetic operators.
There is
exactly one space separating any two items on the second line
(integers or
operators), and there are no leading spaces either.
The range of
values for 'n' is from 2 to 10.
The
operators used are '+' meaning addition.
'-' meaning subtraction.
'*' meaning multiplication.
Output:-
Your output
must be an integer without any leading zeroes and with a
sign only if
the result is negative.The output must be terminated
by an EOLN.
Examples:-
Input:-
3
12 03 123 + +
Output:-
372
{note: 21 + 30 + 321 = 372 }
Input:-
4
54 0 50 94 * + -
Output:-
-44
{note: 45 * 0 = 0; 0 + 05 =5; 5 - 49 = -44 }
Input:
3
21 3 5 + *
Output:
75
{ note: 12 + 3 = 15; 15 * 5 = 75 }
PROBLEM 2:
Given a line
of variable declarations like in Pascal programs, you
have to
identify the type of a variable. The input to your program
will consist
of Pascal language like variable declaration, terminated
by EOLN.
e.g.
int1,int2,int3,int4 : integer;
The line
following such an input will contain a variable name.
e.g. int4
Your program
should identify the type of the variable, and print the
variable
name followed by its type terminated by EOLN.
For example,
in the above case , the output is
int4 integer
integer if the type of the variable is integer,
real if the type of the variable is real,
char if the type of the variable is char,
boolean if the type of the variable is boolean,
undefined if the variable is not any of the above
type or is not
declared.
Note that
all the strings that you output must be in lower-case as
shown above.
There can be one or more spaces between the variable name
and the type
name in your output.
A variable
will be at the most 8 (eight) characters long, and the
maximum
number of variables declared in such an input is limited to
50.
Your program
should not make any assumptions regarding the number of
spaces
separating items on the line. There may be 0 or more leading
blanks,
trailing blanks and 0 or more spaces before or after any
variable
name, comma, colon or type name. The declarations of the
variables
will be given in the lower-case only.
Examples
--------
Input:
abc, boy, int1 : boolean;
boy
Output:
boy
boolean
Input:-
cat,
myreal,bigreal: real;
dog
Output:-
dog
undefined
Input:-
x1, y2,
none : text ;
y2
Output:-
y2
undefined
PROBLEM 3:
A pack of 52
playing cards has four suites ( Hearts, Spades, Clubs
and Diamonds
) with 13 cards in each suite. A card is represented by
a letter
{h,s,c or d} denoting each of the four suites(Hearts, Spades,
Clubs and
Diamonds) respectively. The letter is immediately followed
by a number
from 1 to 13 denoting the particular card in that suite.
Thus, the
Four of Hearts is represented by h4, Ten of Spades by s10.
and so on.
A
"4-sequence" is a set of four cards of the same suite in consecutive
order, e.g.
{c10,c11,c12,c13}. Wrap-around sequences like
{d11,d12,d13,d1},
{d13,d1,d2,d3} etc. are not valid. A "3-trail" is a
set of three
cards of the same number but belonging to different
suites,
e.g.
{c6,h6,s6}, {d1,c1,s1}, etc.
Given a set
of 13 distinct cards you have to determine if the given
set contains
a 4-sequence or a 3-trail. Assume that the given set will
contain a
single 4-sequence or a single 3-trail or neither. That is,
it
will not
contain both.
The input
consists of the 13 cards on one line, each card represented
as explained
above. Each "card" is separated from the other by a
single
space. There
are no leading spaces before the first card and no
trailing
spaces after
the last card.
Output
Specification:
----------------------
If the input
set contains a 4-sequence, output the cards that form the
4-sequence
in increasing order of the card numbers separated by one or
more spaces
terminated by an EOLN.
If the input
set contains a 3-trail, output the cards that form the
3-trail in
the order of {h,s,c,d} separated by one or more spaces
terminated
by an EOLN.
If the input
set contains neither of the two, then output "none" on a
line. The
output must be in lower-case letters only.
Sample Input
And Output:
-------------------------
Input:
h1 d7 s2 d8
d3 h13 d12 h11 d5 d6 h2 s1 h10
Output:
d5 d6 d7 d8
Input:
h1 h2 h10
h11 h13 s1 s2 d1 d3 d5 d6 d7 d12
Output:
h1 s1 d1
Input:
h12 d7 s2 c1
d1 h13 d2 h11 d5 d6 h9 s11 c2
Output:
s2 c2 d2
Input:
s1 h2 s3 h4
s5 h6 s7 h8 s9 h10 c11 d12 c13
Output:
none
PROBLEM 4:
Write a
program for maintaining the appointments of patients in
different
departments
of a hospital. Assume that each patient has a unique
integer-
identifier(id)
and so also every department. A patient can seek
appointments
to one or
more departments and is also allowed to cancel an appointment
from
any
department. The program should be able to list out at any time the
number
of patients
who have valid appointments with a given department or the
number
of
departments with which a given patient has appointments.
INPUT
------
The input to
your program is a sequence of commands each command on a
separate
line. There
are four commands as follows:
1) S
patient-id department-id
Example
S 3013 1023
(Patient
with id 3013 is seeking appointment from department with id
1023)
2) C
patient-id department-id
Example:
C 10293 0112
(Patient
with id 10293 is cancelling his appointment from department
with id
0112)
3) D
department-id
Example
D 23
Output
-------
Print the
total number of patients who have valid appointments with
the
department
having the id 23. Cancelled appointments should not be
counted.
Terminate
your output by an EOLN. If there are no appointments for the
department
then your program must output 0 followed by an EOLN. The
output
must not
have any sign and there should be no leading zeroes in the
output.
4) P
patient-id
Example:
P 101
Print the
total number of departments with which the patient with id
101 has
valid
appointments. Cancelled appointments should not be counted.
Terminate
your output
by an EOLN. If the patient does not have any valid
appointment
with any
department then your program must output 0 followed by an
EOLN.
The output
must not have any sign and there should be no leading zeroes
in
the output.
Your program
must be capable of handling any number of departments and
any
number of
patients. You may assume that there are no receding blanks
before
the command
character and that erroneous input will not be given to
your
program.
Each command line is terminated by EOLN and the input is
terminated
by an EOF.
EXAMPLES
---------
S 100 200
S 100 201
S 100 203
S 101 203
S 101 240
C 100 200
S 101 207
C 101 240
P 100
D 203
D 200
S 100 200
S 101 231
D 200
S 102 245
D 203
P 104
PROBLEM 5:
Write a
program to merge two linked lists.
INPUT
------
The input to
the program will be two lines, each terminated by EOLN.
Line 1 :
sequence of integers for the first list
Line 2 :
sequence of integers for the second list
The integers
appearing on each of the lines may not be in ascending
order.
So you must
arrange the integers on a line as a linked list in
non-decreasing
order. Once
a line of input is read, the integers on that line must be
output
as an
ordered list of numbers on the same line terminated by an EOLN.
After
obtaining two ordered linked lists, you must merge them such that
there
are no
duplicate elements in the resultant list and the new list has
elements
in a
non-decreasing order.
The elements
in the new list must be printed on the same line
terminated
by
EOLN.
The elements
in the input list will be integers and
duplicate integers
will
not be
provided on a line of input.
OUTPUT
------
The output
of your program must consist of three lines, each terminated
by EOLN.
Line 1 :
elements of the first list in ascending order.
Line 2 :
elements of the second list in ascending order.
Line 3 :
elements of the merged list in ascending order.
In case the
output list is empty, output an EOLN.
EXAMPLES
--------
Input :
20 10 5 13 30
5 2 10 9
Output :
5 10 13 20 30
2 5 9 10
2 5 9 10 13 20 30
PLEASE NOTE
------------
The words
'Input:' and 'Output:' are not a part of the inputs and
outputs.
Do not
attempt to input or output these words using your program.
Assume
that the
input values are all correct. Do not do any input validation
and
do not
output anything other than what is defined in the output
specification
otherwise
the grader will fail to check your program properly.
PROBLEM 6:
Write a
program to maintain the current stock of machine parts of a
workshop. A
part is
identified by a 10 character part-id. The production and
consumption
of
parts take
place within the workshop. You may assume that over
consumption
is
allowed(
that is, the stock can go negative also).
INPUT &
OUTPUT
--------------
The input to
your program is a sequence of action commands each command
on a
separate
line.
The four
commands are as follows:
1) Production of a part( command is P )
P SCR1110810 1500
This implies
that 1500 units of the part with id SCR1110810 have been
produced.
( Note that
a part entry has to be created if one with this part-id
does not
already
exist).
2) Consumption of a part( command is C )
C NPN1012136 2000
2000 units
of the part with part-id NPN1012136 have been consumed.
( Note that
a part entry has to be created if one with this part-id
does not
already
exist).
3) To output
the number of parts whose stock is less than the given
number
( command is
L )
L 100
This
requires your program to output the number of parts with stock
less than
100. Your
output should be an integer ( greater than or equal to zero )
without any
sign or leading zeroes.
Terminate
your output by an EOLN.
4) To output
the number of times the stock of the given part has gone
from >=0 to negative.
( command is F )
F NPN1012136
This
requires your program to output the number of times the stock of
the part
with part-id
NPN1012136 has gone from >=0 to negative. Your output
should be
an integer (
greater than or equal to zero ) without any sign or any
leading
zeroes.
Terminate your output by an EOLN.
If the stock
has never become negative, you must output a 0 terminated
by an
EOLN.
In the above
assume that there is exactly 1 blank between the command
(P, C or F )
and the part-id. Your program must be capable of handling
any number
of parts. Assume that there are no leading spaces before
the command
character.
PROBLEM 7:
Write a
program that will generate a specified number of fibonacci
numbers.
The first
two numbers in the fibonacci number series are always 1. Each
succeeding number in the series is such that its value
is equal to the
sum
of its
preceding two numbers.
Input:-
The program
should accept an integer indicating the number of elements
to be
generated in the series. The input number will be a natural
number.
Output:-
The output
of the program should contain the required number of
elements
of the
fibonacci series. The numbers in the series must be separated
by a space.
Examples:-
1. Input:
5
Output:-
1 1 2 3 5
2. Input:
7
Output:-
1 1 2 3 5 8 13
3. Input:
2
Output:-
1 1
PROBLEM 8:
A set can be
implemented using arrays. Write a program to implement
the
basic set
operations on sets of the following
specifications
The set may
hold maximum of 100 elements. The elements of the sets
are
integers.
The
operations to be performed on these sets are
1.
Intersection denoted by the letter I
intersection of sets A and B yields a
set whose elements
are both in A and B
2.
Difference denoted by the letter D
A difference B yields a set whose
elements are the
elements of A not in B
The elements
in a set will be given as a sequence of integers on a
line
EOLN will
mark the end of the sequence.
The input
consists of 3 lines
line 1:
elements of set A
line 2:
elements of set B
line 3: set
operator( I or D )
The output
should consist of the result ofoperation
A
<operator> B
The elements
of the resultant set must be output on
a line
separated by
blanks and without any leading zeroes. The line must be
terminated
by an EOLN.
Note : The
elements of the input sets will be given in non-decreasing
order.
The elements
in the output must also be in non-decreasing order.
Sample Input
and Output:
Input:
0 23 456 765 1000 5678 7654 8001 10000
23 234 543
765 1235 10000 12347
I
Output:
23
765 10000
Input:
-10 0 15 25 125
-15 -10 0 20
D
Output:
15 25 125
PROBLEM 9:
Given a set
of vertical and a set of horizontal line segments, in the
format
specified below, write a Pascal program to find the total
number of
crossings amongst the line segments.
( See figure
below ).
|
|
|
|
-----|----------|---------------
|
|
|
|
|
-----|---------------------
|
|
|
|
|
-----|----------------
|
Input :-
The input to
your program will be as follows:
line 1: an
integer m {number of horizontal line
segments}
line 2: an
integer n {number of vertical line
segments}
line 3: x11
x12 y1 x21 x22 y2 ...xm1 xm2 ym
{3m integers specifying the horizontal
lines}
line 4: y11
y12 x1 y21 y22 x2 ... yn1 yn2 xn
{3n integers specifying the vertical lines}
In line3,
three integers define a line segment
Example:-
x11 x12 and y1 define a horizontal line segment with
endpoint co-ordinates (x11, y1) and (x12, y1).
Similarly in
line 4, y11 y12 and x1 define a vertical line segment
with endpoint co-ordinates (x1, y11) and
(x1, y12).
Assume that
the maximum number of horizontal line segments is 20.
Similarly
the maximum number of vertical line segments is 20.
Note: If two line segments merely touch each
other and do not
cross then it is not a valid crossing.
For example the following are not valid
crossings.
|
--------+----------- |
| |-----------
| | |
| |
| | _____________
| | |
| +------------- |
| |
|
Examples :-
Input:
3
2
1 10 3 30 2
5 4 20 6
10 1 5 25 30
100
Output:
3
Input:
1
1
10 20 10
20 15 15
Output:
0
PROBLEM 10:
N numbers,
starting from 1, are placed around a circular table.
Starting
from 1 every Kth number around the table is removed. This
process is
continued until all the numbers are removed from the table.
For example
If N = 10 and K = 3 the order in which numbers removed are
1 4 7 10 5 9
6 3 8 2
Write a
program which prints out the sequence of numbers in the same
order as
removed for any given N and K.
Input:-
Two numbers
N and K given on a single line terminated by an EOLN.
Example:-
Input:-
10
3
Output:-
1 4 7 10 5 9 6 3 8 2
Hint: Use
circular linked list.
PROBLEM 11:
Write a
Pascal program to build a number triangle. Given 4 integers,
the number
triangle is built as follows:
A11
A12 A13 A14
Root members of the number triangle of
height 4
+
+ +
A21
A22 A23 A21 = A11+A12, A22 = A12+A13, A23 =
A13+A14
+ +
A31 A32 A31 = A21+A22, A32 = A22+A23
+
A41 A41 = A31+A32
Given a
number, search for the number from root and starting from
root,
print in
increasing order all the levels at which the number is found.
If the
number is not found in the triangle, print 0.
Level of the
root is 1.
The three
lines of input to your program are
1) The first
line will be an integer h giving the height of the
triangle.
2) The
second line will have h integers which are the root members
of
the triangle.
3) The last
line contains the number to be searched.
The output
of your program will be the levels at which the number
to be
searched occurs in the triangle, one per line. Output the
level(s)
without any leading zeroes. If the number does not occur,
print 0.
Terminate your output by an EOLN. Assume that the maximum
height of
the triangle is 10. In case the number occurs more than once
at
a level,
that level number should be output only once.
Input:-
4
1 2 3 4
8
Output:-
3
Triangle is
as follows:
1 2
3 4 Level 1
3
5 7 Level 2
8
12 Level 3 ( 8 is at this
level )
20 Level 4
Input:-
5
4 2 1 1 1
4
Output:-
1
3
PROBLEM 12:
Write a
Pascal program to search a line of text for a pattern. The
pattern is
of the form X+Y*Z where X, Y and Z are
distinct
characters.
The + and * are interpreted as follows,
X*Y Zero or more occurrence(s) of X followed by
Y
X+Y 1 or more occurrence(s) of X followed by Y.
Thus k+j
kj, kkj, kkkj, kkkkj etc
k*j
j, kj, kkj, kkkj etc
The input to
your program will be two lines of text each terminated
by an EOLN.
The first line is a line of text of maximum 80 characters.
The second
line contains the pattern to be searched in the first line.
The output
of your program should be the position in the first line
at which the
matching pattern occurs ( ie. the matching pattern begins
at that
position - the first character in the line has position 1).
If the pattern
is not found, output a zero. The output should not
contain any
leading zeroes. Terminate your output by an EOLN.
In case the
entire pattern is found at more than one position, output
the last
position. The position output should be such that we do not
get a
matching pattern in the immediately preceding position.
Input:-
this is not a major issue.
s+u*e
Output:-
22
The pattern
is always of the form X+Y*Z.
u is at
position 24. "sue" matches the pattern.
But
"ssue" also matches. So the position is 22
and not 23.
Input:-
astro astonish assume atomic attribute
static
a+s*t
Output:-
42
Here , there
are a lot of matches.
But the
"at" in "static" is the last one to match.
PROBLEM 13:
A
"saddle point" of a matrix A is defined as the element A[i,j] such
that A[i,j]
is the smallest element in row "i" of the matrix and
the largest
element in column "j" of the matrix.
Given a 9x9
matrix whose elements are non-negative integers, you have
to output
its saddle point if it exists or -1 (minus one) if the
saddle point
does not exist. The saddle point if it exists, is
always
unique.
Assume that
the rows and the columns of the matrix are numbered
from 1 to 9.
The input consists of the 9x9 matrix ie. there are 9 lines
with 9
integers on each line.
If the given
matrix has a saddle point, you have to output three
integers on
a line terminated by EOLN. The three integers, in order,
are the
saddle point, the row index and the column index of the
saddle
point.
Integer
numbers on the same line must be output separated by blanks
and without
any leading zeroes. If the given matrix does not have a
saddle
point, you must output -1 on a line terminated by EOLN.
Input:-
2 3
4 5 6 7 8 9 10
4 5
6 7 8 9 10
11 12
8 9
10 11 12 13 14 15
16
2 3
4 5 6 7 8
9 10
3 5
6 7 8 9 10
11 12
2 3
4 5 6 7 8
9 10
7 5
6 7 8 9 10
11 12
2 3
4 5 6 7 8
9 10
6 3
4 5 6 7 8
9 10
Output:-
8 3 1
In the above
matrix, the integer 8 at position [3,1] is the saddle
point, as
per the definition of the saddle point given above.
PROBLEM 14:
Given an
input text which resembles a Pascal program segment, write
a program to
output the maximum degree of nesting of the
"begin"
-- "end" keywords.
The first
line of input consists of an integer denoting the number
of lines of
text to follow. The text will contain a Pascal program
segment
which will have an arbitrary degree of nesting of begin-end
statements.
You may
assume that every "begin" will have a corresponding "end"
and that the
keywords "begin" and "end" will always be in lower
case
letters.
The output
of your program should be an integer denoting the maximum
degree of
begin-end nesting found in the text. Terminate your output
by an EOLN.
The ouput integer should not have any leading zeroes.
Input:-
var i, j : integer;
begin
while (i<10) do begin
if j=10 then begin
j := succ(j);
i := pred(k)
end;
if true then begin flag
:= false end
end;
if j=7 then begin
j := j+1;
i := i+j
end
end
Output:-
3
PROBLEM 15:
Given a
piece of text, find the frequency distribution of word lengths
(ie. how
many words have one letter, how many have two letters,...).
Find the
word-length having the highest frequency and print that
word-length
followed by its occurrence count. In
case two or more
word-
lengths have
the highest frequency, print the largest word-length and
its
occurrence
count.
A
"word" is made up of alphanumeric characters and delimited by white-
spaces or
period( ie. full stop ).
The first
line of input specifies the number of lines of text to
follow
( say N ).
Each word in the piece of text can be assumed to be smaller
than
15
characters. Your output will be two integers as above, separated by
one or
more spaces
with no leading zeroes and terminated by an EOLN.
Example:-
Input:
2
This is
a sample text. The text has sentences and sentences have
words.
Some words
are small. Some words are big.
Output:
4 6
PROBLEM 16:
In this
problem you have to find out a path between two points in a
maze.
The maze is
represented here as a 7x7 matrix containing the elements
0, 1, 2 and
3. The '0's are part of the path from the starting point
represented
by a '2' to the ending point represented by a '3'. The
'1's
represent
blocks in the maze. There is a unique path from '2' to '3'
and it
always
exists and there are no dead-ends and no branches in the path.
The
elements '2'
and '3' occur only once in the matrix. Assume that the
rows and the
columns of
the matrix are numbered from 1 to 7.
The input
consists of 7 lines, each line containing 7 integers, thus
forming
the 7x7
matrix.
The output
should consist of a sequence of lines, each line containing
a pair
of integers
which are the row and column indices of the elements in the
path
from the
starting point '2' to the ending point '3' in the order of
the
traversal,
including the indices for the '2' and the '3'. Integers on
the same
line must be
output separated by blanks and without any leading
zeroes.
Sample Input
& Output:
Input:
1 0 1 1 1 1
2
0 1 0 1 1 0
1
0 1 1 0 0 1
1
1 0 1 1 1 1
1
1 1 0 0 1 1
1
1 1 1 1 0 1
1
1 1 1 1 1 0
3
Output:
1 7
2 6
3 5
3 4
2 3
1 2
2 1
3 1
4 2
5 3
5 4
6 5
7 6
7 7
Explanation:
The indices
for the starting point '2' are (1,7) and the ending point
are
(7,7). The
rest are the indices of the '0's that form the path from
the
'2' to the
'3' in the order of traversal ie. after the '2' at (1,7),
the
next element
in the path is the '0' at (2,6), followed by the '0' at
(3,5),
followed by the '0' at (3,4) and so on till the '3' at (7,7).
PROBLEM 17:
Consider a
shop 'Linked List Electronics ' which allows its customers
to
purchase
items on credit. (The payment can be made later.) They are
planning
to automate their record-keeping for such
customers. They have less
than 100
customers.They
want a progrm as per the following desciption
Whenever a
customer purchases an item the operator will enter a line of
input
purchase name item_name
-----------------------
You may
assume that only the last name of the customer is given as one
word.
Also the
item name can be assumed to be a single word.
Whenever the
customer pays up another line of the form
payment-name item-name
----------------------
is entered.
For multiple
payments and purchases;multiple lines will be entered with
one
entry per
line .
The end of
input will be indicated by a line containing just the word
'stop'.
After that a
seperate line of input will specify a customer name.The
program
should
output the items purchased by the customer which are not yet
paid for.
The output
should be alphabetically ordered and all items in one line.
If their are
no pending items ,output "nothing".Assume maximum length
of a word
to be 50
characters.
SAMPLE
INPUT:
purchase wilson vcr
purchase wilson radio
purchase graey tv
payment wilson radio
purchase wilson tv
stop
wilson
SAMPLE
OUTPUT:
tv vcr
NOTE : YOU
MUST USE LINKED LISTS.
PROBLEM 18:
An anagram
of the word x is the word formed by the characters of the
word x
with each
letter being used only those many times as in word x.For
example
post,opst,tops
are some anagrams of the word 'stop'.
Input to the
program will be the word (less than 8 char.s) terminated
by eoln.
Output of
the program should be the list of all anagrams of the input
word;
alphabetically
sorted with one word per line.The upper case letters are
lower
than the
lower case letters.Terminate the last word also with eoln.
SAMPLE
INPUT:
tea
OUTPUT: aet
ate
eat
eta
tae
tea
PROBLEM 19:
Write a program to accept a finite set of
alphabets and all its
nonempty
subsets in
lexicographic order.The set of alphabetic symbols will have
at
most eight
chars.Note that the no. of such non-empty subsets is equal
to
(2^n -
1),where n is the no. of elements in the given set.
For
example;given a set {a,b,c},the list of its non-empty subsets is
{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}.
Input Format
:The input will consist of two lines.
First line
indicating the no. of elements in the input set say n .
Second will
have a string of n non-blank alphabetical characters
forming a
set.
Note that
the characters themselves will be given in alphabetical
order.
Output
Format:The output must list each of the required subsets on a
seperate
line (ie.the
no. of lines in the output must be equal to the no. of
non-empty
subsets of
the given set.) The characters in each line ,also the
subsets
themselves
should be in alphabetical order.
SAMPLE
INPUT: 3
abc
OUTPUT: a
ab
abc
ac
b
bc
c
PROBLEM 20:
Consider a teller counter in a bank.There are
two clerks handling the
job.
Each of them can handle any transaction at
the counter. Mr.Fast takes
5 minutes per transaction irrespective of the
type of transaction.
Mr.Slow needs 8 minutes per transaction. The
bank is planning to
improve
customer satisfaction and wants to know the
varios statistical
parameters
of its performance. The follwing is
specification of one of the
programs.
Implement it using the Que data stucture.
The input to the program consists of a
sequence of positive integers
terminated by the number -1. The input
numbers indicate the arrival
pattern
of customers.
Assume that the start of the program is at
time 0.The first no.
indicates
how many minutes from the arrival of the
first customer the second
customer
arrives , and so on.
You have to
simulate the service to the customers at the teller
counter.
Assume that
the customer will go to the earliest available counter for
his work.
However ;if both counters are free ; then preference is given
to
Mr.Fast. The
order of service is strictly in the order of arrival.
The input is
a table of number of people waiting for service at every
minute.
You need to
print this for the first 21 minutes from 0 to 20
(inclusive).
For each
minute one line of input is required containing the time and
the no. of
people waiting for service.The two items are seperated by a
single
space. For
the same purpose,you can assume that a customer arriving at
time t
is in the
que at time t,if no counter is free at that time.
SAMPLE
INPUT: OUTPUT:
0 0 0
0 1 0
1 2 1
2 3 1
2 4 1
8 5 0
-1 6 0
| |
| |
16 0
--------------------------------------------------------------------------------
From
d0013014@ncb.ernet.in Mon Jul 17 14:07:30 2000
Date: Mon,
17 Jul 2000 14:06:40 +0630 (EDT)
From:
Jaykirit-Shukla <d0013014@ncb.ernet.in>
To:
Madhavi-N <c9913006@adithya.ncb.ernet.in>
please solve
the problems and provide me this solutons.
return
favours you know.
PROBLEM 1:
n
non-negative integers and (n-1) arithmetic operators from the set
(+,-,*) are
given on a single line as follows:
<num1><num2>...<numn><op1><op2>...<opn-1>
Write a
program to evaluate the expression
formed left to right as:
<mun1><op1><mun2><op2>...<mun(n-1)><op(n-1)><mun(n)>
In the above
mun1 is obtained by reversing the digits of num1,
mun2 by
reversing the digits of num2 and so on.
Thus 241 56 * has to be evaluated as 142 * 65.
Input:-
The input
will consist of 2 lines, each terminated by EOLN.
Line 1: n,
the number of integers
Line 2: a
sequence of n integers( with reversed digits)followed by
(n-1)
arithmetic operators.
There is
exactly one space separating any two items on the second line
(integers or
operators), and there are no leading spaces either.
The range of
values for 'n' is from 2 to 10.
The
operators used are '+' meaning addition.
'-' meaning subtraction.
'*' meaning multiplication.
Output:-
Your output
must be an integer without any leading zeroes and with a
sign only if
the result is negative.The output must be terminated
by an EOLN.
Examples:-
Input:-
3
12 03 123 + +
Output:-
372
{note: 21 + 30 + 321 = 372 }
Input:-
4
54 0 50 94 * + -
Output:-
-44
{note: 45 * 0 = 0; 0 + 05 =5; 5 - 49 = -44 }
Input:
3
21 3 5 + *
Output:
75
{ note: 12 + 3 = 15; 15 * 5 = 75 }
PROBLEM 2:
Given a line
of variable declarations like in Pascal programs, you
have to
identify the type of a variable. The input to your program
will consist
of Pascal language like variable declaration, terminated
by EOLN.
e.g.
int1,int2,int3,int4 : integer;
The line
following such an input will contain a variable name.
e.g. int4
Your program
should identify the type of the variable, and print the
variable
name followed by its type terminated by EOLN.
For example,
in the above case , the output is
int4 integer
integer if the type of the variable is integer,
real if the type of the variable is real,
char if the type of the variable is char,
boolean if the type of the variable is boolean,
undefined if the variable is not any of the above
type or is not
declared.
Note that
all the strings that you output must be in lower-case as
shown above.
There can be one or more spaces between the variable name
and the type
name in your output.
A variable
will be at the most 8 (eight) characters long, and the
maximum
number of variables declared in such an input is limited to 50.
Your program
should not make any assumptions regarding the number of
spaces
separating items on the line. There may be 0 or more leading
blanks,
trailing blanks and 0 or more spaces before or after any
variable
name, comma, colon or type name. The declarations of the
variables
will be given in the lower-case only.
Examples
--------
Input:
abc, boy, int1 : boolean;
boy
Output:
boy
boolean
Input:-
cat,
myreal,bigreal: real;
dog
Output:-
dog
undefined
Input:-
x1, y2,
none : text ;
y2
Output:-
y2
undefined
PROBLEM 3:
A pack of 52
playing cards has four suites ( Hearts, Spades, Clubs
and Diamonds
) with 13 cards in each suite. A card is represented by
a letter
{h,s,c or d} denoting each of the four suites(Hearts, Spades,
Clubs and Diamonds)
respectively. The letter is immediately followed
by a number
from 1 to 13 denoting the particular card in that suite.
Thus, the
Four of Hearts is represented by h4, Ten of Spades by s10.
and so on.
A
"4-sequence" is a set of four cards of the same suite in consecutive
order, e.g.
{c10,c11,c12,c13}. Wrap-around sequences like
{d11,d12,d13,d1},
{d13,d1,d2,d3} etc. are not valid. A "3-trail" is a
set of three
cards of the same number but belonging to different
suites,
e.g.
{c6,h6,s6}, {d1,c1,s1}, etc.
Given a set
of 13 distinct cards you have to determine if the given
set contains
a 4-sequence or a 3-trail. Assume that the given set will
contain a
single 4-sequence or a single 3-trail or neither. That is, it
will not
contain both.
The input
consists of the 13 cards on one line, each card represented
as explained
above. Each "card" is separated from the other by a single
space. There
are no leading spaces before the first card and no
trailing
spaces after
the last card.
Output
Specification:
----------------------
If the input
set contains a 4-sequence, output the cards that form the
4-sequence
in increasing order of the card numbers separated by one or
more spaces
terminated by an EOLN.
If the input
set contains a 3-trail, output the cards that form the
3-trail in
the order of {h,s,c,d} separated by one or more spaces
terminated
by an EOLN.
If the input
set contains neither of the two, then output "none" on a
line. The
output must be in lower-case letters only.
Sample Input
And Output:
-------------------------
Input:
h1 d7 s2 d8
d3 h13 d12 h11 d5 d6 h2 s1 h10
Output:
d5 d6 d7 d8
Input:
h1 h2 h10
h11 h13 s1 s2 d1 d3 d5 d6 d7 d12
Output:
h1 s1 d1
Input:
h12 d7 s2 c1
d1 h13 d2 h11 d5 d6 h9 s11 c2
Output:
s2 c2 d2
Input:
s1 h2 s3 h4
s5 h6 s7 h8 s9 h10 c11 d12 c13
Output:
none
PROBLEM 4:
Write a
program for maintaining the appointments of patients in
different
departments
of a hospital. Assume that each patient has a unique
integer-
identifier(id)
and so also every department. A patient can seek
appointments
to one or
more departments and is also allowed to cancel an appointment
from
any
department. The program should be able to list out at any time the
number
of patients
who have valid appointments with a given department or the
number
of
departments with which a given patient has appointments.
INPUT
------
The input to
your program is a sequence of commands each command on a
separate
line. There
are four commands as follows:
1) S
patient-id department-id
Example
S 3013 1023
(Patient
with id 3013 is seeking appointment from department with id
1023)
2) C
patient-id department-id
Example:
C 10293 0112
(Patient
with id 10293 is cancelling his appointment from department
with id
0112)
3) D
department-id
Example
D 23
Output
-------
Print the
total number of patients who have valid appointments with the
department
having the id 23. Cancelled appointments should not be
counted.
Terminate
your output by an EOLN. If there are no appointments for the
department
then your program must output 0 followed by an EOLN. The
output
must not
have any sign and there should be no leading zeroes in the
output.
4) P
patient-id
Example:
P 101
Print the
total number of departments with which the patient with id
101 has
valid
appointments. Cancelled appointments should not be counted.
Terminate
your output
by an EOLN. If the patient does not have any valid
appointment
with any
department then your program must output 0 followed by an
EOLN.
The output
must not have any sign and there should be no leading zeroes
in
the output.
Your program
must be capable of handling any number of departments and
any
number of
patients. You may assume that there are no receding blanks
before
the command
character and that erroneous input will not be given to
your
program.
Each command line is terminated by EOLN and the input is
terminated
by an EOF.
EXAMPLES
---------
S 100 200
S 100 201
S 100 203
S 101 203
S 101 240
C 100 200
S 101 207
C 101 240
P 100
D 203
D 200
S 100 200
S 101 231
D 200
S 102 245
D 203
P 104
PROBLEM 5:
Write a
program to merge two linked lists.
INPUT
------
The input to
the program will be two lines, each terminated by EOLN.
Line 1 :
sequence of integers for the first list
Line 2 :
sequence of integers for the second list
The integers
appearing on each of the lines may not be in ascending
order.
So you must
arrange the integers on a line as a linked list in
non-decreasing
order. Once
a line of input is read, the integers on that line must be
output
as an
ordered list of numbers on the same line terminated by an EOLN.
After
obtaining two ordered linked lists, you must merge them such that
there
are no
duplicate elements in the resultant list and the new list has
elements
in a
non-decreasing order.
The elements
in the new list must be printed on the same line
terminated
by
EOLN.
The elements
in the input list will be integers and
duplicate integers
will
not be
provided on a line of input.
OUTPUT
------
The output
of your program must consist of three lines, each terminated
by EOLN.
Line 1 :
elements of the first list in ascending order.
Line 2 :
elements of the second list in ascending order.
Line 3 :
elements of the merged list in ascending order.
In case the
output list is empty, output an EOLN.
EXAMPLES
--------
Input :
20 10 5 13 30
5 2 10 9
Output :
5 10 13 20 30
2 5 9 10
2 5 9 10 13 20 30
PLEASE NOTE
------------
The words
'Input:' and 'Output:' are not a part of the inputs and
outputs.
Do not
attempt to input or output these words using your program.
Assume
that the
input values are all correct. Do not do any input validation
and
do not
output anything other than what is defined in the output
specification
otherwise
the grader will fail to check your program properly.
PROBLEM 6:
Write a
program to maintain the current stock of machine parts of a
workshop. A
part is
identified by a 10 character part-id. The production and
consumption
of
parts take
place within the workshop. You may assume that over
consumption
is
allowed(
that is, the stock can go negative also).
INPUT &
OUTPUT
--------------
The input to
your program is a sequence of action commands each command
on a
separate
line.
The four
commands are as follows:
1) Production of a part( command is P )
P SCR1110810 1500
This implies
that 1500 units of the part with id SCR1110810 have been
produced.
( Note that
a part entry has to be created if one with this part-id
does not
already
exist).
2) Consumption of a part( command is C )
C NPN1012136 2000
2000 units
of the part with part-id NPN1012136 have been consumed.
( Note that
a part entry has to be created if one with this part-id
does not
already
exist).
3) To output
the number of parts whose stock is less than the given
number
( command is
L )
L 100
This
requires your program to output the number of parts with stock
less than
100. Your
output should be an integer ( greater than or equal to zero )
without any
sign or leading zeroes.
Terminate
your output by an EOLN.
4) To output
the number of times the stock of the given part has gone
from >=0 to negative.
( command is F )
F NPN1012136
This
requires your program to output the number of times the stock of
the part
with part-id
NPN1012136 has gone from >=0 to negative. Your output
should be
an integer (
greater than or equal to zero ) without any sign or any
leading
zeroes.
Terminate your output by an EOLN.
If the stock
has never become negative, you must output a 0 terminated
by an
EOLN.
In the above
assume that there is exactly 1 blank between the command
(P, C or F )
and the part-id. Your program must be capable of handling
any number
of parts. Assume that there are no leading spaces before
the command
character.
PROBLEM 7:
Write a
program that will generate a specified number of fibonacci
numbers.
The first
two numbers in the fibonacci number series are always 1. Each
succeeding number in the series is such that its value
is equal to the
sum
of its
preceding two numbers.
Input:-
The program
should accept an integer indicating the number of elements
to be
generated in the series. The input number will be a natural
number.
Output:-
The output
of the program should contain the required number of
elements
of the
fibonacci series. The numbers in the series must be separated
by a space.
Examples:-
1. Input:
5
Output:-
1 1 2 3 5
2. Input:
7
Output:-
1 1 2 3 5 8 13
3. Input:
2
Output:-
1 1
PROBLEM 8:
A set can be
implemented using arrays. Write a program to implement the
basic set
operations on sets of the following
specifications
The set may
hold maximum of 100 elements. The elements of the sets
are
integers.
The operations
to be performed on these sets are
1.
Intersection denoted by the letter I
intersection of sets A and B yields a
set whose elements
are both in A and B
2.
Difference denoted by the letter D
A difference B yields a set whose elements
are the
elements of A not in B
The elements
in a set will be given as a sequence of integers on a line
EOLN will
mark the end of the sequence.
The input
consists of 3 lines
line 1:
elements of set A
line 2:
elements of set B
line 3: set
operator( I or D )
The output
should consist of the result ofoperation
A
<operator> B
The elements
of the resultant set must be output on
a line
separated by
blanks and without any leading zeroes. The line must be
terminated
by an EOLN.
Note : The
elements of the input sets will be given in non-decreasing
order.
The elements
in the output must also be in non-decreasing order.
Sample Input
and Output:
Input:
0 23 456 765 1000 5678 7654 8001 10000
23 234 543
765 1235 10000 12347
I
Output:
23
765 10000
Input:
-10 0 15 25 125
-15 -10 0 20
D
Output:
15 25 125
PROBLEM 9:
Given a set
of vertical and a set of horizontal line segments, in the
format
specified below, write a Pascal program to find the total
number of
crossings amongst the line segments.
( See figure
below ).
|
|
|
|
-----|----------|---------------
|
|
|
|
|
-----|---------------------
|
|
|
|
|
-----|----------------
|
Input :-
The input to
your program will be as follows:
line 1: an
integer m {number of horizontal line
segments}
line 2: an
integer n {number of vertical line
segments}
line 3: x11
x12 y1 x21 x22 y2 ...xm1 xm2 ym
{3m integers specifying the horizontal
lines}
line 4: y11
y12 x1 y21 y22 x2 ... yn1 yn2 xn
{3n integers specifying the vertical lines}
In line3,
three integers define a line segment
Example:-
x11 x12 and y1 define a horizontal line segment with
endpoint co-ordinates (x11, y1) and (x12, y1).
Similarly in
line 4, y11 y12 and x1 define a vertical line segment
with endpoint co-ordinates (x1, y11) and
(x1, y12).
Assume that
the maximum number of horizontal line segments is 20.
Similarly
the maximum number of vertical line segments is 20.
Note: If two line segments merely touch each
other and do not
cross then it is not a valid crossing.
For example the following are not valid
crossings.
|
--------+----------- |
| |-----------
| | |
| |
| | _____________
| | |
| +------------- |
| |
|
Examples :-
Input:
3
2
1 10 3 30 2
5 4 20 6
10 1 5 25 30
100
Output:
3
Input:
1
1
10 20 10
20 15 15
Output:
0
PROBLEM 10:
N numbers,
starting from 1, are placed around a circular table.
Starting from
1 every Kth number around the table is removed. This
process is
continued until all the numbers are removed from the table.
For example
If N = 10 and K = 3 the order in which numbers removed are
1 4 7 10 5 9
6 3 8 2
Write a
program which prints out the sequence of numbers in the same
order as
removed for any given N and K.
Input:-
Two numbers
N and K given on a single line terminated by an EOLN.
Example:-
Input:-
10
3
Output:-
1 4 7 10 5 9 6 3 8 2
Hint: Use
circular linked list.
PROBLEM 11:
Write a
Pascal program to build a number triangle. Given 4 integers,
the number
triangle is built as follows:
A11
A12 A13 A14
Root members of the number triangle of
height 4
+
+ +
A21
A22 A23 A21 = A11+A12,
A22 = A12+A13, A23 = A13+A14
+ +
A31 A32 A31 = A21+A22, A32 = A22+A23
+
A41 A41 = A31+A32
Given a
number, search for the number from root and starting from root,
print in
increasing order all the levels at which the number is found.
If the
number is not found in the triangle, print 0.
Level of the
root is 1.
The three
lines of input to your program are
1) The first
line will be an integer h giving the height of the
triangle.
2) The
second line will have h integers which are the root members
of the triangle.
3) The last
line contains the number to be searched.
The output
of your program will be the levels at which the number
to be
searched occurs in the triangle, one per line. Output the
level(s)
without any leading zeroes. If the number does not occur,
print 0.
Terminate your output by an EOLN. Assume that the maximum
height of
the triangle is 10. In case the number occurs more than once
at
a level,
that level number should be output only once.
Input:-
4
1 2 3 4
8
Output:-
3
Triangle is
as follows:
1 2
3 4 Level 1
3
5 7 Level 2
8
12 Level 3 ( 8 is at this
level )
20 Level 4
Input:-
5
4 2 1 1 1
4
Output:-
1
3
PROBLEM 12:
Write a
Pascal program to search a line of text for a pattern. The
pattern is
of the form X+Y*Z where X, Y and Z are
distinct
characters.
The + and * are interpreted as follows,
X*Y Zero or more occurrence(s) of X followed by
Y
X+Y 1 or more occurrence(s) of X followed by Y.
Thus k+j
kj, kkj, kkkj, kkkkj etc
k*j
j, kj, kkj, kkkj etc
The input to
your program will be two lines of text each terminated
by an EOLN.
The first line is a line of text of maximum 80 characters.
The second
line contains the pattern to be searched in the first line.
The output
of your program should be the position in the first line
at which the
matching pattern occurs ( ie. the matching pattern begins
at that
position - the first character in the line has position 1).
If the
pattern is not found, output a zero. The output should not
contain any
leading zeroes. Terminate your output by an EOLN.
In case the
entire pattern is found at more than one position, output
the last
position. The position output should be such that we do not
get a
matching pattern in the immediately preceding position.
Input:-
this is not a major issue.
s+u*e
Output:-
22
The pattern
is always of the form X+Y*Z.
u is at
position 24. "sue" matches the pattern.
But
"ssue" also matches. So the position is 22
and not 23.
Input:-
astro astonish assume atomic attribute
static
a+s*t
Output:-
42
Here , there
are a lot of matches.
But the
"at" in "static" is the last one to match.
PROBLEM 13:
A
"saddle point" of a matrix A is defined as the element A[i,j] such
that A[i,j]
is the smallest element in row "i" of the matrix and
the largest
element in column "j" of the matrix.
Given a 9x9 matrix
whose elements are non-negative integers, you have
to output
its saddle point if it exists or -1 (minus one) if the
saddle point
does not exist. The saddle point if it exists, is
always
unique.
Assume that
the rows and the columns of the matrix are numbered
from 1 to 9.
The input consists of the 9x9 matrix ie. there are 9 lines
with 9
integers on each line.
If the given
matrix has a saddle point, you have to output three
integers on
a line terminated by EOLN. The three integers, in order,
are the
saddle point, the row index and the column index of the
saddle
point.
Integer
numbers on the same line must be output separated by blanks
and without
any leading zeroes. If the given matrix does not have a
saddle
point, you must output -1 on a line terminated by EOLN.
Input:-
2 3
4 5 6 7 8
9 10
4 5
6 7 8 9 10
11 12
8 9
10 11 12 13 14 15
16
2 3
4 5 6 7 8
9 10
3 5
6 7 8 9 10
11 12
2 3
4 5 6 7 8
9 10
7 5
6 7 8 9 10
11 12
2 3
4 5 6 7 8
9 10
6 3
4 5 6 7 8
9 10
Output:-
8 3 1
In the above
matrix, the integer 8 at position [3,1] is the saddle
point, as
per the definition of the saddle point given above.
PROBLEM 14:
Given an
input text which resembles a Pascal program segment, write
a program to
output the maximum degree of nesting of the
"begin"
-- "end" keywords.
The first
line of input consists of an integer denoting the number
of lines of
text to follow. The text will contain a Pascal program
segment
which will have an arbitrary degree of nesting of begin-end
statements.
You may
assume that every "begin" will have a corresponding "end"
and that the
keywords "begin" and "end" will always be in lower
case
letters.
The output
of your program should be an integer denoting the maximum
degree of
begin-end nesting found in the text. Terminate your output
by an EOLN.
The ouput integer should not have any leading zeroes.
Input:-
var i, j : integer;
begin
while (i<10) do begin
if j=10 then begin
j := succ(j);
i := pred(k)
end;
if true then begin flag
:= false end
end;
if j=7 then begin
j := j+1;
i := i+j
end
end
Output:-
3
PROBLEM 15:
Given a
piece of text, find the frequency distribution of word lengths
(ie. how
many words have one letter, how many have two letters,...).
Find the
word-length having the highest frequency and print that
word-length
followed by its occurrence count. In
case two or more
word-
lengths have
the highest frequency, print the largest word-length and
its
occurrence
count.
A
"word" is made up of alphanumeric characters and delimited by white-
spaces or period(
ie. full stop ).
The first
line of input specifies the number of lines of text to follow
( say N ).
Each word in the piece of text can be assumed to be smaller
than
15
characters. Your output will be two integers as above, separated by
one or
more spaces
with no leading zeroes and terminated by an EOLN.
Example:-
Input:
2
This is
a sample text. The text has sentences and sentences have
words.
Some words
are small. Some words are big.
Output:
4 6
PROBLEM 16:
In this
problem you have to find out a path between two points in a
maze.
The maze is
represented here as a 7x7 matrix containing the elements
0, 1, 2 and
3. The '0's are part of the path from the starting point
represented
by a '2' to the ending point represented by a '3'. The '1's
represent
blocks in the maze. There is a unique path from '2' to '3'
and it
always
exists and there are no dead-ends and no branches in the path.
The
elements '2'
and '3' occur only once in the matrix. Assume that the
rows and the
columns of
the matrix are numbered from 1 to 7.
The input
consists of 7 lines, each line containing 7 integers, thus
forming
the 7x7
matrix.
The output
should consist of a sequence of lines, each line containing
a pair
of integers
which are the row and column indices of the elements in the
path
from the
starting point '2' to the ending point '3' in the order of the
traversal,
including the indices for the '2' and the '3'. Integers on
the same
line must be
output separated by blanks and without any leading zeroes.
Sample Input
& Output:
Input:
1 0 1 1 1 1
2
0 1 0 1 1 0
1
0 1 1 0 0 1
1
1 0 1 1 1 1
1
1 1 0 0 1 1
1
1 1 1 1 0 1
1
1 1 1 1 1 0
3
Output:
1 7
2 6
3 5
3 4
2 3
1 2
2 1
3 1
4 2
5 3
5 4
6 5
7 6
7 7
Explanation:
The indices
for the starting point '2' are (1,7) and the ending point
are
(7,7). The
rest are the indices of the '0's that form the path from the
'2' to the
'3' in the order of traversal ie. after the '2' at (1,7),
the
next element
in the path is the '0' at (2,6), followed by the '0' at
(3,5),
followed by the '0' at (3,4) and so on till the '3' at (7,7).
PROBLEM 17:
Consider a
shop 'Linked List Electronics ' which allows its customers
to
purchase
items on credit. (The payment can be made later.) They are
planning
to automate their record-keeping for such
customers. They have less
than 100
customers.They
want a progrm as per the following desciption
Whenever a
customer purchases an item the operator will enter a line of
input
purchase name item_name
-----------------------
You may
assume that only the last name of the customer is given as one
word.
Also the
item name can be assumed to be a single word.
Whenever the
customer pays up another line of the form
payment-name item-name
----------------------
is entered.
For multiple
payments and purchases;multiple lines will be entered with
one
entry per
line .
The end of
input will be indicated by a line containing just the word
'stop'.
After that a
seperate line of input will specify a customer name.The
program
should
output the items purchased by the customer which are not yet
paid for.
The output
should be alphabetically ordered and all items in one line.
If their are
no pending items ,output "nothing".Assume maximum length
of a word
to be 50
characters.
SAMPLE
INPUT:
purchase wilson vcr
purchase wilson radio
purchase graey tv
payment wilson radio
purchase wilson tv
stop
wilson
SAMPLE
OUTPUT:
tv vcr
NOTE : YOU
MUST USE LINKED LISTS.
PROBLEM 18:
An anagram
of the word x is the word formed by the characters of the
word x
with each
letter being used only those many times as in word x.For
example
post,opst,tops
are some anagrams of the word 'stop'.
Input to the
program will be the word (less than 8 char.s) terminated
by eoln.
Output of
the program should be the list of all anagrams of the input
word;
alphabetically
sorted with one word per line.The upper case letters are
lower
than the
lower case letters.Terminate the last word also with eoln.
SAMPLE
INPUT:
tea
OUTPUT: aet
ate
eat
eta
tae
tea
PROBLEM 19:
Write a program to accept a finite set of
alphabets and all its
nonempty
subsets in
lexicographic order.The set of alphabetic symbols will have
at
most eight
chars.Note that the no. of such non-empty subsets is equal
to
(2^n -
1),where n is the no. of elements in the given set.
For
example;given a set {a,b,c},the list of its non-empty subsets is
{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}.
Input Format
:The input will consist of two lines.
First line
indicating the no. of elements in the input set say n .
Second will
have a string of n non-blank alphabetical characters
forming a
set.
Note that
the characters themselves will be given in alphabetical
order.
Output
Format:The output must list each of the required subsets on a
seperate
line (ie.the
no. of lines in the output must be equal to the no. of
non-empty
subsets of
the given set.) The characters in each line ,also the
subsets
themselves
should be in alphabetical order.
SAMPLE
INPUT: 3
abc
OUTPUT: a
ab
abc
ac
b
bc
c
PROBLEM 20:
Consider a teller counter in a bank.There are
two clerks handling the
job.
Each of them can handle any transaction at
the counter. Mr.Fast takes
5 minutes per transaction irrespective of the
type of transaction.
Mr.Slow needs 8 minutes per transaction. The
bank is planning to
improve
customer satisfaction and wants to know the
varios statistical
parameters
of its performance. The follwing is
specification of one of the
programs.
Implement it using the Que data stucture.
The input to the program consists of a
sequence of positive integers
terminated by the number -1. The input
numbers indicate the arrival
pattern
of customers.
Assume that the start of the program is at
time 0.The first no.
indicates
how many minutes from the arrival of the
first customer the second
customer
arrives , and so on.
You have to
simulate the service to the customers at the teller
counter.
Assume that
the customer will go to the earliest available counter for
his work.
However ;if both counters are free ; then preference is given
to
Mr.Fast. The
order of service is strictly in the order of arrival.
The input is
a table of number of people waiting for service at every
minute.
You need to
print this for the first 21 minutes from 0 to 20
(inclusive).
For each
minute one line of input is required containing the time and
the no. of
people waiting for service.The two items are seperated by a
single
space. For
the same purpose,you can assume that a customer arriving at
time t
is in the
que at time t,if no counter is free at that time.
SAMPLE
INPUT: OUTPUT:
0 0 0
0 1 0
1 2 1
2 3 1
2 4 1
8 5 0
-1 6 0
| |
| |
16 0
__________________________________________________________________________________________
OOPJ MGPT 3 August , 2001
Problem No.
1 (Identifying the Shapes)
you will
be given a integer matrix as input which will consists of only 1 or 0. The 1's
will form patterns . Pattern will be
either square or rectangle or
triangle and nothing else!. Also patterns will be disjoint and will not
overlap. pattern will consist
of atleast three 1's.no
pattern will share common boundary with any other pattern. The patterns will be parallel to the matrix
wherever possible. u have to find the
pattern from top-left to bottom-right and
print "square","rectangle",triangle" as the pattern is
on first found first printbasis
beginning form top-left and ending at bottom- right
Input:
1) on first line ,2 integers M
& N which is the dimension of the input
matrix
2) then on M lines ,N
integers(0 or 1 only) each per line
Output:
pattern that is found . print
one pattern name per line
Example
1)Input:
3 4
1 1 0 0
1 1 0 0
0 0 0 0
Output :
square
2)input:
8 9
1 0 0 0 0 0 0 0 0
1 1 0 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1
1 1 0 0 1 1 1 1 1
1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 1
0 1 1 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0
output:
triangle
rectangle
triangle
square
____________________________________________________________________
Problem
No. 2 (Crossword Problem)
- denotes a blank space.
# denotes a filled space.
u have to place words in place
of -
i/p specification-
1st line=2 int M,N separated
by space,
next M lines=N chars(i.e.-M by
N char matrix)
next line=int X (<=10)
spacifing no of words to place in matrix
next line=X words
separated by space.
o/p specification-
M by N char matrix WITHOUT any
space.
hints-
i/p matrix won't contain
anything else than '#','-' or alphabet.
words will inputed in asc.
order of their length. i.e.-min length
word will at start
and max length word at end.
there will be a unique
solution to the problem.
no two words will fulfill same
condition.(like "tall" and "poll" will
fulfill "--ll".
such cases won't be there.)
(that's all what i
remember!!!)
example-
Input
5 5
---##
t##--
-##-#
---l#
###l#
5
to see stop tall pawl
Output
see##
t##to
o##a#
pawl#
###l#
_______________________________________________________________________
Wordchain
Problem
There will be N words supplied
to the user as input and there will be
two conditions associated with it,either there can
be a unique chain of words that are common to a pair of
words e.g. ginger gerund the substring "ger" is common to both.
This common substring will be
more than or equal to 3 words. Find the chain and print it,if no chain existent
print IMPOSSIBLE.
Note:The first word entered in
the input will be the starting word of the word chain,always.
Test Cases:
Input-
2
start
finish
Output-
IMPOSSIBLE
Input-
4
begin
gerund
under
ginger
Output-
begin
ginger
gerund
under
Input-
8
whisper
format
perform
person
workshop
shopper
sonnet
network
Output-
whisper
person
sonnet
network
workshop
shopper
perform
format
___________________________________________________________________________
DSAL MGPT 22
September 2001
Problem No.
1
A project graph is represented by states
and activities. Each state has an earliest time of completion (ET) and
a latest time(LT) of completion. The activities are assumed
to be completed in a finite amount of time.
A vertex represents each state and the activities are
represented by directed edges from one
state to the next, where the weight of the edge is the time
taken to complete an activity and transition from
one state to the next.
ET of first state is 0;
ET of a state = Max(ET of immediate preceeding states +
weight of edges )
After all the ET has been calculated:
LT of last state = ET of last state
LT of each state = Min(LT of immediate succeeding states -
weight of edge)
Input specs:
The first line will consist of an integer M which represents
the number of states (vertices)
This will be followed by M lines each giving the vertex name
which will be a word not greater than 15
chars Next line will be an integer N representing no. of edges
This will be followed by N lines each representing the
from and to vertices of an edge and its weight separated by
spaces. Next line will be an integer X representing number of
outputs This is followed by X lines each specifying a vertex
name.
Output specs:
On a separate line - For each vertex specified in the last X
lines of the input specs, display the vertex
name, its earliest time and its latest time separated by
spaces and terminated by a newline char.
Assumptions :
1) Cycle will not have any edges
2) The first and last vertex name in the input specs will be
the first and last vertex in the graph
*Nothing has been specified abt the input vertex names being
specified in topological sort order
Example:
Input:
8
C#
PASCAL
C++
ASP
.NET
HTML
JAVA
UNIX
12
C# JAVA 3
C# ASP 2
HTML .NET 6
C# HTML 8
JAVA C++ 5
C# .NET 4
ASP UNIX 25
.NET PASCAL 2
ASP C++ 5
HTML PASCAL 9
C++ PASCAL 1
PASCAL UNIX 7
4
HTML
.NET
PASCAL
C#
Output:
HTML 8 11
.NET 14 18
PASCAL 17 20
C# 0 0
___________________________________________________________________________
Problem No. 2
implement the
following sort algorithm:
accept a number n. accept n elements to be sorted. split
these elements into 2 groups-first group containing the first (n+1)/2 elements
and the second group containing the remaining elements. now, split both the
groups into small segments of size
k. now, take the
first segment of k elements from first group and the first segment of k
elements from the second group and sort it and store it. similarly, proceed
with the next segments of k elements from both the groups and store the sorted values after the values stored for previous segment...note
that the last segment in a group might contain less than k elements. k starts
from 1 and increases in powers of 2...1,2,4,8,etc... u have to repeat this
process until k becomes greater than (n+1)/2 when all the elements get sorted
out. in each iteration of k, u have to print the order of the n elements which
u store after sorting the
k-element segments, and, before going to the next iteration
u have to again split these partially sorted
n elements into 2 groups as done before.
_________________________________________________________________________
Problem No.
3
Given a set of numbers, a
tree has to be formed. The output has to state
whether the tree is a complete binary tree(CBT), almost
complete tree(ABT),
strictly binary tree(SBT) or an arbitary tree(ARB).
If the tree is a Complete binary tree, in which
case it is also an almost
complete binary tree and strictly binary tree; the output
should state it as
a complete binary tree i.e CBT.
Similarly, if the tree is an almost complete
binary tree, it is also a
strictly binary tree. The output should be ABT.
Input :
Input will be a set of natural numbers
terminated with -1.
Output :
The output should be CBT, ABT, SBT or ARB
according to the case. The
output should terminate with a new line character.
Example:
Input
10 8 15 4 20 22 5 -1
Output
CBT //Note it is also a ABT and SBT
Input
10 8 15 4 5 -1
Output
ABT //here it is also an SBT
______________________________________________
Problem 4:
The input will consist of an integer that
denotes the original size of
the class followed by names and marks of students. The
students have to be
allocated roll nos on the basis of hash function:
ROLL_NO= MARKS % CAPACITY OF
CLASS
Note 0 is acceptable as the roll no of the student.
If a student say X gets a roll no which is
already allotted to another
student (Y) then the next available roll no is allotted to
X.
If the number of students exceed 70% of the
class capacity then the
capacity is doubled.(//... Wish this happens with
engineering admissions
also). The roll nos are recalculated on the basis of the new
class capacity.
The students who had already been allotted roll nos(ie
before the increase
in capacity) will have roll nos in the order that they were
previously given
and for the remaining students the normal allottment
procedure is followed.
Input :
The first line of input will consist of the original
class size. Next, the
name of the student and his marks will be given. The name of
the student
will not exceed 15 characters and will not have any spaces.
'STOP' will
indicate the end of input.
Output:
The output should consist of the final
streength of the class. The roll
no, the name and the marks of the student should be shown in
the lines that
follow. The output has to be in the ascdending order of the
roll nos and
should end on a new line.
Input:
5
aaa 56
bbb 80
ccc 59
ddd 84
eee 45
fff 72
ggg 86
hhh 48
iii 95
jjj 85
STOP
Output:
20
0 bbb 80
4 ddd 54
5 jjj 85
6 ggg 86
12 fff 72
15 iii 95
16 aaa 56
19 ccc 59
Disclaimer -
All problems are collected from postings on NCSTJ2001 and from my
e-mails. If any of the problem statement has problem than let me know.