# Data Structures and Algorithms using Python

A 3 month course which includes content that will help you learn everything you need to know about Data Structures and Algorithms.

• Domain : CSE ### A Quick Overview

A data structure is a named location that can be used to store and organize data. An algorithm is a collection of steps to solve a particular problem. Learning data structures and algorithms allows us to write efficient and optimized computer programs. Data structures provide a means to manage large amounts of data efficiently for uses such as storing and analyzing data from autonomous vehicles' sensors. Any programmer knows that Data-Structures and Algorithms are the building blocks of any well-designed piece of software. Students generally are very good at understanding the textbook definitions of Stack, Heap, or Linked-lists. However, when you put them in practice, that is when you start seeing gaps in the student's understanding. By learning this module from SKILL-LYNC, we will

• Help you clock in 200+ hours of coding for a wide range of problems
• Teach you how scalable programs are built
• Expose you to what top tech companies expect from programmers

# GET COURSE COUNSELLING TODAY

Get a 1-on-1 demo to understand what is included in the course and how it can benefit you from an experienced sales consultant. The demo session will help you enroll in this course with a clear vision and confidence. ### COURSE SYLLABUS

#### 1Introduction

i. Abstract data type and Data Structure
ii. Complexity Analysis

• Asymptotic analysis
• Comparison of functions
• Recurrence Relations
• Time complexity
• Space complexity

iii. Iteration
iv. Recursion c. Assignment

#### 2Lists

• Arrays
• Static arrays
• Dynamic arrays
• 2D arrays
• Strings
• Singly Linked List and its operations
• Doubly Linked List and its operations
• Circular Linked List and its operations #### 3Stacks and Queues

• Stacks
• Implementations- using arrays, using linked lists
• Operations
• Applications
• Queues
• Implementations- using arrays, using linked list, using two stacks
• Circular queues
• Priority queues
• Amortized Analysis
• Stacks and Queues in Python  #### 4Trees

• Trees
• Binary Trees: representations.
• Pre-order, In-order, Post-order traversals
• Expression trees
• Successor and Predecessor
• Binary Search Trees and their operations
• AVL Trees and their operations
• Red Black trees, Interval trees, Segment trees, B-trees, B+ trees #### 5 Heaps and Tries

• Heaps
• Min Heap
• Max Heap
• Implementation
• Operations
• Priority Queues
• Implementations
• Uses
• Tries
• Implementations
• Uses #### 6Graphs

• Graphs
• Representation
• Implementation
• Types of Graphs
• Minimum cost spanning tree problem
• Traversing Graph
• Depth First Search
• Single Source Shortest path problem
• Dijkstra's algorithm
• Bellman–Ford algorithm
• Disjoint Sets
• Union by rank
• Path compression
• Applications

#### 7Sorting

• Sorting
• Types of sorting techniques
• Bubble Sort
• Insertion Sort
• Selection Sort
• Quick Sort
• Merge Sort
• Heap Sort
• Count Sort
• Bucket Sort
• Shell Sort
• Topological Sort #### 8Searching and Hashing

•  Searching
• Linear Search
• Binary Search
• Hashing
• Hash function
• Collision handling
• Chaining
• Linear probing, primary clustering
• Double hashing
• Hash Tables
• Collection Module in Python #### 9 Greedy Algorithms

• Optimisation Problems
• Types of algorithms
• Greedy Algorithms
• Strategy of Greedy Algorithms
• Elements of Greedy Algorithms
• Applications of Greedy Algorithms #### 10Divide and Conquer

• Divide and Conquer Techniques
• Strategy of Divide and Conquer Techniques
• Advantages of Divide and Conquer Techniques
• Disadvantages of Divide and Conquer Techniques
• Master theorem of Divide and Conquer Techniques
• Applications of Divide and Conquer Techniques
• Special types of problems
• Bit Manipulation problems
• Two pointer problems
• Sliding Window problems
• Merge Intervals problems #### 11Backtracking

• Backtracking
• Brute Force Approach
• N Queens Problem
• String matching Algorithms
• Brute Force Method
• KMP
• Rabin Karp
• Data Structures for storing strings #### 12Dynamic Programming

• Dynamic Programming
1. Approaches of Dynamic Programming
2. Top down approach
3. Bottom up approach
4. Properties of Dynamic Programming
• Comparison of Algorithmic Techniques learnt
• Regular Expressions
• Pattern matching algorithm
• Complexity Classes
• P, NP, NP Hard, NP Complete
• Is P==NP?
• Problem Solving Summary  ### Extensive assignments on thorough usage of DSA concepts

