Data Structures & Algorithms: Coding Interview Masterclass

Data Structures and Algorithms : A data structure is way of organizing data in a computer so that it can be used efficiently.  In dictionary, words must be organized alphabetically then only we can able to find the word in a short time. Otherwise it’s not possible. Such a way in library, we should group the books based on the book type like technology, fiction or non-fiction like that then only we can able to find the book easily whatever we want.

Data Structures and Algorithms : Algorithm means, well defined procedure to implement something. There may be lots of way to implement the specific problem, but algorithms is efficient way to do that. 

Data structures and Algorithms : When we talk about best algorithms, best practice, or performance of the program is everything based on execution time for the program. An ultimate aim for every programmer is reduce the execution time of the program. Am I right? So when we will say that, this is the best algorithms for this process. So answer I simple. The algorithm which is gives the result in a short time in all the cases. That is a suitable algorithm for that process

Data Structures and Algorithms : There will often be trade-offs that we will need to identify and decide upon. As computer scientists, in addition to our ability to solve problems, we will also need to know and understand solution evaluation techniques. In the end, there are often many ways to solve a problem. Finding a solution and then deciding whether it is a good one are tasks that we will do over and over again 

Data Structures and Algorithms : In real time we might have lots of option while choosing an algorithm. Which mean for the single problem we will have lots of algorithms to solve the problem. Analysis the algorithm is help you to choose the right one. We will analysis the algorithm based on complexity of the program. So it’s very important to know how to calculate the complexity of the program.

Data Structures and Algorithms : Asymptotic Analysis is the great idea that handles these kind issues while analyzing algorithms. In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input size (which means we don’t measure the actual running time). We calculate, how does the time (or space) taken by an algorithm increases with the input size   

Data Structures and Algorithms : Whatever the number I am searching for and its is present in the last element of this array. Then it will be a worst case for this case.

 If an element is there in 1 st position of this list of values it will be the best case scenario. If its present in the middle, than it will be average case.

Data Structures and Algorithms : In this Video, you’ll be presented with the common rules of logarithms, also known as the “log rules”. 

Data Structures and Algorithms : In this video we are going to discuss about different levels of complexity in terms of Big O

When we talk about the code complexity, we will have different levels of complexity for the algorithms.

Data Structures and Algorithms : This video is quick wrap-up which you learnt in this unit.

Data Structures and Algorithms : This course is purely designed to focus on data structures and algorithms. I am strongly believing that, data structures and algorithm are not a technology. using correct data structures and writing efficient algorithm is a skill, So I am going to focus on to teach you how the apply this skill in Real time application which means how to apply this knowledge while choosing data structure in real application.

As an instructor, I should make you comfortable to understand the concept which is we are going to discuss in this course. So I need some programming language to explain the concepts     

Data Structures and Algorithms : Whenever we want to work with large number of data values, we need to use much number of different variables. As the number of variables are increasing, complexity of the program also increases and programmers get confused with the variable names. There may be situations in which we need to work with large number of similar data values. To make this work more easy, programming languages provides a concept called "Array" Data Structures. That’s what we are going to discuss in this lecturer in Data Structures and Algorithms course.

Data Structures and Algorithms : Its Implementation approach for 1D Array Implementation

Data Structures and Algorithms : All popular languages, like C/C++, Java or Perl start indexing an array from 0 while the last index is the array length minus 1. While this is usual to most developers, it is not a same fact for all programming languages. For example in Fortran, when you declare an array with 'integer a(10)', an int array having 10 elements, the index starts from 1 and ends at 10 (however you can override this behavior using a statement like, integer a(0:9), by declaring an array with indices from 0 to 9).   

Data Structures and Algorithms : In this video we are going to discuss about 2 DIMENSIONAL ARRAY

When we talk about 2D array, all the features from the 1D array applicable for 2 D array as well. The difference is, this array having 2 dimensional. To understand this, it’s better to think of the two-dimensional array as a matrix. A matrix can be thought of as a grid of numbers, arranged in rows and columns, kind of like a bingo board.

Data Structures and Algorithms :

Like array, Linked list is the another way to sore the data. So before we move to linked list in detail we first understand why linked list and what is the problem with array data structure.

