Microsoft Technical Interview

Interview started with basic introduction round. Interviewer had shared codelity to do online coding.

Before writing code of given proble statement interviewer was more eager to know the approach of solution.

Few questions are important before solving any quesitons. They expect to reply properly:

• Explain me the approach for the solution of this problem?
• What will be the time and space complexity?
• Why list or array or hashmap or disctionary?
• Do you have any alternative approach to solve this problem?

Below were the questions:

53. Maximum Subarray

This is a pretty simple question. You can solve by using Kadane's algorithm technique.

Another questions..

Policemen catch thieves

Given an array of size n that has the following specifications:

Each element in the array contains either a policeman or a thief.
Each policeman can catch only one thief.
A policeman cannot catch a thief who is more than K units away from the policeman.

We need to find the maximum number of thieves that can be caught.

Example:

Input : arr[] = {'P', 'T', 'T', 'P', 'T'},
k = 1.

Output : 2.

Here maximum 2 thieves can be caught, first
policeman catches first thief and second police-
man can catch either second or third thief.

This problem can be solved by using greedy technique.

Always be yourself. Push hard and always explain approach before writing code. Keep talking during interview. Don't be silent for a while too.

Solution

53. Maximum Subarray

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        # Kadane's Algorithm
        max_so_far = float('-inf')
        max_ending_here = 0
        size = len(nums)
        
        for i in range(size):
            max_ending_here = max_ending_here + nums[i]
            if (max_so_far < max_ending_here):
                max_so_far = max_ending_here
                
            if max_ending_here < 0:
                max_ending_here = 0 
        
        return max_so_far
        
        

Policemen catch thieves

def policeThief(arr, n, k):
    i = 0
    l = 0
    r = 0
    res = 0
    thi = []
    pol = []
 
    # store indices in list
    while i < n:
        if arr[i] == 'P':
            pol.append(i)
        elif arr[i] == 'T':
            thi.append(i)
        i += 1
 
    # track lowest current indices of
    # thief: thi[l], police: pol[r]
    while l < len(thi) and r < len(pol):
         
        # can be caught
        if (abs( thi[l] - pol[r] ) <= k):
            res += 1
            l += 1
            r += 1
             
        # increment the minimum index
        elif thi[l] < pol[r]:
            l += 1
        else:
            r += 1
 
    return res