Logicmojo
Learn Data Structure, Algorithms and SystemDesign From Scratch
Course Content 100 lectures22:25:0

Course Information Preview01:14

This course explains all the deep concepts of Data structure and Algorithms with the help of problems. These problems are frequently asked during interviews. System Design problems also explains with all core components of distributed system.

Segregation logic to Sort an array of 0's, 1's and 2's  12:27

Given an array consisting only 0's, 1's and 2's. Write a program to sort  this array in O(n) time complexity with only one traversal ~~~~ Asked in : Amazon, Microsoft, Adobe, WalmartLabs

Linear time approach to solve jump game problem 08:41

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a program to find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through that element. ~~~~ Asked in: Adobe, Intuit

Digit rearrangement method to find next greater number with same set of digits 12:23

You have given a number. You have to find out next greater number to given number with the same set of digits ~~~~Asked in : Morgon Stanley, Makemystrip, Amazon

Rectangle Overlap problem 11:16

A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its bottom-left corner, and (x2, y2) are the coordinates of its top-right corner. Like above two rectangle given with there respective coordinates. Find if these rectangle overlap or not. ~~~~Asked in: GoldmanSachs, Expedia, OLA

Greedy Techniques to find minimum number of platforms 11:4

You are given arrival and departure time of trains reaching to a particular station. Write a program to find minimum number of platforms required to accommodate the trains at any point of time ~~~~ Asked-in: DE-Shaw, Paytm, Cisco

Techniques to print matrix in spiral order without any extra space 12:31

you are given a matrix of m x n elements (m rows, n columns), Write a Program to print all elements of the matrix in spiral order ~~~~Asked in: Microsoft, OLA, PayTm, Oracle

Count frequencies of array elements in O(n) time complexity 18:5

Given an unsorted array of integers whose each element lies in range of 0 to n-1 where n is the size of the array, Calculate the frequency of all the elements present in the array in O(n) time and constant space ~~~~Askedin: PayTm, VmWare, Amazon

Linear time approach to solve Stock Buy Sell Problem 15:14

You are given an array represents cost of a stock on each day. You are allowed to buy and sell the stock only once.  Write an program to maximize the profit in single buy and sell ~~~~ Asked in: Amazon, Microsoft, Flipkart, DE-Shaw

In-place techniques matrix rotation method by 90 degree 12:20

You are given a square matrix, Write a Program to turn it by 90 degrees in anti-clockwise direction without using any extra space ~~~~ Asked in : Facebook, Google, Amazon, Microsoft

Array puzzle of solving celebrity problem 08:59

There are ( N+1 ) people in a party, they might or might not know each others names. ?There is one celebrity in the group (total N + 1 people), celebrity does not know any of N peoples by name and all N people know celebrity by name. You are given the list of people’s names (N + 1), You can ask only one question from the people. Do you know this name? How many maximum number of questions you need to ask to know the celebrity name? ~~~~Asked in: Google, Flipkart, Amazon, Microsoft

Lexicographical order method to solve next permutation problem 17:30

Implement the next permutation, which rearranges numbers into the numerically next greater permutation of numbers. If such arrangement is not possible, it must be rearranged as the lowest possible order ie, sorted in an ascending order. The replacement must be in-place, do not allocate extra memory ~~~~Asked in: Microsoft, Morgon Stanley, Samsung, Intuit

QuickSelect Algorithm to find the Kth smallest Element in array - 1 10:47

Given an array of integers which is non sorted, find kth smallest element in that array ~~~~ Vmware, SapLabs, WalmartLabs

Xor method to find the element that occurs one 04:8

Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space ~~~~Asked in : Flipkart, Amazon, PayTm

Binary search method to find square root of an element 05:35

Given an integer x, find square root of x without sqrt() function ~~~~Asked in : Accolite, Qualcomm

Rain Trapping Problem 09:52

you are given positive integers in the form of array which represent an elevation map where the width of each bar is 1, Write a Program to compute how much water it is able to trap after raining ~~~~ Asked in : Microsoft, DE-Shaw, Amazon, Adobe

Merge sort method to Count inversion in an array 12:26

