Learn and practice the Top K Elements and Two Heaps patterns to solve coding interview problems.

Speedrun the Oracle Coding Interview: Top Problems in Python

This module will teach you the underlying concepts and equip you with the techniques needed to use heaps to efficiently solve a diverse range of problems. In many problems, we need to find the k most/least frequent or k largest/smallest elements in a given set of elements. Such problems, common in data analysis, natural language processing, online algorithms, as well as in recommendation systems, may be solved using the Top K Elements pattern. The fast insertion and deletion operations possible with heaps make them ideal to implement efficient algorithms for such problems. Further, we can use two heaps when we need to simultaneously keep track of the k largest elements in a set, as well as the k smallest elements in the same set. Extending this idea, each heap may be based on a separate dataset. These techniques are used to solve problems categorized under the Two Heaps pattern.

Heaps

# Statement

Given a list of points on a plane, where the plane is a 2-D array with (x, y) coordinates, find the $k$ closest points to the origin $(0, 0)$.

> **Note:** Here, the distance between two points on a plane is the Euclidean distance: $
\sqrt{x^2 + y^2}
$

**Constraints:**

* $1 \leq$ `k` $\leq$ `points.length` $\leq 10^3$
* $-10^4 <$ `x[i]`, `y[i]`$< 10^4$

# Examples

# Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:


What is the output if the following list of points and value of k is given as input? 

Select all that apply.

points = [[1, 3], [-2, 4], [2, -1], [-2, 2], [5, -3], [3, -2]]

k = 3

What is the output if the following list of points and value of k is given as input?
Select all that apply.
points = [[1, 3], [-2, 4], [2, -1], [-2, 2], [5, -3], [3, -2]]
k = 3

What is the output if the following list of points and value of k is given as input? 

Select all that apply.

points = [[1, -3], [4, -2], [2, -1], [-2, 2], [-5, 3], [3, -2]]

k = 4

What is the output if the following list of points and value of k is given as input?
Select all that apply.
points = [[1, -3], [4, -2], [2, -1], [-2, 2], [-5, 3], [3, -2]]
k = 4

What is the output if the following list of points and value of k is given as input? 

Select all that apply.

points = [[1, 3], [2, -4], [2, -1], [-2, 2]]

k = 3

What is the output if the following list of points and value of k is given as input?
Select all that apply.
points = [[1, 3], [2, -4], [2, -1], [-2, 2]]
k = 3

What is the output if the following list of points and value of k is given as input? 

Select all that apply.

points = [[-1, -3], [-4, -5], [-2, -2], [-2, -3]]

k = 3

What is the output if the following list of points and value of k is given as input?
Select all that apply.
points = [[-1, -3], [-4, -5], [-2, -2], [-2, -3]]
k = 3

K Closest Points to Origin

K Closest Points to Origin

# Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.


# Try it yourself

Implement your solution in `main.py` and `point.py` in the following coding playground.

A `Point` class has two data members, `x` and `y` coordinates. You may add members or methods to it to support your solution.

> **Note:** The order of the points returned is not significant.

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
  
    # Write your code here


Help me debug only the function K Closest Points to Origin . . I don't need the corrected code.I don't want explanations or code review. Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Please help me understand why this code failed for the last failed test case. Don't give me the corrected code. . If yes, then Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Your current task is to review only the k_closest function and the other function(s) invoked in it/them. Do not review extra/helper files or functions not invoked in the solution function k_closest. Do not review the code of data structures objects instantiated like a binary tree, linked list, trie, union find, etc., in the solution functions. Just review the solution/algorithm function of the problem. Also, Answer the following questions: Is the Top K Elements pattern used? Take your time and review the code.

Please provide a brief time complexity analysis of the function k_closest. While calculating time complexity, include the time complexity of built-in Python functions invoked by the code. The Answer should be to the point and in a few lines.

Please provide a brief Space complexity analysis of the function k_closest. While calculating space complexity, include the space complexity of built-in Python functions invoked by the code. Do not include the space used for the input parameters and the space used for just returning an output(not used as a scratch space). The Answer should be to the point and in a few lines

TwoDArray

convert

