wu :: forums - Print Page


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

        riddles >> cs >> Problem Set for MS 
        
(Message started by: tuxilogy on May 16^th, 2006, 7:57am)

Title: Problem Set for MS
Post by tuxilogy on May 16^th, 2006, 7:57am

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

Title: Re: Problem Set for MS
Post by SMQ on May 16^th, 2006, 9:00am

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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1146281214) 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

Title: Re: Problem Set for MS
Post by tuxilogy on May 23^rd, 2006, 10:01am

Please give me some sugestions...

Title: Re: Problem Set for MS
Post by Barukh on May 24^th, 2006, 5:27am

Q1 part 1 maybe implemented as follows:

Code:

func dec( v )
begin
d = 0
loop ( v ) [ dc = d; d ++ ]
ret dc
end

Title: Re: Problem Set for MS
Post by SMQ on May 24^th, 2006, 6:03am

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

Title: Re: Problem Set for MS
Post by towr on May 24^th, 2006, 6:37am

You could perhaps use recursion.
(You can use a loop to do something based on a variable being non-zero)

Title: Re: Problem Set for MS
Post by towr on May 24^th, 2006, 6:49am

This should just about do it too.. I think.
I know, I know, it's horrendous ;D

Code:

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).

Title: Re: Problem Set for MS
Post by SMQ on May 24^th, 2006, 8:11am

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

Title: Re: Problem Set for MS
Post by SMQ on May 24^th, 2006, 8:22am

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

Title: Re: Problem Set for MS
Post by towr on May 24^th, 2006, 2:26pm

on 05/24/06 at 08:11:27, 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.

Title: Re: Problem Set for MS
Post by sonYoak on Nov 7^th, 2006, 4:03pm

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?

Title: Re: Problem Set for MS
Post by Barukh on Nov 7^th, 2006, 4:33pm

on 11/07/06 at 16:03:48, 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...

Title: Re: Problem Set for MS
Post by Dagny on Nov 19^th, 2006, 4:53am

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.

Title: Re: Problem Set for MS
Post by svanloon on Jan 24^th, 2007, 9:47am

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;
}
}