Find the first circular tour that visits all petrol pumps

Suppose there is a circle. There are n petrol pumps on that circle. You are given two sets of data.

1. The amount of petrol that every petrol pump has.
2. Distance from that petrol pump to the next petrol pump.

Calculate the first point from where a truck will be able to complete the circle (The truck will stop at each petrol pump and it has infinite capacity). Expected time complexity is O(n). Assume for 1 litre petrol, the truck can go 1 unit of distance.

For example, let there be 4 petrol pumps with amount of petrol and distance to next petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}. The first point from where truck can make a circular tour is 2nd petrol pump. Output should be “start = 1” (index of 2nd petrol pump).

Simple Solution is to consider every petrol pumps as starting point and see if there is a possible tour. If we find a starting point with feasible solution, we return that starting point. The worst case time complexity of this solution is O(n^2).

We can use a Queue to store the current tour. We first enqueue first petrol pump to the queue, we keep enqueueing petrol pumps till we either complete the tour, or current amount of petrol becomes negative. If the amount becomes negative, then we keep dequeueing petrol pumps till the current amount becomes positive or queue becomes empty.

Instead of creating a separate queue, we use the given array itself as queue. We maintain two index variables start and end that represent rear and front of queue.

// C program to find circular tour for a truck
#include <stdio.h>
// A petrol pump has petrol and distance to next petrol pump
struct petrolPump
{
  int petrol;
  int distance;
};
// The function returns starting point if there is a possible solution,
// otherwise returns -1
int printTour(struct petrolPump arr[], int n)
{
    // Consider first petrol pump as a starting point
    int start = 0;
    int end =  1;
    int curr_petrol = arr[start].petrol - arr[start].distance;
    /* Run a loop while all petrol pumps are not visited.
      And we have reached first petrol pump again with 0 or more petrol */
    while (end != start || curr_petrol < 0)
    {
        // If curremt amount of petrol in truck becomes less than 0, then
        // remove the starting petrol pump from tour
        while (curr_petrol < 0 && start != end)
        {
            // Remove starting petrol pump. Change start
            curr_petrol -= arr[start].petrol - arr[start].distance;
            start = (start + 1)%n;
            // If 0 is being considered as start again, then there is no
            // possible solution
            if (start == 0)
               return -1;
        }
        // Add a petrol pump to current tour
        curr_petrol += arr[end].petrol - arr[end].distance;
        end = (end + 1)%n;
    }
    // Return starting point
    return start;
}
// Driver program to test above functions
int main()
{
    struct petrolPump arr[] = {{6, 4}, {3, 6}, {7, 3}};
    int n = sizeof(arr)/sizeof(arr[0]);
    int start = printTour(arr, n);
    (start == -1)? printf("No solution"): printf("Start = %d", start);
    return 0;
}

Output:

start = 2

Time Complexity: Seems to be more than linear at first look. If we consider the items between start and end as part of a circular queue, we can observe that every item is enqueued at most two times to the queue. The total number of operations is proportional to total number of enqueue operations. Therefore the time complexity is O(n).

Auxiliary Space: O(1)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Minimum swaps to make two arrays identical

Given two arrays which have same values but in different order, we need to make second array same as first array using minimum number of swaps.
Examples:

Input  : arrA[] = {3, 6, 4, 8},
         arrB[] = {4, 6, 8, 3}
Output : 2
we can make arrB to same as arrA in 2 swaps
which are shown below,
swap 4 with 8,   arrB = {8, 6, 4, 3}
swap 8 with 3,   arrB = {3, 6, 4, 8}

This problem can be solved by modifying the array B. We save the index of array A elements in array B i.e. if ith element of array A is at jth position in array B, then we will make arrB[i] = j
For above given example, modified array B will be, arrB = {3, 1, 0, 2}. This modified array represents distribution of array A element in array B and our goal is to sort this modified array in minimum number of swaps because after sorting only array B element will be aligned with array A elements.

So we count these swaps in modified array and that will be our final answer.
Please see below code for better understanding.

