/2021Fall-EE538-HW4

Primary LanguageStarlark

HW4 EE538 - Computing Principles for Electrical Engineers

  • Please clone the repository, edit README.md to answer the questions, and fill up functions to finish the HW.
  • For non-coding questions, you will find Answer below each question. Please write your answer there.
  • For coding questions, please make sure that your code can run bazel run/test. In this homework, you will need to fill up cpplib.cc and tests in tests.
  • For submission, please push your answers to Github before the deadline.
  • Deadline: Wednesday, October 20th by 23:59 pm
  • Total: 120 points. 100 points is considered full credit.

Question 1 (80 Points. Medium)

Please implement the following class for MaxHeap:

  • Provide Gtest for methods that are marked with "GT".
class MaxHeap {
 public:
  MaxHeap(); // default constructor

  int getParentIndex(int i); //GT
  int getLeftIndex(int i); //GT
  int getRightIndex(int i); //GT
  int getLargestChildIndex(int i); //GT

  int getLeft(int i);
  int getRight(int i);
  int getParent(int i);

  int top(); //GT
  void push(int v); //GT
  void pop(); //GT
  void TrickleUp(int i);
  void TrickleDown(int i);

  vector<int> data_;
};

Write several tests using GTest for your function in tests/q1_student_test.cc.

Please create your test cases and run the following command to verify the functionality of your program.

bazel test tests:q1_student_test

Question 2 (20 Points. Medium)

Write a function int findKthSmallest(const vector<vector<int>> &input, int k) that finds the kth smallest element among all elements in all vectors and returns that value.

  • You should do this without sorting the vector
  • Provide time complexity for your function
  • if k is invalid(eg: k <= 0), return -INX_MAX

Example:
input: [ [0, 2], [1, 5], [6, 3, 15] ] and k = 2
output: 1

input: [ [0, 2], [1, 2, 5], [6, 2, 2, 3, 15] ] and k = 7
output: 3

Write several tests using GTest for your function in tests/q2_student_test.cc.

Please create your test cases and run the following command to verify the functionality of your program.

bazel test tests:q2_student_test

Question 3 (20 Points. Hard)

Write a function vector<vector<int>> kClosest(vector<vector<int>>& points, int k)

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0). The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)^2 + (y1 - y2)^2). You should return the answer from the closest to the farthest. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]

Write several tests using GTest for your function in tests/q3_student_test.cc.

Please create your test cases and run the following command to verify the functionality of your program.

bazel test tests:q3_student_test

Optional Question (No Credit - Hard)

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Write a function ListNode* mergeKLists(vector<ListNode*>& lists) that merge all the linked-lists into one sorted linked-list and return it.

Example:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list: 1->1->2->3->4->4->5->6