Data Structure & Algorithms Complete Course in Java

Linked List Creation Introduction

Single Linked List (Insertion, Search)

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

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

Given a linked list, sort it using merge sort algorithm

You are given a double Link List with one reference of each node pointing to the next node just like in a single link list. The second reference however can point to any node in the list and not just the previous node.Write a program in O(n) time which will create a copy of this list

Given a linked list, WAP to reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed

Stack Operation Implementation

Queue Operation Implementation

Circular Queue Implementation

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

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

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

Sliding Window Problem using deque Data Structure [Amazon, Flipkart]

Binary Search Algorithm Introduction

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

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 in order of the given Binary Tree. The first node of Inorder traversal (left most node in binary tree) must be head node of the DLL

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

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

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

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

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

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

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

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

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

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

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

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

Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree ~ Flipkart, VMware

Heapify operation implementation [Adobe]

Min/Max Heap Implementation [Cisco]

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

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 a data structure for Least Recently Used (LRU) cache. It should support the following operations: get(key)and set(key,value)

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

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

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

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

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

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

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's algorithm allows us to find the shortest path between any two vertices of a graph ~~~~ Asked in : Google, Uber, Facebook

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

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

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

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 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

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

find an arrangement of N queens on a chess board, such that no queen can attack any other queens on the board. The chess queens can attack in any direction as horizontal, vertical, horizontal and diagonal way [Asked in : VISA, Intuit]

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

Sudoku solving Problem - 2 [Intuit]

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

Given a maze, NxN matrix.matrix[0][0] (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

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

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

How to Solve DP problems- Tips and Tricks

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

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

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

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

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

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

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

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

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 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

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

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

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

As part of this community, take advantage of discounts on products and services

that can help you with your career and personal goals.