// C++ program to make an array same to another
// using minimum number of swap
#include <bits/stdc++.h>
using namespace std;
// Function returns the minimum number of swaps
// required to sort the array
int minSwapsToSort(int arr[], int n)
{
    // Create an array of pairs where first
    // element is array element and second element
    // is position of first element
    pair<int, int> arrPos[n];
    for (int i = 0; i < n; i++)
    {
        arrPos[i].first = arr[i];
        arrPos[i].second = i;
    }
    // Sort the array by array element values to
    // get right position of every element as second
    // element of pair.
    sort(arrPos, arrPos + n);
    // To keep track of visited elements. Initialize
    // all elements as not visited or false.
    vector<bool> vis(n, false);
    // Initialize result
    int ans = 0;
    // Traverse array elements
    for (int i = 0; i < n; i++)
    {
        // already swapped and corrected or
        // already present at correct pos
        if (vis[i] || arrPos[i].second == i)
            continue;
        // find out the number of  node in
        // this cycle and add in ans
        int cycle_size = 0;
        int j = i;
        while (!vis[j])
        {
            vis[j] = 1;
            // move to next node
            j = arrPos[j].second;
            cycle_size++;
        }
        // Update answer by adding current cycle.
        ans += (cycle_size - 1);
    }
    // Return result
    return ans;
}
// method returns minimum number of swap to make
// array B same as array A
int minSwapToMakeArraySame(int a[], int b[], int n)
{
    // map to store position of elements in array B
    // we basically store element to index mapping.
    map<int, int> mp;
    for (int i = 0; i < n; i++)
        mp[b[i]] = i;
    // now we're storing position of array A elements
    // in array B.
    for (int i = 0; i < n; i++)
        b[i] = mp[a[i]];
    /* We can uncomment this section to print modified
      b array
    for (int i = 0; i < N; i++)
        cout << b[i] << " ";
    cout << endl; */
    // returing minimum swap for sorting in modified
    // array B as final answer
    return minSwapsToSort(b, n);
}
//  Driver code to test above methods
int main()
{
    int a[] = {3, 6, 4, 8};
    int b[] = {4, 6, 8, 3};
    int n = sizeof(a) / sizeof(int);
    cout << minSwapToMakeArraySame(a, b, n);
    return 0;
}

Output:

2

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Subarray Inversions

We have an array A of n integers that we’re planning on sorting. Specifically, we want to know how close the array is to sorted. In order to achieve this, we introduce the idea of an inversion. An inversion in array is a pair of two indices i and jsuch that i < j and A[i] > A[j]. If our array contains one inversion, we need only swap A[i]and A[j] in order to sort the array. An array that contains 0 inversions is by definition sorted.

Problem: Given an array A of n integers, find the sum of the number of inversions in all subarrays of length k. To clarify, one must determine the number of inversions in each of the n – k + 1 subarrays of length k and add them together.

Input: The first line contains two space separated integers n and k. The next line contains a sequence of n space separated integers where the ith integer in the sequence is A[i].

Examples:

Input : arr[] = {1 2 3 4 5 6}
        k = 2
Output : 0

Input : arr[] = {1 6 7 2}
        k = 3
Output : 2
There are two subarrays of size 3,
{1, 6, 7} and {6, 7, 2}. Count of
inversions in first subarray is 0
and count of inversions in second
subarray is 2. So sum is 0 + 2 = 2

Input :  8 4
12 3 14 8 15 1 4 22
Output : 14

Input :  10 5
15 51 44 44 76 50 29 88 48 50
Output : 25

[1] Naive Approach

This problem seems fairly trivial at first, and we can easily implement a naive algorithm to brute force the solution. We simply create a window of length k and roll the window along A, adding the number of inversions in the window at each iteration. To find the number of inversions, the simplest approach is to use two for loops to consider all pairs of elements and increment a counter if the pair forms an inversion.

This approach is very easy to implement, but is it efficient? Let’s analyze the algorithm. The outermost loop runs n – k + 1 times, once for each k-subarray of A. At each of these iterations, we find the number of inversions in the window. To do this, we consider element 1 and elements 2, …, n, then element 2 and elements 3, …, n until element n – 1 and element n. Effectively, we’re performing n + (n – 1) + (n – 2) + … + 1 = n(n + 1)/2operations. Thus, our algorithm performs approximately (n – k + 1)(n)(n + 1)/2operations which is O(n^3 – kn^2). Since k can range from 1 to n, the worst case performance for this algorithm is O(n^3) when k = n/2. We can do better!

