Given an unsorted linked list, sort the list using merge sort.
Example: 3 -> 4 -> 5-> 1 -> 2 Output: 1 -> 2 -> 3 -> 4 -> 5 Merge sort is a divide and conquer algorithm. Here we divide the elements into smaller parts, then while merging them, we merge according to sorted order. Example: Consider below elements, we start dividing exactly half of […]
Sort a linked list using insertion sort.
Sort a linked list using insertion sort. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 Insertion sort is a comparison based sorting algorithm. In this algorithm we divide the list into 2 parts. The left most part is sorted part, and the right most part is unsorted part. In insertion […]
Reorder list in to alternate nodes like first lowest and first highest.
Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You may not modify the values in the list’s nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it to 1->4->2->3. Example 2: Given 1->2->3->4->5, reorder it to 1->5->2->4->3. The C++ algorithm will works as shown below: Step 1: Find the […]
Given a sentence and maxWidth. Arrange the text in such a way that each line has exactly maxWidth characters and is fully justified.
Your answer should be of greedy approach. You should pack as many words you can in each line. If you cannot fit the whole word, then fill the extra spaces with ‘ ‘ (empty space). Extra spaces between words should be evenly distributed between the words. Example: Input: words = ["This", "is", "an", "example", "of", […]
Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space? Solution Explanation: Take an extra pointer “fast” and assign its starting point to head. Every iteration moves the “fast” pointer 2 steps forward and “head” pointer 1 step forward. At certain point, if there is a cycle, both “head” and “fast” pointer will meet at […]
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Example 1: Input: [2,2,1] Output: 1 Example 2: Input: [4,1,2,1,2] Output: 4 We can solve this by 2 methods: 1. unordered_map 2. XOR operation. We shall discuss both of the solutions in this tutorial. 1. Solution using unordered_map. […]
Soduku Solver
Before solving this problem, it is recommended that you go through “valid sudoku” problem. Check if the given board is valid Sudoku or not explanation with solution in CPP This is a classic problem of backtracking with DFS. The solution is very simple. We have a DFS helper function, to check if the “num” from […]
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s. Example: Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ] The solution for this problem can be done with the help of DFS. The logic is to loop through the string one by one. Once we find a palindromic string for the string str(0, i) we store the current string […]
Surrounded Regions
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region. DFS: We can solve this problem in 2 ways: 1. BFS 2. DFS In this tutorial we solve it by using DFS. The solution here is very simple. First we check if any of the edges of row and column is […]
Woord Ladder
You are given 2 words beginWord and endWord. You need to return the number of words, that will transform from beginWord to endWord beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] This question can be solved in 2 ways. 1. BFS 2. 2 end BFS 1. Solving using regular BFS: So the question […]