Back To Course Home

Data Structures for Coding Interviews in Java

0% completed

Complexity Measures

Comparing Algorithms Example: Measuring Time Complexity of a Single Loop Algorithm Example: Time Complexity of an Algorithm With Nested Loops Introduction to Asymptotic Analysis and Big O Other Common Asymptotic Notations and Why Big O Trumps Them Useful Formulae Common Complexity Scenarios Challenge: Big (O) of Nested Loop with Addition Solution: Big O of a Nested Loop with Addition Challenge: Big (O) of Nested Loop with Subtraction Solution: Big O of a Nested Loop with Subtraction Challenge: Big O of Nested Loop with Multiplication Solution: Big O of Nested Loop with Multiplication Challenge: Nested Loop with Multiplication (Basic)Solution: Nested Loop with Multiplication (Basic)Challenge: Nested Loop with Multiplication (Intermediate)Solution: Nested Loop with Multiplication (Intermediate)Challenge: Nested Loop with Multiplication (Advanced)Solution: Nested Loop with Multiplication (Advanced)Challenge: Nested Loop with Multiplication (Pro)Solution: Nested Loop with Multiplication (Pro)Complexity Interview Questions

Arrays

What is an Array?Two Dimensional Arrays What Is a List?Challenge: Remove Even Integers From Array Solution: Remove Even Integers From Array Challenge: Merge Two Sorted Arrays Solution: Merge Two Sorted Arrays Challenge: Find Two Numbers That Add Up to K Solution: Find Two Numbers That Add Up to K Challenge: Product of Array Except Self Solution: Product of Array Except Self Challenge: Find Minimum Value in Array Solution: Find Minimum Value in Array Challenge: First Non-Repeating Integer in an Array Solution: First Non-Repeating Integer in an Array Challenge: Find Second Maximum Value in an Array Solution: Find Second Maximum Value in an Array Challenge: Rotate Array Solution: Rotate Array Challenge: Rearrange Positive & Negative Values Solution: Rearrange Positive & Negative Values Challenge: Rearrange Sorted Array in Max/Min Form Solution: Rearrange Sorted Array in Max/Min Form Challenge: Maximum Subarray Solution: Maximum Subarray Array Interview Questions

Linked Lists

What is the Singly Linked List (SLL)?Basic Linked List Operations Insertion in a Singly Linked List Insertion in Singly Linked List (Insert After)Singly Linked List Deletion (Implementation)Linked Lists vs. Arrays What is a Doubly Linked List (DLL)?Linked List with Tail Challenge: Insertion at Tail Solution: Insertion at Tail Challenge: Search in a Singly Linked List Solution: Search in a Singly Linked List Challenge: Deletion by Value Solution: Deletion by Value Challenge: Find the Length of a Linked List Solution: Find the Length of a Linked List Challenge: Reverse Linked List Solution: Reverse Linked List Challenge: Linked List Cycle Solution: Linked List Cycle Challenge: Middle of the Linked List Solution: Middle of the Linked List Challenge: Remove Duplicates from a Linked List Solution: Remove Duplicates from a Linked List Challenge: Union and Intersection of Linked Lists Solution: Union and Intersection of Linked Lists Challenge: Return the Nth Node from End Solution: Return the Nth Node from End Challenge: Find If a Doubly Linked List Is a Palindrome Solution: Find If a Doubly Linked List Is a Palindrome Linked list Interview Questions

Stack/Queues

What is a Stack?Stack (Implementation)What is a Queue?Queue (Implementation)Challenge: Generate Binary Numbers From 1 to n Using a Queue Solution: Generate Binary Numbers From 1 to n Using a Queue Challenge: Implement Two Stacks Using One Array Solution: Implement Two Stacks Using One Array Challenge: Reverse First k Elements of Queue Solution: Reverse First k Elements of Queue Challenge: Implement Queue Using Stacks Solution: Implement Queue Using Stacks Challenge: Sort Values in a Stack Solution: Sort Values in a Stack Challenge: Evaluate Postfix Expression Using a Stack Solution: Evaluate Postfix Expression Using a Stack Challenge: Next Greater Element Using a Stack Solution: Next Greater Element Using a Stack Challenge: Find the Celebrity Solution: Find the Celebrity Challenge: Valid Parentheses Solution: Valid Parentheses Challenge: Min Stack Solution: Min Stack Stack/Queue Interview Questions

Graphs

What is a Graph?Representation of Graphs Graph Implementation Complexities of Graph Operations What is a Bipartite Graph?Graph Traversal Algorithms Challenge: Implement Breadth-First Search Solution: Implement Breadth-First Search Challenge: Implement Depth-First Search Solution: Implement Depth-First Search Challenge: Detect Cycle in a Directed Graph Solution: Detect Cycle in a Directed Graph Challenge: Find a Mother Vertex in a Directed Graph Solution: Find a Mother Vertex in a Directed Graph Challenge: Count the Number of Edges in an Undirected Graph Solution: Count the Number of Edges in an Undirected Graph Challenge: Check If a Path Exists between Two Vertices Solution: Check If a Path Exists between Two Vertices Challenge: Graph Valid Tree Solution: Graph Valid Tree Challenge: Find the Shortest Path between Two Vertices Solution: Find the Shortest Path between Two Vertices Challenge: Remove Edge from a Directed Graph Solution: Remove Edge from a Directed Graph Graph Interview Questions