public class Subarray_Inversions {
    // Inversion counting method, slides window of [start,
    // end] across array
    static int inversion_count(int n, int k, int[] a)
    {
        int count = 0;
        for (int start = 0; start < n - k + 1; start++) {
            int end = start + k;
            count += bubble_count(a, start, end);
        }
        return count;
    }
    // Helper function, counts number of inversions via
    // bubble sort loop
    public static int bubble_count(int[] arr, int start, int end)
    {
        int count = 0;
        for (int i = start; i < end; i++) {
            for (int j = i + 1; j < end; j++) {
                if (arr[i] > arr[j]) {
                    count++;
                }
            }
        }
        return count;
    }
    public static void main(String[] args)
    {
        int n = 10;
        int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
        int k = 5;
        long result = inversion_count(n, k, arr);
        System.out.println(result);
    }
}

Output:

 25

[2] Mergesort-based Implementation

One optimization we can make is improving our inefficient, quadratic-time inversion counting method. One approach could involve using a mergesort-based method as outlined in this article. Since this runs in O(nlogn), our overall runtime is reduced to O(n^2logn), which is better, but still won’t be able to handle cases for which n = 10^6 for instance.

import java.util.*;
public class Subarray_Inversions {
    // Inversion counting method, slides window of [start,
    // end] across array
    static int inversion_count(int n, int k, int[] a)
    {
        int count = 0;
        for (int start = 0; start < n - k + 1; start++) {
            int[] sub_array = new int[k];
            for (int i = start; i < start + k; i++) {
                sub_array[i - start] = a[i];
            }
            count += subarray_inversion_count(sub_array);
        }
        return count;
    }
    // Counts number of inversions when merging
    public static long merge_inversion_count(int[] arr,
                                int[] left, int[] right)
    {
        int i = 0, j = 0, count = 0;
        while (i < left.length || j < right.length) {
            if (i == left.length) {
                arr[i + j] = right[j];
                j++;
            } else if (j == right.length) {
                arr[i + j] = left[i];
                i++;
            } else if (left[i] <= right[j]) {
                arr[i + j] = left[i];
                i++;
            } else {
                arr[i + j] = right[j];
                count += left.length - i;
                j++;
            }
        }
        return count;
    }
    // Divide and conquer approach -- splits array and counts
    // inversions via merge method
    public static long subarray_inversion_count(int[] arr)
    {
        if (arr.length < 2)
            return 0;
        int m = (arr.length + 1) / 2;
        int left[] = Arrays.copyOfRange(arr, 0, m);
        int right[] = Arrays.copyOfRange(arr, m, arr.length);
        return subarray_inversion_count(left) +
               subarray_inversion_count(right) +
               merge_inversion_count(arr, left, right);
    }
    public static void main(String[] args)
    {
        int n = 10;
        int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
        int k = 5;
        long result = inversion_count(n, k, arr);
        System.out.println(result);
    }
}

Output:

 25

[3] Overlapping Subarrays Implementation

Let’s revisit our overall approach. We’re looking at the window [0, k) and finding the number of inversions, then we look at [1, k+1). There’s a significant overlap in this range: we’ve already counted the number of inversions in [1, k) during the first iteration, and now we’re counting them again! Instead of counting inversions, let’s count the change in inversions from one window to the next. Effectively, shifting the window is just adding one element to the head of the window and removing an element from its tail — the body of the window remains the same. Checking for inversions among internal elements would be redundant; all we need to do is add the number of inversions induced by the new element and subtract the number of inversions induced by the removed element. We now only need to count the number of inversions in the first window, which we can do in O(klogk) time, and for each of the n – k additional windows, we simply perform one iteration through the k elements in the array to find the change in the number of inversions. Our overall runtime is now O(k(n – k) + klogk) = O(nk – k)which is still worst case O(n^2).

