Author |
Topic: Problem Set for MS (Read 5832 times) |
|
tuxilogy
Newbie
Posts: 45
|
 |
Problem Set for MS
« on: May 16th, 2006, 7:57am » |
 Quote  Modify
|
Hi guys
Please help me out in solving these problems.
I am applying for MS Internship, and would be very grateful if you can donate something
q1: You have an abstract computer, so just forget everything you know about computers, this one only does what I'm about to tell you it does. You can use as many variables as you need, there are no negative numbers, all numbers are integers. You do not know the size of the integers, they could be infinitely large, so you can't count on truncating at any point. There are NO comparisons allowed, no if statements or anything like that. There are only four operations you can do on a variable.
1) You can set a variable to 0.
2) You can set a variable = another variable.
3) You can increment a variable (only by 1), and it's a post increment.
4) You can loop. So, if you were to say loop(v1) and v1 = 10, your loop would execute 10 times, but the value in v1 wouldn't change so the first line in the loop can change value of v1 without changing the number of times you loop.
You need to do 3 things.
1) Write a function that decrements by 1.
2) Write a function that subtracts one variable from another.
3) Write a function that divides one variable by another.
q2: A character set has 1 and 2 byte characters. One byte characters have 0 as the first bit. You just keep accumulating the characters in a buffer. Suppose at some point the user types a backspace, how can you remove the character efficiently. (Note: You cant store the last character typed because the user can type in arbitrarily many backspaces)
q3: hat is the simples way to check if the sum of two unsigned integers has resulted in an overflow.
Q4. How do you represent an n-ary tree? a program to print the nodes of such a tree in breadth first order?
Please help me
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
|
Re: Problem Set for MS
« Reply #1 on: May 16th, 2006, 9:00am » |
Quote Modify
|
For Q1 part 1): Operation 2) is not strictly necessary, and thinking about how to copy a variable with only operations 1), 3) and 4) should point you in the right direction. Now if you can do part 1), part 2) should be simple from there, and likewise part 3) should be easy from part 2).
Q2 has been recently discussed here.
Q3 should be trivial, just think about the relationship of the result to the arguments.
Q4 should have come up in your DS&A class you've been feeding us homework assignments from.  If you can do a bredth-first listing of a binary tree you shouldn't have any trouble with an n-ary tree...
Hope that points you in the rights directions. 
[edit]Hmm: Q1 part 3) may not be as easy as I first thought, even given Q1 part 2). Maybe there's an interesting problem lurking in there after all. [/edit]
--SMQ
|
| « Last Edit: May 16th, 2006, 9:27am by SMQ » |
IP Logged |
--SMQ
|
|
|
tuxilogy
Newbie
Posts: 45
|
|
Re: Problem Set for MS
« Reply #2 on: May 23rd, 2006, 10:01am » |
Quote Modify
|
Please give me some sugestions...
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Problem Set for MS
« Reply #3 on: May 24th, 2006, 5:27am » |
Quote Modify
|
Q1 part 1 maybe implemented as follows:
Code:
func dec( v )
begin
d = 0
loop ( v ) [ dc = d; d ++ ]
ret dc
end
|
|
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Problem Set for MS
« Reply #4 on: May 24th, 2006, 6:03am » |
Quote Modify
|
After which Q1 part 2 is downright trivial:
Code:func subtract(a, b) // subtract b from a
begin
c = a;
loop (b) [ c = dec(c); ]
ret c;
end |
|
As for Q1 part 3, I'm still stuck myself--only having fixed-count loops and no other conditionals is throwing me off--but I haven't put a whole lot of thought into it, either.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Problem Set for MS
« Reply #5 on: May 24th, 2006, 6:37am » |
Quote Modify
|
You could perhaps use recursion.
(You can use a loop to do something based on a variable being non-zero)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Problem Set for MS
« Reply #6 on: May 24th, 2006, 6:49am » |
Quote Modify
|
This should just about do it too.. I think.
I know, I know, it's horrendous 
Code:
function divide(a,b)
{
res=0;
div=b;
loop(a)
{
dec(b);
b2 = b;
loop (div) // add div to b2
b2++;
res++; // increment our result
loop(b) // if non-zero
{
dec(res); // undo increment
b = subtract(b2, div); // undo addition
}
}
return res;
}
|
|
I suppose it warrants some explanation.
Basicly it follows the idea of repeatedly subtracting b from a. To do this, we first store b in div (so we don't destroy our divider), and subtract 1 at a time from b while we loop through a.
In each loop we add div to b, and if b isn't 0 enter the b-loop and subtract div again (undoing our change). If b is 0 the loop does nothing and b will be div, ready for another count-down.
The same do/undo thing is used for counting the number of times we subtracted b from a. Add 1 at the start of the a-loop, and subtract it in the b-loop (when we haven't reached 0 yet).
|
| « Last Edit: May 24th, 2006, 7:23am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Problem Set for MS
« Reply #7 on: May 24th, 2006, 8:11am » |
Quote Modify
|
I see where you're going with that, but I don't think it works: if b is non-zero the undo loop happens b times, not just once...
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Problem Set for MS
« Reply #8 on: May 24th, 2006, 8:22am » |
Quote Modify
|
How about this: q is the quotient; r is the remainder; s is a boolean flag; t is a temporary. We use towr's method to set s to 1 if t is 0 and 0 otherwise. For a remainder (modulus) function, just return r instead of q.
Code:function divide(a, b) // divide a by b
begin
t = b; q = 0; r = 0;
loop(a) [
inc r;
t = dec(t);
s = 0; inc s; // set s = 1
loop(t) [ s = 0; ] // set s = 0 iff t > 0
loop(s) [ inc q; r = 0; t = b; ] // increment and reset iff t == 0
]
return q;
end |
|
[edit]removed an unnecessary dec(s)[/edit]
--SMQ
|
| « Last Edit: May 24th, 2006, 8:29am by SMQ » |
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Problem Set for MS
« Reply #9 on: May 24th, 2006, 2:26pm » |
Quote Modify
|
on May 24th, 2006, 8:11am, SMQ wrote:| I see where you're going with that, but I don't think it works: if b is non-zero the undo loop happens b times, not just once... |
|
Well, that's not a problem unless the variables that are changed are both on the left and right side of the assignment.
Unfortunately I miscorrected what happens to the 'res' variable (in fact nothing happens with it now, since dec(res) should be assigned to something)
But since neither b2 nor div is changed, b = subtract(b2,div) will have the same value no matter how often you evaluate it.
It's easy to fix the 'res' bit. Though still not pretty.
I like your version better anyway. It's neater and more efficient.
|
| « Last Edit: May 24th, 2006, 2:31pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sonYoak
Newbie
Posts: 2
|
|
Re: Problem Set for MS
« Reply #10 on: Nov 7th, 2006, 4:03pm » |
Quote Modify
|
I think you can use recursion to solve for Q1 part 3 too. For a / b = q
Code:div(a, b)
begin
q = 0; a1 = increment(a);
loop(a1 - b)
q = 1 + div(a - b, b);
return q;
end
|
|
When answering questions like these, is it better to give a recursive answer or non-recursive answer?
|
| « Last Edit: Nov 7th, 2006, 4:04pm by sonYoak » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Problem Set for MS
« Reply #11 on: Nov 7th, 2006, 4:33pm » |
Quote Modify
|
on Nov 7th, 2006, 4:03pm, sonYoak wrote:| When answering questions like these, is it better to give a recursive answer or non-recursive answer? |
|
I am not sure recursion is allowed in this case...
|
|
IP Logged |
|
|
|
Dagny
Newbie
Posts: 4
|
|
Re: Problem Set for MS
« Reply #12 on: Nov 19th, 2006, 4:53am » |
Quote Modify
|
Reply to Q2
Store the 2-byte character in byte reversed order(i.e. right byte is stored in the left and vice versa).
while retrieving(using) keep the reversed byte in mind for 2-byte characters.
While deleteing just check for the first bit of the last byte of current data, if it is 0 delete 1 byte otherwise delete last 2 bytes.
|
| « Last Edit: Nov 19th, 2006, 4:55am by Dagny » |
IP Logged |
|
|
|
svanloon
Newbie
Posts: 1
|
|
Re: Problem Set for MS
« Reply #13 on: Jan 24th, 2007, 9:47am » |
Quote Modify
|
Here's my java implementation. It seems to work.
public class Number {
public static void main(String[] args) {
Number number = new Number();
int originalNumber = 10;
int subtractor = 6;
int result = number.subtract(originalNumber, subtractor);
System.out.println(result);
}
private int decrementByOne(int originalNumber) {
int result = 0;
for(int i = 0; i < originalNumber; i++) {
result = i;
}
return result;
}
private int subtract(int x, int y) {
int result = x;
for(int temp = 0; temp < y ; temp++) {
result = decrementByOne(result);
}
return result;
}
}
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print