Kodeday

  Given an input string and a substring. Find the frequency of occurrences of a substring in a given string. Input : man (pattern) dhimanman (string) Output : 2 Solution: def lpsarray(pat,m,lps): l=0 i=1 lps[0]=0 while(i<m): if pat[i]==pat[l]: l+=1 lps[i]=l i+=1 else: if l!=0: l=lps[l-1] else: lps[i]=0 i+=1 def kmpsearch(pat,txt): m=len(pat) n=len(txt) lps=[None]*m lpsarray(pat,m,lps) i=0 j=0 res=0 next_i=0 while(i<n): if pat[j]==txt[i]: j=j+1 i+=1 if j==m: j=lps[j-1] res+=1 if lps[j]!=0: next_i+=1 i=next_i j=0 elif i<n and pat[j]!=txt[i]: if(j!=0): j=lps[j-1] else: i+=1 return res t...

  You are given a read-only array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing. Return A and B. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Note that in your output A should precede B. Example: Input:[3 1 2 5 3] Output:[3, 4] A = 3, B = 4 Solution: class Solution:     # @param A : tuple of integers     # @return a list of integers     def repeatedNumber(self, A):         d={}                  for i in A:             if i in d:                 d[i]+=1             else:                 d[i]=1         for i in range(1,len(A)+1):             if i not in d:   ...

  Find the   contiguous   subarray within an array,   A   of length   N   which has the   largest sum . Input Format: The first and the only argument contains an integer array, A. Output Format: Return an integer representing the maximum possible sum of the contiguous subarray. Constraints: 1 <= N <= 1e6 -1000 <= A[i] <= 1000 For example: Input 1: A = [1, 2, 3, 4, -10] Output 1: 10 Explanation 1: The subarray [1, 2, 3, 4] has the maximum possible sum of 10. Input 2: A = [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output 2: 6 Explanation 2: The subarray [4,-1,2,1] has the maximum possible sum of 6. Solution: we can use  Kadane's Algo O(n) | O(1) class Solution:     # @param A : tuple of integers     # @return an integer     def maxSubArray(self, A):         s=-(2**30)         ans=0         for i in A:       ...

  Problem Description Given an integer array  A , find if an integer  p  exists in the array such that the number of integers greater than  p  in the array equals to  p . Input Format The first and only argument is an integer array A. Output Format Return 1 if any such integer p is found else return -1. Example Input Input 1: A = [3, 2, 1, 3] Input 2: A = [1, 1, 3, 3] Example Output Output 1: 1 Output 2: -1 Example Explanation Explanation 1: For integer 2, there are 2 greater elements in the array. So, return 1. Explanation 2: There is no such integer exists. Solution: class Solution: # @param A : list of integers # @return an integer def solve(self, A):     A=sorted(A)     n=len(A)     if A[-1]==0:         return 1                          for i in range(n-1):             if A[i]==A[i+...