import java.util.*;
public class Subarray_Inversions {
    // Inversion counting method, slides window of [start,
    // end] across array
    static long inversion_count(int n, int m, int[] arr)
    {
        long count = 0;
        count += subarray_inversion_count_initial(Arrays.copyOfRange(arr, 0, m));
        long subarray_count = subarray_inversion_count_initial(Arrays.copyOfRange(arr, 1, m));
        for (int start = 1; start <= n - m; start++) {
            int end = start + m - 1;
            long[] ans = subarray_inversion_count(arr, start, end, subarray_count);
            count += ans[0];
            subarray_count = ans[1];
        }
        return count;
    }
    // start >=1; find inversion in interval [start, end)
    public static long[] subarray_inversion_count(int[] arr, int start,
                                          int end, long subarray_count)
    {
        int new_element = arr[end];
        long count = subarray_count;
        for (int i = start; i < end; i++) {
            if (new_element < arr[i])
                count++;
        }
        long totalSum = count;
        int last_element = arr[start];
        for (int i = start + 1; i <= end; i++) {
            if (last_element > arr[i])
                count--;
        }
        long[] ans = { totalSum, count };
        return ans;
    }
    // Counts number of inversions when merging
    public static long merge_inversion_count(int[] arr, int[] left,
                                                       int[] right)
    {
        int i = 0, j = 0, count = 0;
        while (i < left.length || j < right.length) {
            if (i == left.length) {
                arr[i + j] = right[j];
                j++;
            } else if (j == right.length) {
                arr[i + j] = left[i];
                i++;
            } else if (left[i] <= right[j]) {
                arr[i + j] = left[i];
                i++;
            } else {
                arr[i + j] = right[j];
                count += left.length - i;
                j++;
            }
        }
        return count;
    }
    // Divide and conquer approach -- splits array and counts
    // inversions via merge method
    public static long subarray_inversion_count_initial(int[] arr)
    {
        if (arr.length < 2)
            return 0;
        int m = (arr.length + 1) / 2;
        int left[] = Arrays.copyOfRange(arr, 0, m);
        int right[] = Arrays.copyOfRange(arr, m, arr.length);
        return subarray_inversion_count_initial(left) +
               subarray_inversion_count_initial(right) +
               merge_inversion_count(arr, left, right);
    }
    public static void main(String[] args) throws Exception
    {
        int n = 10;
        int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
        int k = 5;
        long result = inversion_count(n, k, arr);
        System.out.println(result);
    }
}

Output:

 25

[4] Binary Indexed Tree Implementation

Iterating over each window seems inevitable, so the bottleneck here appears to be the way we handle the windows. We know that consecutive windows overlap significantly, so all we need to know is the number of elements greater than the newly added element and number of elements less than the newly removed element. Many times, algorithms that perform the same or similar operation(s) repeatedly can be improved by the use of a more robust data structure. In our case, we’re looking for a dynamic data structure that can efficiently answer queries about an element’s relative position when sorted. We can use a self-balancing binary tree to actually maintain a sorted list, but insertion/removal takes logarithmic time. We can do this in constant time using a Binary Indexed Tree, or Fenwick Tree.

A binary indexed tree is a tree represented in the form of an array. It uses clever bit manipulation to compute the cumulative sum of elements very efficiently. We can call the function update(index, val) function to add val to BIT[index] and all of the ancestors of index. The function read(index) returns the sum of the values stored at BIT[index]and all of the ancestors of index in the tree. Thus, calling read(index) returns the cumulative sum of all elements in BIT less than or equal to index. Instead of storing values, if we simply store 1, we can use read(index + 1) to determine the number of elements less than index. Now, we can construct a binary indexed tree by inserting the elements (updating) of the first window. For subsequent windows, we can remove the trailing element by calling update(tail_element, -1) and add the new element with update(head_element, 1). Since this is a tree, the longest possible root-node path is O(logk), Thus, we achieve an optimal runtime of O(nlogk + klogk) = O(nlogk)!

Or do we…? Remember, binary indexed trees allocate memory for every possible value in the range [0, max_element], so this requires O(max_element) time and space. For very sparse arrays, this can be quite costly. Instead, we can define a hash function to . We can do this because we’re only concerned about inversions — as long as we keep the relative magnitude the same (i.e. A[i] <= A ==> A[hash(i)] <= A[hash(j)]), our solution will still be correct. Thus, we can map all the elements in A to the set {0, 1, 2, …, n}, yielding a guaranteed runtime of O(nlogk).

