Author |
Topic: ::-- New MS standard questions --:: (Read 790 times) |
|
arvind_tiwary
Newbie
Posts: 4
|
 |
::-- New MS standard questions --::
« on: Apr 20th, 2006, 5:34am » |
 Quote  Modify
|
------- 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
|
| « Last Edit: Apr 20th, 2006, 7:17am by arvind_tiwary » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: ::-- New MS standard questions --::
« Reply #1 on: Apr 20th, 2006, 6:13am » |
Quote Modify
|
For 3:
| hidden: |
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--;
}
|
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
livinginthepast
Newbie
Posts: 1
|
|
Re: ::-- New MS standard questions --::
« Reply #2 on: May 5th, 2006, 5:11am » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: ::-- New MS standard questions --::
« Reply #3 on: May 8th, 2006, 10:00am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
sk
Newbie
Posts: 45
|
|
Re: ::-- New MS standard questions --::
« Reply #4 on: Jan 21st, 2007, 11:40pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print