Given an unsorted Array, Write a Program to find the count of Inversion required to make this array sorted. [The inversions of an array indicate; how many changes are required to convert the array into its sorted form ~~~~Asked in : Google, Microsoft

Binary search method to find Median of two sorted Array 20:19

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)) ~~~~ Asked in: Intuit, Adobe

Design a data Structure which support Insert delete, Random in O(1) time Preview19:13

Design a data structure which performs the following operations(Insert an element/Remove an element /find random element) in O(1) time complexity ~~~~ Asked in : Google, Facebook, Amazon

System Design Problems Discussion 17 lectures 4:38:37

Design Facebook's Newsfeed, which would contain posts, photos, videos, and status updates from all the people ~~~~ Asked in: Amazon

Design Tiny URL 15:15

Design a URL shortening service like TinyURL. This service will provide short aliases for all long URLs ~~~~ Asked in : Flipkart, Facebook, Goldman Sach,

Design a video sharing service like Youtube. User can upload,search and view the videos

Design BookMyShow 20:30

Design an online movie ticket booking system like : bookmyshow.com ~~~~Asked in : Amazon,Uber

Design Uber 19:33

Design a ride sharing system like Uber

System design component: Sharding techniques 12:16

Understanding the sharding techniques used in Distributed System. Sharding is technique to break up a big database (DB) into many smaller parts. For understanding scalable architecture, sharding is mandatory to understand

Backend System techniques for distributed system : SQl/NoSQL 13:39

Understanding of scalable architecture of DB. This section explains the relational databases and non-relational databases and CAP theoram used in distributed system

Design WhatsApp Chat Service 19:36

Design an instant messaging service like Whatsapp and Facebook Messenger where a user can send the instant message to other user through mobile ~~~Asked in : SapLabs, Facebook

Design Generic Deck of Cards Preview08:38

Design the data structures for a generic deck of cards by using objected orinted princial ~~~~ Asked in : OLA, Juniper Networks

Design parking Lot 13:32

Design a parking lot System using object-oriented principles ~~~~Asked in : Cisco, Flipkart, Oracle

Design Online Hotel Booking System 11:54

Design online hotel booking system Like : makemytrip.com, agoda.com ~~~~ Asked in : Makemytrip, Booking.com, Expedia

Design a file hosting service like Dropbox or Google Drive ~~~~ Asked in : NetApp, Cisco

Design Hit Counter 20:19

