Join Us
Loading Similar Posts
Entering edit mode
Avg CTC: 18lpa
Role: Summer Analyst
Job Link: Technology Summer Analyst Program
Question 1
Click here to Practice
Submit Problem to OJ
An online reselling app, Keeto, allows vendors to resell items online to their customers. The prices of the items could rise and fall every day. The vendor can purchase an item one day and sell that item on any of the following days. To buy the item on a particular day the vendor has to sell any previous items. The app designers have been given the task to analyze the fluctuations in the prices of an item and calculate the maximum profit that a vendor can earn from buying and selling the items in atmost K transactions. One transaction is counted for a purchase+sale of an item. So, maximum profit will be analysed for at most k transactions.
Given the prices of an item for N days, write an algorithm to find the maximum profit that a vendor can earn from buying and selling the items at most k times.
Input
The first line of the input consists of an integer - num, representing the number of days for which the prices of items are given (N).
The next line consists of N space-separated integers - priceDay0, priceDay1,..............., priceDayN-1, representing the price of an item on that particular day.
The last line consist of an integer - kTransaction representing the transactions to be analysed (K).
Output
Print an integer representing the maximum profit that a vendor can earn from buying and selling the items at most in k transactions.
Constraints
0 <= kTransaction < num <= 500
0 <= priceDay0, priceDay1,..............., priceDayN-1 <= 10^9
Example
Input:
6
5 20 10 30 50 70
2
Output:
75
Question 2
A product manufacturing company label all their products. They manage the production by creating an online hierarchy on their website. In the hierarchy, they maintain the number of products manufactured in their company for every product. Each product is denoted as a node in the hierarchy whose value denotes the number of manufactured products of that product. The oldest product of the company is made the root of the hierarchy. The related products are connected by a relational edge in the hierarchy. The manufacturing team wants to analyze the data of manufactured products which are present within the given range X i.e. range [low, high] including the low and high. Range X is denoted as [low, high] i.e., low denotes the products which are available in minimum quantity and high denotes the maximum quantity of manufactured products. They will then use this data to fulfill their orders.
Write an algorithm that will output the list of quantities of products which are available in that given range.
Input
The first line of the input consists of two integers - numRelEdges and constant, representing the number of relational edges in the hierarchy (N) and a constant number whose value is always 2.
The next N lines consist of two space-separated integers representing the quantities of the manufactured products of the two products which are connected by a relational edge in the hierarchy. The first value in the first line will be of the oldest product of the company.
The next line consists of an integer - numProd, representing the number of products (M).
The next line consists of M space-separated integers - manufacProd0, manufacProd1,........., manufacProdM-1 representing the manufactured products of respective product IDs.
The next line consists of an integer - low representing the low values of the range of the quantities of the manufactured products required for the analysis.
The last line consists of an integer - high representing the high values of the range of the quantities of the manufactured products required for the analysis.
Output
Print space-separated integers representing the quantities of unique products sorted in ascending order which are available in that given range [low, high] inclusive of low and high. If the product quantities are not available in that given range then print -1.
Example:
Input
4 2
0 1
1 2
1 3
1 4
5
14 3 19 4 10
4
18
Output
4 10 14
Explanation:
The hierarchy is as follows:
0(14)
/ \
(3)1 2(19)
/ \
(4)3 4(10)
The range for analysis as [low,high]:[4,18]
The quantities of the manufactured products available in the hierarchy are: 14, 3, 19, 4, 10.
The quantities that lie within the given range are: 4, 10, 14.
Question 3
Click here to Practice
Submit Problem to OJ
An online streaming application wishes to analyze the popularity of the web series streaming on their application. Every web series is given a unique ID. The users have voted for their one of the most favorite web series. To analyze the popularity of the web series, the marketing team has picked N users (with ID 0 to N-1) of the application and recorded the ID of the web series voted by the users. The marketing team analyze the web series in batches of size K. The first batch consists of web series voted by users with IDs 0 to K-1. For the next batch, the web series of the first user with ID 0 is removed from the left side and the web series of the next user with ID is added from the right side and so on for further batches until the Nth user (with ID N-1). For every batch, the maximum number of votes for a web series needs to be recorded. The marketing team manager wants to add this feature in their system to save the team's time.
Write an algorithm to find the maximum number of votes for a web series for every batch.
Input
The first line of the input consists of an integer - numUsers, representing the number of users (N).
The second line consists of N space-separated integers - wsID[0], wsID1......., wsID[N-1], representing the ID of the web series voted by the users.
The last line consists of an integer- batch Size, representing the number of web series included in a batch for analysis (K).
Output
Print space-separated integers representing the maximum number of votes for a web series for every batch.
Constraints
1 <= batchSize <= numUsers < 1000
-10^6 < wsID[0], wsID1,......., wsID[N-1] < 10^6
Example
Input:
6
20 10 20 16 40 40
3
Output:
2 1 1 2
Explanation:
In the first batch, the web series with ID 20 is voted by a maximum of 2 users.
In the second batch, every web series is voted by 1 user only.
In the third batch, every web series is voted by 1 user only.
In the fourth batch, the web series with ID 40 is voted by a maximum of 2 users.
So, the output is [2, 1, 1, 2].
Entering edit mode
Solution to problem 1
Analysis
We can solve the problem using dynamic programming. Let dp[day][k][state] denote the max profit obtained by performing exactly k transactions until day day such that state is a binary value depicting if we currently have a stock unit bought. More formally,
state = 0implies that we don't have a stock unit bought and we can buy a new stock unit right away.state = 1implies that we have a stock unit currently and we should sell it before we can buy any more new units.
Now, we can use the following transitions for the dynamic programming defined above :
- From
dp[day][k][1], we can sell the stock at the costprice[day]and move todp[day+1][k+1][0]. - From
dp[day][k][0], we can buy the stock at the costprice[day]and move todp[day+1][k][1].
Thus we can solve the problem in a time complexity of O(N*K) using the dynamic programming solution explained.
PseudoCode
For an interview setup, the most optimal implementation of this solution is listed below with a space complexity of O(K).
maxProfit(prices, k):
// dp[k][state] -> We have performed k transactions so far and state determines my current state
// if we have a stock (state=1) i can go to dp[k+1][0] by selling the current stock
// if we dont have a stock (state=0) i can go to dp[k][1] by buying the current stock
dp[][] = new int[k+1][2]{-inf} //create dp as a k+1x2 array initialised with -inf
dp[0][0] = 0 //base case : 0 transactions with no stock in hand => 0 profit
for(price in prices): //iterate through the prices array containing the prices of the stock for the n days
for transactions_so_far from k-1 down to 0:
//if state is 1, we have a stock to sell and we perform one more transaction on this day.
dp[transactions_so_far+1][0] = max(dp[transactions_so_far+1][0], dp[transactions_so_far][1] + price)
//if state is 0, we can buy stock today
dp[transactions_so_far][1] = max(dp[transactions_so_far][1], dp[transactions_so_far][0] - price)
return max(dp)
Remarks
It is possible to solve this problem in a time complexity of O(NlogK) and even O(N) but for the given constraints, the explained solution will work just fine.
Entering edit mode
Solution to Problem 3
Analysis
The given problem can be solved by the sliding window technique. We can maintain a hashmap to keep track of the frequency of the elements in our current window. Also we maintain a Self Balancing BST (which can handle duplicates) which stores the frequencies of the elements in our window. Now we can simply find the maximum frequency of some element in the current window in O(logN) through the BST. As we move our window, we update the frequency of the elements in the hashmap and the BST, thereby maintaining the invariant. The solution works in a time complexity of O(NlogK) and a space complexity of O(N).
PseudoCode
solve(votes, k):
freq = new hashmap //hashmap to maintain the frequency of elements in current window
counts = new BST //BST that stores the frequencies of the elements in the current window
ans = new int[]
for i from 1 to N: //add the new scanned element
if(freq[votes[i]] != 0): //if the old frequency is not zero, we remove the old frequency from the BST
counts.erase(freq[votes[i]])
freq[votes[i]]++ //increase the frequency and the new frequency to the BST
counts.insert(freq[votes[i]])
if(i>k): //if we have scanned more than k elements so far, we need to remove some element
counts.erase(freq[votes[i-k]]) //remove the old frequency of the element to be removed from the BST
freq[votes[i-k]]-- //decrement the frequency
if(freq[votes[i-k]] != 0): //if the frequency does not become zero, add the new frequency to the BST
counts.insert(freq[votes[i-k]])
if(i>=k): //if we have scanned atleast k elemnts we append the max element in the BST to the ans array
ans.append(counts.max())
return ans
Entering edit mode
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001][2];
long long solve(vector<long long> &arr, long long n, long long k, long long i, long long val) {
if (i >= n || k == 0)
return 0;
long long take = 0;
long long not_take=0;
if (dp[i][k][val] != -1)
return dp[i][k][val];
if (val == 0) {
take = - arr[i]+solve(arr, n, k, i + 1, 1) ;
} else {
take = arr[i]+solve(arr, n, k - 1, i + 1, 0) ;
}
not_take = solve(arr, n, k, i + 1, val);
long long ans=max(take,not_take);
return dp[i][k][val] = max(take, not_take);
}
int main() {
long long t;
cin >> t;
while (t--) {
long long n, k;
cin >> n >> k;
vector<long long> arr(n);
for (long long i = 0; i < n; i++) {
cin >> arr[i];
}
memset(dp, -1, sizeof(dp));
long long x = solve(arr, n, k, 0, 0);
cout << x << endl;
}
return 0;
}
Q-why this code is not working for all the test case while the similar code is working(given below)?
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[1001][1001][2];
ll func(ll idx,ll flag,vector<ll> &a,ll k,ll n)
{
if(idx==n)
{
return 0;
}
if(k==0)
{
return 0;
}
if(dp[idx][k][flag]!=-1)
{
return dp[idx][k][flag];
}
ll ans;
ll ntake = 0,take = 0;
if(flag==0)
{
take = -a[idx]+func(idx+1,1,a,k,n);
}
else
{
take = a[idx]+func(idx+1,0,a,k-1,n);
}
ntake = func(idx+1,flag,a,k,n);
ans = max(take,ntake);
return dp[idx][k][flag] = max(take,ntake);
}
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n,k;
cin>>n>>k;
memset(dp,-1,sizeof(dp));
vector<ll> a(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<func(0,0,a,k,n)<<endl;
}
}
this one is working ... why not the first one