import sys
import json
from point import Point
# from user_code import Point

sys.path.append("../ds_v1")
from data_structure import DataStructure

# throw parsing errors for incorrect test case format
def parsingError(element_string, error_message):
 sys.stderr.write(f"Parsing Error: {element_string} {error_message}")
 exit()

# className: MyCustomDS
class TwoDArray(DataStructure):
 def __init__(self):
 self.array = []
 pass

 def __str__(self):
 pass

 # return value will be passed to user program
 def construct(self, inp_string: str, type_of_arr: int) -> any:
 # parse test case in json string 'value' to your desired data structure

 final_list = json.loads(inp_string) # string to list

 result = []

 for i in range(len(final_list)):
 result.append(Point(final_list[i][0], final_list[i][1]))

 return result

 def to_string(self,array):
 st = "["
 for i in range(len(array)):
 st += "["
 for k in range(len(array[i])): 
 st += str(k)
 if k < len(array[i]) - 1:
 st += ", "
 st += "]"
 if i < len(array) - 1:
 st += ", "
 st += "]"
 return st

 def point_array_to_array(self, points):
 array = []
 for point in points:
 array.append([point.x, point.y])
 return array
 # input param contains return value of user program
 def traverse(self, input: any, type_of_arr: int) -> str:
 # return 
 # convert your data structure 'input' to a json string representing a test case output
 actual = self.point_array_to_array(input)
 self.array = actual
 return json.dumps((actual))

import sys
import json
from point import Point
# from user_code import Point

sys.path.append("../ds_v1")
from data_structure import DataStructure

# throw parsing errors for incorrect test case format
def parsingError(element_string, error_message):
 sys.stderr.write(f"Parsing Error: {element_string} {error_message}")
 exit()

# className: MyCustomDS
class convert(DataStructure):
 def __init__(self):
 self.array = []
 pass

 def __str__(self):
 pass

 # return value will be passed to user program
 def construct(self, inp_string: str, type_of_arr: int) -> any:
 # parse test case in json string 'value' to your desired data structure

 final_list = json.loads(inp_string) # string to list

 result = []

 for i in range(len(final_list)):
 result.append(Point(final_list[i][0], final_list[i][1]))

 return result

 def to_string(self,array):
 st = "["
 for i in range(len(array)):
 st += "["
 for k in range(len(array[i])): 
 st += str(k)
 if k < len(array[i]) - 1:
 st += ", "
 st += "]"
 if i < len(array) - 1:
 st += ", "
 st += "]"
 return st

 def point_array_to_array(self, points):
 array = []
 for point in points:
 array.append([point.x, point.y])
 return array
 # input param contains return value of user program
 def traverse(self, input: any, type_of_arr: int) -> str:
 # return 
 # convert your data structure 'input' to a json string representing a test case output
 actual = self.point_array_to_array(input)
 self.array = actual
 return json.dumps((actual))

