Java Programming Language
Context and Problem Statement: A web search engine returns you a list of web-links that match the set of words in your query. Each web-link is assigned an integer for identification purposes(page-ID) This is done by maintaining an "inverted index". An inverted index, at a very elementary level, is a mapping that takes a word and returns to you a list of web-links which contains the word. That list would be a sorted(ranked) array of page-IDs where the web-link with the highest rank for the query is displayed on top. When your query to the web search engine contains multiple words, the search engine needs to find the sorted array for each word and then computes the intersection of these arrays. Given the number of webpages existing in the world-wide-web, this work is very computationally challenging! In this assignment you are required to write programs which takes as input two sorted arrays and returns a new array containing the elements found in both the sorted arrays. It is alright if the input arrays have duplicates, but the returned array should be duplicate free! Below are how the arrays are represented ARRAY 1[]=[1,5,6,6,9,9,9,11,11,21]. Here length of ARRAY1 is m. ARRAY2[] =[6,6,9,11,21,21,21]. Here length of ARRAY 2 is n Array to be returned would be ARRAY []=[6,9,11,21]. ATTN: Please be reminded that you cannot use library functions to do any of the tasks required above. Doing so would straight up result in a score of Zero! You will solve the problem in three ways: - (1) [40 points] Implement the function in such a way that your solution solves the problem with O(mn) time complexity. O(mn) is same as O(mn). This brute-force method suggested has a name called "loop-join" where you basically just traverse through the elements of one array comparing it to the elements of the other array. (2) [40 points] In a separate implementation, code up a solution in such a way that your solution solves the problem with O(nlog(m)) time complexity or O(mlog(n)) time complexity. Here log means to the base of 2 . I'm sure you already know that the hint is to use Binary Search. (3) 20 points ] In the form of sentences, as a comment in your code (at the bottom of your Solution2), you are required to suggest how can Solution 2 be improved by leveraging the fact that both the arrays are already sorted. Suggest a solution so that your suggested solution can run linearly with O(m+n) time complexity. Your suggestion should be no more than 5 sentences :) (1) Your code should be well commented which explains all the steps you are performing to solve the problem. A submission without code comments will immediately be deducted 15 points! (2) As a comment in your code, please write your test-cases on how you would test your solution assumptions and hence your code. A submission without test cases will immediately be deducted 15 points! Example of cases to be tested for are like: What if the array input which is expected does not exist - that is, input is a null. How should your code handle such a situation? Maybe output some message like "Null input case, so no output"? What if the length of the array is one? ... so on and so forth. Please Remember: Although, written as comments - You will address your test cases in the form of code and not prose :)
