To be honest, I’ll not talk here about what is Data Science and why should we use it. For, that there are already millions of pages to read on the web. Am not going to waste my as well as your time on that.
Via this platform, will try share with you as much as possible all practical problems which I face/have faced at my workplace or in google code jams where I held Rank #93 in 2019, and Rank #581 in 2018.
In a coding interview, the problem is not Technology which we all fear of, the real problem is how can we can break the problem in various sets/pieces. The thing here, which am talking about, is Data Structures and Algorithmic Design. This simple yet complex subject is embedded EVERYWHERE in data science realm.
Assume any Machine Learning technique you use, the science behind is the way how that ALGORITHM is constructed. Therefore, it becomes vital for us to understand the application of this subject.
I will try to post solved questions in this forum, with complexity varying from easy to very hard, and if you have any queries regarding the same, let’s take the advantage of this forum to discuss the same.
- Any Programming language (I’ll recommend Python for all you Data Analysts and Data Scientists)
- How to measure algorithm complexity (Such as ** “BIG-O” ** Not necessary to know in advance but if you do that is a plus) as I’ll be using some Complexity Notations alongside algorithm for better understanding
So here’s comes a sweet easy problem: SUM OF THE TWO NUMBERS
CAUTION!!! Do not go by the name as it is not simply RETURN (a+b) . We’ll use the concept DYNAMIC Programming (Subset Problem) here.
Write a function that takes in a nonempty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array, in any order. If no two numbers sum up to the target sum, the function should return an empty array.
- Note that the target sum has to be obtained by summing two different integers in the array; you can’t add a single integer to itself in order to obtain the target sum.
You can assume that there will be at most one pair of numbers summing up to the target sum.
array = [3, 5, -4, 8, 11, 1, -1, 6]
targetSum = 10
[-1, 11] // The numbers could be in any order
So let’s start writing Pseudo-Code for the problem:
Albeit the optimal complexity that can be achieved in O(logn) which I’ve mentioned in the comments, but to understand the problem better, I had to go with this approach “”" Complexity --> (n-1)(n-1) + c --> O(n^2)
** “”" Complexity --> (n-1)(n-1) + c --> O(n^2)**
I/P - array, targetSum
FOR index_of_array_input_seq from 0 TO length(array)-2 DO
FOR index_of_array_next_seq from index_of_array_input_seq+1 to index_of_array_input_seq -1 DO
IF array[index_of_array_input_seq] + array[index_of_array_next_seq] = targetSum THEN
return [ array[index_of_array_input_seq], array[index_of_array_next_seq] ] # Pair
# End Inner FOR
return  # empty_array
#End Outer FOR
Since, I have done 95% task for you, all I ask from all of you is to code the same and post the solution here and If you have a better solution with less Runtime complexity, then please post the same
I’ll post the possible solutions for this.
P.S. Note: My frequency of questions will be based ion the response I receive.
By: Anish Arya