Trees

What is a Tree?Types of Trees What Makes a Tree Balanced?What is a Binary Tree?More on Complete Binary Trees Skewed Binary Tree What is a Binary Search Tree (BST)?Insertion in Binary Search Trees Insertion in BST (Complete Implementation)Search in Binary Search Trees (Implementation)Deletion in Binary Search Trees Deletion in Binary Search Trees (Implementation)Pre-Order Traversal in Binary Search Trees In-Order Traversal in Binary Search Trees Post-Order Traversal in Binary Search Tree What is an AVL Tree?AVL Insertion AVL Deletion What is a Red-Black Tree?Red-Black Tree Insertion Red-Black Tree Deletion What is a 2-3 Tree?2-3 Insertion 2-3 Deletion of Element at Leaf Node 2-3 Deletion of Element at Internal Node 2-3-4 Trees Overview of Trees Challenge: Find Minimum Value in Binary Search Tree Solution: Find Minimum Value in Binary Search Tree Challenge: Find kth Maximum Value in Binary Search Tree Solution: Find kth Maximum Value in Binary Search Tree Challenge: Find Ancestors of a Given Node in a BST Solution: Find Ancestors of a Given Node in a BST Challenge: Find the Height of Binary Search Tree Solution: Find the Height of Binary Search Tree Challenge: Find Nodes at k Distance from the Root Solution: Find Nodes at k Distance from the Root Tree Interview Questions

Trie (Advanced Trees)

What is a Trie?The Structure of a Trie Insertion in a Trie Search in a Trie Deletion in a Trie Challenge: Total Number of Words in a Trie Solution: Total Number of Words in a Trie Challenge: Find All Words Stored in Trie Solution: Find All Words Stored in Trie Challenge: Array Sort Using Trie Solution: Array Sort Using Trie Challenge: Word Formation From a Dictionary Using Trie Solution: Word Formation From a Dictionary Using Trie Trie Interview Questions

Heaps

Heap Representation in Arrays

Max Heap: Introduction

Max Heap (Implementation)

Min Heap: An Introduction

Min Heap (Implementation)

Challenge: Convert Max Heap to Min Heap

Solution: Convert Max Heap to Min Heap

Challenge: Find k Smallest Elements in an Array

Solution: Find k Smallest Elements in an Array

Challenge: Find K Largest Elements in an Array

Solution: Find K Largest Elements in an Array

Heap Interview Questions

Hash Tables

What is a Hash Table?Hash Functions Collisions in Hash Tables Building a Hash Table from Scratch Add/Remove & Search in a Hash Table (Implementation)Complete Implementation of Hash Tables Trie vs Hash Table HashMap vs HashSet Challenge: An Array as a Subset of Another Array Solution: An Array as a Subset of Another Array Challenge: Check if Arrays are Disjoint Solution: Check if Arrays are Disjoint Challenge: Find Symmetric Pairs in an Array Solution: Find Symmetric Pairs in an Array Challenge: Trace the Complete Path of a Journey Solution: Trace the Complete Path of a Journey Challenge: Find Two Pairs in an Array Such That a+b = c+d Solution: Find Two Pairs in an Array Such That a+b = c+d Challenge: A Subarray with a Sum of 0 Solution: A Subarray with a Sum of 0 Challenge: Word Formation Using a Hash Table Solution: Word Formation Using a Hash Table Challenge: Find Two Numbers That Add up to k—Hashing Solution: Find Two Numbers That Add up to k—Hashing Challenge: First Non-Repeating Integer in an Array—Hashing Solution: First Non-Repeating Integer in an Array—Hashing Challenge: Linked List Cycle—Hashing Solution: Linked List Cycle—Hashing Challenge: Remove Duplicates from Linked List - Hashing Solution: Remove Duplicates from Linked List - Hashing Challenge: Union and Intersection of Linked Lists — Hashing Solution: Union and Intersection of Linked Lists — Hashing Hashing Interview Questions

Summary of Data Structures

Overview of Linear & Non-Linear Data Structures Conclusion

Heap Representation in Arrays

The lesson elaborates how to Use Arrays for the Implementation of Heaps.

Heaps can be implemented using Arrays. The contents of a heap with n nodes are stored in such a way that all the parent nodes occur in the first half of array (n/2), while the leaves are present at the last n/2 positions. So the last parent will be at the n/2th position.

The node at the kth position will have its children placed as follows:

The Left child at 2k+1
The Right child at 2k+2.

See the figure below to see how nodes are mapped on the array:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.