import java.util.*;
public class Subarray_Inversions {
    // Declare binary indexed tree with global scope
    static BIT bit;
    // first window, counts first k elements and creates
    // BIT
    static long inversionCountBIT1(int[] arr, int start,
                                               int end)
    {
        bit = new BIT(arr.length);
        long count = 0;
        for (int index = start; index >= end; index--) {
            count += bit.read(arr[index]);
            bit.update(arr[index], 1);
        }
        return count;
    }
    // subsequent windows, removes previous element, adds
    // new element, and increments change in inversions
    static long inversionCountBIT2(int[] arr, int start,
                                       int end, long val)
    {
        bit.update(arr[start + 1], -1); // remove trailing element
        // find number of elements in range [start, end-1]
        // greater than first
        int numGreaterThanFirst = start - end - bit.read(arr[start + 1] + 1);
        long count = val + bit.read(arr[end]) - numGreaterThanFirst;
        bit.update(arr[end], 1); // adds leading element
        return count;
    }
    // Main method to count inversions in size k subarrays
    public static long inversionCount(int n, int k, int[] arr)
    {
        bit = new BIT(n);
        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        int[] asort = arr.clone();
        // Map elements from [A[0]...A[n-1]] to [1...n]
        Arrays.sort(asort);
        int index = 0;
        int current = 1;
        for (int i = 0; i < n; i++) {
            if (!freq.containsKey(asort[i])) {
                freq.put(asort[i], current);
                current++;
            }
        }
        for (int i = 0; i < n; i++) {
            arr[i] = freq.get(arr[i]);
        }
        long count = 0;
        long val = 0;
        //[start - end] ==> start - end = k+1
        for (int start = n - 1; start >= k - 1; start--) {
            int end = start - k + 1;
            if (start == n - 1) { // First pass
                val = inversionCountBIT1(arr, n - 1, n - k);
            } else { // subsequent passes
                val = inversionCountBIT2(arr, start, end, val);
            }
            count += val;
        }
        return count;
    }
    public static void main(String[] args) throws Exception
    {
        int n = 10;
        int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
        int k = 5;
        long result = inversionCount(n, k, arr);
        System.out.println(result);
    }
    // Implementation of Binary Indexed Tree
    static class BIT {
        int[] tree;
        int maxVal;
    public BIT(int N)
        {
            tree = new int[N + 1];
            maxVal = N;
        }
        // Updates BIT, starting with element at index
        // and all ancestors
        void update(int index, int val)
        {
            while (index <= maxVal) {
                tree[index] += val;
                index += (index & -index);
            }
        }
        // Returns the cumulative frequency of index
        // starting with element at index and all ancestors
        int read(int index)
        {
            --index;
            int cumulative_sum = 0;
            while (index > 0) {
                cumulative_sum += tree[index];
                index -= (index & -index);
            }
            return cumulative_sum;
        }
    };
}

Output:

 25


Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

5 Difference between Application Server and Web Server in Java

Application server and web server in Java both are used to host Java web application. Though both application server and web server are generic terms, difference between application server and web server is a famous J2EE interview question. On  Java J2EE perspective main difference between web server and application server is support of EJB. In order to run EJB or host enterprise Java application (.ear) file you need an application server like JBoss, WebLogic, WebSphere or Glassfish, while you can still run your servlet and JSP or java web application (.war) file inside any web server like Tomcat or Jetty.

Application Server vs Web Server

  1. 1. Application Server supports distributed transaction and EJB. While Web Server only supports Servlets and JSP.
  2. Application Server can contain web server in them. most of App server e.g. JBoss or WAS has Servlet and JSP container.
  1. Though its not limited to Application Server but they used to provide services like Connection pooling, Transaction management, messaging, clustering, load balancing and persistence. Now Apache tomcat also provides connection pooling.

4.In terms of logical difference between web server and application server. web server is      supposed to provide http protocol level service while application server provides                support to web service and expose business level service e.g. EJB.

  1. Application server are more heavy than web server in terms of resource utilization.

Personally I don’t like to ask questions like Difference between Application Server and Web Server. But since its been asked in many companies, you got to be familiar with some differences. Some times different interviewer expect different answer but I guess on Java’s perspective until you are sure when do you need an application server and when you need a web server, you are good to go.

 

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

10 Object Oriented Design Principles Java Programmer should know about them

