arindam.mitra2
BAN USER- 0of 0 votes
AnswersYou are given a tree (an undirected acyclic connected graph) with N nodes, and edges numbered 1, 2,
- arindam.mitra2 in -
3...N-1. Each edge has an integer value assigned to it, representing its length.
We will ask you to perfrom some instructions of the following form:
DIST a b : ask for the distance between node a and node b
or
KTH a b k : ask for the k-th node on the path from node a to node b.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
Answersimplement a stack which will support three additional operations in addition to push and pop:
- arindam.mitra2
1.peekLowestElement()//return the lowest element in the stack without removing it from the stack
2.peekHighestElement()//return the highset element in the stack without removing it from the stack
3.peekMiddleElement()//return the (size/2 +1)th lowest element in the stack without removing it from the stack.
faster is better.Assume every method will be called with equal frequency.| Report Duplicate | Flag | PURGE
WorksApp Software Engineer / Developer Stacks
i think there are two sub cases :
case 1:cost is linearly proportional to the the length of the log ,in which case,irrespective of the positions of cuts,we have to spent money equal to some constant times of total length of the rod.
case 2 :is when cost of cutting is not linearly proportional ,then we have to minimize sum of k terms ,each representing cost of a particular cut.keeping in mind that (a+b+c..)^n>a^n +b^n +...we should try to keep the size of the log as small as possible i.e k=n.
let X=x2- x1
Y=y2-y1
Then to reach from (x1,y1) to (x2,y2) we need X+Y steps of which Y are of kind(0,+1) and X are of kind (+1,0) .Thus the total number of such paths is (X+Y) C X.
1.2 3.4 2.4
3.9 4.0 2.1
7.9 1.6 0.5
should be converted to
1 4 2
4 4 2
8 1 1
1.2 3.4 2.4
3.9 4.0 2.1
7.9 1.6 0.5
should be converted to
1 4 2
4 4 2
8 1 1
an o(n) without stack solution:
(assuming the input is well parenthized)
step 1:read character from left untill a '(' is found or input ends.
step 2:if input ends exit;
step 3:if '(' is found check if the next character is'(' ?
if false go to step 1;
else check for the duplicacy for the 2nd '(' recursively//"eg:..(((....)))"
if the the next char(suppose i) of 2nd's matching ')' is
another ')' report 1st '(' duplicate;
else go to next 1 with next symbol as i+1;
here each character is visited only once.so tc is o(n).
modification of the maximum sum sub array problem.we have to change the recurrence.
- arindam.mitra2 September 27, 2011the strstr () procedure does the string matching.which we can not use.
- arindam.mitra2 September 27, 2011in o(nk)time and o(n) space worst case it could be done.
- arindam.mitra2 August 26, 2011
what should be the output for input : () ?
- arindam.mitra2 December 07, 2013