Amazon | OA Coding Questions and Solutions | Set - 3 | 2022

Question

All past online assesments of Amazon can be found using the tag "amazon_oa" in the search bar.

Here is the link : https://www.desiqna.in/tag/amazon_oa

Answer 1

Recently took the OA from Amazon, and here are the two questions being assigned:

 

1)

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 may return the answer in any order. 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]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.

 

Constraints:

• 1 <= k <= points.length <= 104
• -104 < xi, yi < 104

Code : 

 

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        priority_queue<pair<int, int>> maxPQ;
        for (int i = 0 ; i < points.size(); i++) {
            pair<int, int> entry = {squaredDistance(points[i]), i};
            if (maxPQ.size() < k) {
                // Fill the max PQ up to k points
                maxPQ.push(entry);
            } else if (entry.first < maxPQ.top().first) {
                // If the max PQ is full and a closer point is found,
                // discard the farthest point and add this one
                maxPQ.pop();
                maxPQ.push(entry);
            }
        }
        
        // Return all points stored in the max PQ
        vector<vector<int>> answer;
        while (!maxPQ.empty()) {
            int entryIndex = maxPQ.top().second;
            maxPQ.pop();
            answer.push_back(points[entryIndex]);
        }
        return answer;
    }

private:
    int squaredDistance(vector<int>& point) {
        // Calculate and return the squared Euclidean distance
        return point[0] * point[0] + point[1] * point[1];
    }
};

Answer 2

2)

Amazon Alexa AI team is working to add feature that suggest days for camping based on the weather forecast. According to survey, a day is ideal for camping if the amount of rainfall has been non-increasing for the prior k days from the considered day and will be non-decreasing for the following k days from the considered day. Given the predicted rainfall for the next n days, find all ideal days. Formally a day is ideal if the following is true.
day[i-k]>=day[i-k+1]>=....>=day[i-1]>=day[i]<=day[i+1]<=....<=day[i+k-1]<=day[i+k]
Return the ideal days in ascending order. The ith element of the array represents the data for the day i+1. Example, given/Input day=[3,2,2,2,3,4], k=2
here day1>=day2>=day3<=day4<=day5, so day3 is ideal
also day2>=day3>=day4<=day5<=day6, so day4 is ideal
The answer is [3,4]
Ex:- Given/Input day=[1,0,1,0,1], k=1
So, day1>=day2<=day3
day3>=day4<=day5
Output: [2,4]

 

Ex:- Given/input day=[1,0,0,0,1], k=2
So, day1>=day2>=day3 <=day4<=day5
Output: [3]

 

Ex:- Given day=[1,1,1,1,1,1,1,1,1,1], k=3

 

So, day1>=day2>=day3>=day4<=day5<=day6<=day7
day2>=day3>=day4>=day5<=day6<=day7<=day8
day3>=day4>=day5>=day6<=day7<=day8<=day9
day4>=day5>=day6>=day7<=day8<=day9<=day10
Output: [4,5,6,7]

 

Input method takes 2 arguments day[n] and k(an integer)
returns int[], the ideal days in sorted ascending

Code : 

def idealDays(days, k):
    n = len(days)
    result = []
    leftIdeal = [0 for _ in range(n)]
    rightIdeal = [0 for _ in range(n)]
    for i in range(1, n):
        if days[i] <= days[i-1]:
            leftIdeal[i] = leftIdeal[i-1] + 1
    for i in reversed(range(n-1)):
        if days[i] <= days[i+1]:
            rightIdeal[i] = rightIdeal[i+1] + 1
    for i in range(n):
        if leftIdeal[i] >= k and rightIdeal[i] >= k:
            result.append(i+1)
    return result

Comments

can you translate this to java