Kodeday

  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:             ...

  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 pa...

  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: ...

  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: