I appeared for Amazon Interview which was scheduled yesterday. I was asked 2 DSA questions and problems related to OOPS & OS in my first interview round.

Problem 1

Given a 2D array containing only 0, 1 and 2 with following definition :

0 : Healthy Patient with no vaccine
1 : Patient infected with virus
2 : Healthy Vaccinated patient

If patient is infected with virus and it can infect the adjacent patients, if not vaccinated, in a unit time (if they not infected i.e 0 will be converted to 1). We need to find the minimum time in which all the neutral patients gets infected (that is all 0s are converted to 1) or print -1 if it is not possible.

My Approach : I was able to solve this problem in 20 min. My approach was simply to use BFS and find the minimum time.

Problem 2

Given an array of integers (with both positive and negative values) we need to find the maximum number of disjoint subarrays having equal sum.

Example :

Input : [1, 2, 3] Output : 2 {since we have at most 2 subarrays with sum = 3 i.e. [1, 2],[3]}

Input: [2 2 2 -2] Output : 2 {two subarrays each with sum = 2 i.e. [2],[2, 2, -2]}

My Approach

First approach that came to my mind was to find the prefix sum array and then taking each element (prefix[i]) as target finding the number of subarrays with sum = prefix[i] .

But this failed in the case of negative numbers. So I thought of using a suffix array as well to check from last (following the same process as above). But this again failed other test cases.

NOTE Do tell me how to handle the negative cases?

OOPS Questions

1. I was coding using Java. So he asked language specific questions related to Java. Like byte code etc.
2. Overriding vs Overloading with examples.
3. Exception Handling
4. Object class