# 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.cmax:
self.cmax = v



`

Tags:

Categories:

Updated: