Remove Stones to Minimize the Total

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:

• Choose any piles[i] and remove floor(piles[i] / 2) stones from it.

Notice that you can apply the operation on the same pile more than once.

Return the minimum possible total number of stones remaining after applying the k operations.

floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).

Example 1:

Input: piles = [5,4,9], k = 2
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [5,4,5].
- Apply the operation on pile 0. The resulting piles are [3,4,5].
The total number of stones in [3,4,5] is 12.

Example 2:

Input: piles = [4,3,6,7], k = 3
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 3. The resulting piles are [4,3,3,7].
- Apply the operation on pile 4. The resulting piles are [4,3,3,4].
- Apply the operation on pile 0. The resulting piles are [2,3,3,4].
The total number of stones in [2,3,3,4] is 12.

Approach

Java

import java.util.Collections;
import java.util.PriorityQueue;

public class MinimumStoneSum {
    public static void main(String[] args) {

        int[] piles = { 5, 4, 9 };
        int k = 2;

        System.out.println(minStoneSum(piles, k));

    }

    static int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> q = new 
        PriorityQueue<Integer>( Collections.reverseOrder());

        for (int i = 0; i < piles.length; i++)
            q.add(piles[i]);

        while (k > 0 && q.size() > 0) {
            int x = q.peek();
            if (x > 1) {
                
                   q.poll;
                q.add((x + 1) / 2);
            }
            k--;
        }
        int sum = 0;
        while (!q.isEmpty()) {
            sum += q.poll();

        }
        return sum;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int minStoneSum(vector<int> &piles, int k)
{

    priority_queue<int> q;

    for (int i = 0; i < piles.size(); i++)
        q.push(piles[i]);

    while (k > 0 && q.size() > 0)
    {
        int x = q.top();
        if (x > 1)
        {
            q.pop();

            q.push((x + 1) / 2);
        }
        k--;
    }
    int sum = 0;
    while (!q.empty())
    {
        sum += q.top();
        q.pop();
    }
    return sum;
}
int main()
{
    vector<int> piles = {5, 4, 9};
    int k = 2;

    cout << minStoneSum(piles, k) << "\n";

    return 0;
}

Flight Discount

Your task is to find a minimum-price flight route from Syrjala to Metsala. You have one discount coupon, using which you can halve the price of any single flight during the route. However, you can only use the coupon once.

Example:

Input:  n = 3, m = 4, edges = {{1, 2, 3}, {2, 3, 1}, {1, 3, 7}, {2, 1, 5}}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const long long inf = 10000000000000000LL;

const long long N = 100005;
long long vis[N];
long long dis1[N], dis2[100005];

void dijkistrasAlgorithm(long long s, long long dis[],
                         vector<pair<long long, long long>> adj[])
{
    priority_queue<pair<long long, long long>> q;

    //initialize with very big number
    for (int i = 1; i < N; i++)
        dis[i] = inf;
    dis[s] = 0;
    q.push({0, s});

    //mark visited array as not visited
    memset(vis, 0, sizeof(vis));

    //iterate till the end of queue
    while (!q.empty())
    {

        long long a = q.top().second;

        //remove from the queue
        q.pop();

        //if already visited
        if (vis[a])
            continue;

        //mark as visited
        vis[a] = 1;
        for (auto edge : adj[a])
        {
            long long b = edge.first;
            long long w = edge.second;

            //relaxation
            if (dis[a] + w < dis[b])
            {
                dis[b] = dis[a] + w;
                q.push({-dis[b], b});
            }
        }
    }
}

long long flightDiscount(int n, int m,
                         vector<vector<long long>> &edges)
{

    vector<pair<long long, long long>> adj1[n + 1];
    vector<pair<long long, long long>> adj2[n + 1];

    for (long long i = 0; i < m; i++)
    {
        long long a = edges[i][0];
        long long b = edges[i][1];
        long long w = edges[i][2];

        adj1[a].push_back({b, w});
        adj2[b].push_back({a, w});
    }
    dijkistrasAlgorithm(1, dis1, adj1);
    dijkistrasAlgorithm(n, dis2, adj2);
    long long mn = inf;
    for (auto edge : edges)
    {
        long long a = edge[0];
        long long b = edge[1];
        long long w = edge[2];
        mn = min(mn, dis1[a] + dis2[b] + w / 2);
    }
    return mn;
}
int main()
{

    long long n = 3, m = 4;

    vector<vector<long long>> edges = {{1, 2, 3},
                                       {2, 3, 1},
                                       {1, 3, 7},
                                       {2, 1, 5}};

    cout << flightDiscount(n, m, edges) << "\n";

    return 0;
}

Implement a queue using two stacks

Implement a queue using two stacks. Recall that a queue is a FIFO (first-in, first-out) data structure with the following methods: enqueue, which inserts an element into the queue, and dequeue, which removes it.

Example:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

class MyQueue
{
public:
    stack<int> s1;
    stack<int> s2;

