gnahzy
BAN USER@Eugene, interesting test framework. but actually you didn't implement my code correctly. that what i got:
>>> DP.count_unique_strings("acababbbbcbcaabaaacabcacbaabbc")
[1, 1, 1, 1, 1, 1, 2, 3, 4, 1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2
, 1, 2, 1]
[0, 1, 2, 1, 2, 3, 3, 3, 3, 4, 5, 6, 1, 1, 2, 3, 3, 3, 3, 4, 1, 1, 1, 2, 1, 1, 1
, 3, 3, 2]
111
>>> DP.count_unique_strings("abbabaaaacccbccabbaabccabacbaacabcbaabbbbccbbcbacac
bcabcaccbbbaaacabacacabcbbaccaaacaaaabaccccbcccca")
[1, 1, 2, 1, 1, 1, 2, 3, 4, 1, 2, 3, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 1, 1
, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 3, 4, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2,
1, 2, 3, 1, 1, 2, 3, 4, 1, 1, 1, 2, 3, 4, 1, 1, 2, 3, 4, 1]
[0, 1, 1, 3, 4, 5, 5, 5, 5, 4, 4, 4, 3, 4, 4, 2, 1, 1, 3, 3, 5, 1, 1, 2, 1, 2, 1
, 1, 1, 1, 2, 3, 1, 1, 2, 1, 1, 3, 3, 3, 3, 4, 4, 6, 6, 8, 9, 1, 1, 2, 3, 1, 2,
1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 1, 2, 1, 2, 3, 4, 1, 1, 2, 2, 2, 1, 1,
3, 3, 3, 6, 7, 7, 7, 7, 4, 5, 1, 1, 1, 1, 4, 5, 5, 5, 5, 4]
439
@eugene, yes... you are right. my code does not work case like 'aba'. made some modification to handle this case:
def count_unique_strings(string):
if not string: return 0
# c1[i] denotes the number of substrings
# which consists of one unique char and ends at string[i]
c1 = [0] * len(string)
# c2[i] denotes the number of substrings
# which consists of two unique chars and ends at string[i]
c2 = [0] * len(string)
# other[i] represents the other character
# in the two-char substrings which ends at string[i].
# so in the two-char substrings, one char is string[i],
# the other one is other[i]
other = [''] * len(string)
c1[0] = 1
for i in range(1, len(string)):
if string[i] == string[i - 1]:
c1[i] = c1[i - 1] + 1
c2[i] = c2[i - 1]
other[i] = other[i - 1]
else:
c1[i] = 1
# if the current char is the same as the other char
# for substrings ending at string[i-1], we have two methods to constructs
# two-char substring ending at string[i]:
# 1. use the one-char substring ending at string[i - 1] + the current character
# 2. use the two-char substring ending at string[i - 1]
if string[i] == other[i - 1]:
c2[i] = c1[i - 1] + c2[i - 1]
# otherwise, we only have one way to construct the two-char
# substrings ending at string[i - 1]
else:
c2[i] = c1[i - 1]
other[i] = string[i - 1]
print(c1)
print(c2)
return sum(c1) + sum(c2)
[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
[0, 0, 2, 2, 4, 4, 6, 6, 8, 8, 10, 10]
78
@Pankaj. no, it is supposed to be C2[i] = C1[i-1], which means, if we find a char that is different from the last char, the total number of substrings which consists of two unique letters and ends at the current position equals to the total number of substrings which consists of one unique letter and ends at the last position.
My code outputs 9 for the input "aabc"
backtracing.
1. sort x first.
2. iterate through x, find a unused digit that is greater than or equal to the target digit in y.
2.a if we can find a digit that is strictly greater than that in y, we find a solution, add all unused digits in x into the result in ascending order
2.b if we can only find a digit in x that is equal to the target digit in y, we continue this execution path.
def rearrange(x, y):
assert len(x) == len(y)
x.sort()
used_x = [False] * len(x)
result = []
rearrange_helper(x, y, used_x, result)
return result
def rearrange_helper(x, y, used_x, result):
#print(result)
if all(used_x):
return False
target_yi = len(result)
for i in range(len(x)):
if not used_x[i]:
if x[i] > y[target_yi]:
used_x[i] = True
result.append(x[i])
result += [x[i] for i in range(len(x)) if not used_x[i]]
return True
elif x[i] == y[target_yi]
used_x[i] = True
result.append(x[i])
if rearrange_helper(x, y, used_x, result):
return True
else:
used_x[i] = False
del result[-1]
return False
a dynamic programming solution. O(n) time complexity.
def count_unique_strings(string):
if not string: return 0
# c1[i] denotes for string[:i +1 ], the number of unique string with one character
# c2[i] denotes for string[:i + 1], the number of unique string with two character
c1 = [0] * len(string)
c2 = [0] * len(string)
c1[0] = 1
for i in range(1, len(string)):
if string[i] == string[i - 1]:
c1[i] = c1[i - 1] + 1
c2[i] = c2[i - 1]
else:
c1[i] = 1
c2[i] = c1[i - 1]
return sum(c1) + sum(c2)
actually, we can make the number in the blacklist a hole in valid range.
1. generate a random number in the valid range(1, 1000 - len(list)).
2. iterate through the blacklist, if the generated number is greater than or equals than the number in the blacklist, we should increase the generated number by 1.
Example: valid range [1,10], black list[2,4,7]
we should generate a number between[1, 10 - 3]
if we got a 1, since 1 is smaller than any number in the blacklist, we don't need to jump any hole, just return 1
if we got a 5, we iterator through the black list:
5 >= 2: jump the hole, 5 -> 6
6>= 4: jump the hole, 6 ->7
7>=7, jump the hole, 7 ->8
so 8 will be returned.
Code as follows:
def generate_random(lower, upper, list):
"""Generate a random number in [lower, upper] and not in list"""
assert lower < upper
list = [x for x in list if lower <= x <= upper]
list.sort()
assert (upper - lower + 1) > len(list)
n = random.randint(lower, upper - len(list))
print(n, end= " ")
for x in list:
if x > n:
break
else:
n += 1
return n
use regular expression
def find_kth_in_encoded_str(str, k):
assert k > 0 and len(str) > 0
l = 0 #the length of decoded string
# use regular expression to
# find a match which contains a string followed by a num
for mo in re.finditer(r"(?P<s>[a-z]+)(?P<c>[0-9]+)", str, flags = re.I):
s = mo.group('s') # the string
c_str = mo.group('c') # the repeation number
if not c_str or c_str[0] == '0':
raise ValueError("repeation number <{0}> is incorrect.", c_str)
c = int(c_str)
# the total length of the decoded matched string.
t = len(s) * c
l += t
# if k falls in this range, find the kth char
if t >= k:
i = k % len(s) - 1
return s[i]
else:
k -= t
raise Exception("k is larger than the length of the decoded string {0}".format(l))
def get_largest_sum_subarray(array):
assert len(array) > 1
max_sum = second_max_sum = current_sum = array[0]
start = end = 0
for i in range(1, len(array)):
if current_sum < 0:
current_sum = 0
start = i
current_sum += array[i]
if current_sum > max_sum:
second_max_sum = max_sum
max_sum = current_sum
end = i
elif current_sum > second_max_sum:
second_max_sum = current_sum
if max_sum < -1:
raise Exception("max sum is less than 1")
if start == 0 and end == len(array) - 1:
max_sum = second_max_sum
return max_sum
1. we can solve this use binary search, which is O(logN).
2. implement @Cole 's idea in python, which is O(n)
def get_hindex_unsorted2(array):
# the trick is the h index can not be greater than either the size of the array
# or the max citation in the paper list.
max_hindex = min(len(array), max(array))
# citations[i] = the number of paper with citation being i
# for citation > max_hindex, we will put it into citations[max_hindex]
citations = [0] * (max_hindex + 1)
for x in array:
citations[min(x, max_hindex)] += 1
# paper count = the number of papers with citations greater than i
paper_count = 0
for i in range(max_hindex, -1, -1):
paper_count += citations[i]
if paper_count >= i:
# we find more than i papers with citations greater than i
return i
def get_hindex_sorted(array):
return get_hindex_helper(array, 0, len(array) - 1)
def get_hindex_helper(array, left, right):
assert left <= right
if left == right:
return min(len(array) - left, array[left])
mid = (left + right)//2
n = len(array) - mid
m = array[mid]
#there are n papers whose citations are at least m.
if n == m:
return n
elif m > n:
return get_hindex_helper(array, left, mid)
else: # n > m
return get_hindex_helper(array, mid + 1, right)
use binary search. O(nlogn)
def find_row(matrix):
"""Given a 2D array containing only 0/1 s and each row is in sorted order.
Find the row which contains maximum number of 1s."""
deleted = [False] * len(matrix)
return find_row_helper(matrix, deleted, 0, len(matrix) - 1)
def find_row_helper(matrix, deleted, left, right):
assert left <= right, "left index {0} is greater than right index {1}".format(left, right)
if left == right:
if all(deleted):
return None
else:
return [i for i in range(len(deleted)) if not deleted[i]]
mid = (left + right) // 2
has_one = False
for i in range(len(matrix)):
if not deleted[i] and matrix[i][mid] == 1:
has_one = True
if has_one:
for i in range(len(matrix)):
if matrix[i][mid] == 0:
deleted[i] = True
return find_row_helper(matrix, deleted, left, mid)
else:
return find_row_helper(matrix, deleted, mid + 1, right)
the even position number should start at len(array)//2.
for the first half. for the int at position i, array[0:i] has been sorted. if i is odd, insertion sort array[i] into array[0:i]. if i is even, swap it with an odd position number in the second half and then do the insertion sort.
then insertion sort the second half.
def sort_even_odd(array):
l = len(array)
even_start = l // 2
even_ptr = even_start
if even_ptr % 2 == 0:
even_ptr += 1
for i in range(even_start):
if i % 2 == 0:
assert even_ptr < l, "even_start={0}, even_pr={1}, i = {2}".format(even_start, even_ptr, i)
array[i], array[even_ptr] = array[even_ptr], array[i]
even_ptr += 2
for j in range(i - 1, -1, -1):
if array[j + 1] < array[j]:
array[j + 1], array[j] = array[j], array[j + 1]
else:
break
for i in range(even_start, l):
for j in range(i - 1, even_start - 1, -1):
if array[j + 1] < array[j]:
array[j + 1], array[j] = array[j], array[j + 1]
else:
break
return array
Edit: the probability was calculated wrong at the first time. i have fixed it.
1. randomly select one country c1
2. put it back to the country set,
3. randomly pick another country c2
4. return the one with more population.
suppose there are n countries.
the probability that the country with the smallest population being picked is 1/n * 1/ n
the probability that the second smallest country being picked is 3/n^2
the probability that the kth smallest country being picked is 2 * 1/n * (k - 1)/n + 1/n * 1/n = (2k - 1) / n^2
O(n) time with hashtable.
def get_consecutive_sequence(list):
# key = element in list;
# value[0] = the number of elements in the left side of the key
# value[1] = the number of elements in the right side of the key
d = {}
for x in list:
if x not in d:
d[x] = [0,0]
if x - 1 in d:
d[x][0] = d[x-1][0] + 1
if x + 1 in d:
d[x][1] = d[x+1][1] + 1
# get the element who has maximum of value[0] + value[1]
max_x = max(d, key=lambda x : d[x][0] + d[x][1])
# construct the result
result = [i for i in range(max_x - d[max_x][0], max_x)] \
+ [i for i in range(max_x, max_x + d[max_x][1] + 1)]
return result
def merge_in_place(A, B):
"""Given two sorted array. A is of length 6 and B is 3. Both they contain 3 elements.
merge them into A in place"""
assert(len(A) == 6)
assert(len(B) == 3)
ai, bi, i = 2, 2, 5
while ai >= 0 or bi >= 0:
if bi < 0 or (ai >= 0 and A[ai] >= B[bi]):
A[i] = A[ai]
i -= 1
ai -= 1
elif ai < 0 or (bi >= 0 and B[bi] > A[ai]):
A[i] = B[bi]
i -= 1
bi -= 1
return A
O(n^2) time. O(n^2) space
def maximum_subarray(array, n):
l = len(array)
c = [[0 for i in range(l)] for j in range(l)]
max_length = 0
for i in range(l):
c[i][i] = array[i]
if c[i][i] == n:
max_length = 1
for size in range(2, l + 1):
for i in range(0, l - size + 1):
j = size - 1 + i
c[i][j] = c[i][j - 1] + array[j]
if c[i][j] == n and size > max_length:
max_length = size
return max_length
def multiply(alist):
flist = [1] * len(alist)
blist = [1] * len(alist)
for i in range(1, len(alist)):
flist[i] = alist[i - 1] * flist[i - 1]
for i in range(len(alist) - 2, -1, -1):
blist[i] = alist[i + 1] * blist[i + 1]
return [x * y for x, y in zip(flist, blist)]
use a stack.
1. push all the elements in the original list into a stack in reversed order
2. get the top element in the stack,
2.a if the element is a list: push all the elements in this list into the stack in reversed order
2.b if the element is a number: append to the result list.
- gnahzy November 01, 2012