Object Oriented Design Principles are core of OOP programming, but I have seen most of the Java programmers chasing design patterns like Singleton pattern, Decorator pattern or Observer pattern, and not putting enough attention on learning Object oriented analysis and design. It’s important to learn basics of Object oriented programming like Abstraction, Encapsulation, Polymorphism and Inheritance. But, at the same time, it’s equally important to know object oriented design principles, to create clean and modular design. I have regularly seen Java programmers and developers of various experience level, who either doesn’t heard about these OOP and SOLID design principle, or simply doesn’t know what benefits a particular design principle offers, or how to apply these design principle in coding.

Bottom line is, always strive for highly cohesive and loosely couple solution, code or design. Looking open source code from Apache and Sun are good examples of learning Java and OOPS design principles. They show us,  how design principles should be used in coding and Java programs. Java Development Kit follows several design principle like Factory Pattern in BorderFactory class,  Singleton pattern in Runtime class, Decorator pattern on various java.io classes. By the way if you really interested more on Java coding practices then read Effective Java by Joshua Bloch , a gem by the guy who wrote Java Collection API.

If you are interested in learning object oriented principles and patterns, then you can look at my another personal favorite Head First Object Oriented Analysis and Design. This an excellent book and probably the best material available in object oriented analysis and design, but it often shadowed by its more popular cousin Head First Design Pattern by Eric Freeman. Later is more about how these principle comes together to create pattern you can use directly to solve known problems. These books helps a lot to write better code, taking full advantage of various Object oriented and SOLID design principles.

Though best way of learning any design principle or pattern is real world example and understanding the consequences of violating that design principle, subject of this article is Introducing Object oriented design principles for Java Programmers, who are either not exposed to it or in learning phase. I personally think each of these OOPS and SOLID design principle need an article to explain them clearly, and I will definitely try to do that here, but for now just get yourself ready for quick bike ride on design principle town 🙂

DRY (Don’t repeat yourself)

Our first object oriented design principle is DRY, as name suggest DRY (don’t repeat yourself) means don’t write duplicate code, instead use Abstraction to abstract common things in one place. If you have block of code in more than two place consider making it a separate method, or if you use a hard-coded value more than one time make them public final constant. Benefit of this Object oriented design principle is in maintenance. It’s important  not to abuse it, duplication is not for code, but for functionality . It means, if you used common code to validate OrderID and SSN it doesn’t mean they are same or they will remain same in future. By using common code for two different functionality or thing you closely couple them forever and when your OrderID changes its format , your SSN validation code will break. So beware of such coupling and just don’t combine anything which uses similar code but are not related.

 

Encapsulate What Changes

Only one thing is constant in software field and that is “Change”, So encapsulate the code you expect or suspect to be changed in future. Benefit of this OOPS Design principle is that Its easy to test and maintain proper encapsulated code. If you are coding in Java then follow principle of making variable and methods private by default and increasing access step by step e.g. from private to protected and not public. Several of design pattern in Java uses Encapsulation, Factory design pattern is one example of Encapsulation which encapsulate object creation code and provides flexibility to introduce new product later with no impact on existing code.

Open Closed Design Principle

Classes, methods or functions should be Open for extension (new functionality) and Closed for modification. This is another beautiful SOLID design principle, which prevents some-one from changing already tried and tested code. Ideally if you are adding new functionality only than your code should be tested and that’s the goal of Open Closed Design principle. By the way, Open Closed principle is “O” from SOLID acronym.

 

Single Responsibility Principle (SRP)

Single Responsibility Principle is another SOLID design principle, and represent  “S” on SOLID acronym. As per SRP, there should not be more than one reason for a class to change, or a class should always handle single functionality. If you put more than one functionality in one Class in Java  it introduce coupling between two functionality and even if you change one functionality there is chance you broke coupled functionality,  which require another round of testing to avoid any surprise on production environment.

 

Dependency Injection or Inversion principle

Don’t ask for dependency it will be provided to you by framework. This has been very well implemented in Spring framework, beauty of this design principle is that any class which is injected by DI framework is easy to test with mock object and easier to maintain because object creation code is centralized in framework and client code is not littered with that.There are multiple ways to  implemented Dependency injection like using  byte code instrumentation which some AOP (Aspect Oriented programming) framework like AspectJ does or by using proxies just like used in Spring. See this example of IOC and DI design pattern to learn more about this SOLID design principle. It represent “D” on SOLID acronym.

 

