Panda Guru LogoPanda
Guru

PayPal OA - Java backend engineer

Round 1

Questions:

  1. Items Purchase
    n items where the price of the ith item is price[i]. A frequent customer has m discount coupons. If x discount coupons are used on the ith item, its price is reduced to the integer floor(price[i] / 2^x), e.g. floor(3/2^1) = floor(1.5) = 1.
    Find the minimum amount needed to purchase all the items of the shop using at most m coupons.

    Example: Consider n = 2, price = [2, 4], m = 2. The optimum solution:

    • Purchase item 1 for 2.
    • Use 2 coupons on item 2, so the discounted price is 4/2^2 = 4 / 4 = 1.
      The amount required = 2 + 1 = 3.

    Function Description: Complete the function findMinimumPrice in the editor below.
    findMinimumPrice has the following parameters:

    • int price[n]: the original prices of the items
    • int m: the number of discount coupons

    Constraints:

    • 1 <= n <= 10^5
    • 0 <= m <= 10^9
    • 1 <= price[i] <= 10^9
  2. Java Specific Question
    Create and implement Product class.
    Implement the classes shown:

    • Create a class called Product that implements the /Product interface.
    • This class should have the following properties:
      • String productid
      • int salesVelocity
      • int stockLevel
    • Implement the constructor Product(String productid, int salesVelocity, int stockLevel)
    • Create a class called InventoryClearance.
    • Create a method called identifyClearanceItems(List<Product> products) that returns a list of strings representing the product IDs that are eligible for clearance.

    Constraints:

    • 1 <= n <= 10^5
    • 0 <= salesVelocity <= 10^5
    • 0 <= stockLevel <= 10^5
Candidate's Approach
  1. For the Items Purchase question, the approach involves using a greedy algorithm combined with a max heap. The steps are as follows:

    • Heapify the price array.
    • Continuously pop the largest price, apply the discount using the coupons, and push the discounted price back into the heap.
    • Stop when either the number of coupons (m) becomes 0 or the price array is empty.
    • Finally, return the sum of the remaining prices in the array.

    The time complexity is O(m * log(n)) and space complexity is O(n).

  2. For the Java specific question, the implementation involves creating the Product class with the specified properties and constructor, and the InventoryClearance class with the method to identify clearance items based on the given criteria.

Interviewer's Feedback

No feedback provided.