shoudaw
BAN USER- 0of 0 votes
Answers
- shoudaw in United States/** * Implement a method which takes an integer array and returns an integer array (of equal size) in * which each element is the product of every number in the input array with the exception of the * number at that index. * * Example: * [3, 1, 4, 2] => [8, 24, 6, 12] */ public int[] selfExcludingProduct(int[] input) { // implementation... }
| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm
"""
Given a undirected graph with corresponding edges. Find the number of
possible triangles?
Example:
0 1
2 1
0 2
4 1
Answer:
1
"""
def _dfs(level, root, node, connections):
N = 3
if level == N:
if root == node:
return 1
else:
return 0
else:
res = 0
for item in connections[node]:
res += _dfs(level + 1, root, item, connections)
return res
def get_num_triangles_dfs(list_node_pair):
"""
@param list_node_pair, a list of edges which are
represented as tuples.
"""
nodes = set()
connections = {}
for item in list_node_pair:
a = item[0]
b = item[1]
nodes.add(a)
nodes.add(b)
if a in connections:
connections[a].append(b)
else:
connections[a] = [b]
if b in connections:
connections[b].append(a)
else:
connections[b] = [a]
mysum = 0
for item in nodes:
mysum += _dfs(0, item, item, connections)
res = mysum / 6
return res
"""
Given a undirected graph with corresponding edges. Find the number of
possible triangles?
Example:
0 1
2 1
0 2
4 1
Answer:
1
"""
def _get_triangles_common_edge(edge, connections):
n1, n2 = edge
n1_nodes = set(connections[n1])
n2_nodes = set(connections[n2])
count = len(n1_nodes.intersection(n2_nodes))
return count
def get_num_triangles(list_node_pair):
"""
@param list_node_pair, a list of edges which are
represented as tuples.
"""
connections = {}
for item in list_node_pair:
a = item[0]
b = item[1]
if a in connections:
connections[a].append(b)
else:
connections[a] = [b]
if b in connections:
connections[b].append(a)
else:
connections[b] = [a]
mysum = 0
for key in connections:
for item in connections[key]:
edge = (key, item)
mysum += _get_triangles_common_edge(edge, connections)
res = mysum / 6
return res
class Solution:
# @param num, a list of integer
# @return a list of integer
def nextPermutation(self, num):
length = len(num)
if not num:
return []
i = length - 1
# find the last item which has at least one
# item that is greate than it and behind it.
# the item is num[j], the item that greater than
# it and behind it is mun[i]
max_j = -1
max_j_i = None
while i >= 0:
j = i - 1
while j >= 0:
if num[j] < num[i]:
if j > max_j:
max_j = j
max_j_i = i
break
j -= 1
i -= 1
j = max_j
i = max_j_i
if max_j != -1:
# it is not a descending array
num[i], num[j] = num[j], num[i]
for k in range(j + 1, length):
for l in range(k, length):
if num[k] > num[l]:
num[k], num[l] = num[l], num[k]
else:
# it is a descending array
return num
return num
You need to consider whether there are duplicates
"""
Generate all permutations of given sequence
of elements.
Return a list of all distinct permutations.
E.g.
generate([1, 2, 3]) ->
[1, 2, 3], [1, 3, 2], [2, 3, 1],
[2, 1, 3], [3, 1, 2], [3, 2, 1]
"""
_results = []
def perm(A):
global _results
A = sorted(A)
_results = []
_aux([], A)
return _results
def _aux(one_result, remain):
global _results
if not remain:
_results.append(one_result)
else:
num = len(remain)
for i in range(num):
if i > 0 and remain[i - 1] == remain[i]:
continue
else:
_aux(one_result + [remain[i]],
remain[:i] + remain[i + 1:])
RepRutviOrtiz, Android Engineer at AMD
I am experienced in teaching other translators through one-on-one mentoring and professional development courses. I am passionate about Unbinding spell ...
RepLicholsLowry, Associate at AMD
I am Lichols, I am an outreach worker in Desmonds Formal Wear company .I specialise in a variety of different ...
- shoudaw April 03, 2014