Mike and HashTrick Java

justformyntra8 · June 12, 2019, 8:35am

The Question is unclear- could you please explain the question?

cutiecoder · June 13, 2019, 4:41pm

Hi,
see everytime when a number repeats, it is given a new hash value which is equal to the number of distinct numbers occurred till now. So we have to just store the last occurrences of all the numbers and assign the values incrementally, in ascending order of the positions of their last occurrences.

justformyntra8 · June 13, 2019, 6:51pm

It is giving a timed out error despite a linear time complexity. Lemme know where I’m mistaken

github.com

bhardwaj-aman/java-data-structures-practice-questions/blob/master/(*)Mike and HashTrick

package HashingPractice;
import java.util.*;
public class MikeAndHashTrick {
    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        int a = s.nextInt();
        int[] b = new int[a];
        for (int i = 0; i < a; i++) {
            b[i] = s.nextInt();
        }
        int[] c = new int[a];
        int j=0;
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for (int i=a-1;i>=0;i--){
            if(!arr.contains(b[i])){
                c[j]=b[i];
                j++;
               arr.add(b[i]);
            }
        }

This file has been truncated. show original

cutiecoder · June 15, 2019, 8:51am

Hi,
see what you have to do in this question is make a hashmap and a arraylist now when you go to each element in the given array you will first check that whether your arraylist contains that element if not simply put that element in the map with its value as the index of the element else put that element in the arraylist too.Next you have to just sort your arraylist according to the values of that elements in the hashmap.

cutiecoder · June 19, 2019, 2:00pm

Hi @justformyntra8
as you are not responding to the doubt I am marking your doubt as resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “Ask Doubt” section, when your doubt is resolved.

cutiecoder · June 19, 2019, 2:00pm

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.