Disclaimer: Most of the content below will be cited. If any sentence is not cited, I want to clarify that this article is only for knowledge purpose and I will not be earning any money from it.

Insertion Sort

  • INSERTION-SORT can take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they already are.
  • In INSERTION-SORT, the best case occurs if the array is already sorted.

T [Best Case]= O(n)

  • If the array is in reverse sorted order i.e in decreasing order, INSERTION-SORT gives the worst case results.

T [Worst Case]= θ()

  • Average…


Kruskal:

  • Kruskal’s algorithm can also run on the disconnected graphs/ Connected Components
  • Kruskal’s algorithm can be applied to the disconnected graphs to construct the minimum cost forest, but not MST because of multiple graphs
  • (True/False) — Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm | False

Prim’s algorithm outperforms the Kruskal’s algorithm in case of the dense graphs.

  • Sorting all edges by their weights takes (O(|E| log |E|) time (done in Kruskal’s Algo) | True
  • When using union-find data structures, using both path compression and rank-based heuristics is superior to (i.e., …


Beam Transformations

  1. GroupByKey (GBK) : KV<K,V> → KV<K,Iterable<V>>
  2. CoGroupByKey (CoGBK): <KV<Id,CoGbkResult>> ; special map from tuple tag PCollection → Iterable<PCollection>

3. Combine.perKey :

3.1. Serializable Function<Iterable<T>,T>

3.2 CombineFn<InputT,AccumT,OutputT>

  • Flatten: PCollectionList<T> is created, then merged
  • Partition: returns a partition for (override) PCollectionList<T> with PartitionFn.
  • Distinct.create: PCollection<KV<Type1,Type2>>
  • Count.perKey: PCollection<KV<Type1,Long>>

Binary Search

  • Binary Search in Arrays : Arrays.binarySearch()
binarySearch(T[] a, T key)
binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)
binarySearch(T[] a, T key, Comparator<? super T> c)
  • Binary Search in Collection : Collections.binarysearch()

It works for objects Collections like ArrayList and LinkedList.

binarySearch(List<? extends Comparable<? super T>> list, T key)
binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

References:

https://www.geeksforgeeks.org/collections-binarysearch-java-examples/


In Java, we broadly categorize Queues into the following two types

  • Bounded Queues (all queues in java.util.concurrent package)
  • Unbounded Queues (all queues in java.util package)

Bounded Queues are queues which are bounded by capacity that means we need to provide the max size of the queue at the time of creation.

For example: ArrayBlockingQueue

ArrayBlockingQueue is a bounded, blocking queue backed by an array

BlockingQueue queue = new ArrayBlockingQueue(1024);

queue.put("1");

Object object = queue.take();

Unbounded Queues are queues which are NOT bounded by capacity that means we should not provide the size of the queue.

For example LinkedList

Priority Queues

Class PriorityQueue<E>

An unbounded priority queue based on a priority heap.

References


Disclaimer: Most of the content below will be cited. If any sentence is not cited, I want to clarify that this article is only for knowledge purpose and I will not be earning any money from it.

Related Story : Sorting Algorithms- Properties/Pros/Cons/Comparisons

It is relationship between variables in your program which holds true just before the loop is ever run (referred as establishing the invariant) and is true again at the bottom of the loop (referred as maintaining the invariant)

// the Loop Invariant must be true here
while ( TEST CONDITION ) {
// top of the loop…


Neutral things at MNC

  • Some people create unnecessary dependencies in projects for their advantage
  • Small work could be stretched to show them as big tasks in large MNCs by some people. A day’s work could be stretched to 3–5 days. It could also depend on the person not knowing the product.
  • IT complaints to need to be made install freeware. Restriction to install tools for working — Information Security
  • Business Analyst has a functional role. S/He comes at the beginning/end of SDLC
  • Seat and computer allotment might take time(depends upon the company) [Study GRE/ Prepare for SOP/LOR]
  • Useless timesheets( you…

In the 21st century, the startup world is a parallel universe that co-exists along with huge legacy companies. While startups innovate on a per-day basis to survive in the industry, large legacy company try harder to keep innovation at the core of the development process of their products.
Working in a startup might be one of the best learning experience, a newbie could ever have. But after a year or two, one might have the thirst to work on bigger products in larger teams. …


Disclaimer: Most of the content below will be cited. If any sentence is not cited, I want to clarify that this article is only for knowledge purpose and I will not be earning any money from it.

Related Story : Sorting Algorithms- Properties/Pros/Cons/Comparisons

Growth Relation

[ <<< symbol => (grows much much slower than) ]

Constant <<< Poly-logs <<< Polynomials <<< Factorial (n!) <<< Exponential (n^n)

Example:

1 < log(n) < n^(1/2) < n (i.e. n¹) < n log(n) ~ log(n!) < n² < n³ <<< 2^n < 3^n <<< n! <<< n^n

  • A recurrence is an equation or inequality that describes…

Disclaimer: Most of the content below will be cited. If any sentence is not cited, I want to clarify that this article is only for knowledge purpose and I will not be earning any money from it.

Related Story : Sorting Algorithms — Basics

Sorting Algorithms- Properties/Pros/Cons/Comparisons

BFS vs DFS

  • Both the algorithms are used to traverse graphs and creates a tree for the path of its traversal.
  • BFS is a vertex based algorithm, whereas DFS is an edge based algorithm
  • BFS uses Queue data structure for its working while DFS uses Stack data structure for its working
  • Structure of the constructed tree…

Ayush Arora

Full-Stack Data Engineer | System Design Enthusiast | ayusharora.me

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store