Slice - SDE 1 , DSA, behavioral interview #Slice

Problem Statement

You are given a list of n points in a 2D plane, where each point represents the top vertex of a right-angled triangle. For each point (x, y) (with y > 0), two lines are drawn through it: one with slope +1 and another with slope -1. These lines intersect the X-axis (where y = 0) at two points, forming a triangle with vertices at (x, y) and the two intersection points.

A triangle is overshadowed if its top vertex (x, y) lies strictly inside or on the boundary of another triangle formed by a different point. Your task is to count the number of triangles that are not overshadowed by any other triangle.

Input

points: A list of n integer arrays, where points[i] = [x_i, y_i] represents the coordinates of the i-th point.

• 1 <= n <= 10^5
• -10^9 <= x_i <= 10^9
• 1 <= y_i <= 10^9

Output

Return an integer representing the number of triangles that are not overshadowed.

Examples

Example 1

Input: points = [[0,1], [2,1]]

Output: 2

Explanation:

For point [0,1]:

Lines with slopes +1 and -1 intersect the X-axis at [1,0] and [-1,0].

Forms triangle [[0,1], [1,0], [-1,0]].

For point [2,1]:

Lines intersect at [3,0] and [1,0].

Forms triangle [[2,1], [3,0], [1,0]].

Neither top vertex ([0,1] or [2,1]) lies inside or on the boundary of the other triangle. Result: Both triangles are not overshadowed, so output is 2.

Example 2

Input: points = [[0,2], [1,1]]

Output: 1

Explanation:

For point [0,2]:

Lines intersect at [2,0] and [-2,0].

Forms triangle [[0,2], [2,0], [-2,0]].

For point [1,1]:

Lines intersect at [2,0] and [0,0].

Forms triangle [[1,1], [2,0], [0,0]].

The top vertex [1,1] lies on the boundary of the triangle formed by [0,2], so it is overshadowed. Result: Only the triangle from [0,2] is not overshadowed, so output is 1.

Example 3

Input: points = [[0,2], [1,1], [3,3]]

Output: 1

Explanation:

Triangle from [0,2]:

Base interval: [-2,2].

Vertices: [[0,2], [-2,0], [2,0]].

Triangle from [1,1]:

Base interval: [0,2].

Vertices: [[1,1], [0,0], [2,0]].

Triangle from [3,3]:

Base interval: [0,6].

Vertices: [[3,3], [0,0], [6,0]].

Point [1,1] is on the boundary of [0,2]’s triangle, so its triangle is overshadowed.

Point [0,2] is inside [3,3]’s triangle, so its triangle is overshadowed.

Result: Only [3,3]’s triangle is not overshadowed, so output is 1.

Constraints

• 1 <= points.length <= 10^5
• points[i].length == 2
• -10^9 <= points[i][0] <= 10^9
• 1 <= points[i][1] <= 10^9
• All points are unique.

Notes

• Lines with slopes +1 and -1 through a point (x, y) intersect the X-axis at (x + y, 0) and (x - y, 0), respectively.
• A point is considered inside or on the boundary of a triangle if it lies within its interior, on its edges, or at its vertices.
• Assume floating-point precision does not affect containment checks.

Solution Hints

• Step 1: Remove duplicate points to avoid counting identical triangles.
• Step 2: For each point (x, y), compute base points (x - y, 0) and (x + y, 0), forming interval [x - y, x + y].
• Step 3: Use a heap to sort points by x - y. Check if a point’s top vertex is inside another triangle by: Ensuring its X-coordinate is within the other’s base interval. Checking if its Y-coordinate is below the lines’ Y-values at that X.
• Step 4: Count triangles not overshadowed, using a list to track active triangles.

Implement allocateSlot() and vacateSlot() functions for a multi-story parking lot.

The parking area has z floors, each floor having x rows and y columns. The entry point is at x = 0, y = 0, z = 0.

For simplification, the distance from the entry point was taken to be x + y + z.

If two slots had the same distance from the entry point, then the slot with the smallest floor number would be considered, followed by the column number and row number.

Alternatively described as:

Given a multi-story parking lot with z floors, and each floor with x rows and y columns. A combination of x, y, z defines a unique spot in the parking lot. There is a single entrance to this parking lot at ground floor z=0, x=0, y=0. Write the below two functions:

• allocateNearestSpot()
• vacateSpot(z, x, y)

Explain past projects completely, discuss them, and answer questions around them. The interviewer asked in-depth questions about my past projects and current work at my company.

How would you handle conflict?

How would you debug an error in your code?

Why did you leave the last company?