zilchistDeepblue
BAN USER- 4of 4 votes
AnswersGiven a polygon with N vertexes and N edges. There is an int number(could be negative) on every vertex and an operation in set(*,+) on every edge. Every time, we remove an edge E from the polygon, merge the two vertexes linked by the edge(V1,V2) to a new vertex with value: V1 op(E) V2. The last case would be two vertexes with two edges, the result is the bigger one.
- zilchistDeepblue in United States
Return the max result value can be gotten from a given polygon.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an int array sequence:
- zilchistDeepblue in United States
1
1,1
2,1
1,2,1,1
1,1,1,2,2,1
3,1,2,2,1,1
1,3,1,1,2,2,2,1
1,1,1,3,2,1,3,2,1,1
...
What's the rule of the sequence?
Given an other int array a[], how to determine if a is in the sequence?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
Using DP to log the temp values got and make adjustment according to current operator and previous operator could achieve good performance. Here is my solution by Python:
import sys
dp = {}
def calc(inp, length, index, pre):
global dp
pre_value = dp[pre]
if index == (length-1):
if pre_value == inp[len(inp)-1]:
result = str(inp[0])
for i in range(1,length):
result += pre[i] + str(inp[i])
print "matching: " + result + "=" + str(inp[length])
return
# "+"
nex = pre + '+'
dp[nex] = pre_value + inp[index+1]
calc(inp, length, index+1, nex)
# "-"
nex = pre + '-'
dp[nex] = pre_value - inp[index+1]
calc(inp, length, index+1, nex)
last = pre[len(pre)-1]
# "*"
nex = pre + '*'
if last == '*' or last == '/' or last == '$':
dp[nex] = pre_value * inp[index+1]
else:
pre_value = dp[pre[:len(pre)-1]]
if last == '+':
dp[nex] = pre_value + inp[index] * inp[index+1]
else:
dp[nex] = pre_value - inp[index] * inp[index+1]
calc(inp, length, index+1, nex)
# "/"
if inp[index+1] == 0:
return
nex = pre + '/'
if last == '*' or last == '/' or last == '$':
dp[nex] = pre_value / inp[index+1]
else:
pre_value = dp[pre[:len(pre)-1]]
if last == '+':
dp[nex] = pre_value + inp[index] / inp[index+1]
else:
dp[nex] = pre_value - inp[index] / inp[index+1]
calc(inp, length, index+1, nex)
if __name__ == "__main__":
inp = [2,1,3,4,5,8]
length = len(inp) - 1
pre = '$'
dp[pre] = inp[0]
calc(inp, length, 0, pre)
There would be negative values in the vertexes, so doing + firstly is not the optimal solution.
- zilchistDeepblue January 16, 2013Example: given a quad, (1)--e1(+)--(2)--e2(*)--(-2)--e3(*)--(3)--e4(+)--(1). Removing edge e3 will result in a triangle: (1)--e1(+)--(2)--e2(*)--(-6)--e4(+)--(1).
- zilchistDeepblue January 15, 2013@a1729, does the arrays in this sequence in an exactly ascendent(>=) length order? If the second question change to: given two arrays, determine if they are in the same sequence. What's the optimal solution?
- zilchistDeepblue January 11, 2013@upper Anonymous, if you get a rand 3, the output will be 5. I think this is a perfect solution.
- zilchistDeepblue January 08, 2013@ Johny, It does work correctly. But what's the principal of using topological sort for this problem? I think the output order of ts is the logical order of nodes. What's the relation between the logical order and the final order of this problem? Could you please explain it in detail?
- zilchistDeepblue January 04, 2013
@adam, could you please explain more in detail what is the bits combinations and how to come up with the result with certain days? Thanks.
- zilchistDeepblue February 13, 2013