yokuyuki
BAN USER1. It does check to the right of the array when arr[mid] == mid when it sets start = mid+1. Yours doesn't.
2. I think the phrasing of the question needs to be better, but I don't think you can do it in log n time without the constraint that the numbers be increasing sorted AND >= 0. Checking the mid in a binary search without the constraint that the array is >= 0 doesn't reveal any information on where in the array all the elements that are equal to the index are.
I don't get how this answer, which is clearly wrong, got upvoted.
>> if (val == 0) {
This line is the problem. If the element at index m is equal to the index, you're not done searching because there could be elements past m which are also equal to the index that you haven't searched yet. You can't just return m at that point; you have to search until a[m] == m and a[m+1] == m+1. You also have to account for the edge case in which m+1 is past the end of the array. On top of that, the question is asking for the elements and not the last index where the element value is equal to its index.
Here's a counter-example that doesn't work for this implementation:
[0 1 2 4]
In the first iteration, l = 0, r = 3, so m = 1. val = a[m] - m = 1 - 1 = 0 which will return m = 1 which is wrong because 2 is also equal to its index.
Below is a correct Python implementation:
def find_elements_equal_to_index(arr):
start = 0
end = len(arr)-1
while start <= end:
mid = (start+end)/2
if arr[mid] == mid:
if mid+1 < len(arr) and arr[mid+1] == mid+1:
start = mid+1
else:
return arr[:mid+1]
else:
end = mid-1
return None
I was counting each call of std::reverse as a traversal, but after understanding what std::reverse is, I can see how it is n swaps.
However, this answer would be unacceptable in an interview because they usually prohibit using convenience functions and want to see you do the actual element swaps.
If positive k is rotating to the right and negative k is rotating to the left, you can just adjust them all to rotate to the right by taking the modulus of k by the length of the array. Below is my Python version:
def rotate(arr, k):
k %= len(arr)
if k != 0:
current = 0
store = arr[current]
for i in range(len(arr)):
current = (current + k) % len(arr)
arr[current], store = store, arr[current]
return arr
Python version:
def is_valid_bst(node):
previous_value = None
stack = []
while stack or node:
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
if previous_value > node.value:
return False
else:
previous_value = node.value
node = node.right
return True
1. Check if there are 4 points.
2. Find the distances of the other coordinates to the first coordinate.
3. Find the furthest distance which is the opposite corner and the two equal distances which are the two sides.
4. The two sides should be equal length and the furthest distance should be sqrt(2) * side.
Python version:
def determine_if_square(coords):
def distance(pair1, pair2):
return ((pair1[0]-pair2[0])**2 + (pair1[1]-pair2[1])**2)**0.5
def approx_equal(a, b):
return abs(a-b) / (abs(a) + abs(b)) * 2 < 0.001
if len(coords) != 4:
return False
selected = coords[0]
distance_to_selected = [distance(coord, selected) for coord in coords[1:]]
furthest_distance = max(distance_to_selected)
adjacent = []
for i in range(len(distance_to_selected)):
if distance_to_selected[i] == furthest_distance:
furthest = i
else:
adjacent.append(i)
if len(adjacent) != 2 or not approx_equal(distance_to_selected[adjacent[0]], distance_to_selected[adjacent[1]]):
return False
return approx_equal(furthest_distance, distance_to_selected[adjacent[0]]*(2**0.5))
Python version:
def evaluate_postfix(expression):
stack = []
split_expression = expression.split()
for chunk in split_expression:
try:
value = float(chunk)
stack.append(value)
except ValueError:
value1 = stack.pop()
value2 = stack.pop()
if chunk == '+':
result = value2 + value1
elif chunk == '-':
result = value2 - value1
elif chunk == '*':
result = value2 * value1
elif chunk == '/':
result = value2 / value1
elif chunk == '%':
result = value2 % value1
else:
raise SyntaxError('Invalid operator')
stack.append(result)
return stack.pop()
Python version:
def intersect_sorted_array(arr1, arr2):
index1 = 0
index2 = 0
intersection = set()
while index1 < len(arr1) and index2 < len(arr2):
if arr1[index1] > arr2[index2]:
index2 += 1
elif arr1[index1] < arr2[index2]:
index1 += 1
else:
intersection.add(arr1[index1])
index1 += 1
index2 += 1
return intersection
Python version:
def maximal_subarray(arr):
if not arr:
return []
max_sum = arr[0]
max_start = 0
max_end = 0
current_sum = arr[0]
current_start = 0
for i in range(1, len(arr)):
current_sum += arr[i]
if current_sum < arr[i]:
current_sum = arr[i]
current_start = i
if current_sum > max_sum:
max_sum = current_sum
max_start = current_start
max_end = i
return arr[max_start:max_end+1]
Assuming an existing node class with node.left, node.right, and node.value properties, below is a Python solution:
- yokuyuki June 25, 2013