def evaluate_results(self) -> object:
 """
 self.__inputs is the list of inputs that are passed as input to function
 self.__actual_output is a list of outputs that is produced by the learner's code
 return : self.__edu__result object
 """
 from heapq import heappush, heappop

 class Point:
 # __init__ will be used to make a Point type object
 def __init__(self, x, y):
 self.x = x
 self.y = y

 # __lt__ is used for max-heap
 def __lt__(self, other):
 return self.distance_from_origin() > other.distance_from_origin()

 # __str__ is used to print the x and y values
 def __str__(self):
 return '[{self.x}, {self.y}]'.format(self=self)

 # distance_from_origin calculates the distance using x, y coordinates
 def distance_from_origin(self):
 # ignoring sqrt to calculate the distance
 return (self.x * self.x) + (self.y * self.y)

 __repr__ = __str__

 # return value will be passed to user program
 def construct(inp_list) -> any:
 # parse test case in json string 'value' to your desired data structure

 result = []

 for i in range(len(inp_list)):
 result.append(Point(inp_list[i][0], inp_list[i][1]))

 return result

 def point_array_to_array(points):
 array = []
 for point in points:
 array.append([point.x, point.y])
 return array

 def to_string(array):
 st = "["
 for i in range(len(array)):
 st += "["
 for k in range(len(array[i])): 
 st += str(k)
 if k < len(array[i]) - 1:
 st += ", "
 st += "]"
 if i < len(array) - 1:
 st += ", "
 st += "]"
 return st

 def k_closest_test(points, k):
 max_heap = []

 # put first 'k' points in the max heap
 for i in range(k):
 heappush(max_heap, points[i])

 # go through the remaining points of the input array, if a point
 # is closer to the origin than the top point of the max-heap, remove
 # the top point from heap and add the point from the input array
 for i in range(k, len(points)):
 if points[i].distance_from_origin() < max_heap[0].distance_from_origin():
 heappop(max_heap)
 heappush(max_heap, points[i])

 # the heap has 'k' points closest to the origin, return them in a list
 return list(max_heap)
 
 # multiple outputs will be added at each index respectively for a single test_case
 expected_outputs = [] 
 input1 = construct(self.__inputs[0])
 expected = point_array_to_array(k_closest_test(input1, self.__inputs[1]))
 actual = self.__actual_outputs[0]
 # store the 1st expected output that should be displayed to the user 
 expected_outputs.append(expected) 
 if json.dumps(sorted(expected)) == json.dumps(sorted(actual)):
 self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
 else:
 self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

 return self.__edu_result

from point import Point
import heapq

def k_closest(points, k):
  
    # Replace this placeholder return statement with your code
    return []

k closest points to origin.yaml

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : [[-1,-3],[-4,-5],[-2,-2],[-2,-3]]
    - 2 : 3
    output:
    - 1 : []
  - name: "testcase 2"
    inputs:
    - 1: [[1, 3], [2, 4], [2, -1], [-2, 2], [5, 3], [3, -2]]
    - 2: 3
    output:
    - 1 : []
  - name: "testcase 3"
    inputs:
    - 1: [[1,3],[-2,4],[2,-1],[-2,2],[5,-3],[3,-2]]
    - 2: 3
    output:
    - 1 : []
  - name: "testcase 4"
    inputs:
    - 1: [[1,3],[2,-4],[2,-1],[-2,2]]
    - 2: 3
    output:
    - 1 : []
  - name: "testcase 5"
    inputs:
    - 1: [[1,-3],[4,-2],[2,-1],[-2,2],[-5,3],[3,-2]]
    - 2: 4
    output:
    - 1 : []


def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
 """
 self.__inputs is the list of inputs that are passed as input to function
 store the result using the self.store_result(error_msg, status)
 return : void
 """

 def two_length(times):
 for time in times:
 if len(time) != 2:
 return False
 return True


 def is_valid_2d_array(arr):
 if not isinstance(arr, list) or not all(isinstance(row, list) for row in arr):
 return False

 for row in arr:
 if any(elem is None or isinstance(elem, bool) for elem in row):
 return False
 if not all(isinstance(elem, int) for elem in row):
 return False

 return True


 def check_values(points):
 for point in points:
 if not -10000 <= point[0] <= 10000 or not -10000 <= point[1] <= 10000:
 return False

 return True

 points = self.__inputs[0]
 k = self.__inputs[1]

 if not is_valid_2d_array(points):
 self.store_result ("'points' should be a 2D integer array", ValidationFunction.FAIL)
 elif not (1 <= len(points) <= 1000):
 self.store_result ("'points' length should be in range [1,1000]", ValidationFunction.FAIL)
 elif not (1 <= k <= len(points)):
 self.store_result ("'k' should be in range (1 <= k <= "+str(len(points))+")", ValidationFunction.FAIL)
 elif not two_length(points):
 self.store_result ("'points[i]' should have two values [x,y]", ValidationFunction.FAIL)
 elif not check_values(points):
 self.store_result ("'points[i][j]' should be in the range [-10000,10000]", ValidationFunction.FAIL)
 else:
 self.store_result("", ValidationFunction.PASS)

Try to solve the K Closest Points to Origin problem.

Top K Elements

Two Heaps

Conclusion

K Closest Points to Origin

Statement

Examples

Understand the problem

Figure it out!

Try it yourself