Source: binarysearch | Learn Algorithms Together
Description:
Given a list of integers
nums, return the number of contiguous arithmetic sequences of length≥ 3.Input: nums = [5, 7, 9, 11, 12, 13]
Output: 4
Answer:
return sum(map( lambda n: n*(n-1)//2, [len(list(g)) for _, g in groupby(zip(nums[:-1], nums[1:]), lambda p: p[1] - p[0])]))Explanations:
-
groupby(zip(nums[:-1], nums[1:]): divide input list into pairs, groupby there differences between elements. -
output after list of groupby could be like:
[[(5, 7), (7, 9), (9, 11)], [(11, 12), (12, 13)]] -
As given return the number of contiguous arithmetic sequences of length
≥ 3. means count the number of sub-group of group with length >= 2. Calculate byn*(n-1)//2with n = length of group.
Source: binarysearch | Learn Algorithms Together
Description:
You are given a two-dimensional list of integers
matrixwhich contains1s and0s. Given that each row is sorted in ascending order with0s coming before1s, return the leftmost column index with the value of1. If there's no row with a1, return-1.Can you solve it faster than O(nm).
Answer:
return -1 if not len([matrix[i].index(1) for i in range(len(matrix)) if 1 in matrix[i]]) else min([matrix[i].index(1) for i in range(len(matrix)) if 1 in matrix[i]])Explanations:
Actually it should be:
left_most = [matrix[i].index(1) for i in range(len(matrix)) if 1 in matrix[i]]
return -1 if not len(left_most) else min(left_most)But the answer still fits under time limitation.
Source: binarysearch | Learn Algorithms Together
Description:
You are given a list of integers
numswhere each number represents a vote to a candidate.Return the ids of the candidates that have greater than ⌊3n⌋ votes, in ascending order.
Bonus: solve in O(1) space.
Answer:
return sorted(list(c for c in Counter(nums) if Counter(nums)[c] > len(nums)/3))Source: binarysearch | Learn Algorithms Together
Description:
You are given an integer
nrepresenting the number of seats in an airplane. The first person has lost their ticket, so they pick a random seat. Everyone else still has their ticket, but if their seat is already taken, they will also randomly pick an available seat.Return the probability that the last person gets their assigned seat.
Answer:
return 0.5 if n != 1 else 1Explanations:
This is just a tricky question.
Collection of 1-line Python answers on some online code challenges.
Source: binarysearch | Learn Algorithms Together
Description:
You are given two lists of integers
aandbrepresenting sensor metrics. Each list contains unique integers anda ≠ b. One of the lists contains accurate sensor metrics but the other one is faulty. In the faulty list one number that wasn't the last number was dropped and a fake value was appended to the end of the list. Return the number that was dropped.Input
a = [1, 2, 3]
b = [2, 3, 5]
Output
1
Answer:
return set(a).difference(set(b)).pop() if set(b).difference(set(a)).pop() == b[-1] else set(b).difference(set(a)).pop()Explanations:
Long version:
class Solution:
def solve(self, a, b):
_a = set(a)
_b = set(b)
__a = _a.difference(_b)
__b = _b.difference(_a)
x = __b.pop()
if x == b[-1]:
return __a.pop()
else:
return x
print(__a, __b)Source: binarysearch | Learn Algorithms Together
Description:
You are given a two-dimensional list of integers
matrixwhere each row is sorted in ascending order. Return the smallest number that exists in every row. If there's no solution, return-1.
Answer:
return -1 if not matrix else min(set.intersection(*[set(n) for n in matrix])) if set.intersection(*[set(n) for n in matrix]) else -1Explanations:
Just find the intersection of rows.
Source: binarysearch | Learn Algorithms Together
Description:
Given a non-negative integer
n, return the length of the longest consecutive run of1s in its binary representation.
Answer:
return max([len(list(g)) for c, g in groupby(str(bin(n))) if c == '1']) if n else 0Explanations:
Convert binary of n to string, groupby and find the max length of groupby object of '1'.