Learn Data Structures and Algorithms using Python:

Arrays

Equilibrium point  String

Reverse words in a given string:

• Given a String of length S, reverse the whole string without reversing the individual words in it. Words are separated by dots.
• Complete the function which takes a string S containing characters and outputs a single line containing the reversed String.
• Constraints:
1 <= T <= 100
1 <= |S| <= 2000

 Argument Print i.like.this.program.very.much much.very.program.this.like.i pqr.mno mno.pqr

Remove Duplicates

• Given a string, the task is to remove duplicates from it. Expected time complexity O(n) where n is length of input string and extra space O(1) under the assumption that there are total 256 possible characters in a string. Original order of characters must be kept same.
• Complete the function that takes a string and prints the modified string without duplicates and same order of characters.
• Constraints:
1 <= |string|<= 1000

 Argument Print skilllync skilync Skill lync courses Skil ync oure

Finding middle element in a linked list

• Given a singly linked list of N nodes. The task is to find the middle of the linked list. For example, if given linked list is 1->2->3->4->5 then the output should be 3.
If there are even nodes, then there would be two middle nodes, we need to print the second middle element. For example, if given linked list is 1->2->3->4->5->6 then the output should be 4.
• The task is to complete the function getMiddle() which takes the list reference and returns data of the middle element of the linked list.
• Expected Time Complexity: O(N).
Expected Space Complexity: O(1).
• Constraints:
1 <= T <= 500
1 <= N <= 5000

 Argument Return 1 2 3 4 5 3 2 4 6 7 5 1 7 Pairwise swap elements of a linked list • Given two numbers represented by two linked lists of size N and M. The task is to return a sum list. The sum list is a linked list representation of the addition of two input numbers.
• Complete the function addTwoLists() which takes both the linked lists and returns the new list.
• Expected Time Complexity: O(N) + O(M)
Expected Auxiliary Space: O(N) + O(M)
• Constraints:
1 <= N, M <= 5000

 Argument Return (4,5) & (3,4,5) (3 9 0) (6,3) & (7) (7 0)

Trees

Binary Tree to DLL

• Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. The left and right references in nodes are to be used as previous and next references respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL.
• Complete the function bToDLL() that takes root node of the tree as a parameter and returns the head of DLL .
• Expected Time Complexity: O(N).
Expected Space Complexity : O(H). H is the height of the tree and this space is used implicitly for recursion stack.
• Constraints:
1 <= Number of nodes <= 1000
1 <= Data of a node <= 1000 Graph

Bellman Ford Algorithm

• Implement the Bellman Ford Algorithm to find Shortest paths to all vertices from a single source.
• Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges.
• If there is a negative weight cycle then print -1
• Expected Time Complexity- O(VE)

Minimum Swaps to Sort

• Given an array of integers. Find the minimum number of swaps required to sort the array in non-decreasing order.
• complete the function minSwaps() which takes the array arr[] and prints the minimum number of swaps required to sort the array. If the array is already sorted, return 0.
• Constraints:
1 <= size of A <= 105
1 <= A[] <= 106
• Expected Time Complexity: O(NlogN).
Expected Space Complexity : O(N).
 Argument print 1 5 4 3 2 2 8 9 16 15 1

Stacks Queues

Get minimum element from stack

• You are given N elements and your task is to Implement a Stack in which you can get minimum element in O(1) time.
• Complete the three methods push() which take one argument an integer 'x' to be pushed into the stack, pop() which returns a integer popped out from the stack and getMin() which returns the min element from the stack. (-1 will be returned if for pop() and getMin() the stack is empty.)
• Expected Time Complexity : O(1) for all the 3 methods.
Expected Space  Complexity : O(1) for all the 3 methods.
• Constraints:
1 <= Number of queries <= 100
1 <= values of the stack <= 100

 command Print push(2) push(3) pop() getMin() push(1) getMin() 321 ### Project 2

A set of 20 problems to solve in an optimised way with the given restrictions of time and space complexity

Arrays and Strings

Subarray with given sum

• Given an unsorted array A of size N of non-negative integers, find a continuous sub-array which adds to a given number S.
• Implement a method subArraySum(a[], s), where A is array of size n and s is the sum.
• And return the starting and ending positions (0 indexing) of FIRST such occurring subarray from the left if sum equals to subarray, else print -1.
• Code knowing that-

1 <= N <= 107
1 <= Ai <= 1010

 Arguments print 1 2 3 7 5, 12 1 3 1 2 3 4 5 6 7 8 9 10, 15 0 4

Permutations of a given string