    void push(int x)
    {
        while (!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }
        s1.push(x);
        while (!s2.empty())
        {
            s1.push(s2.top());
            s2.pop();
        }
    }
    int pop()
    {
        int x = s1.top();
        s1.pop();
        return x;
    }
    int peek()
    {
        return s1.top();
    }
    bool empty()
    {
        int flag = 0;
        if (s1.empty())
            flag = 1;
        return flag;
    }
};

int main()
{
    MyQueue myQueue;
    myQueue.push(1);
    myQueue.push(2);

    cout << "[";
    cout << myQueue.peek() << ", ";
    cout << myQueue.pop() << ", ";
    if (myQueue.empty())
        cout << "true";
    else
        cout << "false";

    cout << "]";

    return 0;
}

Reverse String while maintaining relative order of delimiters

Given a string and a set of delimiters, reverse the words in the string while maintaining the relative order of the delimiters. For example, given "hello/world:here", return "here/world:hello"

Example:

Input:  str = "hello/world:here", delimeters = {':', '/'}
Output: here/world:hello

Approach

C++

#include <bits/stdc++.h>
using namespace std;

string delimiterReverse(string str,
                        vector<char> &delimiters)
{
    string res = "";
    queue<char> delimitersFound;
    stack<string> words = stack<string>();
    int lastIndex = 0;

    for (int i = 0; i < str.length(); ++i)
    {
        for (int j = 0; j < delimiters.size(); ++j)
        {
            if (str[i] == delimiters[j])
            {
                delimitersFound.push(str[i]);
                words.push(str.substr(lastIndex, i - lastIndex));
                lastIndex = i + 1;
                break;
            }
        }
        if (i == (str.length() - 1) && (str[i] !=
                                        delimitersFound.front()))
        {
            words.push(str.substr(lastIndex, i - lastIndex + 1));
        }
    }
    while (!words.empty())
    {
        if (!words.empty())
        {
            res += words.top();
            words.pop();
        }
        if (!delimitersFound.empty())
        {

            res += delimitersFound.front();
            delimitersFound.pop();
        }
    }
    return res;
}

int main()

{

    string str = "hello/world:here";

    vector<char> delimiters = {':', '/'};
    cout << delimiterReverse(str, delimiters);

    return 0;
}

Running median of a sequence

Compute the running median of a sequence of numbers. That is, given a stream of numbers, print out the median of the list so far on each new element.

Recall that the median of an even-numbered list is the average of the two middle numbers.

For example, given the sequence [2, 1, 5, 7, 2, 0, 5], your algorithm should print out:

Example:

Input:  arr = [2,1,5,7,2,0,5]
Output: [2, 1.5, 2, 3.5, 2, 2, 2]

Approach

C++

#include <bits/stdc++.h>
using namespace std;

//maximum priority queue
priority_queue<double> max1;

//minimum priority queue
priority_queue<double, vector<double>, greater<double>> min1;

//variable to hold the median
double median = 0;

//add numner into the priority
//queues
void addNum(int num)
{

    //if both are of equal size

    if (max1.size() == min1.size())
    {

        //if current element is
        //greter than median then
        //push into minimum priority
        //queue and set meadin as top
        //of min priority queue
        if (num > median)
        {
            min1.push(num);
            median = min1.top();
        }

        //else push into the max  queue
        //and set median as top of max queue
        else
        {
            max1.push(num);
            median = max1.top();
        }
    }

    //if min size is more
    else if (min1.size() > max1.size())
    {

        //if element is more than median
        //then push the top of min into max
        //and current element into the min
        if (num > median)
        {
            max1.push(min1.top());
            min1.pop();
            min1.push(num);
        }
        //else push into the max
        else
            max1.push(num);

        //set median as average of
        //min top and max top elements
        median = (min1.top() + max1.top()) / 2;
    }
    //if max size if greater
    else
    {
        //if current is more than then
        //median then push into the min
        //queue
        if (num > median)
        {
            min1.push(num);
        }

        //else push the top of max into
        //the min and current into the max
        else
        {
            min1.push(max1.top());
            max1.pop();
            max1.push(num);
        }
        //set the median as average of
        //top of min and max
        median = (min1.top() + max1.top()) / 2;
    }
}

//function to find the meadin of running
//stream
double findMedian()
{
    return median;
}
int main()
{
    int arr[] = {2, 1, 5, 7, 2, 0, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "[";
    for (int i = 0; i < n; i++)
    {
        addNum(arr[i]);
        cout << findMedian();
        if (i != n - 1)
            cout << ", ";
    }
    cout << "]";
    return 0;
}

Minimum Cabs

Assume there are N persons and each person needs exactly one cab. For each person, you are given the start time and end time (both inclusive) during which that person will travel. Find the minimum number of cabs required.

Example:

Input:  n = 6, arr ={{1, 0, 2, 0}, {16, 0, 21, 30}, {9, 30, 13, 0}, {21, 30, 22, 30}, {21, 30, 22, 30}, {12, 0, 12, 30}}
Output: 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;

bool cmp(pair<double, double> a, pair<double, double> b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}

int minimumCabs(int n, vector<vector<int>> &arr)
{
    vector<pair<double, double>> v;
    for (int i = 0; i < n; i++)
    {
        double s1 = arr[i][0], s2 = arr[i][1];
        double e1 = arr[i][2], e2 = arr[i][3];

        double x1 = s2 / 60, x2 = e2 / 60;
        v.push_back({x1 + s1, e1 + x2});
    }
    sort(v.begin(), v.end(), cmp);
    priority_queue<double, vector<double>, greater<double>> q;
    for (int i = 0; i < n; i++)
    {
        if (q.empty())
            q.push(v[i].second);
        else
        {
            double y = q.top();
            if (y < v[i].first)
                q.pop();
            q.push(v[i].second);
        }
    }
    return q.size();
}
int main()
{

    int n = 6;

    vector<vector<int>> arr = {{1, 0, 2, 0},
                               {16, 0, 21, 30},
                               {9, 30, 13, 0},
                               {21, 30, 22, 30},
                               {21, 30, 22, 30},
                               {12, 0, 12, 30}};

    cout << minimumCabs(n, arr) << "\n";

    return 0;
}