This is an animated, visual and spatial way to learn data structures and algorithms
Talk to us!
Mail us about anything - anything! - and we will always reply :-)
Data structures and Algorithms have a symbiotic relationship. The choice of data structure significantly influences the algorithms' performance and complexity and vice versa. Also learn about abstract data types and how they relate to data structures.
What is the performance of your code? How do you measure this? What is complexity and what is its relationship with performance?
The Big O notation becomes much clearer when you practice find the complexity of some sample pieces of code. Let's see how many of these you get right!
Linked lists are just one way to implement lists. Linked lists are less interesting in Java then in other programming languages such as C and C++ which require the developer to manage memory.
However lists are useful and a very core data structure so it makes sense to start off this class by understanding how we can set up a linked list in Java.
A few basic problems working with lists should give you a good idea of how to traverse and linked lists, add elements to a list and count the number of elements in a list.
The source code attached to this lecture has solutions for even more linked list based problems which are not covered in this lecture.
Linked lists and arrays solve the same kind of problems, holding a list or a collection. When would you use one over the other? Learn how you can make an informed choice.
The stack is a very simple and easy to understand data structure. However it lies underneath many complicated real world problems and is incredibly useful.
Let's build a stack for real using Java. It'll have all the operations we're interested in - push, pop, peek, size etc. It can hold any data type, it's a generic class.
Problems which use stacks as a part of their solutions are very common in programming interviews. Matching parenthesis to check for well formed expressions is a classic interview question - let's solve this using the stack we're already implemented.
Another interview question implemented. You have space available but your processing needs to be very fast indeed. How would you keep track of the minimum element of a stack as it changes?
The queue belongs to the same linear data structure family as the stack but it's behavior is very different. Queues are much more intuitive as there are plenty of real world examples where a queue is the fair and correct way of processing.
A common, fast but slightly tricky implementation of the queue is the array where the last element wraps around to the first. An interview favorite, let's see how to implement the circular queue.
We know the stack, and we know the queue. This problem brings them together. It's possible to mimic the behavior of a queue using 2 stacks in the underlying implementation. Let's write the most efficient code possible to make this work.
The simplest and most naive sorting algorithm.
This belongs to a class of algorithms which uses divide and conquer to break the problem set into smaller pieces. This also makes a time-space trade off to get a faster running time.
Binary search is a pretty nifty way to search through a sorted list in O(Log N) time. It's also an interview favorite so make sure you understand it well!
The binary tree is an incredibly useful hierarchical data structure. Many other, more complex data structures, use the binary tree as the foundation. Let's see what a binary tree looks like and learn some simple terminology associated with the tree.
Traversing a binary tree can be done in variety of ways. The breadth first traversal visits and processes nodes at every level before moving on to the next. Let's visualize breadth first traversal and see how it's implemented.
Depth first traversal can be of 3 types based on the order in which the node is processed relative to it's left and right sub-trees. Pre-order traversal processes the node before processing the left and then the right sub trees.
Depth first traversal can be of 3 types based on the order in which the node is processed relative to it's left and right sub-trees.
In-order traversal processes the left subtree, then the node itself and then it's right sub trees. Post-order traversal processes the node *after* it's left and right subtrees.
The algorithms are all remarkably similar and very easy once you use recursion.
Find the minimum value in a binary search tree, find the maximum depth of a binary tree and mirror a binary tree. Learn to solve these problems recursively and see implementation details.
Priority Queues allow us to make decisions about which task or job has the highest priority and has to be processed first. Common operations on a Priority Queue are insertion, accessing the highest priority element and removing the highest priority element.
The Binary Heap is the best implementation of the Priority Queue.
The Binary Heap is logically a Binary Tree with specific constraints. Constraints exist on the value of a node with respect to it's children and on the shape of the tree. The heap property and the shape property determine whether a Binary Tree is really a Heap.
The Binary Heap may logically be a tree, however the most efficient way to implement it is using an array. Real pointers from parent to child and from child to parent become implicit relationships on the indices of the array.
Let's build a real heap in Java!
How do we ensure that when we add an element or remove an element from an existing heap, that the heap property and shape property is maintained? This operation is called Heapify.
Once we understand heapify, adding and removing elements from a heap become very simple.
Loonycorn is us, Janani Ravi, Vitthal Srinivasan, Swetha Kolalapudi and Navdeep Singh. Between the four of us, we have studied at Stanford, IIM Ahmedabad, the IITs and have spent years (decades, actually) working in tech, in the Bay Area, New York, Singapore and Bangalore.
Janani: 7 years at Google (New York, Singapore); Studied at Stanford; also worked at Flipkart and Microsoft
Vitthal: Also Google (Singapore) and studied at Stanford; Flipkart, Credit Suisse and INSEAD too
Swetha: Early Flipkart employee, IIM Ahmedabad and IIT Madras alum
Navdeep: longtime Flipkart employee too, and IIT Guwahati alum
We think we might have hit upon a neat way of teaching complicated tech courses in a funny, practical, engaging way, which is why we are so excited to be here on Udemy!
We hope you will try our offerings, and think you'll like them :-)