Posts

Showing posts from November, 2018

final vs immutable

final vs Immutability in Java final :  In Java,  final  is a modifier which is used for class, method and variable also. When a variable is declared with final keyword, it’s value can’t be modified, essentially, a constant. Immutability  :  In simple terms, immutability means unchanging over time or unable to be changed. In Java, we know that String objects are immutable means we cant change anything to the existing String objects. Differences between final and immutability final means that you can’t change the object’s reference to point to another reference or another object, but you can still mutate its state (using setter methods e.g). Whereas immutable means that the object’s actual value can’t be changed, but you can change its reference to another one. final modifier is applicable for variable but not for objects, Whereas immutability applicable for an object but not for variables. By declaring a reference variable as final, we won’t get any ...

Given million number in a list. How to mutiply each element by a constant with minimum time complexity

With Streams, this is simple, here's an example with 100 numbers: Integer MUTIPLY_ELEMENT = 2 ; List < Integer > resultNumbers = IntStream . range ( 0 , 100 ) . parallel () . map ( i -> i * MUTIPLY_ELEMENT ) . boxed () . collect ( Collectors . toList ()); if you do care about ordering, but still want to gain the benefit of parallel processing, you can take advantage of the fact that your operation (multiplying by 2) is simple enough that the resulting numbers will still be in the same relative "natural" order and just call  sorted()  on the stream after the  map() call. However, the sorting operation could very well take just as long as if you just did it single threaded. Also, understand that this is by NO MEANS a "real world" scenario, you will almost never come across an actual problem like this. Hopefully you're just trying to get your head around parallelism in general, bec...

Java is Pass by Value and Not Pass by Reference

Pass by Value : The method parameter values are copied to another variable and then the copied object is passed, that’s why it’s called pass by value. Pass by Reference : An alias or reference to the actual parameter is passed to the method, that’s why it’s called pass by reference. public class Main {  public static void main(String[] args) {  int x = 5;  change(x);  System.out.println(x);  }  public static void change(int x)   {  x = 10;  }  }  Output: 5 Reference

Time Complexity Chart Data Structures

Image
Big-O Complexity Chart Horrible Bad Fair Good Excellent O(log n), O(1) O(n) O(n log n) O(n^2) O(2^n) O(n!) Operations Elements Common Data Structure Operations Data Structure Time Complexity Space Complexity Average Worst Worst Access Search Insertion Deletion Access Search Insertion Deletion Array Θ(1) Θ(n) Θ(n) Θ(n) O(1) O(n) O(n) O(n) O(n) Stack Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n) Queue Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n) Singly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n) Doubly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n) Skip List Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n log(n)) Hash Table N/A Θ(1) Θ(1) Θ(1) N/A O(n) O(n) O(n) O(n) Binary Search Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n) Cartesian Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n) O(n) O(n) O(n) B-Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) Red-Black Tr...

Quick Sort

Image
Recursive package com.programming.ds.sorting; import com.programming.tool.ProgrammingTools; /**  * There are many different versions of quickSort that pick pivot in different  * ways.  *  * Always pick first element as pivot.  *  * Always pick last element as pivot (implemented below)  *  * Pick a random element as pivot.  *  * Pick median as pivot.  *  * The key process in quickSort is partition(). Target of partitions is, given  * an array and an element x of array as pivot, put x at its correct position in  * sorted array and put all smaller elements (smaller than x) before x, and put  * all greater elements (greater than x) after x. All this should be done in  * linear time.  *  * 1) QuickSort is a divide and conquer algorithm. Large list is divided into  * two and sorted separately (conquered), sorted list is merge later.  *  * 2) On "in-place" implem...