yagamiram
BAN USERThis is can be done in two ways:
1. Check if there is odd number of cycle. If it is then it is NO
2. If it is even number of cycle the print yes
3.If it doesn't contain cycle print yes.
-This is a bi-partite graph.
Second method:
DFS
Check if there is an edge from child to parent. If it is then check whether the parent is "Tester or Developer". If it is same as child then Print NO. Otherwise "Yes".
I think my below code is a partial dynamic program
I have used a dictionary to store the values of column. multiplying the column values will take at most len(column) and after that theta(1) amortized running time.
And the inner for loop will be skipped if the multiplication of row values = 0.
If I'm wrong or any other improvement can be done for the efficiency, pls post it!
#!usr/bin/python3
col_dict = {}
def row_calculation(row,number):
total = 1
for elem in row:
total = elem * total
return total
def column_calculation(column,number):
if number not in col_dict:
total =1
for elem in column:
total = elem * total
col_dict[number] = total
return total
else:
return col_dict[number]
def main():
matrix_list = [[1,2,3,1],[1,0,-1,2],[-1,1,1,1]]
new_matrix = []
row_length = len(matrix_list)
column_length = len(matrix_list[0])
for row in range(len(matrix_list)):
temp_list = []
row_value = row_calculation(matrix_list[row],row)
if row_value is 0:
temp_list = [0]*column_length
new_matrix.append(temp_list)
continue
for elem in range(len(matrix_list[row])):
column_list = [matrix_list[col_number][elem] for col_number in range(row_length)]
column_value = column_calculation(column_list,elem)
if (column_value * row_value) > 0:
temp_list.append(1)
elif (column_value * row_value) < 0:
temp_list.append(-1)
else:
temp_list.append(0)
new_matrix.append(temp_list)
print(new_matrix)
if __name__ == "__main__" : main()
This is can be done in big-oh(log n) complexity.
The question needs to return the strictly next larger but smaller than anything for a given element.
And finding next larger takes big-oh (h).
find_node_closer_to_k takes big-oh(log n) and next_larger takes(log n)
- yagamiram February 09, 2014so overall time complexity is big-oh(log n)