A selection of 3 questions from LeetCode

Leet Code Practice Selection

2 days left for the Palantir interview. I do practice with Leet Code questions and I would like to share some problems with their solutions

50. Pow(x, n)

Implement pow(x,n)

And important corner case is n can be minus.

def myPow(x, n):
    """
    :type x: float
    :type n: int
    :rtype: float
    """
    if x == 0:
        return 0
    if n<0:
        x = 1/x
        n = -n
    res = 1
    while n != 0:
        if n&1 == 1:
            res *= x
        x *= x
        n >>= 1
    return res

287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

• You must not modify the array (assume the array is read only).
• You must use only constant, O(1) extra space.
• Your runtime complexity should be less than O(n2).
• There is only one duplicate number in the array, but it could be repeated more than once.

Solution

• I provide here an nlogn solution. Note that the elements I got is in $[1,len(nums)-1]$ and I can count elements smaller than and greater than the $mid=\frac{j+i}{2}$. Having a duplicate would disturb this balance and we detect it carefully and then recurse to that side.
• I read this, providing a really interested O(n) solution to this algorithm.

def findDuplicate(nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        return binSearch(nums,1,len(nums)-1)
        
def binSearch(arr,i,j):
    if i>=j:
        return i
    else:
        q = (j+i) // 2
        less_c = 0
        bigger_c = 0
        for e in arr:
            if i <= e <= j:
                if e <= q:
                    less_c += 1
                else:
                    bigger_c +=1
        if less_c > bigger_c:
            return binSearch(arr,i,q)
        else:
            return binSearch(arr,q+1,j)

print findDuplicate([1,2,3,9,4,5,6,7,8,9,10])

9

124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example: Given the below binary tree,
1
/ \
2 3
Return 6.

def maxPathSum(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    self.cmax = float('-inf')
    last = self.postOrder(root)
    return self.cmax

def postOrder(self,node):
    if not node:
        return 0
    l = self.postOrder(node.left)
    r = self.postOrder(node.right)
    tot = l+r+node.val
    self.updateMax(tot)
    if l > r:
        return max(0,tot - r)
    else:
        return max(0,tot - l)

def updateMax(self,v):
    if v>self.cma`x:
        self.cmax = v