Programming Questions

count_smaller_numbers_after_self_with_bit.cpp

class Solution
{
  void add( std::vector<int>& bit, int i, int val )
  {
    for ( ; i < bit.size(); i += i & -i )
      bit[i] += val;
  }

  int query( std::vector<int>& bit, int i )
  {
    int ans = 0;
    for ( ; i > 0; i -= i & -i )
      ans += bit[i];
    return ans;
  }

public:
  std::vector<int> countSmaller( std::vector<int>& nums )
  {
    int len = nums.size();
    auto tmp = nums;
    std::sort( nums.begin(), nums.end() );
    for ( int i = 0; i < len; i++ )
      nums[i] = std::distance( tmp.begin(), std::lower_bound( tmp.begin(), tmp.end(), nums[i] ) ) + 1;
    std::vector<int> bit( len + 1 );

    std::vector<int> result( len );
    for ( int i = len - 1; i >= 0; i-- )
    {
      result[i] = query( bit, nums[i] - 1 );
      add( bit, nums[i], 1 );
    }
    return result;
  }
};

count_smaller_numbers_after_self_with_bst.cpp

// https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/

class Solution {
    typedef struct Node
    {
        Node(int v): val(v), count(1), left(nullptr), right(nullptr)
        {}
        
        int val;
        int count;
        Node* left;
        Node* right;   
    } Node;
    
    int insert(Node** p_root, int val)
    {        
        int count = 0;
        while( *p_root )
        {
            if((*p_root)->val >= val)
            {
                (*p_root)->count++;
                p_root = &(*p_root)->left;
            }
            else
            {
                count+=(*p_root)->count;
                p_root = &(*p_root)->right;
            }
        }
        
        *p_root = new Node(val);
        return count;
    }
public:
    vector<int> countSmaller(vector<int>& nums)
    {
        int len = nums.size();
        std::vector<int> result(len, 0);
        
        Node* root = nullptr;
        for(int i=len-1; i>=0; --i)
        {
            result[i]=insert(&root, nums[i]);
        }
        return result;
    }
};

falling_squares_with_segmented_tree.cpp

// https://leetcode.com/problems/falling-squares/description/

class Solution
{
  std::vector<int> heights;

  int query( int idx, int lo, int hi, int ql, int qh )
  {
    if ( lo > hi || qh < lo || hi < ql )
      return 0;

    if ( ql <= lo && hi <= qh )
      return heights[idx];

    int mid = lo + ( hi - lo ) / 2;
    return std::max( query( 2 * idx + 1, lo, mid, ql, qh ), query( 2 * idx + 2, mid + 1, hi, ql, qh ) );
  }

  int update( int idx, int lo, int hi, int ql, int qh, int newvalue )
  {
    if ( lo > hi || qh < lo || hi < ql )
      return heights[idx];

    if ( lo == hi )
    {
      heights[idx] = newvalue;
      return heights[idx];
    }

    int mid = lo + ( hi - lo ) / 2;
    auto left = update( 2 * idx + 1, lo, mid, ql, qh, newvalue );
    auto right = update( 2 * idx + 2, mid + 1, hi, ql, qh, newvalue );
    heights[idx] = std::max( std::abs(left), std::abs(right) );
    return heights[idx];
  }

public:
  std::vector<int> fallingSquares( std::vector<std::pair<int, int>>& positions )
  {
    std::vector<int> mapped;
    mapped.reserve( positions.size() * 2 );
    for ( const auto& elem : positions )
    {
      mapped.push_back( elem.first );                    // start inclusive
      mapped.push_back( elem.first + elem.second - 1 );  // end inclusive
    }
    std::sort( mapped.begin(), mapped.end() );
    mapped.erase( std::unique( mapped.begin(), mapped.end() ), mapped.end() );

    int len = mapped.size();
    heights.resize( len << 2 );

    std::vector<int> result;
    int max_height = 0;
    for ( const auto& elem : positions )
    {
      int ql = std::distance( mapped.begin(), std::lower_bound( mapped.begin(), mapped.end(), elem.first ) );
      int qh = std::distance( mapped.begin(),
                              std::lower_bound( mapped.begin(), mapped.end(), elem.first + elem.second - 1 ) );

      int current_height = query( 0, 0, len - 1, ql, qh );
      current_height += elem.second;
      update(0, 0, len-1, ql, qh, current_height);
      max_height = std::max( max_height, current_height );
      result.push_back( max_height );
    }
    return result;
  }
};

PROGRAMMING_QUESTIONS