Data Structures and Algorithms : Whatever we have discussed in last video. Its singly linked list. Which means in every node holding value and another node which means reference of next node.

Data Structures and Algorithms :

A Single linked list contains two parts within it right. One part is holding actual data and another part contains reference of next node. But, A Doubly Linked List (DLL) contains an extra pointer, typically we can call it as previous pointer

Data Structures and Algorithms : In ordinary Doubly Linked List requires space for two address fields to store the addresses of previous and next nodes. A memory efficient version of Doubly Linked List can be created using only one space for address field with every node. This memory efficient Doubly Linked List is called XOR Linked List. or Memory Efficient as the list uses bit-wise XOR operation to save space for one address. In the XOR linked list, instead of storing actual memory addresses, every node stores the XOR of addresses of previous and next nodes.

Data Structures and Algorithms : If you see the  Singly linked list and doubly liked list, Last node reference will point to null right. But in circular linked list, Last node reference will point to first node so that it will form a circle. Here you can start your iteration from anywhere you want. But in singly and doubly linked list you can start the iteration from Head node only. Which means 1st node

Data Structures and Algorithms : Its Implementation approach for  Linked List

Data Structures and Algorithms : Home work

Data Structures and Algorithms : Till now we have discussed about Array and Linked list and various form of array and linked list.

But when we should prefer linked list over array and when we should prefer array over linked list. Lets discuss this in this video.

Data Structures and Algorithms : Hash table is a data structure used to store a key-value pair. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the data that is the idea of hash table

Data Structures and Algorithms : Hashing is a technique used in Hash table to convert a range of key values into a range of indexes of an array. Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects. We're going to use modulo operator to get a range of key values.

Data Structures and Algorithms : Some times if you apply a hash function to two different keys its generate the same index number for both the keys. But both the element can’t go to the same place. This is known as collisions. And we have seen 2 different ways to handle collisions one is separate chaining and another one is open addressing.

Data Structures and Algorithms : This video is quick wrap-up which you learnt in this unit.

Data Structures and Algorithms : Stack is a simple data structure and its another option to storing data and stack is some what similar to Linked Lists. In a stack, the order in which the data arrives is important.   

Data Structures and Algorithms : When we use stack data structure to store the element, we can do basic operation like inserting element into the stack and remove the element from the stack. It’s basically PUSH and POP.     

Data Structures and Algorithms : Now we are going to see some real-world application for Stack data structure.

Data Structures and Algorithms : Its Implementation approach for Stack using Linked List

Data Structures and Algorithms : Its Implementation approach for Stack using Array

Data Structures and Algorithms : Queue is another data structure used to storing data and it is similar to Linked Lists and stack. In a queue, the order in which the data arrives is important. Let’s say for example, a queue is a line of people or things waiting to be served in sequential order starting at the beginning of the line or sequence. A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO)

Data Structures and Algorithms : When we use queue data structure to store the element, we can do basic operation like inserting element into the queue and remove the element from the queue. It’s basically ENQUEUE and DEQUEUE. These or the main operation in queue.

Data Structures and Algorithms : Here we are going to see some real-world application for Queue data structure.

Data Structures and Algorithms : Its Implementation approach for Queue Using Linked List

Data Structures and Algorithms : Its Implementation approach for Queue Using Array

Data Structures and Algorithms : In this video we are going to talk about priority queue. Priority queue is similar to queue and only difference is, while adding the element in to the priority queue data will add in sorted order. That’s it. That the only different between normal queue and priority queue. Other than this, everything is similar like enqueue, dequeue operations and basic feature of queue like the element which is inserted first the one will come out first. So everything will be similar to normal queue.

Data Structures and Algorithms : This is quick wrap-up for whatever we have covered in this Unit.

Data Structures and Algorithms : Tree is another type of data structure like linked list, Stack and Queue. But Tree is somewhat different from these data structure. Means Tree is the nonlinear data structure while linked list, Stack and Queue are linear data structure. Which means, In Linked list, Stack and queue node are simply pointing to next node means one node will point to another node. But in tree nodes are pointing no many number of nodes. these nodes are leaf of the tree   