• Given a string S. The task is to print all permutations of a given string. Implement perm(s) method where s is a string in capital letter. Print all permutations of a given string S with single space and all permutations should be in lexicographically increasing order.
• Constraints:
1 ≤ size of string ≤ 5

 Argument String Output display ABC ABC ACB BAC BCA CAB CBA ABSG ABGS ABSG AGBS AGSB ASBG ASGB BAGS BASG BGAS BGSA BSAG BSGA GABS GASB GBAS GBSA GSAB GSBA SABG SAGB SBAG SBGA SGAB SGBA

Trees

Determine if Two Trees are Identical Count Leaves in Binary Tree

• Given a Binary Tree of size N , You have to count leaves in it. For example, there are two leaves in following tree
•         1
/      \
10      39
/
5
• Argument is a string representing the tree as described below:
• The values in the string are in the order of level order traversal of the tree where, numbers denote node values, and a character “N” denotes NULL child.
• For example:  Count Leaves in Binary Tree

1. For the above tree, the string will be: 5 2 3 1 N 7 4 N 8 N 6 N N
• Complete the function countLeaves() that takes the tree string as parameter and returns the count of leaves in tree.
Constraints:
1<= N <= 104

 Argument value Return value 3 4 2 2 4 8 10 7 N 5 1 3 3

Lowest Common Ancestor in a Binary Tree

• Given a Binary Tree with all unique values and two nodes value n1 and n2. The task is to find the lowest common ancestor of the given two nodes. We may assume that either both n1 and n2 are present in the tree or none of them is present.
• Complete the function lca() that takes nodes, n1, and n2 as parameters and returns LCA node as output.
• Expected Time Complexity: O(N).
Expected Space Complexity : O(H).
H is the height of the tree.
• Constraints:
1 <= Number of nodes <= 100
1 <= Data of a node <= 1000

Sorting

Linked list of 0s, 1s and 2s, sort it.

• Given a linked list of N nodes where nodes can contain values 0s, 1s, and 2s only. The task is to segregate 0s, 1s, and 2s linked list such that all zeros segregate to head side, 2s at the end of the linked list, and 1s in the mid of 0s and 2s.
• complete the function segregate() which segregates the nodes in the linked list as asked in the problem statement and returns the head of the modified linked list. The printing is done automatically by the driver code.
• Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
• Constraints:
1 <= N <= 103

 Arguments Print 1 2 2 1 2 0 2 2 0 1 1 2 2 2 2 2

Searching

Find first repeated character

• Given a string S. The task is to find the first repeated character in it. We need to find the character that occurs more than once and whose index of second occurrence is smallest. S contains only lowercase letters.
Argument is a string S.
• print the first repeating character in the string. If no such character exist print -1.
• Constraints:
1 <= |S| <=104

 Argument Return Skilllync l helloWorld l

Check if two arrays are equal or not

• Complete the function which takes two arrays A and B of equal size. Find if given arrays are equal or not. Two arrays are said to be equal if both of them contain same set of elements, arrangements (or permutation) of elements may be different though. If there are repetitions, then counts of repeated elements must also be same for two array to be equal.
• Print 1 if the arrays are equal else print 0.

• Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
• Constraints:
1 <= N <= 107
1 <= A[],B[] <= 1018

 Argument Return 1 2 5 4 0, 2 4 5 0 1 1 1 2 5, 2 4 15 0

Hashing

Relative Sorting

• Given two arrays A1[] and A2[] of size N and M respectively. The task is to sort A1 in such a way that the relative order among the elements will be same as those in A2. For the elements not present in A2, append them at last in sorted order. It is also given that the number of elements in A2[] are smaller than or equal to number of elements in A1[] and A2[] has all distinct elements.
Expected time complexity is O(N log(N)).
• Length of arrays N and M and next two line contains N and M elements respectively.
• Output:
Print the relatively sorted array.
• Constraints:
1 ≤ A1[], A2[] <= 106

 Arguments Print 2 1 2 5 7 1 9 3 6 8 8, 2 1 8 3 2 2 1 1 8 8 3 5 6 7 9 2 6 7 5 2 6 8 4, 2 6 4 5 2 2 6 6 4 5 7 8

Graph

Shortest Source to Destination Path

• Given a boolean 2D matrix (0-based index), find whether there is path from (0,0) to (x,y) and if there is one path, print the minimum no of steps needed to reach it, else print -1 if the destination is not reachable. You may move in only four direction ie up, down, left and right. The path can only be created out of a cell if its value is 1.
• Complete the function for implementing this. Arguments are two integers n and m denoting the size of the matrix, an n*m matrix and two integers x and y denoting the index of the destination. Print the min no of steps needed to reach the destination.