Favor Composition over Inheritance

Always favor composition over inheritance ,if possible. Some of you may argue this, but I found that Composition is lot more flexible than Inheritance. Composition allows to change behavior of a class at run-time by setting property during run-time and by using Interfaces to compose a class we use polymorphism which provides flexibility of to replace with better implementation any time. Even Effective Java advise to favor composition over inheritance.

 

Liskov Substitution Principle (LSP)

According to Liskov Substitution Principle, Subtypes must be substitutable for super type i.e. methods or functions which uses super class type must be able to work with object of sub class without any issue”. LSP is closely related to Single responsibility principle and Interface Segregation Principle. If a class has more functionality than subclass might not support some of the functionality ,and does violated LSP. In order to follow LSP SOLID design principle, derived class or sub class must enhance functionality, but not reduce them. LSP represent  “L” on SOLID acronym.

 

Interface Segregation principle (ISP)

Interface Segregation Principle stats that, a client should not implement an interface, if it doesn’t use that. This happens mostly when one interface contains more than one functionality, and client only need one functionality and not other.Interface design is tricky job because once you release your interface you can not change it without breaking all implementation. Another benefit of this design principle in Java is, interface has disadvantage to implement all method before any class can use it so having single functionality means less method to implement.

 

Programming for Interface not implementation

Always program for interface and not for implementation this will lead to flexible code which can work with any new implementation of interface. So use interface type on variables, return types of method or argument type of methods in Java. This has been advised by many Java programmer including in Effective Java and Head First design pattern book.

 

Delegation principle

Don’t do all stuff  by yourself,  delegate it to respective class. Classical example of delegation design principle is equals() and hashCode() method in Java. In order to compare two object for equality we ask class itself to do comparison instead of Client class doing that check. Benefit of this design principle is no duplication of code and pretty easy to modify behavior.
Here is nice summary of all these OOP design principles :

All these object oriented design principle helps you write flexible and better code by striving high cohesion and low coupling. Theory is first step, but what is most important is to develop ability to find out when to apply these design principle. Find out, whether we are violating any design principle and compromising flexibility of code, but again as nothing is perfect in this world, don’t always try to solve problem with design patterns and design principle they are mostly for large enterprise project which has longer maintenance cycle.

 

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

How to use Comparator and Comparable in Java?

 

Difference between Comparator and Comparable in Java is very popular Java interview question mostly asked in telephonic round and writing code to sort object using Comparable or Comparator is popular on  written test round of interview.The question was this “How you will sort Employee object based on his EmployeeID and his name” and this involves the use of both Comparable as well as Comparator interface in Java. This post is my revision on Java fundamentals similar to I did about equals method in Java and  some tips to override hashCode in Java. All of these methods are fundamentals in Java programming language and correct understanding is must for any Java developer. Comparators and comparable in Java are two interfaces which is used to implement sorting in Java. It’s often required to sort objects stored in any collection classes like ArrayList, HashSet or in Array and that time we need to use either  compare() or  compareTo()method defined in java.util.Comparator and java.lang.Comparable. In this Java tutorial we will see example of  Comparator and Comparable to sort object in Java and discuss some best practices around when to use Comparator interface etc. Any way before moving ahead Let’s see some important differences between Comparable and Comparator in Java.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

 

Can You Overload or Override Static methods in Java

Can static method be overridden in Java, or can you override and overload static method in Java, is a common Java interview question, mostly asked to 2 years experienced Java programmers. Answer is, No, you can not override static method in Java, though you can declare method with same signature in sub class. It won’t be overridden in exact sense, instead that is called method hiding. But at same time, you can overload static methods in Java, there is nothing wrong declaring static methods with same name, but different arguments. Some time interviewer also ask, Why you can not override static methods in Java? Answer of this question lies on time of resolution. As I said in difference between static and dynamic binding , static method are bonded during compile time using Type of reference variable, and not Object. If you have using IDE like Netbeans and Eclipse, and If you try to access static methods using an object, you will see warnings. As per Java coding convention, static methods should be accessed by class name rather than object. In short Static method can be overloaded, but can not be overridden in Java. If you declare,  another static method with same signature in derived class than static method of super class will be hidden, and any call to that static method in sub class will go to static method declared in that class itself. This is known as method hiding in Java.

 

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Nested Static Class in Java

