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
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.
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.
sum the array and divide by 2. That is the target sum. If the division by two doesn't yield an integer, then you know there is not a solution for sure. Then try to solve using a monte-carlo approach by selecting an element at random from array A and introducing to an initially empty array B. Maintain a running sum of B. Retain the move if the sum of the new array is less than the target sum. If it goes over, then discard the attempt and additionally discard one of the previous entries at random (with say 50% probability), so that you don't get trapped in a local minima. This is essentially an error minimisation routine, and you can use it to get the closest solution if an explicit solution isn't necessarily available. Continue until the target is achieved, or error term is not improving (in the event you are unsure a solution exists).
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.
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
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.
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
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
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.
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.
Same Chad
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
1,3,2,-8,3,5,-10
This this and should fail if i am thinking same as you were
ANS :: 0 to 3 and 4 to 7
sum the array and divide by 2. That is the target sum. If the division by two doesn't yield an integer, then you know there is not a solution for sure. Then try to solve using a monte-carlo approach by selecting an element at random from array A and introducing to an initially empty array B. Maintain a running sum of B. Retain the move if the sum of the new array is less than the target sum. If it goes over, then discard the attempt and additionally discard one of the previous entries at random (with say 50% probability), so that you don't get trapped in a local minima. This is essentially an error minimisation routine, and you can use it to get the closest solution if an explicit solution isn't necessarily available. Continue until the target is achieved, or error term is not improving (in the event you are unsure a solution exists).
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.
[1,5] is not a subarray. It is a subsequence.
A subarray for an array is kind of like a substring for a string.
@@anand_undavia That makes a lot of sense now. Thank you
@@anand_undavia great explanation, I had the same question
They should clarify what subarray means. I was also under the impression that subarray is a subsequence
Yep both of them ignored that
The solution is dependent on if the array is sorted?
No, the array doesn’t need to be sorted.
Is this interview result will be hire / lean hire or strong hire?
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
Bro 2,12 is not even 24
Your brain tricked you into thinking 2*12=2+12
I found it amusing that he preached about mastering the programming language for interviews, yet stumbled over range functions.
Nice work! 🔥
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.
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
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
in both these two sample the result should be none, why exactly will this not work?
A subarray is a contiguous part of array, when array doesn't have contiguous indexes it can't be termed as subarray.
Why do we assume the list is sorted? Good solution otherwise
We just don’t assume it is sorted.
will this solution work in case of this [1, 3, 7, 2 , 11] ?
the output for this is None because a subarray is a contiguous part of array.
Google would never ask such questions. I mean it's simple to code .
At first i thought the left person is a girl
You're not alone bro 😄
at first I thought the right person was a girl.
we've all been there :)
also don't forget asking the interviewer if they prefer prefer him/he/she/her/them/they
lol this is a basic question .