You are not logged in.
This is an interview question. Find the greatest subarray whose total equals 0 given an array containing both positive and negative values without 0. I attempted to solve this. This is what I came up with.
best_index_hash[start_index] = [(0,start_index)]
else:
hash_sum[current_sum] = [start_index]
if keys:
for k_1 in keys:
best_start = hash_sum.get(k_1)[0]
best_end_list = hash_sum.get(k_1)[1:]
for best_end in best_end_list:
if abs(best_start-best_end) in best_index_hash:
best_index_hash[abs(best_start-best_end)].append((best_start+1,best_end))
else:
best_index_hash[abs(best_start-best_end)] = [(best_start+1,best_end)]
if best_index_hash:
(bs,be) = best_index_hash[max(best_index_hash.keys(),key=int)].pop()
return array[bs:be+1]
else:
print "No sub array with sum equal to 0"
def Main():
a = [6,-2,8,5,4,-9,8,-2,1,2]
b = [-8,8]
c = [-7,8,-1]
d = [2200,300,-6,6,5,-9]
e = [-9,9,-6,-3]
print sub_array_sum(a)
print sub_array_sum(b)
print sub_array_sum(c)
print sub_array_sum(d)
print sub_array_sum(e)
if __name__ == '__main__':
Main()According to this blog, when the number of subsequences is quadratic and the time to sum a subsequence is linear, the most naïve answer is cubic.
I'm not sure if this will cover all of the edge cases. It would be great if someone could remark on that. I'd also like to expand this to sums equaling any K rather than simply 0. How should I proceed? Any suggestions for further optimising this are also welcome.
Hello, my name is Hikam, and I'm a Prolific Java programmer with 4+ years of experience and a solid background in RESTful and JSP development. OddPointer is looking for efficient programming. In recent years, I have built an average of 10+ native Java apps per year. I'm also familiar with C++, C, and HTML, and am actively learning CSS and Python.
Offline
I've hired/interviewed many applicants and administered countless programming tests over the years. I can't speak for other companies/recruiters/HR of course, since every outfit is different with a different corporate culture. However, from my perspective, I never really cared or evaluated the actual result/code the applicant puts forth. For me, the key thing was for the applicant to *explain* their approach, describe what they feel could be improved with more time/effort. I always made sure that there wasn't enough time given to 'finish' a *polished* version of the code, since for me the purpose was also to find out how the applicant dealt with time pressure/stress and - again - how they communicated under that. It also was a great test to see if they were genuine, and didn't happen to find the test on the Internet. I purposely allowed Internet connection on the laptop I gave the applicant. They were free to do what they wanted. If they copied the test, it was an automated, unconditional 'thank you, but no thanks' (which I warned them for at the start of the test).
Just my 2c.
Offline