A nested class is actually a member of a top-level class, so it’s not much difference with a static variable. All instances of the top-level class will have a reference of same nested class if its static, otherwise each of them will refer to a different instance of nested class.

One of the main advantages of making a nested class static is how you instantiate it. Suppose you declare a nested class B inside a top level class A, then it would be referred as A.B and you can create an instance of this class as A.B nestedStaticInstance = new A.B(), unlike Testing.B bs = new Testing(). new B(); for creating an instance of a non-static class, also known as inner class.

So, Yes, you can declare a class static in Java, provided the class is inside a top level class. Such classes are also known as nested classes and they can be declared static, but if you are thinking to make a top level class static in Java, then it’s not allowed. If you do so, the compiler will complain saying “illegal modifier for the class, only public, abstract and final are permitted”.

Now, let’s see some code in action to prove our point. First, let’s try to declare a top level class static in Java and see if we can do it or no.

How to make a static class in Java

You can see the compile-time error, it means it is illegal to use the static modifier with a top level class in Java. It doesn’t matter whether the class is public or package and whether its name is same as the name of the Java source file. In short, you cannot make a top level class static in Java i.e. the class which is not inside another class. Here is another example, where I have tried to make a non-public but top level class static in Java:

Can you make a class static in Java

You can see, still, the same compile time error, “illegal modifier for the class, only public, abstract and final are permitted” is thrown”.  If you are hearing about nested or inner class first time, You should first read a good core Java book e.g. Head First Java to learn more about nested class in Java.

Now, let’s try to make a nested class i.e. a class inside the top level class static in Java. As per theory, you can declare a nested class static in Java, let’s see that in code.

This time there is no compiler error, it means you can make a nested class static in Java. I have also shown you how you can create an instance of the nested static class in Java. You can see, you can create an instance without creating an instance of the outer class which was not possible with non-static nested class or inner class.

Can we declare a class Static in Java?

That’s all about whether you can declare a class static in Java or not. Of course, you cannot make a top level class static in Java but you can always make a nested class static in Java. In fact, it is one of the best practice and also suggested in Effective Java to prefer nested static class instead of non-static inner class.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Can we declare a class Static in Java?

The answer to this question is both Yes and No, depending on whether you are talking about a top level class or a nested class in Java. You cannot make a top level class static in Java, the compiler will not allow it, but you can make a nested class static in Java. A top level class is a class which is not inside another class. It may or may not be public i.e. you can have more than one class in a Java source file and only needs to be public, whose name must be same as the name of the file, rest of the class or interface on that file may or may not be public. On the other hand, a nested class is a class inside a top level class. It is also known as the inner class or member class in Java.

Now, let’s think about what is the meaning of static class, why would someone want to make a class static in Java? If you are familiar with concept of static method and static variable in Java, then you know that anything static can be accessed without creating instance of the class.

For example, you can access the static variable directly as ClassName.variable and you can invoke the static method as ClassName.staticMethod(), this is a great convenience for calling utility method or accessing constants.

This convenience is the main reason Java programmers like to declare nested class as static in Java. Remember, A nested class, if it’s not static then you can’t create its instance without first creating an instance of the outer class, which is a bit inconvenient. Such classes are known as Inner class and they are always associated with an instance of outer class.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at  http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Operator Overloading

/* C++ program to find the power of a given number using operator overloading concept*/

#include<iostream.h>
#include<conio.h>
#include<math.h>
int power(int,int);
float power(float,float);
void main()
{
int b,p,r;

float br,pr,rr;
clrscr();
cout<<“enter the integer base and integer power”;
cin>>b>>p;
cout<<“enter the real base and real power”;
cin>>br>>pr;
r=power(b,p); /* first function will be called*/
rr=power(br,pr); /* second function will be called*/
cout<<“the power of”<<b<<“and”<<p<<“is”<<r;
cout<<“\n”<<“the power of”<<br<<“and”<<pr<<“is”<<rr;
}
int power(int a,int b)
{
return pow(a,b);
}
float power(float c,float d)
{
return pow(c,d);
}

Output:
enter the integer base and integer power
2
2
enter the real base and real power
1.2
3.2
the power of 2 and 2 is 4
the power of 1.2 and 3.2 is 1.792

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide