wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> ::-- New MS standard questions --:: 
        
(Message started by: arvind_tiwary on Apr 20^th, 2006, 5:34am)

Title: ::-- New MS standard questions --::
Post by arvind_tiwary on Apr 20^th, 2006, 5:34am

------- Questions-----

1. Given a string and regular expression, write a function to findout whether the string satisfies the regular expression.

2. How can u represent Rs. 1 to 301 in minimum no of denomination. that is how many coins u need and what should be written on them i.e. their value.

3. U have an Integer Array but the aray can have certain bad blocks. u h ave to reverse the array without touching the bad blocks.

4 .Given a adjacency matrix of a graph, we have to find the minimum nodes that together influence all the edges of the graph.A node influences all the
edges which are connected to it.It is a directed acyclic graph.

5. Given a number in the form of a string and an integer n create a linked list of the reversed string inserting a node with value 0 after every nth node
Must consider
i) n <= 0
ii) string is NULL
iii) n < length(string)
iv) n is not a multiple of the length of the string
v) n is a multiple of the length of the string

Ex : string : "1234" n = 2
Output : 4->3->0->2->1->0

Post the soln .. thx

Title: Re: ::-- New MS standard questions --::
Post by towr on Apr 20^th, 2006, 6:13am

For 3:
[hideb]
l=0;
r=array.length-1;

while (true)
{
while(bad(array, r))
r--;
while(bad(array, l))
l++;
if( l < r)
swap(array, l, r);
else
break;
l++, r--;
}
[/hideb]

Title: Re: ::-- New MS standard questions --::
Post by livinginthepast on May 5^th, 2006, 5:11am

No. 2 seems incomplete. It's as if something's missing from the statement. I assume that when you are measuring a value you cannot use the same denomination twice. Correct me if I am wrong...

Title: Re: ::-- New MS standard questions --::
Post by Grimbal on May 8^th, 2006, 10:00am

1. can we use the regexp package? If not, what is the syntax to take into account?

2. If you can have multiple coins with the same denomination, obviously one denomination of 1 is enough. If what you want is the minimum number of coins, then the pattern 1, 2, 4, ... is optimal with 9 coins. (you can not make more than 255 different amounts with 8 coins)

3. towr's code looks good to me, except that I would check that r and l don't cross when skipping bad blocks, just in case all blocs are bad...

4. I would select all nodes that are not pointed to, remove theses ane their direct children and continue until all are taken or removed.

5. Not very difficult. The trick is to start from the end.

Title: Re: ::-- New MS standard questions --::
Post by sk on Jan 21^st, 2007, 11:40pm

for 2.

sort them in descending order
apply greedy strategy. it does not give u optimal solution. to ensure there is optimal solution,
apply this condition.
//divide the amount by the maximum denomination
//if there is a denomination == remainder then it is the optimal solution else, there is one more denomination that is to be tested.

e.g. u have $1,$2,$5,$10,$20,$25 and u have to make $40
greedy solution wud give $25,$10,$5
if u apply the condition, then
$40%$25 = $15. there is one more denomiation between 15 and 25. So get a greedy solution based on that. if the remainder is 0 then the new solution is the optimal solution.

there might be some complications if there was one more denomination say $22. So got to evaluate the time complexity