Kodeday

  You are given an array (zero-indexed) of   N   non-negative integers,   A 0 ,   A 1   ,…,   A N-1 . Find the minimum sub-array  A l ,  A l+1 ,…,  A r  so if we sort(in ascending order) that sub-array, then the whole array should get sorted. If  A  is already sorted, output  -1 . Example : Input 1: A = [1, 3, 2, 4, 5] Return: [1, 2] Input 2: A = [1, 2, 3, 4, 5] Return: [-1] In the above example(Input 1), if we sort the subarray  A 1 ,  A 2 , then whole array  A  should get sorted. ut Solution: class Solution:     # @param A : list of integers     # @return a list of integers     def subUnsort(self, A):         s_a=sorted(A)         if A==s_a:             return [-1]         l=len(A)         minI=-1         maxI=l         f1=True         f2=True         for i in range(l):             if A[i]!=s_a[i] and i>minI and f1==True:                 minI=i                 f1=False             if A[l-i-1]!=s_a[l-i-1] and l-1-i<maxI and f2==True:                 maxI=l-i-1              

  Problem Description Given an array  A  of integers, find the maximum of  j - i  subjected to the constraint of  A[i] <= A[j] . Input Format First and only argument is an integer array A. Output Format Return an integer denoting the maximum value of j - i; Example Input Input 1: A = [3, 5, 4, 2] Example Output Output 1: 2 Example Explanation Explanation 1: Maximum value occurs for pair (3, 4). Solution: class Solution:     # @param A : tuple of integers     # @return an integer     def maximumGap(self, A):         n=len(A)             R = [0] * n              R[n - 1] = A[n - 1]          for j in range(n - 2, -1, -1):              R[j] = max(A[j], R[j + 1]);               i = 0;j=0         diff = -1         while (j < n and i < n):              if (A[i] <= R[j]):                  diff = max(diff, j - i)                  j+=1             else:                  i+=1              return diff                                 Screenshot:

  You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). You need to do this in place. Note that if you end up using an additional array, you will only receive partial score. Example: If the array is [ [1, 2], [3, 4] ] Then the rotated array becomes: [ [3, 1], [4, 2] ] Solution: class Solution:     # @param A : list of list of integers     # @return the same list modified     def rotate(self, A):         l = len(A)         for i in range(l//2):             A[i], A[l-i-1] = A[l-i-1], A[i]         ans = [[A[j][i] for j in range(l)] for i in range(len(A[0]))]         return ans Screenshot:

  Given a read-only array of n + 1 integers between 1 and n, find one number that repeats in linear time using less than O(n) space and traversing the stream sequentially O(1) times. Sample Input: [3 4 1 4 1] Sample Output: 1 If there are multiple possible answers ( like in the sample case above ), output any one. If there is no duplicate, output -1 Solution class Solution:     # @param A : tuple of integers     # @return an integer     def repeatedNumber(self, A):         l_A=len(A)         s_A=set(A)         d={}         l_s=len(s_A)         if l_A==l_s:             return -1         for i in A:             if i in d:                 d[i]+=1             else:                 d[i]=1         for i,j in d.items():             if j>1:                 return i          Screenshot:

  You are given a binary string( i.e.   with characters   0   and   1 ) S consisting of characters S 1 , S 2 , …, S N . In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and flip the characters S L , S L+1 , …, S R . By flipping, we mean change character   0   to   1   and vice-versa. Your aim is to perform ATMOST one operation such that in final string number of  1 s is maximised. If you don’t want to perform the operation, return an empty array. Else, return an array consisting of two elements denoting L and R. If there are multiple solutions, return the lexicographically smallest pair of L and R. Notes : Pair (a, b) is lexicographically smaller than pair (c, d) if a < c or, if a == c and b < d. For example, S = 010 Pair of [L, R] | Final string _______________|_____________ [1 1] | 110 [1 2] | 100 [1 3] | 101 [2 2] | 000 [2 3] | 001 We see that two pairs [1, 1] and [1, 3] give same number of 1s in f

  Given a non-negative number represented as an array of digits, add 1 to the number ( increment the number represented by the digits ). The digits are stored such that the most significant digit is at the head of the list. Example: If the vector has  [1, 2, 3] the returned vector should be  [1, 2, 4] as  123 + 1 = 124 .   NOTE:  Certain things are intentionally left unclear in this question which you should practice asking the interviewer. For example, for this problem, following are some good questions to ask : Q :  Can the input have 0’s before the most significant digit. Or in other words, is  0 1 2 3  a valid input? A :  For the purpose of this question,  YES Q :  Can the output have 0’s before the most significant digit? Or in other words, is  0 1 2 4  a valid output? A :  For the purpose of this question,  NO . Even if the input has zeroes before the most significant digit. Solution: class Solution:     # @param A : list of integers     # @return a list of integers     def plusO

  You are given an array of N integers, A 1 , A 2 ,…, A N . Return maximum value of   f(i, j)   for all 1 ≤   i, j   ≤ N. f(i, j)  is defined as  |A[i] - A[j]| + |i - j| , where |x| denotes the absolute value of x. For example , A=[1, 3, -1] f(1, 1) = f(2, 2) = f(3, 3) = 0 f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3 f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4 f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5 So, we return 5. Solution: class Solution:     # @param A : list of integers     # @return an integer     def maxArr(self, A):         a=[]         b=[]         for i in range(len(A)):             a.append(A[i]-i)             b.append(A[i]+i)         return max(max(a)-min(a),max(b)-min(b)) Screenshot: