russs
BAN USERThis is an interesting question. At first glance, this is a graph search, either BFS or DFS. On another thought, the input stream seems already indexed, more like a NoSQL table input, or stream data in HDFS. Consider this is an Amazon question, you should consider this question as a big data question with inputs from distributed file systems.
The solution is just a simple key based inquiry with concurrent threads.
Implement using asynchronized tasks, then aggregate and deduplicate on the results returned from tasks based on the level of associations.
I believe this answer is what Amazon wants. If you go with the graph approach, you will enter the interviewer's trap, then he will follow up with memory limitation etc questions.
interface RateLimit
{
/** Sets the rate, from 1 to 1000000 queries per second */
void setQPS(int qps);
/** accept or reject a request, called when request is received */
bool allowThisRequest();
}
/// <summary>
///
/// </summary>
public class RatingThrottler : RateLimit
{
private long lastTick = 0;//DateTime.UtcNow.Ticks
private long waitPeriod = 0;//default no throttling
private const long NUM_TICKS_PER_SECOND = 10000 * 1000000; //10k ticks per ms
private object syncLock = new object();
public void setQPS(int qps)
{
waitPeriod = NUM_TICKS_PER_SECOND / qps;
}
public bool allowThisRequest()
{
long curTick = DateTime.UtcNow.Ticks;
lock(syncLock){
if ( curTick - lastTick >= waitPeriod)
{
lastTick = curTick;
return true;
}
}
return false;
}
}
It is 50/50 based on odds, since every birth is independent thing.
Since this is brain teaser, you won't get 100 points if you only answer this.
The boy/girl number is even in total. But those families with multiple children will likely have more boys than girls. It is a fact that, with fixed income, the more children you have, the less you can support for each child. So on average the education, medical care for each boy is lower than each girl. As a result of natural death of disease, boys have more fatal rates. So in 20 years, the number of girls should be larger than boys.
Serialization: BFS, assign each node an ID using binary map. Root node ID: 1. Then assign left child node a 0 in a new bit, the right child node a 1, such as 01, 11. Finally store all nodes in a sequence of key value pairs of [ Node.ID, Node.Value]
- russs June 25, 2015