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

        riddles >> cs >> MS/Google interview questions (II)
        
(Message started by: Ivan on Sep 28th, 2006, 12:29am)
Title: MS/Google interview questions (II)
Post by Ivan on Sep 28th, 2006, 12:29am
Let's continue ... :-)

Q1. Say you want to bid something. And you will win if your bid Y is larger than the actual value of the item X, which uniformly distributed over (0, 100). If you win, the item's value will increase by 50% (that is, your profit will be 1.5X-Y). If you lose, you get / lose nothing (i.e., profit 0).

Now tell me what your strategy will be to maximize your profit.

Q2. You tear a piece of paper into n parts. Give an algorithm to piece those n parts back to the original paper.

Q3. Using OO to design a chess system.  
Title: Re: MS/Google interview questions (II)
Post by towr on Sep 28th, 2006, 1:14am
Q1:
[hide]maximize  
[int] 0y 1.5x-y dx
= - 0.25 y2
So pick y = 0, or just don't bet[/hide]
Title: Re: MS/Google interview questions (II)
Post by TenaliRaman on Oct 6th, 2006, 11:17am
Q3>
I have been recently working on a checkers system and trying to design it in OO paradigm. For some reason, i feel OO is not the best paradigm to go for when working with such board games.

In any case, this is the kind of design i would go for (C/S model),

Class BoardSimulator
--Stores Board Positions
--Simulates moves

Class BoardRender extends BoardSimulator(If GUI needed)
--Renders Board State on Screen
--Acts as a server, opens 0-2 sockets for 0-2 players to connect
(0 sockets == 2 human players, 1 socket == human vs computer, 2 socket == computer vs computer)
--Can communicate board state to the players and reads their moves
--Should have interface to accept inputs from human players

Abstract Class PlayerEngine (if equipped with AI player)
--Connects to server
--Reads board position and comes up with a move based on whatever technique used
--The move generator technique should be defined as virtual, so that several player engines can be utilised

I had something similar going for checkers. For some reason, if i try to break the classes further, it only became a mess on paper. Cant say if this is the best way to do it, infact, if someone has a better idea, i would like to hear it out.

-- AI
Title: Re: MS/Google interview questions (II)
Post by vivekv16 on Nov 7th, 2006, 12:26am
Lets say you bid Y, you will start earning profits if X is in between (2/3)*Y and Y. So, you if you maximize 1/3*Y, that will give you the best chance of earning a profit. And that is maximized at Y=100.

So, always bid 100?  
Title: Re: MS/Google interview questions (II)
Post by Grimbal on Nov 7th, 2006, 1:03am
I don't think so.

I assume the profit is zero if X>Y and (1.5X - Y) if X<=Y.

Once we have fixed a bet Y we can ignore the cases X>Y, so X is uniformly distributed between 0 and Y.  The profit is then uniformly distributed between -Y and +Y/2  Obviously there is a loss on average.

So, bet 0.
Title: Re: MS/Google interview questions (II)
Post by vivekv16 on Nov 7th, 2006, 9:04am
Im sorry, I think I assumed there are no losses. Wording it as "profit will be 1.5X - Y" made me think that you just earn nothing if 1.5X is less than Y.
Title: Re: MS/Google interview questions (II)
Post by Ivan on Nov 26th, 2006, 12:02pm
I think the formula should be the following:
1/y int] 0y 1.5x-y dx
= - 0.25 y
...

on 09/28/06 at 01:14:34, towr wrote:
Q1:
[hide]maximize  
[int] 0y 1.5x-y dx
= - 0.25 y2
So pick y = 0, or just don't bet[/hide]
Title: Re: MS/Google interview questions (II)
Post by towr on Nov 26th, 2006, 12:57pm

on 11/26/06 at 12:02:44, Ivan wrote:
I think the formula should be the following:
1/y int] 0y 1.5x-y dx
= - 0.25 y
...
The whole integration interval actually has length 1, but the function is 0 from y to 1, so it'd be
1/1 ([int] 0y 1.5x-y dx + [int] y1 0 dx ),
but that's just [int] 0y 1.5x-y dx
Title: Re: MS/Google interview questions (II)
Post by Ivan on Nov 26th, 2006, 6:14pm

on 11/26/06 at 12:57:42, towr wrote:
The whole integration interval actually has length 1, but the function is 0 from y to 1, so it'd be
1/1 ([int] 0y 1.5x-y dx + [int] y1 0 dx ),
but that's just [int] 0y 1.5x-y dx


Yeah, you are right. Sorry that I forgot this.
Title: Re: MS/Google interview questions (II)
Post by towr on Nov 27th, 2006, 1:06am

on 11/26/06 at 18:14:41, Ivan wrote:
Yeah, you are right. Sorry that I forgot this.
Don't worry about it, I forgot about it too. Took me a while to remember why I did it that way  ;D
Title: Re: MS/Google interview questions (II)
Post by satish1004 on Dec 17th, 2006, 9:45am
can u plz explain me clearly about your function @  towr

i didn't understand tht  :(
Title: Re: MS/Google interview questions (II)
Post by towr on Dec 17th, 2006, 10:57am

on 12/17/06 at 09:45:35, satish1004 wrote:
can you pleazse explain to me clearly about your function @  towr

i didn't understand that  :(
You have choice of Y; so you want to see what happens on average, given some Y.
There are two cases to consider. Either Y will be smaller than (or equal to) X, in which case you will neither have a profit or a loss; or Y is greater, in which case your profit is 1.5X-Y.
The average profit will therefore be the integral (http://mathworld.wolfram.com/Integral.html) over this function, divided by the interval length. However, the interval length is a constant, so Y will be maximized at the same point regardless of what it is (as long as it's positive).
Title: Re: MS/Google interview questions (II)
Post by shishir85 on Feb 8th, 2007, 11:28pm

on 09/28/06 at 01:14:34, towr wrote:
Q1:
[hide]maximize  
[int] 0y 1.5x-y dx
= - 0.25 y2
So pick y = 0, or just don't bet[/hide]

towr, I think the integral should be:
(1/100)[int] 0y 1.5x-y dx
Though this would not affect answer.

As you can see here (http://en.wikipedia.org/wiki/Uniform_distribution_%28continuous%29) probability density function of a uniform distribution is given by f(x) = 1/(b-a) when a<x<b.

An example: if we try to compute mean of a uniform distribution, we do something like this:
(1/b-a)[int]ab x dx
= (b+a)/2
Title: Re: MS/Google interview questions (II)
Post by towr on Feb 9th, 2007, 1:12am

on 02/08/07 at 23:28:26, shishir85 wrote:
Though this would not affect answer
Indeed it wouldn't, which is why I left it out. And someone else mentioned before as well ;)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board