@shawngao thanks for this! there is a good video explanation of the algorithm here
Hope it helps someone.
@shawngao thanks for this! there is a good video explanation of the algorithm here
Hope it helps someone.
We essentially want to find all the edges that form a cycle and return the last one. Below is my code using union find.
You can find very clear explanation of union find algo in this link: https://youtu.be/ID00PMy0-vE
This question is very similar to finding cycle in undirected graph using union find
class Solution(object):
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
ds = DisjointSet()
result = []
for u, v in edges:
ds.make_set(u)
ds.make_set(v)
for u, v in edges:
parent1 = ds.find_set(u)
parent2 = ds.find_set(v)
if parent1 == parent2: # cycle, add to result list
result.append([u, v])
else:
ds.union(u, v)
return result[-1]
class Node(object):
def __init__(self, data, parent = None, rank = 0):
self.data = data
self.parent = parent
self.rank = rank
def __str__(self):
return str(self.data)
def __repr__(self):
return self.__str__()
class DisjointSet(object):
def __init__(self):
self.map = {}
self.num_sets = 0
def make_set(self, data):
node = Node(data)
node.parent = node # very important!
self.map[data] = node
self.num_sets += 1 # make_set increases the number of disjoint sets by one
def union(self, data1, data2):
# gets nodes given data values
node1 = self.map[data1]
node2 = self.map[data2]
# get parents given nodes
parent1 = self.find_set_util(node1)
parent2 = self.find_set_util(node2)
# if they are part of same set do nothing
if parent1.data == parent2.data:
return
# else whoever's rank is higher becomes parent of other
if parent1.rank >= parent2.rank:
# increment rank only if both sets have same rank
if parent1.rank == parent2.rank:
parent1.rank = parent1.rank + 1
parent2.parent = parent1
else:
parent1.parent = parent2
self.num_sets -= 1 # union decreases the number of disjoint sets by one
# Finds the representative of this set
def find_set(self, data):
return self.find_set_util(self.map[data]) # pass in the node
# Find the representative recursively and does path compression as well.
def find_set_util(self, node):
parent = node.parent
if parent == node:
return parent
node.parent = self.find_set_util(node.parent) # path compression
return node.parent
Use two pointers: left and right
class Solution(object):
def findLengthOfLCIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left, right, max_length = 0, 0, 1
if not nums: return 0
for i in range(1, len(nums)):
# we've found a continuous increasing subsequence, move right
if nums[i - 1] < nums[i]:
right += 1
# find max_length
max_length = max(max_length, right - left + 1)
else:
# move left and right
left = right = i
return max_length
python solution:
def valid_password(s):
left, right, max_length = 0, 0, 0
while right < len(s):
while right < len(s) and s[right].isdigit():
right += 1
left = right
found_upper = False
while right < len(s) and not s[right].isdigit():
if s[right].isupper():
found_upper = True
right += 1
if found_upper:
max_length = max(max_length, right - left)
return -1 if max_length == 0 else max_length
You would like to set a password for an email account. However, there are two restrictions on the format of the passowrd. It has to contain at least one uppercase character and it cannot contain any digits.
You are given a string S consisting of N alphanumerical characters. You would like to find the longest substring of S that is a valid password. A substring is defined as a contiguous segment of a string.
For example, given "a0Ba", the substrings that are valid passowrds are "B" and "Ba". Note that "aBa" is not a substring and 'a0B' is not a valid password.
Write a function that givne a non-empty string S consisting of N characters, returns the length of the longest substring that is a valid password. If there is not such substring, your function should return -1.
Example 1:
S = "a0Ba"
return 2
Example 2:
S = "a0bb"
return -1
@hutashan-gmail.com good job and thanks for the reply :-D. btw met this at a (the?) major online retailer's online coding assessment.
A non-empty zero-indexed array A consisting of N integers is given. A slice of that array is a pair of integers (P, Q) such that O <= P <= Q <= N
Integer P is called the beginning of the slice; integer Q is called the end of the slice. The number Q - P + 1 is called the size of the slice. A slice (P, Q) of array A is called ascending if the corresponding items form a strictly increasing sequence: A[P] < A[P + 1] < ... < A[Q - 1] < A[Q].
Note that we consider a slice (P, P) consisting of one element to be ascending.
For example, consider array A such that:
A[0] = 2
A[1] = 2
A[2] = 2
A[3] = 2
A[4] = 1
A[5] = 2
A[6] = -1
A[7] = 2
A[8] = 1
A[9] = 3
Pair (0, 3) is a slice of array A of size 4 that is not ascending.
Pair (2, 2) is a slice of size 1 that is ascending.
Pair (4, 5) is a slice of size 2 that is ascending.
Pair (6, 7) and (8, 9) are other slices of size 2 that are ascending.
There is no slice of array A that is ascending and has size greater than 2.
Write a function:
def solution(A)
that, given a zero-indexed array consisting of N integers, returns the beginning of any ascending slice of maximal size.
For instance, in the above example, the function may return 4, 6, or 8 as explained above.
For the following array A consisting of N = 3 elements:
A[0] = 30
A[1] = 20
A[2] = 10
the function may return 0, 1 or 2, because all the ascending slices of this array have size 1.
Assume that:
* N is an integer within range [1..150,000]
* each element of A is an integer within the range [-2**31 .. 2**31 - 1]
Complexity:
* expected worse-case time complexity is O(N)
* expected worse-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input can be modified.