DO
BAN USER- 1of 1 vote
AnswersGiven two strings containing only numbers, return product of the two strings. Strings are large so conversion to interger is not possible.
- DO in United States for High Availability| Report Duplicate | Flag | PURGE
VMWare Inc Staff Engineer Algorithm - 0of 0 votes
AnswersYour code is inside a service that receives a large stream of integers, large enough that it can't be stored on any disk. You don't know the how many integers will be there on the stream. You have to write a sampler which selects K integers such that likelihood of selecting any integer from the stream is equal.
- DO in United States for Compute| Report Duplicate | Flag | PURGE
Digital Ocean IC3 Algorithm
Idea is to Keep a stack and push every element to stack but before that pop out all elements that are smaller and update its daysToWarm. Notice we push indices on stack. By virtue of this algo notice Stack always contains elements in increasing order from top i.e. top one smallest. Since each element gets pushed and popped from stack atmost once time complexity is O(n). Here is a c++ version.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void
daysToBeWarm(vector<int> &dailyTemp, vector<int> &daysToWarm)
{
stack<int> S;
for(int i=0; i<dailyTemp.size(); i++)
{
while(!S.empty() && dailyTemp[i]>dailyTemp[S.top()])
{
daysToWarm[S.top()] = i-S.top();
S.pop();
}
S.push(i);
}
}
int
main(int argc, char *argv[])
{
vector<int> dailyTemp;
int i;
while(1)
{
cin>>i;
if(i!=-1)
dailyTemp.push_back(i);
else
break;
}
vector<int> daysToWarm(dailyTemp.size(),0);
daysToBeWarm(dailyTemp,daysToWarm);
for(int i=0;i<daysToWarm.size();i++)
cout<<daysToWarm[i]<<" ";
}
Trivial case: 0 white prob 0; 0 red prob 1
Otherwise each pick can have 3 outcomes 1. pick white and eat it. 2. pick red and eat, if last pick put red back 3. pick red and put back.
Each outcome gives a new sample (1) gives w-1,r while (2) gives w, r-1 and (3) gives w,r but last red put back is true
Recursively calculate probability of last white in each of 3 outcomes. Then multiply result of each outcome with the probability of that outcome. And you have your result. Here is a solution using DP with memoization:
- DO December 07, 2017