Constraints:
1<=n,m<=20

 Arguments Print 3 4, 1 0 0 0 1 1 0 1 0 1 1 1, 2 3 5 3 4, 1 1 1 1 0 0 0 1 0 0 0 1, 0 3 3

Minimum Cost Path Circle of strings

• Given an array of strings A[], determine if the strings can be chained together to form a circle. A string X can be chained together with another string Y if the last character of X is same as first character of Y. If every string of the array can be chained, it will form a circle.
• For eg for the array arr[] = {“great", “skill", “trains", “lync"} the answer will be Yes as the given strings can be chained as “great", “trains", “skill" and “lync"
• Input: array A[].
• Output: If chain can be formed, then print 1, else print 0.
• Constraints
0 <= size of A <= 30
0 <= A[i] <= 10

 Arguments Print abc bcd cdf 0 ab bc cd da 1

Stacks queues

First non-repeating character in a stream

• Given an input stream of N characters consisting only of lower case alphabets. The task is to find the first non repeating character, each time a character is inserted to the stream. If no non repeating element is found print -1.
• Argument is x character array which are inserted to the stream.
• Output:
For each test case in a new line print the first non repeating elements separated by spaces present in the stream at every instinct when a character is added to the stream, if no such element is present print -1.
• Constraints:
1 <= N <= 500

 Arguments Print a a b c a -1 b b a a c a -1 c

Heap

Rearrange characters Dynamic programming

Longest Common Subsequence

• Given two strings: string X of length m and string Y of length n find the longest common subsequence-
• The longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.
• For example, if X = “ABCBDAB” and Y = “BDCABA”, the LCS(X, Y) = {“BCBA”, “BDAB”, “BCAB”}.

Maximum sum of increasing subsequences Count number of hops

• A frog jumps either 1, 2 or 3 steps to go to top. In how many ways can it reach the top.
• Complete the function which takes input N denoting the total number of steps and prints the number of ways to reach the top.
• Constraints:
1 ≤ N ≤ 50

 Arguments Print 1 1 5 13

Greedy

N meetings in one room

• There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i]) where S[i] is start time of meeting i and F[i] is finish time of meeting i.
• What is the maximum number of meetings that can be accommodated in the meeting room?
• Complete the function which takes the array containing the starting time of all the meetings S [ i ] and the array containing the finishing time of all the meetings F [ i ].
• Print the order in which the meetings take place separated by a space.
• Constraints:
1 ≤ N ≤ 100
1 ≤ S[ i ], F[ i ] ≤ 100000

 Argument Print 1 3 0 5 8 5, 2 4 6 7 9 9 1 2 4 5

Minimise the sum of product

• You are given two arrays, A and B, of equal size N. The task is to find the minimum value of A * B + A * B +…+ A[N-1] * B[N-1], where shuffling of elements of arrays A and B is allowed.

• Argument is the array A[] and array B[] and print the minimum sum.
• Constraints:
1 <= Size of Arrays <= 107
1 <= A[], B[] <= 1018

 Argument return 3 1 1, 6 5 4 23 6 1 9 5 4, 3 4 8 2 4 80

Largest number possible

Given two numbers 'N' and 'S' , find the largest number that can be formed with 'N' digits and whose sum of digits should be equals to 'S'.

• Input: integers N and S, where N is the number of digits and S is the sum.
• Print the largest number that is possible. If their is no such number, then print -1
• Constraints:
1 <= N <= 50
0 <= S <= 500
• Expected Time Complexity: O(n)

 Arguments Print 2 9 90 3 20 992

Divide and conquer

Find the element that appears once in sorted array

• Given a sorted array A, size N, of integers; every element appears twice except for one. Find that element that appears once in array.
• Input the array.
• Print the number that appears only once in the array.
• Constraints:
1 ≤ N ≤ 107
0 ≤ A[i] ≤ 1017

 Arguments Print 1 1 2 2 3 3 4 50 50 65 65 4

Two pointer & sliding window

Longest Distinct characters in string

• Given a string S, find length of the longest substring with all distinct characters.  For example, for input "abca", the output is 3 as "abc" is the longest substring with all distinct characters.
• Input: String s.
• Print length of smallest substring with maximum number of distinct characters.
Constraints:
1 ≤ size of str ≤ 10000

 Arguments Print abababcdefababcdab 6

Smallest window in a string containing all the characters of another string

