Problems

1. Computational number theory. Write a program CubeSum.java that prints out all integers of the form $a^3+b^3$where $a$ and$b$𝑏 are integers between 0 and $n<$ in sorted order, without using excessive space. That is, instead of computing an array of the $n^2$ sums and sorting them, build a minimum-oriented priority queue, initially containing $(0^3,0,0),(1^3+1^3,1,1),(2^3+2^3,2,2),…,(n^3+n^3,n,n)$. Then, while the priority queue is nonempty, remove the smallest item $i^3+j^3,i,j)$, print it, and then, if $j<n$, insert the item $(i^3+(j+1)^3,i,j+1)$. Use this program to find all distinct integers $a,b,c$, and $d$ between 0 and $10^6$such that $a^3+b^3=c^3+d^3$𝑎3+𝑏3=, such as $1729=9^3+10^3=1^3+12^3$.

#include <iostream>
using namespace std;

class cubeSum {

public:
     int i, j, sum;
     cubeSum(int i = 0, int j = 0) {
          this->sum = i * i * i + j * j * j;
          this->i = i;
          this->j = j;
     }
     int compareTo(const cubeSum &that) {
          if (this->sum > that.sum) return 1;
          else if (this->sum < that.sum) return -1;
          return 0;
     }
     string toString() {
          string res = to_string(sum) + " = " + to_string(i) + "^3" " + " + to_string(j) + "^3";
          return res;
     }
};

template <typename key>
class MinPQ {
     key *arr;
     int N;
     int i = 0;

     bool greeter(key &key1, key &key2) {
          return key1.compareTo(key2) > 0;
     }

     void swim(int k) {
          while (k > 1 && greeter(arr[k / 2], arr[k])) {
               swap(arr[k], arr[k / 2]);
               k = k / 2;
          }
     }

     void sink(int k) {
          while (2 * k <= i) {
               int j = 2 * k;

               if (j < i && greeter(arr[j], arr[j + 1])) j++; // find out which one is smaller 2k or 2k+1

               if (!greeter(arr[k], arr[j])) break; // break if the parent's key is smaller than both children's key

               swap(arr[k], arr[j]);
               k = j; // moving down the heap
          }
     }

public:
     MinPQ(int capacity) : N(capacity + 1) {
          arr = new key[capacity + 1]{NULL};
     }

     bool isEmpty() {
          return i == 0;
     }
     bool isFull() {
          return i == N - 1;
     }

     // At most 1 + lg N compares
     void insert(key val) {
          arr[++i] = val;
          swim(i);
     }

     // At most 2 lg N compares
     key delMin() {
          key min = arr[1];
          swap(arr[1], arr[i--]);
          sink(1);
          arr[i + 1] = NULL; // prevent loitering
          return min;
     }
};

int main() {
     int n = 4;
     MinPQ<cubeSum> *PQ = new MinPQ<cubeSum>(n);
     for (int i = 0; i < n; i++) {
          cubeSum cb(i, i);
          PQ->insert(cb);
     }

     while (!PQ->isEmpty()) {
          cubeSum s = PQ->delMin();
          if (s.j < n) {
               cubeSum cb(s.i, s.j + 1);
               PQ->insert(cb);
          }
          cout << s.toString() << endl;
     }
}

1. Index priority-queue implementation. Implement IndexMaxPQ.java by modifying MaxPQ.java as follows: Change pq[] to hold indices, add an array keys [ ] to hold the key values, and add an array qp[] that is the inverse of pq [] — qp[i] gives the position of i in pq[] (the index j such that pq[j] is i). Then modify the code to maintain these data structures. Use the convention that qp[i] is -1 if i is not on the queue, and include a method contains() that tests this condition. You need to modify the helper methods exch() and less() but not sink() or swim().

Merge k Sorted Lists

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int size = 0;
        ListNode* temp;
        for(int i = 0; i < lists.size(); i++) {
            temp = lists[i];
            while(temp!=nullptr) {
                temp = temp -> next;
                size++;
            }
        }
        int* arr = new int[size];
        int j = 0;
        for(int i = 0; i < lists.size(); i++) {
            temp = lists[i];
            while(temp != nullptr) {
                arr[j++] = temp -> val;
                temp = temp -> next;
            }
        }

        heapSort(arr, size);
        
        ListNode* head = new ListNode(0);
        temp = head;

        for(int i = 0; i  < size; i++) {
            temp -> next = new ListNode(arr[i]);
            temp = temp -> next;
        }
        return head -> next;
    }

    
    void sink(int *arr, int k, int n)
    {
        while (k * 2 <= n)
        {
            int j = 2 * k;
            if (j < n && arr[j - 1] < arr[j])
                j++;
            if (!(arr[k - 1] < arr[j - 1]))
                break;

            swap(arr[k - 1], arr[j - 1]);
            k = j;
        }
    }
    
    void heapSort(int* arr, int size) {
        int N = size;

        for (int k = N / 2; k >= 1; k--)
            sink(arr, k, N);

        while (N > 1) {
            swap(arr[0], arr[--N]);
            sink(arr, 1, N);
        }
        
    }
};

Q1: Kth Largest Element in an Array

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int N = nums.size();
        // Bottom-Up 
        // Heap-Ordered
        for (int k = N / 2; k >= 1; k--)
            sink(nums, k, N);

        for(int i = 0; i < nums.size(); i++) {
          cout << nums[i] << " " ;
        }
        int i = nums.size()-1;
        int kthLargest = 0;
        while(k > 0) {
            kthLargest = delMax(nums, i);
            i--;
            k--;
        }
        return kthLargest;
    }

    int delMax(vector<int>& nums, int N) {
        int elem = nums[0];
        swap(nums[0], nums[N]);
        sink(nums, 1, N);
        N--;
        return elem;
    }

    void sink(vector<int>& nums, int k, int N) {
        while(2*k <= N) {
            int j = 2*k;
            if(j < N && nums[j-1] < nums[j]) j++;
            if(nums[k-1] > nums[j-1]) break;
            swap(nums[k-1], nums[j-1]);
            k = j;
        }
    }
};

Q2: Smallest Number in Infinite Set

class SmallestInfiniteSet {
    priority_queue<int,vector<int>,greater<int>> pq;
    int arr[1001];
    
public:
    SmallestInfiniteSet() {
        for(int i = 1; i <= 1000; i++) {
            pq.push(i);
            arr[i] = 1;
        }
    }
    
    int popSmallest() {
        int ans = pq.top();
        pq.pop();
        arr[ans] = 0;
        return ans;
    }
    
    void addBack(int num) {
        if(arr[num] == 1) return;
        arr[num] = 1;
        pq.push(num);
    }
};