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()] = iS.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]<<" ";
}

DO
November 27, 2017 Open Chat in New Window
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 w1,r while (2) gives w, r1 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