Date : 18 November 2020

What is the angle between hands at 10:20?

180

170

190

160

**Ans: 190**

At 10:20 the minute hand is at 4 and it makes an angle of 4*30 = 120 deg from 12.

At 10:20 the hour hand is between 10 and 11 and it makes an angle of

10******30+ (20**30)/60 = 300+10 = 310 deg from 12.

At 10:20 the minute and the hour hands make an angle of 310–120 = 190 deg between them.

Given a heap with n elements that supports insert and extract-min, which of the following tasks can be achieved in O(logn) time?

Finding the median of the elements stored in the heap.

Finding the largest element stored in the heap.

Finding the fifth-smallest element stored in the heap.

None of the given options.

**Ans: **Finding the fifth-smallest element stored in the heap.

`It's a min heap so,`

` 1. Finding the median of the elements stored in the heap. `

`Explanation : `

`For median we need to find middle elements so, total time will be O(nlogn) `

`2. Finding the largest element stored in the heap. `

`Explaination :`

` Largest element will be the last element so total time needed will be O(nlogn) `

`3. Finding the fifth-smallest element stored in the heap. `

`Explaination:`

`First smallest element can be found in O(1) then perform heapify which will take O(logn), so finding fifth smallest element will be O(4*logn) i.e, O(logn).`

Given a binary array, find the maximum length of a contiguous subarray with an equal number of 0 and 1.

`Input:`

[0,1,0]

`Output:`

2

` Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.`

Starting from left of array and keep adding elements to a variable

**sum**Add

**-1 for 0**and**1 for 1**Now, every time sum becomes zero, we know all the elements from begining of array have been neutralized, meaning we have got an equal number of ones and zeroes, let this occurs at index i, so longestContArray = i+1 (because we are dealing with indices)

But we are not done yet!, consider the case : [1,

**1,0**,1,1]

In this case, the sum will never become zero,

but there exists a subarray of length 2, having equal 0 & 1

let's see the value of sum at index: 1 and 3

Ohh!! sum = 2 for both indices

what does this mean???

**This means that if we get the same sum value for two indices i and j, then all the elements within the range [i,j) or (i,j] have been neutralized**What data structure can remember the sum and index

Of course! Map, so we use a map to store the sum and index values,

if sum == 0 then we have already solved the cases

but if sum!=0 and this sum doesn't already exist in the map, then store it with its corresponding index

but if sum !=0 and sum already exists in the map then, depending on whether i - m[sum] > LongestContArray, update LongestContArray

Note we need to store a unique sum value only once, after that whenever we encounter the same sum again our interval length is going to increase only and that is what we want ex- [1,0,1,0,1] we get sum = 1 three times we store sum = 1 for index = 0 only and never update it as we want the longest length.

Solution.cpp

Solution.java

Solution.py

Solution.cpp

int findMaxLength(vector<int>& nums) {int sum=0;unordered_map<int,int> m;unsigned int longestContArray = 0;for(int i=0;i<nums.size();i++){sum += (nums[i]==0)?-1:1;auto it = m.find(sum);if(sum == 0){if(longestContArray < i+1)longestContArray = i+1;}else if(it != m.end()){if(longestContArray < i-it->second)longestContArray = i-it->second;}else if(it == m.end())m.insert({sum,i});}return longestContArray;}

Solution.java

public class Solution {public int findMaxLength(int[] nums) {Map<Integer, Integer> map = new HashMap<>();map.put(0, -1);int maxlen = 0, count = 0;for (int i = 0; i < nums.length; i++) {count = count + (nums[i] == 1 ? 1 : -1);if (map.containsKey(count)) {maxlen = Math.max(maxlen, i - map.get(count));} else {map.put(count, i);}}return maxlen;}}

Solution.py

def findMaxLength(self, nums: List[int]) -> int:mp = {0: -1}prefix_sum = 0result = 0for idx, num in enumerate(nums):prefix_sum += 1 if num == 1 else -1if prefix_sum in mp:result = max(result, idx - mp[prefix_sum])else:mp[prefix_sum] = idxreturn result