Interview Question
Country: United States
Interview Type: Written Test
@Nelson Perez: add memorization to this code and it will save you lot of time.
Second how it is different from subset sum problem?
@variksla: Thanks for the comment
True I though about using memoization but then though that for that to work I need to create a my own hash function which created a hash using the ropes left in the dictionary and the N and I though it was not a good idea to do this specially in an interview.
Yes it is similar to the subset problem where ask you to select of certain number from an array A which adds to an integer N.
To tell you the truth I did not understood quite well the problem I just assume that a list of ropes were given.
But if the ropes were infinite and you had various options 2, 5, 6 then memoization would be an option based on N. :-)
def drroper(self, array_ropes, desired_rope_length):
# initializing local variables for the final sum result
final_sum = array_ropes[0]
# initializing the pointer index to monitor the status of the final sum
start = 0
# getting the length of the array for iteration
length_array_ropes = len(array_ropes)
for i in range(1, length_array_ropes + 1):
# this seems to be like a O(n2) problem but the while loop is run for the length of i
# and not for the entire length of the array hence by means of arbitrary computation
# the total time complexity would be O(n)
# The while loop is run to maintain the final result < or = to the desired rope length
while (final_sum > desired_rope_length) and (start < i - 1):
final_sum = final_sum - array_ropes[start]
start += 1
# Terminating statement if the desired length is obtained
if final_sum == desired_rope_length:
return "It is possible to tie the ropes together"
# If the final sum is less than the required length the additional ropes are added
# to the final sum
if i < length_array_ropes:
final_sum = final_sum + array_ropes[i]
# This is the worst case scenario when the ropes cannot be tied together to obtained
# the desired length
return "The ropes cannot be tied together"
Can you check the code which I worte at the time of coding challenge !!!!
I do not know if it works as it is very messy how it is displayed in CareerCup.
But this is indeed for sure n^2.
It does not matter if you run from for a segment of the array as it is not a constant subset of n because approaches infinity it becomes so the subset of n is infinite as well so it is n^2.
- Nelson Perez February 22, 2015public static bool DrRopes(List<int> ropes, int N) { if(N == 0) return true; if(N < 0) return false; for(int i = 0; i < ropes.Length; i++) { int r = ropes[i]; ropes.RemoveAt(i); if(DrRopes(ropes, N-r)) { return true; } ropes.Insert(i, r); } return false; }