• Given a string S and text T. Output the smallest window in the string S having all characters of the text T. Both the string S and text T contains lowercase english alphabets.
• Input: a string S and text T.
• Output the smallest window of the string containing all the characters of the text. If such window doesn`t exist or this task can not be done then print -1.
• Constraints:
1 <= |N|, |X| <= 1000

 Arguments Print Timetopractice, toc toprac zoomlazapzo, oza apzo

Bit Manipulation

Power of 2

• Given a positive integer N. The task is to check if N is a power of 2. That is N is 2x for some x.
• Input: a single positive integer N.
• Output: Print YES if it is a power of 2 else NO
• Constraints:
1 <= T <= 100
0 <= N <= 1018

 Arguments Print 1 Yes 98 No

# Flexible Course Fees

Choose the plan that’s right for you

Basic

2 Months Access

# \$92.89

Per month for 3 months

• Access Duration : 2 Months
• Mode of Delivery : Online
• Project Portfolio : Available
• Certification : Available
• Email Support : Available
• Forum Support : Available

# \$199.05

Per month for 3 months

• Mode of Delivery : Online
• Project Portfolio : Available
• Certification : Available
• Individual Video Support : 12/ Month
• Group Video Support : 12/ Month
• Email Support : Available
• Forum Support : Available
• Telephone Support : Available
• Dedicated Support Engineer : Available ### WHO IS THIS COURSE FOR ?

• Any Student or Professional willing to develop optimally working software.

## SOFTWARE COVERED

##### PyCharm Community Edition

A data structure is a named location that can be used to store and organize data. An algorithm is a collection of steps to solve a particular problem. Learning data structures and algorithms allows us to write efficient and optimized computer programs. Data structures provide a means to manage large amounts of data efficiently for uses such as storing and analyzing data from autonomous vehicles' sensors. We will be using the Python language to code and solve difficult algorithmic problems. Python is a very easy-to-learn language with great community support and libraries available for use. PyCharm is a versatile and popular IDE using which writing python programs becomes very easy and efficient. There is no need for a licensed language to start learning and implementing programming and problem solving using Data Structures and Algorithms. ### Testimonials

Companies hire from us

See all ### Certification

• Top 5% of the class will get a merit certificate
• Course completion certificates will be provided to all students
• Build a professional portfolio
• E-verified profile that can be shared on LinkedIn  ### SKILL LYNC WORKS TO GET YOU A JOB

See all #### 1Who can take your course?

Any Student or Professional willing to develop optimally working software. This course is designed to help a new developer explore the theory (the science behind everything), the practical (what to do and how to do?), and the bonus (Understanding existing code to optimise it). A prerequisite for this course is basic understanding of the Python programming Language.

#### 2What is included in your course?

This course is a step-by-step description of the Basic and Advanced topics of Data Structures and Algorithms along with code implementation and problem solving sessions. It has 12 small exercises and 2 major exercises to mark course completion.

#### 3What will the student gain from your course?

A complete and thorough understanding of Data Structures and Algorithms. Students will gain confidence in each of the topics with problem solving skills, and understanding real world implications of the algorithms. Upon completion of this course, students will feel comfortable solving code challenges optimally.

#### 4What software skills are you teaching and how well are these tools used in the industry?

Storing data in relevant structures to solve a particular problem and selecting relevant algorithm to solve it is being taught. This is an essential part of showcasing problem solving and analytical skills specially for autonomous vehicles specialised software engineering job interviews.

#### 5What real world application for the tools and techniques will you teach in this course?

All real-world software needs an understanding of data structures and algorithms for building and refactoring. The server-side manipulation of data and implementation of optimised business logic depends on this understanding. Gaining such analytical skills is what we are aiming at.

#### 6Which companies use these techniques and for what?

All companies creating software use these skills, especially for implementing scalable and fast software which holds the most importance for any real time application like autonomous vehicles.

#### 7How is your course going to help me in my path to MS or PhD?

Data structures and Algorithms is one of the most important topics in Computer Science and Allied fields. Many research topics require a program to be coded with the most optimised algorithm for implementing the solution of the research, to demonstrate its results. A good understanding of Data Structures and Algorithms and their code is required for this. Hence, clearing this course in exams and using it for coding a research strategy is essential.

#### 8How is this course going to help me get a job?

As mentioned, this course will help in developing the necessary problem-solving coding skills, for cracking coding interviews of all companies.

#### 9What is the ratio of theory to hands-on practical content?

40% of the course teaches theoretical concepts and 60% of it is coding and handling problems in the most optimised ways. Practising is focused on, without which no skill is learnt best. 