I recently had a google phone screen where i was asked the following question.

Given an array of n integers ( -1e9 <= A[i] <= 1e9 ) return top k combination sum where k <= 1500, n <= 1e5

eg. if n = 4, array = [8, 4, 2], k = 3, the answer will be [14, 12, 10] corresponding to the combinations (8, 4, 2), (8, 4) and (8, 2).

I only know the backtracking solution. How to solve this efficiently?

I am solving this problem from SPOJ : https://www.spoj.com/problems/COT/ I referred to the blog by Anudeep. Find it here : https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/

What I don't understand is what the variable "count" stores for each node. Can someone explain what count refers to and how it helps in finding the ordered statistics? Thanks.

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.

We start at the source square and want to reach the target square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn't in the given list of blocked squares.

Return true if and only if it is possible to reach the target square through a sequence of moves.

The signature of the function is as follows:-

bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target)

Standard BFS and bi-directional BFS are both resulting in MLE (Stack Overflow). What other approaches can we take for this problem?

Also, another follow-up question being, what if the grid is infinite?

Kindly mention your thoughts along with explanation.

Thanks.

Can anyone explain how to use custom comparators or provide a link?

What confuses me the most is that for some comparator we write the comparator as a struct/class and overload the < operator while sometimes we just write a comparator that takes two instances returns true if first should be before second in ordering.

I'll write the following snippets. Is there any difference in those two? It is just a preference? Or both are just different ways to write? If so, which is better? Also, we can just use lambda function to do this, which is much easier but I really wanted to know how traditional comparators worked.

bool comp(int& a, int& b)
{
    return freq[a] < freq[b]; // Freq is a global array.
}

To sort using above comparator we write,

vector arr = {0,5,6,1}; sort(arr.begin(), arr.end(), comp);

class comparator{
     bool operator()(int& a, int& b)
     {
         return freq[a] < freq[b] ; 
     }
};

To sort using this, we write the following,

vector arr = {0,5,6,1}; sort(arr.begin(),arr.end(),comparator);

auto comp = [](int& a, int& b){ return freq[a] < freq[b] };

To sort using lambda, we write the following,

vector arr = {0,5,6,1}; sort(arr.begin(),arr.end(),comp);

Please tell me when to use what, and what the differences are. I really don't seem to understand this.

For an array, if we want to sort in descending order, we can use the greater() comparator. What it means is that the greater element should come before smaller element. But, in case of priority_queue in C++, if we use greater() as comparator, it makes the top element the smallest. So, if I write something like following:-

while(!pq.empty())     // pq is priority_queue of integers
{
   auto c = pq.top();
   pq.pop();
   cout << c << " ";
}

Above code results in integers being printed in ascending order. Can someone explain why is that so? Or does comparator have different meaning in case of priority_queue? For a fact, I know that by default, the priority queue in C++ is max_heap. Does this have to do anything with it? I searched on internet but couldn't find valid reason for this. Thanks.

**My wife and I recently attended a party at which there were four other married couples. Various handshakes took place. No one shook hands with oneself, nor with one's spouse, and no one shook hands with the same person more than once. After all the handshakes were over, I asked each person, including my wife, how many hands he (or she) had shaken. To my surprise each gave a different answer. How many hands did my wife shake?**

I found this question in an online math forum. Took me 13 minutes. How much time did you take?

// Please don't add answer in comment as it will ruin the fun for others. Just comment the time it took you. Thanks.

Recently I have been learning segment tree and so made a template for segment tree. I am not entirely sure that it is all correct and if it can be optimized further. Kindly go through it and if you find anything worth commenting like any mistakes or optimizations, please do so.

Here is the template:-

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

class SegmentTree{
  private : 
        std::vector<int> st,A;
        vector<int> lazy;
        int n;
  public: 
        SegmentTree(vector<int>& a)
        {
          A = a;
          n = a.size();
          st.assign(4*n + 1, 0);     // Max 4n nodes required
          lazy.assign(4*n+1, 0);     // Max 4n nodes required
          build(1,0,n-1);            // build segment tree 
        }
        
        void print()                // Print the st and lazy to debug
        {
            cout << "SegmentTree is as follows "<< endl;
            for(int c: st)
            {
                cout << c << " ";
            }
            cout << "\nLazy is as follows \n";
            for(int c: lazy)
            {
                cout << c<< " ";
            }
            cout << endl;
            
        }
      
          void build(int i, int l, int r)    // Method to build the segTree 
          {
              if(l>r)
              return;
              if(l == r)
              {
                  st[i] = A[l];
              }
              else
              {
                  build(2*i, l,(l+r)/2);
                  build(2*i + 1, (l+r)/2 + 1, r);
                  st[i] = st[2*i] + st[2*i + 1];    // Modify this as needed 
              }
          }
      
      int rsq(int l, int r)                     // Range Sum query.Modify this // as needed for different problems.
      {
          l--;
          r--;
          return query(1,0,n-1,l,r);
      }
      
      void update_range(int l, int r, int diff)
      {
          l--,r--;
          update_lazy(1,0,n-1,l,r ,diff);
      }
      void update_lazy(int i, int a, int b, int l, int r, int diff)
      {
          if(lazy[i]!=0)
          {
              st[i] += (b-a+1)*diff;        // Modify as needed 
              if(a!=b)                      // propagate if not leaf 
              {
                  lazy[2*i] = lazy[i];      
                  lazy[2*i+1] = lazy[i];
              }
              lazy[i] = 0;
          }
          
          if(l>r || l>b || r<a)             // Out of range
          return;
          if(a>=l && r<=b)                  // Completely in range 
          {
              st[i] = (b-a+1)*diff;
              if(a!=b)                  // If not leaf then propagate
              {
                  lazy[2*i] += diff;
                  lazy[2*i+1] += diff;
              }
              return;
          }
          
          update_lazy(2*i, a, (a+b)/2, l, r, diff);
          update_lazy(2*i+1, (a+b)/2+1, b, l, r, diff);
          
          st[i] = st[2*i] + st[2*i+1];      // Modify as needed 
      }

    int query(int i, int a,int b, int l, int r)
    {
        if(lazy[i]!=0)
        {
            st[i] += (b-a+1)*lazy[i];
            if(a!=b)
            {
                lazy[2*i] = lazy[i];
                lazy[2*i+1] = lazy[i];
            }
            lazy[i] = 0;
        }
        if(r<a || b<l || a > b)
        return 0;
        
        if(l<=a && r>=b)
        return st[i];
        
        return query(2*i, a,(a+b)/2, l,r) + query(2*i+1,(a+b)/2 + 1, b,l,r); // MOdify 
        
    }
};


int main()
{
    vector<int> a(8);
    for(int i=0; i<8; i++)
    a[i] = i+1;
    
    SegmentTree* sst = new SegmentTree(a);
    cout << sst->rsq(1,4) << endl;
    sst->update_range(1,4,2);
    cout << sst->rsq(1,4);
    return 0;
    
}

Thanks in advance!