Split an Array into Equal Sum Subarrays (with Google Software Engineer)

[@tryexponent]

Don't leave your software engineering career path to chance. Make sure you're interview-ready with Exponent's software developer interview prep course: bit.ly/3ztsYPt

[@massimomonticelli6010]

Thanks for the video! Really appreciated. Assuming non negative numbers in the list, the loop can also exit - returning None - if the running sum at some point gets greater than the target. Thanks again, Massimo.

[@stevefoo13]

Kool solution. I came up with another one to use two pointers: one at the start of the list and one at the end of list. As you increment and decrement each pointer you add up the sum in two different variables. You would stop when each sum is equal to each other and the start poiner is sequential to the end pointer. If the pointers ever equal one another then there is no equal sub-array.

[@unwanted_spam]

Same Chad

[@kunaljain6932]

You didn't mention that when to increment or decrement it would be nice if you can share that code i guess it's not gonna work in some cases

[@kunaljain6932]

1,3,2,-8,3,5,-10

[@kunaljain6932]

This this and should fail if i am thinking same as you were

[@kunaljain6932]

ANS :: 0 to 3 and 4 to 7

[@shenjun5631]

The solution is dependent on if the array is sorted?

[@massimomonticelli6010]

No, the array doesn’t need to be sorted.

[@xugu624]

What company would ask such easy questions which can be done within 2 minutes?

[@latenightjamming2255]

Hi team I guess this is wrong solution, with input [1,3,2] this will fail as he is trying only to put continuous elements. Thats why his [1,2,3] worked but [1,3,2] will not.

[@yiannig7347]

I found it amusing that he preached about mastering the programming language for interviews, yet stumbled over range functions.

[@Sunny-wi4wm]

Please correct me if I am wrong, I don't think the solution is correct. Does it work for 1,3,3,5 even if it is sorted? I believe it would return None instead of [1,5] [3,3]. May be I missed something.

[@anand_undavia]

[1,5] is not a subarray. It is a subsequence. A subarray for an array is kind of like a substring for a string.

[@Sunny-wi4wm]

@@anand_undavia That makes a lot of sense now. Thank you

[@r.006]

@@anand_undavia great explanation, I had the same question

[@manantank]

They should clarify what subarray means. I was also under the impression that subarray is a subsequence

[@kunaljain6932]

Yep both of them ignored that

[@linshengred]

Is this interview result will be hire / lean hire or strong hire?

[@jacobsimon4699]

Nice work! 🔥

[@Boringpenguin]

A related but way harder problem would be to find any two integer subsequence (not necessarily just splitting the original one up) with equal sum e.g. a = [4, 2, 12, 5, 3, 21], the two subarrays would be [2, 12] and [3, 21], with sum = 24

[@unwanted_spam]

Bro 2,12 is not even 24 Your brain tricked you into thinking 2*12=2+12

[@carefree_ladka]

Google would never ask such questions. I mean it's simple to code .

[@r.006]

Why do we assume the list is sorted? Good solution otherwise

[@massimomonticelli6010]

We just don’t assume it is sorted.

[@latenightjamming2255]

I have tried writing the whole code which is bit more generic and not only for 2 splits but also for k number of splits. def split_array(inp_arr, st_ind, end_ind) base_array_st = [] base_array_end = [] base_array_st = inp_arr[0...st_ind] if st_ind > 0 derived_array = inp_arr[st_ind..end_ind] base_array_end = inp_arr[(end_ind+1)...(inp_arr.length)] if end_ind < (inp_arr.length-1) puts "---splitting----inp_arr----#{inp_arr.inspect}--into----#{derived_array.inspect}---#{(base_array_st + base_array_end).inspect}" # Heree dervied_Array is to be transfered return derived_array, (base_array_st + base_array_end) end def dfs(curr_sub_arrs, k, target_sum, sub_arr_ind = 0) puts "---came inside----dfs----#{curr_sub_arrs.inspect}-----target_sum: #{target_sum}--sub_arr_ind:-#{sub_arr_ind}" sub_arr_to_operate = curr_sub_arrs[sub_arr_ind] if sub_arr_ind < (k-1) value_with_current_subarr = dfs(curr_sub_arrs, k, target_sum, (sub_arr_ind+1)) if sub_arr_to_operate.sum == target_sum return true if value_with_current_subarr else return sub_arr_to_operate.sum == target_sum end curr_sub_arr_length = sub_arr_to_operate.length curr_diff = 1 (1...curr_sub_arr_length).each do |total_elements_to_shift| curr_sub_arr_length.times do |st_ind| end_ind = st_ind + total_elements_to_shift - 1 temp_arr = sub_arr_to_operate derived_array, base_array = split_array(sub_arr_to_operate, st_ind, end_ind) next if base_array.sum != target_sum new_curr_sub_arrays = curr_sub_arrs.clone new_curr_sub_arrays[sub_arr_ind] = base_array new_curr_sub_arrays[sub_arr_ind+1] = derived_array + curr_sub_arrs[sub_arr_ind+1] return true if dfs(new_curr_sub_arrays, k, target_sum, (sub_arr_ind+1)) end end return false end def divide_arr(arr, k) puts "--input---#{arr.inspect}" return -1 if arr.nil? || k.nil? || arr.length < k total_sum = arr.sum return -1 if (total_sum % k) != 0 sum_of_each_subarr = total_sum/k starting_sub_arrs = [] temp_arr = arr (1...k).each do |arr_ind| new_val = temp_arr.pop starting_sub_arrs

[@technovinitySystem]

will this solution work in case of this [1, 3, 7, 2 , 11] ?

[@phanindra5580]

the output for this is None because a subarray is a contiguous part of array.

[@kharljohnrayala]

won't work with these two samples: sample 1 = [1,4,4,5,6,6,10] sample 2 = [1,2,5,6,12] because the correct subarrays for my examples don't have consecutive indexes from original arrays

[@vimalvaira]

in both these two sample the result should be none, why exactly will this not work?

[@phanindra5580]

A subarray is a contiguous part of array, when array doesn't have contiguous indexes it can't be termed as subarray.

[@parthgabhane1419]

At first i thought the left person is a girl

[@shenth27]

You're not alone bro 😄

[@YTGhostCensorshipCanSuckMe]

at first I thought the right person was a girl.

[@sfsdeniso5941]

we've all been there :)

[@cnkumar20]

also don't forget asking the interviewer if they prefer prefer him/he/she/her/them/they

[@someshsangwan3768]

lol this is a basic question .