Data Structures and Algorithms : Further we will discuss about binary tree which is derived from Tree. We can say like if tree met certain condition which is applicable for Binary tree that’s called Binary tree.

 So The things we were discussed about root node, children, height and depth are applicable for binary tree also.

Data Structures and Algorithms : Binary Search Tree is another variant of Binary Tree. In the binary tree we haven’t any restriction for node data. So, if you want to search any node data from binary tree, you have to search both left sub tree and right sub tree. Means we have to visit each and every node of the tree. So, complexity will be O(n) in worst case. That’s why we came for Binary search tree. The main use of binary search tree is Search. It has the restriction for node data’s while storing it into the binary search tree. So, it will simplify the complexity of search operation in Tree. As a result, it reduces the worst case complexity to O(logn).

Data Structures and Algorithms : Its Implementation approach for BST

Its Implementation approach for BST Insert

Its Implementation approach for BST Delete 

Data Structures and Algorithms : Based on the order on which node is visited, tree traversal algorithms are classified into two category.

• Breadth First Search (B F S)

• Depth First Search   (D F S)

Data Structures and Algorithms : Here we will start with Breadth First Search. In the name itself saying that, we have to visit the nodes based on Breadth of the tree. Or simply we can say like search horizontally. And In Breadth first search we have to prioritize the node by visiting all node on the same level before we move down to child node.     

Data Structures and Algorithms : Its Implementation approach for Breadth First Search

Data Structures and Algorithms : In Breadth first search approach for any node, we visit all its children before visiting any of its grand children.     But in Depth first approach, if we would like to go child of any node. We have to complete full left subtree of that node before we move to right child node.           

Data Structures and Algorithms : If we go over pre order traversal, we have to visit root node first and than left node and than right node.

Data Structures and Algorithms : If we go over In order traversal, we have to visit left node first and then root node and than right node. Ok now we will travel through this tree.

Data Structures and Algorithms : If we go over post order traversal, we have to visit left node first and then right node and than root node. Ok now we will travel through this tree.

Data Structures and Algorithms : Its Implementation approach for Depth First Search

Data Structures and Algorithms : This is quick wrap-up for whatever we have covered in this Unit.

Data Structures and Algorithms : Graph is pair of node and connections. I will just draw some circles. I will call it as A, B and C. These circles are nodes. And these nodes are connected with line and we can call this as connection. Its just a connection between the nodes. We will refer this nodes are vertices and we will refer this connection as edges. This is the graph. So Basically A Graph consists of a finite set of vertices and set of Edges which connect a pair of nodes. And A Graph is a non-linear data structure like tree.

Data Structures and Algorithms : So coming to type of graph, there are two kind of graph, i.e

• Direct/Undirected Graph

• Weighted/Un Weighted Graph

Till now what we have discussed and what the example we have used to discuss about the graph is Un directed and un weighted graph. Means we haven’t use any direction when we represent edges and we haven’t given any number to the edges to associate with. I mean weight.

Data Structures and Algorithms : First one is Social Network. Lets take Facebook. In face book we are connected with friends right. How face book handles this connection between you and your friends. And how face book finds the mutual friend details to you when you look at some of your friends profile? Think about what data structure face book might have use for this ? Its Graph.

Data Structures and Algorithms : If we search this in internet, mostly people are talking about the two ways to represent the graph data structure.

• Adjacency Matrix

• Adjacency List

Its hard to represent the graph data structure other than these two ways why because, we can expect one node may connected with more number nodes.  

Data Structures and Algorithms : Matrix the one way to represent Graph data structure in another hand List is another way to do the same Job. So which one is better. Here will compare both the things based on certain factor like accessing node and accessing child node and memory.

Data Structures and Algorithms : Its Implementation approach for Graph

Data Structures and Algorithms : Based on the order on which node is visited, graph traversal algorithms are classified into two category.  

• Breadth First Search (B F S)

• Depth First Search   (D F S)

Data Structures and Algorithms : Its Implementation approach for Graph Traversal

Data Structures and Algorithms : This is quick wrap-up for whatever we have covered in this Unit.