Skip to main content

Featured post

Kafka with Spring boot

Kafka server setup is already mentioned in another post.  The goal of this post is to provide spring boot implementation for custom object produce and consume by kafka broker.

Find pair of numbers in an array with a given sum

There are multiple ways to find the pair of numbers in a given array. The numbers in the array can be in two ways.
  1. Sorted
  2. Unsorted
If the numbers are sorted then we can get easily with the complexity of O(n). The brute force approach will be easily applicable for both the sorted and unsorted array of numbers.

Brute force:

Brute force approach will check each and every number to determine if it equals to the given sum. The complexity of this approach is O(n²).


public void findPair(int[] array, int sum) {
    for(int i = 0; i < array.length - 1; i++) {
        for(int j = i + 1; j < array.length; j++) {
            if(array[i] + array[j] == sum) {
                // The pair is { array[i], array[j] }
            }
        }
    }
}

Sorted:

In this approach, we need to sort the unsorted array(if needed). In this case, the complexity depends on the complexity of the sorting algorithm. If we choose a sorting algorithm of complexity O(n) we can solve this problem in O(n) complexity.


public void findPair(int[] array, int sum) {
    // any sort method can be used.
    Arrays.sort(array);
    int i = 0, j = array.length - 1;
    
    while(i < j) {
        int pairSum = array[i] + array[j];
        if(pairSum == sum) {
            // The pair is { array[i], array[j] }
            // if we want to continue i++ otherwise break
        } else if(pairSum > sum) {
            j--;
        } else {
            i++;
        }
    }
}

Hash / Flag:

In this approach, we can get the pairs in O(n) complexity. We can use hashmap or flag array to set counter for each value and check using negation from the given sum.


public void findPair(int[] array, int sum) {

    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < array.length; i++) {
        map.put(array[i], map.getOrDefault(array[i], 0) + 1);
    }

    for (int i = 0; i < array.length; i++) {
        if(map.containsKey(sum - array[i])) {
            // The pair is { array[i], sum - array[i] }
        }
    }
}

In this way, we will get the pairs twice. Because in each occurrence it will check with the hashmap and make a pair. We can add a set to get unique pairs.

Metrics:

I tried to run these to get some metrics. Sharing those might help to get some understanding.
100001000001000000
Brute force22ms1453msToo long to compute
Sorted
Dual-Pivot Quicksort O(n log(n))
4ms20ms293ms
Hashmap8ms44ms276ms


Comments

Popular posts from this blog

Code Smell বা বাজে কোড

Code Smell বা বাজে কোড বোঝার কিছু প্যাটার্ন আছে যা দেখে বোঝা যায়। এখানে এই সম্পর্কে কিছু ধারনা দেয়া হল। code smell সাধারনত ২ ভাগে বিভক্ত। Code smells within classesCode smells between classesCode smells within classes:
একটা ক্লাসের মধ্যে সাধারনত মেথড গুলোয় কি ধরনের কোড স্মেল হয়ে থাকে এখানে তাই বর্ননা করা হয়েছে। নাম গুলি ইংরেজিতেই রাখা আছে যাতে সরাসরি ইংরেজি নাম দিয়ে গুগল করলেই সব ধরনের রিসোর্স পাওয়া যায়। Comments:
বোঝার মত কমেন্ট আর না বোঝার মত কমেন্টের মধ্যে একটা সুন্দর পার্থক্য আছে। যদি কমেন্ট এমন হয় যে মেথড বা স্টেটমেন্ট ‘কেন’ বাদ দিয়ে ‘কি’ ব্যাখ্যা করে, তাহলেই বুঝতে হবে, কমেন্ট রিমুভ করতে হবে। আর যদি পারা যায় তবে এমনভাবে রিফ্যাক্টর করতে হবে যাতে কমেন্ট না লাগে। কমেন্ট কখনো এক্সিকিউট করে না, এবং এটাই আমরা ভুলে যাই।
কমেন্ট মেশিনের জন্য না, মানুষের বোঝার জন্য লেখা হয়।

Code Smell বা বাজে কোড

Code Smell বা বাজে কোড বোঝার কিছু প্যাটার্ন আছে যা দেখে বোঝা যায়। এখানে এই সম্পর্কে কিছু ধারনা দেয়া হল। code smell সাধারনত ২ ভাগে বিভক্ত। Code smells within classesCode smells between classesCode smells between classes দুই বা ততোধিক ক্লাসের মধ্যে সাধারনত কি ধরনের কোড স্মেল হয়ে থাকে এখানে তাই বর্ননা করা হয়েছে। নাম গুলি ইংরেজিতেই রাখা আছে যাতে সরাসরি ইংরেজি নাম দিয়ে গুগল করলেই সব ধরনের রিসোর্স পাওয়া যায়। Alternative classes with different interfaces: দুইটা মানুষের ভিতরে সবকিছুই এক, শুধু চেহারা ছাড়া মানে যদি দুইটা ক্লাসের ভেতরের স্ট্রাকচার একই হয় কিন্তু বাহিরের আউটলুক ভিন্ন হয় বা যদি ইন্টারফেস আলাদা হয়, সেক্ষেত্রে দুইটা ক্লাসই একটা ইন্টারফেস শেয়ার করতে পারে।

Java Heap Dump

Overview A heap dump is a snapshot of all the objects that are in memory in the JVM at a certain moment. They are very useful to troubleshoot memory-leak problems and optimize memory usage in Java applications.
Heap dumps are usually stored in binary format hprof files.