4 Sum

08 Nov 2018 in Programming on Hash table, Hash, Interview, Python

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

O(n^2)

import collections
class Solution:
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        count = 0
        cnt = collections.defaultdict(int)
        for a in A:
            for b in B:
                cnt[a+b] += 1
        for c in C:
            for d in D:
                count += cnt[-(c+d)]
        # AB = collections.Counter(a+b for a in A for b in B)
        # return sum(AB[-c-d] for c in C for d in D)
        return count

Repeating Sub-Sequence

Given a string, find if there is any sub-sequence that repeats itself. A sub-sequence of a string is defined as a sequence of characters generated by deleting some characters in the string without changing the order of the remaining characters.

Input:

string

Output:

0/1
0 -> No
1 -> Yes 

Example:

abab ------> yes, ab is repeated. So, return 1. 
abba ------> No, a and b follow different order. So, return 0. 

NOTE : sub-sequence length should be greater than or equal to 2

class Solution:
    def isPalindrome(self, s, lo, hi):
        if lo >= hi:
            return 1
        return (s[lo]==s[hi]) and self.isPalindrome(s, lo+1, hi-1)
        
    # @param A : string
    # @return an integer
    def anytwo(self, A):
        n = len(A)
        freq = {}
        for i in range(n):
            if A[i] in freq.keys():
                freq[A[i]] += 1
                if freq[A[i]] >= 3: return 1
            else:
                freq[A[i]] = 1
        tmp = ""
        for i in range(n):
            
            if freq[A[i]] > 1:
                tmp += A[i]
        if not self.isPalindrome(tmp, 0, len(tmp)-1):
            return 1
        else:
            return 0 

##Points on the Straight Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Sample Input :

(1, 1)
(2, 2)

Sample Output :

2

You will be give 2 arrays X and Y. Each point is represented by (X[i], Y[i])

Hint:

• Three points are on the same line when the slopes ((y1-y2)/(x1-x2)) of any 2 points relative to the remaining point (called origin) are the same.
• We count the total number of points that have same slopes to any origin
• Be careful when the points are vertical (x1-x2 = 0)
• Remember to count the overlap points (y1-y2 = x1-x2 = 0)
• The rounding of slopes is not a problem in python

import collections
class Solution:
    # @param A : list of integers
    # @param B : list of integers
    # @return an integer
    def maxPoints(self, A, B):
        if len(A) <= 2: return len(A)
        d = collections.defaultdict(int) # slope : count
        result = 0
        for i in range(len(A)):
            d.clear()
            overlap, curmax = 0, 0
            for j in range(i+1, len(A)):
                dx, dy = A[j] - A[i], B[j] - B[i]
                if dx == 0 and dy == 0:
                    overlap += 1
                    continue
                slope = dy * 1.0 / dx if dx != 0 else 'infinity'
                d[slope] += 1
                curmax = max(curmax, d[slope])
            result = max(result, curmax+overlap+1)
        return result