Good morning. Hope you are doing well. It is a dark, foggy and cold morning in the Twin Cities of Minneapolis and St. Paul. I woke up around 05:00 AM. I finished reading the article Does Facebook Use Sensitive Data for Advertising Purposes? article in the Communications of the ACM magazine. I though the article was interesting. Apparently Facebook has a set of several thousand categories of which up to 1000 can be applied to each user. Not sure if there is an opt out setting. The authors of the paper suggested a tool that can be used in a couple browsers to check and delete the advertising labels assigned to your account.
It seems that in the EU the GDPR has had little for user privacy. The article contains a table containing a list of countries in which homosexuality, which is a label that could be assigned to your account, in which homosexuality is a crime that could be punished by the death penalty. Potentially that could be detrimental to about 1% – 3% of Facebook users.
If you have any interest on this subject, I would suggest for you to read the article and reach your own conclusions. Keep in mind that no one forces you to have an account and use the Facebook platform. Since there are millions of users worldwide, the platform must provide features that are of interest to so many people. I believe there is no charge to use Facebook. They need ways to generate revenue to continue to provide their services.
I am not sure when I registered for HackerEarth. That said, late last week I received the following message via Gmail:
John, we value your opinion I am Sachin Gupta, the founder of HackerEarth. I noticed that you recently joined HackerEarth but haven't spent much time on our platform. I would love to understand what went wrong with your experience and how we can make your journey on HackerEarth more productive. I'd also like to share three things you can do to get started with coding on HackerEarth: o Solve coding problems to prepare for interviews o Competing with fellow developers and earning bragging rights o Participating in hackathons to solve real-world problems We'd love to hear your feedback. To share your thoughts simply reply to this email. Happy Coding! Cheers Sachin
I thought it was a nice touch from HackerRank so I spent some time researching the company on-line and solved my first problem. The main subject of this post is based on the Can you solve it? problem.
I am a firm believer on the idiom “don’t judge a book by its cover” so I will reply in private to the message I received and in the future will try solving a few problems to get a better feeling about what the site has to offer.
Yesterday I spent some time browsing the HackerEarth web site. At some point I selected Can you solve it? and gave it a try.
The problems are presented in a similar style like in other similar web sites. The requirements for this problem follow:
Raman loves Mathematics a lot. One day his maths teacher gave him an interesting problem. He was given an array 'A' consisting of 'n' integers, he was needed to find the maximum value of the following expression: |Ai - Aj| + |i - j| where, 0 <= i, j < n and Ai, Aj are the Array elements. Input: o First line of input contains an integer T denoting number of test cases. o Each test case contains two lines, first line contains integer n where n is the number of elements in array Second line contains n space separated integers Ai. Output: Print the maximum value of the above give expression, for each test case separated in a new line. Constraints: o 1 <= T <= 100 o 1 <= n <= 105 o 0 <= Ai <= 105 Note: Use Fast I/O (scanf/printf or any other ways) to handle large test files.
We are given an array on integers in no specific order which may or may not contain duplicates.
The idea is to return the maximum value for the expression which represents the absolute value of the difference of two array elements added to the difference of their respective indices. I do not believe you should rearrange (i.e., sort) the array.
4 3 1 1 1 4 1 2 3 1 1 69 2 11 13 main <<< result: 2 main <<< result: 2 main <<< result: 4 main <<< result: 4 main <<< result: 0 main <<< result: 0 main <<< result: 3 main <<< result: 3
We are given a number of test cases. The site provides the first two cases. I added the rest.
Each test case is specified by two lines. The first line contains the number of elements in the array. The second line the actual integers.
I founded interesting that HackerEarth did not provide the signature for the function / method that we are required to solve. In addition the HackerEarth IDE provided part of a test scaffolding. I disregarded the test code and wrote my own on my computer. I did copy and pasted it when I was ready to run tests and check if the solution was good enough.
Personally I like complete test scaffoldings and the signature of the class / function(s) / method(s) one has to develop. As you know some people like chocolate while others do not.
Note that I display two results per test cases. The reason for this is that I have two versions of the solution. The first seems to work but it represents the brute force approach. It was not granted full credit. The second value, which seems to match the first on these test cases, is an optimized solution (labeled as “tricky”) which as we will see, not too intuitive and much harder to come up with.
As you might already know, I like to solve problems using my computer and if possible the tools of my choice. This is how most, never generalize, software engineers work. I will use the Java language on a Windows 10 computer and the VSCode IDE. I have access and use for work other programming languages, computers and IDEs, but by choice I am mostly sticking to Java, Windows and VSCode. You are free to use whatever you like which includes the HackerEarth IDE.
One simple note, submit a single solution and do not add text to the answer (i.e., “main <<< “) as I have shown in the examples.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read number of test cases ****
int N = Integer.parseInt(br.readLine().trim());
// **** loop once per test case ****
for (int i = 0; i < N; i++) {
// **** skip array length ****
br.readLine();
// **** create and populate arr[] ****
int[] arr = Arrays.stream(br.readLine().trim().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
// **** compute and display result (two approaches) ****
System.out.println("main <<< result: " + maxValue1(arr, arr.length));
System.out.println("main <<< result: " + maxValue(arr, arr.length));
}
// **** close buffered reader ****
br.close();
}
This is my test scaffolding. Open a buffered reader, read the number of test cases and loop through them.
For each test case, read (skip) the number of elements in the array, read the elements, call the function / method you are developing and display the returned result.
After you are done with all test cases, it is a good idea to close the buffered reader. Since this is not production code, you might not have to close it.
Note that I skipped the number of elements in the array. I was not going to pass the number of elements because I could have just obtained the length inside the called function / method. I just passed it (but not read it) to see if that would save some processing time in the actual function / method. You never know what minor change might affect your score.
/**
* Find the maximum value of the following expression:
* |arr[i] - arr[j]| + |[i -j]|
*
* First pass (searching for inspiration OR brute force).
* Execution time: O(n^2)
*/
static int maxValue1(int[] arr, int n) {
// **** sanity checks ****
if (arr == null || n == 1)
return 0;
// **** initialization ****
int maxVal = -1;
// **** traverse arr[] with first element - O(n) ****
for (int i = 0; i < n - 1; i++) {
// **** traverse arr[] with second element - O(n) ****
for (int j = i + 1; j < n; j++)
maxVal = Math.max(maxVal, Math.abs(arr[i] - arr[j]) + Math.abs(i - j));
}
// **** return max val ****
return maxVal;
}
This is the brute force approach. We perform sanity checks and initialization.
We then traverse the array in two nested loops with O(n ^ 2) execution time.
We compute the value and keep a running maximum value. When done we return the maximum value.
Short and simple, but as expected not good enough!
I spent some time looking for a pattern. I did not come with something simple. The HackerEarth site did not provide a set of hints. In practice, you will always be able to get hints / comments / suggestions from other coworkers and if you are in an interview, the interviewer should provide suggestions.
/**
* Find the maximum value of the following expression:
* |arr[i] - arr[j]| + |[i -j]|
*
* Second pass.
*
* Inspiration from:
* https://www.geeksforgeeks.org/maximum-value-arri-arrj-j/
*
* Execution time: O(n)
*/
static int maxValue(int[] arr, int n) {
// **** sanity checks ****
if (arr == null || n == 1)
return 0;
// **** initialization ****
int[] arrA = new int[arr.length];
int[] arrB = new int[arr.length];
// **** populate arrA[] and arrB[] - O(n)****
for (int i = 0; i < n; i++) {
arrA[i] = arr[i] + i;
arrB[i] = arr[i] - i;
}
// **** for starters ****
int minA = arrA[0];
int maxA = arrB[0];
// **** find max and min in arrA[] - O(n) ****
for (int i = 1; i < n; i++) {
// **** update maxA (if needed) ****
if (arrA[i] > maxA)
maxA = arrA[i];
// **** update minA (if needed) ****
if (arrA[i] < minA)
minA = arrA[i];
}
// **** determine difference ****
int diff1 = (maxA - minA);
// **** for starters ****
int minB = arrB[0];
int maxB = arrB[0];
// **** find max and min in arrB[] - O(n) ****
for (int i = 1; i < n; i++) {
// **** update maxB (if needed) ****
if (arrB[i] > maxB)
maxB = arrB[i];
// **** update minB (if needed) ****
if (arrB[i] < minB)
minB = arrB[i];
}
// **** determine difference ****
int diff2 = (maxB - minB);
// **** return answer ****
return Math.max(diff1, diff2);
}
In the comments section of the function / method I wrote the link to the site I found to get inspiration / hint. What I typically do is start reading and or looking at a code example, until I can proceed. It is better not to read the entire solution or copy and paste the code for it. If you do so you will not learn much from such approach.
The solution is based on an observation and associated implementation. Since this problem is based on a mathematical expression it is simpler to read the description in the specified web site.
In a nutshell we need to generate two arrays which are associated with the observation. Once we have the arrays populated we need to compute the max and min values in each of the two arrays. Note that for simplicity (and efficiency) we compute two differences. When all is set and done the result is the max value of the two differences.
I suggest adding a few print statements, and watch how the solution emerges. In my opinion, this is a tricky problem and takes time to come up with a rather simple implementation. In average a problem under pressure should be solved in about 30 minutes. It took me more than that.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 5,905 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com