# Amazon interview questions

### Meeting Rooms

Given an array of intervals representing N meetings, find out if a person can attend all the meetings. Input: [[6,7],[2,4],[8,12]] Output: true Explanation: None of the meetings overlap with each other. Input: [[1,4],[2,5],[7,9]] Output: false Explanation: Meetings [1,4] and [2,5] overlap with each other. This problem is commonly asked nowadays ...

### Maximal square area

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. This problem is known as maximal square area problem. For example, Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 ...

### Longest subarray without repeated numbers

Given an array, find the length of the longest subarray which has no repeating numbers. Input: A = {1,2,3,3,4,5} Output: 3 Explanation: Longest subarray without any repeating elements are {1,2,3} & {3,4,5}. Thought Process 1. Brute Force In this approach, you will consider each subarray and then check whether that ...

### Single number in an array

Given a non-empty array of integers, every element appears twice except for one. Find that single one. Example 1: Input: [2,2,1,3,4,3,5,4,5,] Output: 1 Example 2: Input: [4,1,2,1,2] Output: 4 Approach 1 You will be thinking it’s a very simple problem. What we all need to do is to take count ...

### Subarrays with given sum

We are given an unsorted array containing positive and negative numbers, we need to find the number of subarrays with the given sum, k. For example, Input:  arr = [2, 4, -5, -5, 6] and k = -10 Output: 1 Explanation: We can see that there is only one subarray (index ...

### Find friend groups

There are Nstudents in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if Ais a direct friend of B, and Bis a direct friend of C, then Ais an indirect friend of C. And we defined a friend circle ...

### Longest Mountain in Array

The mountain at index i in array arris defined such that arr[i-N]..arr[i-1]< arr[i] > arr[i+1] arr[i+N] where i cannot be 0 and arr.length-1 which means that the index(i) cannot be at the extreme ends in the array (start and end of an array). Given an array A of integers, return the length of ...

### Trapping rain water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after rain. For example, Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Basic thought We know water stays at the highest level it is able to, and it always maintains the ...

### Russian doll envelopes

There are a number of envelopes with widths and heights given as a pair of integers (w, h). An envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. Given the list ...

### Longest subarray with sum at most k

Given an array of integers A[], find the length of the longest subarray with the sum at most k where k is an integer. For example: Input: A[] = [10, 5, 2, 7, 1, 9], k = 15 Output: 4 Explanation longest subarray with sum at most K is [ ... 