Author |
Topic: MS/Google interview questions (II) (Read 5713 times) |
|
Ivan
Junior Member
Gender: 
Posts: 70
|
 |
MS/Google interview questions (II)
« on: Sep 28th, 2006, 12:29am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: MS/Google interview questions (II)
« Reply #1 on: Sep 28th, 2006, 1:14am » |
Quote Modify
|
Q1:
maximize
[int] 0y 1.5x-y dx
= - 0.25 y2
So pick y = 0, or just don't bet
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: MS/Google interview questions (II)
« Reply #2 on: Oct 6th, 2006, 11:17am » |
Quote Modify
|
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
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
vivekv16
Newbie
Posts: 2
|
|
Re: MS/Google interview questions (II)
« Reply #3 on: Nov 7th, 2006, 12:26am » |
Quote Modify
|
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?
|
| « Last Edit: Nov 7th, 2006, 12:27am by vivekv16 » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: MS/Google interview questions (II)
« Reply #4 on: Nov 7th, 2006, 1:03am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
vivekv16
Newbie
Posts: 2
|
|
Re: MS/Google interview questions (II)
« Reply #5 on: Nov 7th, 2006, 9:04am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 7th, 2006, 9:05am by vivekv16 » |
IP Logged |
|
|
|
Ivan
Junior Member
Gender:
Posts: 70
|
|
Re: MS/Google interview questions (II)
« Reply #6 on: Nov 26th, 2006, 12:02pm » |
Quote Modify
|
I think the formula should be the following:
1/y int] 0y 1.5x-y dx
= - 0.25 y
...
on Sep 28th, 2006, 1:14am, towr wrote:Q1:
maximize
[int] 0y 1.5x-y dx
= - 0.25 y2
So pick y = 0, or just don't bet
|
|
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: MS/Google interview questions (II)
« Reply #7 on: Nov 26th, 2006, 12:57pm » |
Quote Modify
|
on Nov 26th, 2006, 12:02pm, 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
|
| « Last Edit: Nov 26th, 2006, 12:58pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Ivan
Junior Member
Gender:
Posts: 70
|
|
Re: MS/Google interview questions (II)
« Reply #8 on: Nov 26th, 2006, 6:14pm » |
Quote Modify
|
on Nov 26th, 2006, 12:57pm, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: MS/Google interview questions (II)
« Reply #9 on: Nov 27th, 2006, 1:06am » |
Quote Modify
|
on Nov 26th, 2006, 6:14pm, 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 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
satish1004
Newbie
Posts: 2
|
|
Re: MS/Google interview questions (II)
« Reply #10 on: Dec 17th, 2006, 9:45am » |
Quote Modify
|
can u plz explain me clearly about your function @ towr
i didn't understand tht 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: MS/Google interview questions (II)
« Reply #11 on: Dec 17th, 2006, 10:57am » |
Quote Modify
|
on Dec 17th, 2006, 9:45am, 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 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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
shishir85
Newbie
 
Gender:
Posts: 19
|
|
Re: MS/Google interview questions (II)
« Reply #12 on: Feb 8th, 2007, 11:28pm » |
Quote Modify
|
on Sep 28th, 2006, 1:14am, towr wrote:Q1:
maximize
[int] 0y 1.5x-y dx
= - 0.25 y2
So pick y = 0, or just don't bet
|
|
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 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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: MS/Google interview questions (II)
« Reply #13 on: Feb 9th, 2007, 1:12am » |
Quote Modify
|
on Feb 8th, 2007, 11:28pm, 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 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print