### What FAANG companies expect in their interview from candidates

Its every software engineer’s dream to work with the big FAANG companies…

July 03, 2019

This is another very useful sorting algorithm based on *Heap* data structure.
Read more about Heap Data Structure

In this algorithn, we first prepare heap which satisfies max-heap property. Once we get out max heap ready. We get maximum element at the top. We swap this element with the last index element. And, reduce heapsize by one. Now, since we have put a newer element on top. We will just run max_heapify() algorithm on this array with new heapsize.

Finally we get the sorted array.

- Build a max heap (using max_heapify())
- In a loop starting from last index
- swap 0-index value with current index value (which is the last index in our heap)
- reduce heap size by one. Means, largest element is done. Lets work on remaining array.
- Run max_heapify() on 0-index

See the code here:

```
public class HeapSort {
private int[] arr;
private int heapsize;
public HeapSort(int[] arr) {
this.arr = arr;
this.heapsize = this.arr.length;
}
private int getLeftChild(int index) {
return (index * 2) + 1;
}
private int getRightChild(int index) {
return (index * 2) + 2;
}
private void max_heapify(int index) {
int l = this.getLeftChild(index);
int r = this.getRightChild(index);
int indexOfLargest = index;
if (l < this.heapsize && this.arr[l] > this.arr[index]) {
indexOfLargest = l;
}
if (r < this.heapsize && this.arr[r] > this.arr[indexOfLargest]) {
indexOfLargest = r;
}
if (indexOfLargest != index) {
ArrayUtils.swap(this.arr, index, indexOfLargest);
this.max_heapify(indexOfLargest);
}
}
private void buildMaxHeap() {
for (int i=this.heapsize/2; i>=0; i--) {
this.max_heapify(i);
}
}
public void doHeapSort() {
this.buildMaxHeap();
int l = this.arr.length;
for (int i=l-1; i>0; i--){
ArrayUtils.swap(this.arr, 0, i);
this.heapsize--;
this.max_heapify(0);
}
}
}
```

- This is an in-place algorithm.
- Uses
*Heap*data structure - Performance is very good. its complexity is O(n log n)

The algorithm runs on O(n log n) in worst/average case.

Its every software engineer’s dream to work with the big FAANG companies…

Max Priority Queue is a data structure which manage a list of keys(values). And…

This algorithm is very useful for large input. And, is quite efficient one. It…

First try to understand question. Its a binary tree, not a binary search tree…

Problem Statement Roman numerals are represented by seven different symbols: I…

Introduction In this post we will see following: How to schedule a job on cron…

Introduction There are some cases, where I need another git repository while…

Introduction In this post, we will see how to fetch multiple credentials and…

Introduction I have an automation script, that I want to run on different…

Introduction I had to write a CICD system for one of our project. I had to…

Introduction Java log4j has many ways to initialize and append the desired…