Design a hit counter which counts the number of hits received in the past 5 minutes. Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (i.e. the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1 ~~~~ Asked in : Microsoft, Amazon, OLA

Design Customs HashMap Implementation Internals - 1 Preview17:24

Design custom implementation hashmap, how hashmap works internally in Java

Depth-first search method to find cycle in a graph 13:55

Consider a undirected graph without loops and multiple edges. We have to check whether it is acyclic, and if it is not, then find any cycle ~~~~Asked in : Adobe, MakemyTrip, Intuit

Topological sorting concepts and implementation 16:18

For a directed acyclic graph (DAG), a topological ordering is a linear ordering of its vertices such that for every directed edge from vertex  to vertex  (i.e., edge ),  u is listed before v. problem based on similar concept : There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? ~~~~Asked in : Accolite, Flipkart

Breadth first search algorithm to find Number of IsLand in matrix 14:35

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water ~~~~Asked in : Citrix, Informatica, Expedia

Dijkstra Algorithm explanation with example 19:5

Dijkstra's algorithm allows us to find the shortest path between any two vertices of a graph ~~~~ Asked in : Google, Uber, Facebook

Topological Algorithm to solve alien dictionary problem 12:15

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language ~~~~Asked in : Google, WalmartLabs, Adobe

Breadth first search algorithm to solve Rotten Orange Problem 18:14

Given a matrix of dimension m*n where each cell in the matrix can have values 0, 1 or 2 0: Empty cell 1: Cells have fresh oranges 2: Cells have rotten oranges we have to determine what is the minimum time required so that all the oranges become rotten ~~~~ Asked in : Microsoft, Amazon, Expedia

Trie data structure approach to solve word boggle Problem 11:58

Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell

Given a snake and ladder board, find the minimum number of dice throws required to reach the destination or last cell from source cell ~~~~ Asked in : Amazon, Flipkart

Understanding Queue based approach to Jumping Number problem 11:42

A number is called as a Jumping Number if all adjacent digits in it differ by 1. The difference between ‘9’ and ‘0’ is not considered as 1. Given a positive number x, print all Jumping Numbers smaller than or equal to x ~~~~Asked in : Morgan Stanley, OLA, NetApp

Trie data Structure implementation Preview15:9

Trie is the data structure very similar to Binary Tree. Trie data structure stores the data in particular fashion, so that retrieval of data became much faster and helps in performance

Trie data structure approach to solve type head suggestion problem 16:9

Design the autocomplete feature for example : Google search auto suggestion ~~~~ Asked in : Google, Apple

Longest Common Subsequences 11:8

Given two sequences, print all the possible longest common subsequence present in them. Let X be “XMJYAUZ” and Y be “MZJAWXU” then output is ~~~~ Asked in : Linkedin, PayPal

Edit Distance Problem 13:38

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: 1. Insert a character 2. Delete a character 3. Replace a character ~~~~Asked in : Amazon, Microsoft, Myntra

Coin Change Problem 11:50

Given an unlimited supply of coins of given denominations, find the total number of distinct ways to get a desired change ~~~~ Asked in : Morgan Stanley, Microsoft, PayTm

Longest Palindrome Subsequences 10:9

The Longest Palindromic Subsequence (LPS) problem is the problem of finding the longest subsequences of a string that is also a palindrome ~~~~Asked in : Linkedin, Uber, Paypal

Word Break Problem 13:5

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words ~~~~Asked in : Google, WalmartLabs, IBM

Egg Dropping Problem 09:27

There are n number of eggs and building which has k floors. Write an algorithm to find the minimum number of drops is required to know the floor from which if egg is dropped, it will break ~~~~Asked in : Intuit, Amazon

KnapSack Problems 17:45

Given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W ~~~~Asked in : Amazon, Google

Keystroke Problem 10:58

we have a specially made keyboard which has following four keys 1. This key prints character 'A' 2. (Ctrl-A) 3. (Ctrl-C) 4. (Ctrl-V) If you are allowed to press keys of this special keyboard N times, write a program which calculates maximum numbers of A's possible ~~~~Asked in : Google, Adobe, NetApp

String interleave Problem 13:52

Given three strings A, B and C. Write a function that checks whether C is an interleaving of A and B. C is said to be interleaving A and B, if it contains all characters of A and B and order of all characters in individual strings is preserved ~~~~Asked in : Yahoo, Yatra

Partition Problem 15:41

Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same ~~~~Asked in : Amazon, Microsoft

Wild Card Problem 20:39

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string. ~~~~Asked in : InMobi, OLA, Cisco

Matrix Path Problem 07:47

Given a cost matrix matrix[][] and a position (m, n) in matrix[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). Each cell of the matrix represents a cost to traverse through that cell ~~~~Asked in : Amazon, Facebook

Climbing Stairs Problem 08:15

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top ~~~~Asked in : Morgan Stanley, Accolite, Samsung

N Queen Problem 07:14

In chess, a queen can move as far as she places horizontally, vertically, or diagonally. A chess board has 8 rows and 8 columns.  The problem is to how to place 8 queens in an ordinary chess board so that none of them can hit any other in one move ~~~~Asked in : Accolite, Oracle, VISA

Sudoku Solving Problem - 1 12:20

Given a sudoko puzzle, solve this sudoko puzzle by using backtracking algorithm ~~~~Asked in : Microsoft, Amazon, Flipkart, Oracle

Print all Permutations of a given String 13:12

You are given a string and you are supposed to print all the distinct permutations of the string ~~~~Asked in : Apple, Cisco, Samsung

Rat Maze Problem 20:35

Given a maze, NxN matrix.matrix (left top corner)is the source and matrix[N-1][N-1](right bottom corner) is destination. There are few cells which are blocked, means rat cannot enter into those cells. Rat can move in any direction ( left, right, up and down). A rat has to find a path from source to destination ~~~~Asked in : MakeMyTrip, Yatra, Expedia

Knight Walk Problem 13:30

Given a square chessboard of N x N size, the position of Knight and position of a target is given. We need to find out minimum steps a Knight will take to reach the target position~~~~Asked in : Amazon, WalmartLabs

Implement pow(x, n) 07:14

Given an integer x and a positive number n, write a efficient algorithm to computes x^n

Connect Nodes at Same level in a Binary Tree 11:58

Given a binary tree, WAP to Connect all the nodes in same level of that binary tree

Convert a Binary Tree to Doubly Linked List 13:11

Given a binary tree , convert it to a doubly Linked List(DLL) in-place. The left and right pointers in nodes are to be used as previous and next pointers 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 (left most node in binary tree) must be head node of the DLL

Print nodes at k distance from root 06:35

Given a Binary Tree and a positive integer ‘k’, write code which will print all the nodes which are at distance ‘k’ from the root

Print all Nodes at Distance k from a given Node 17:15

We are given a binary tree (with root node root), a target node, and an integer value K. Return a list of the values of all nodes that have a distance K from the target node.  The answer can be returned in any order

Boundary Traversal of Binary Tree 11:8

Given a binary tree, print boundary nodes of the binary tree Anti-Clockwise starting from the root

Bottom View of Binary Tree 16:50

Given a binary tree, print the values of nodes which would be present in bottom of view of binary tree

Construct Tree from PostOrder 18:24

Given postorder traversal of a binary search tree, construct the binary search tree

Diameter of Binary tree 12:49

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root

Left View of Binary Tree 08:46

Given a binary tree, print the values of nodes which would be present in left view of binary tree. A node will be in the left-view if it is the left-most node at its level

Reverse level order Traversal of Binary Tree 06:5

Given a binary tree, print its nodes level by level in reverse order. It means all the nodes at the last level should be printed first followed by the nodes of second last level and so on

Vertical sum of Binary Tree 12:11

Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines

Spiral Order of Binary Tree 13:29

Given a binary tree, print its nodes level by level in spiral order. i.e. all nodes present at level 1 should be printed first from left to right, followed by nodes of level 2 right to left, followed by nodes of level 3 from left to right and so on

Serialize and Deserialize a Binary Tree 18:0

Write an algorithm to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'

Check if two N-ary trees are Mirror image or not Preview16:21

Given two n-ary trees, the task is to check if they are mirror of each other or not

Group Anagrams Together 11:34

Given an array of strings, return all groups of strings that are anagrams ~~~~Asked in : Snapdeal, MakeMyTrip

Find first non-repeating character from a stream of characters 13:48

Given a stream of characters, find the first non-repeating character from stream. You need to tell the first non-repeating character in O(1) time at any moment

Design and implement LRU 21:12

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get(key)and set(key,value)

Four Sum Problem 13:25

Given an array  of n integers and an integer target, Find if there elements a, b, c, and d in integers present in array  such that a + b + c + d = target. Find all unique quadruplets in the array which gives the sum of target

Convert Number to Words Problems 14:45

Write an efficient algorithm to convert a given number into words. For ex: 1234 as ~~~~Asked in: Oracle,Amazon,Microsoft

Median of running data streams problem 20:11

Given that integers are being read from a data stream. Find median of all the elements read so far starting from the first integer till the last integer. The data stream can be any source of data, example: a file, an array of integers etc

Merge k Sorted arrays 09:11

Given k sorted array, write an efficient algorithm to merge them into one sorted array

Histogram Problem 13:35

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the this histogram

Stack that Supports getMin() in O(1) 16:48

Design a data structure which support push()/pop()/findminimum() operation in O(1) time

Find Maximum size rectangle in Binary Sub-matrix 08:18

Given a binary matrix, find the maximum size rectangle binary-sub-matrix with all 1’s

Linked List 5 lectures 1: 03:52

Given a linked list, in addition to the next reference, each node has a child pointer that can point to a separate list. With the head node, flatten the list to a single-level linked list

Merge two Sorted Linked List 11:1

Given two linked list sorted in increasing order. Given two linked list sorted in increasing order. We have to merge sorted linked lists and return a new single linked list which contains nodes of both linked list in increasing order

Sort Linked List using Merge Sort 17:31

Given a linked list, sort it using merge sort algorithm