# Coderust: Hacking the Coding Interview (Coderust)

Arrays - Merge Overlapping Intervals Merge Overlapping Intervals View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/100003). Math & Stats - Pythagorean Triplets Given an integer array, find all Pythagorean triplets. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/130001). Math & Stats - Find Missing Number Given an array of positive numbers from 1 to n, such that all numbers from 1 to n are present except one; find the missing number. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/90002). Math & Stats - Permute String Implement a method to print all permutations of a given string. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/80002). String - Reverse Words in a Sentence Given a sentence(an array of characters), reverse the order of words. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/250001). Stacks and Queues - Expression Evaluation Given an arithmetic expression, evaluate it. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/30003). Linked List - Swap Nth Node with Head Given the head of a singly linked list and 'N', swap the head with the Nth node. Return the head of the new linked list. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/200002). Back Tracking - Boggle Given an NxN grid of characters and a dictionary, find all words which can be made from the characters in the grid and are present in the given dictionary. A word can start and end at any character in the grid. The next character must be adjacent to the previous character in any of the directions i.e. up, down, left, right and diagonal. The character at each position in the grid can be used only once while making a word. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/170002). Miscellaneous - Sum of Three Values Given an array of integers and a value, determine if there are any three integers in the array whose sum equals the given value. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/20002). Math & Stats - All Subsets Find all subsets of a given set of integers. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/150001). Arrays - Rotate Array Given an array of integers, rotate the array by 'N' elements. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/210003). String - String Segmentation Given a dictionary of words and an input string tell whether the input string can be completely segmented into dictionary words. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/100004). Arrays - Implement Quicksort Given an integer array, sort it in ascending order using quicksort. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/190003). Arrays - Find maximum single sell profit Given a list of stock prices for n days, find the maximum profit with a single buy/sell activity. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/240001). Linked List - Insertion Sort of a Linked List Given the head pointer of a linked list, sort it in ascending order using insertion sort. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/280002). Arrays - Sum of Two Values Given an array of integers and a value, determine if there are any two integers in the array whose sum is equal to the given value. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/830001). Linked List - Reverse a Singly Linked List Given the pointer/reference to the head of a singly linked list, reverse it and return the pointer/reference to the head of reversed linked list. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/70003). Arrays - Find the Smallest Common Number Given three integer arrays sorted in ascending order, have to find the smallest number that is common in all three arrays. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/10003). Arrays - Find Low/High index Given a sorted array of integers, return the low and high index of the given key. Return -1 if not found. The array length can be in the millions with many duplicates. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/130003). Back Tracking - Solve N-Queens Problem Given a chess board of size N x N, determine how many ways N queens can be placed on this board so that no two queens attack each other. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/220001). Linked List - Reverse Even Nodes Given a singly linked list, reverse the nodes at even indices. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/180003). Back Tracking - Find K-sum Subsets Given an array of N positive integers, find all the subsets of the given array that sum up to the number K. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/120002). Linked List - Copy Linked List with Arbitrary Pointer Make a deep copy of the given linked list where each node has two pointers: 'next' and 'arbitrary_pointer'. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/130004). Trees - Iterative Inorder Traversal Write an inorder traversal of a binary tree iteratively. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/170004). Appendix - Other Resources List of other resources that you can use to prepare for programming interviews. String - XML to Tree Convert an XML string to an n-ary tree. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/140003). Stacks and Queues - Queue Using Stacks Implement a queue using Stacks. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/220002). Math & Stats - Is Number Valid? Given an input string, determine if it makes a valid number or not. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/840001). String - Remove White Spaces Given a null terminated string, remove any white spaces (tabs or spaces). View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/10004). Math & Stats - Integer Division Divide two integers without using '/' (division) or '*' (multiplication) operators. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/180001). String - Remove Duplicates Remove duplicate characters from a string. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/160002). Back Tracking - All Possible Braces Print all braces combinations for a given value 'n' so that they are balanced. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/160001). Graphs - Word Chaining Figure out whether the given words can form a circular chain. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/10002). Linked List - Merge Sort Given the head pointer of a linked sort, sort the linked list in ascending order using merge sort, and return the new head pointer of sorted linked list. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/40002). Dynamic Programming - Largest Sum Subarray Given an array, find the contiguous subarray with the largest sum. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/50002). Appendix - Frequently Asked Questions FAQs for Codersut 3.0. Trees - N-ary Tree to Binary Tree Convert an N-ary tree to a Binary tree and then convert the Binary tree back to its original N-ary tree structure. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/820001). Trees - Is Binary Search Tree? Given a binary tree, figure out whether it's a BST. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/290001). Graphs - Minimum Spanning Tree Find the minimum spanning tree of a connected, undirected graph with weighted edges. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/230001). Miscellaneous - Make Columns and Rows Zeros Given a two-dimensional array, if any element within is zero, make its whole row and column zero. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/190002). Trees - Mirror Binary Tree Nodes Given the root node of a binary tree, swap the 'left' and 'right' children for each node. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/850001). Stacks and Queues - Stack Using Queues Implement a stack using Queues. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/260001). Miscellaneous - Host Endianness Determine the host byte order (endianness). View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/860001). Appendix - Testimonials Have questions about Appendix - Testimonials? Go for it! Miscellaneous - Search in a Matrix Search, or find the position of, a given key in a 2D matrix. All rows and columns are sorted. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/100001). Math & Stats - Find kth Permutation Given a set of n elements find their kth permutation. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/140001). Dynamic Programming - Levenshtein Distance Compute the Levenshtein distance between two strings. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/190001). Linked List - Delete Node with a Given Key Given the head of a linked list and a key, delete the node with this given key from the linked list. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/80004). Linked List - Rotate a Linked List Given the head node of a singly linked list and an integer 'n', rotate the linked list by 'n'. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/150002). Math & Stats - All Sum Combinations Given a positive integer, return all possible sum combinations for this number using positive integers. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/120003). Miscellaneous - Closest Meeting Point Given N people on an MxM grid, find the point that requires the least total distance covered by all people to meet at that point. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/120001). Trees - Level Order Traversal of Binary Tree Given the root of a binary tree, display the node values at each level. Node values for all levels should be displayed on separate lines. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/170003). Trees - Print Tree Perimeter Given the root node of a binary tree, print the nodes that form the boundary (perimeter). View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/10005). Graphs - Clone a Directed Graph Given the root node of a directed graph, clone this graph by creating its deep copy so that the cloned graph has the same vertices and edges as the original graph. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/50003). Trees - Connect Same Level Siblings Given a binary tree, connect its siblings at each level. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/250002). Trees - Connect All Siblings Given the root to a binary tree where each node has an additional pointer called a sibling (or next), connect the sibling pointer to the next node in the same level. The last node in each level should point to the first node of the next level in the tree. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/270001). Trees - Nth Highest in BST Find the nth highest node in a Binary Search Tree(BST) View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/190004). String - Find all Palindrome Substrings Given a string, find all substrings that are palindromes. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/140004). Trees - Convert Binary Tree to Doubly Linked List Given a binary tree, convert it to a doubly linked list so that the order of the doubly linked list is the same as an in-order traversal of the binary tree. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/140005). Trees - Check if Two Binary Trees are Identical Given the roots of two binary trees, determine if these trees are identical or not. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/120004). Trees - Inorder Successor BST with Parent Pointers The inorder successor of a node in a binary tree is the next node in an inorder traversal. Write a method to find an inorder successor of a given binary tree node in a binary search tree given parent pointers View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/90003). Dynamic Programming - MaxSum Subsequence - Nonadjacent Elements Find an efficient algorithm to find the maximum sum of a subsequence in an array so that no consecutive elements are part of this subsequence. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/140002). Trees - Serialize/Deserialize Binary Tree Serialize a binary tree to a file and then deserialize it back to a tree so that the original and the deserialized trees are identical. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/230002). Arrays - Move zeros to left Given an integer array, move all elements that are equal to 0 to the left while maintaining the order of other elements in the array. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/180002). Linked List - Remove Duplicates from a Linked List Remove duplicate nodes from a linked list of integers while keeping only the first occurrence of duplicates. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/160003). Linked List - Merge Two Sorted Linked Lists Given two sorted linked lists, merge them so that the resulting linked list is also sorted. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/160004). Linked List - Add Two Integers Given the head pointers of two linked lists where each linked list represents an integer number (each node is a digit), add them and return the resulting linked list. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/130005). Math & Stats - Power of a Number Given a double, 'x', and an integer, 'n', write a function to calculate 'x' raised to the power 'n'. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/170001). Math & Stats - Calculate Square Root Given a double number, write a function to calculate its square root. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/130002). Trees - Delete Zero Sum Sub-Trees Given the root of a binary tree, delete any subtrees whose nodes sum up to zero. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/240004). Dynamic Programming - Coin Changing Problem Given coin denominations and the total amount, find the numberâ€‹ of ways to make the change. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/210001). Miscellaneous - Implement LRU Cache Implement a Least Recently Used (LRU) Cache. Discuss data structures involved. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/110001). Arrays - Binary Search Given a sorted array of integers, return the index of the given key. Return -1 if not found. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/240002). Arrays - Find Maximum in Sliding Window In this challenge, we must find the maximum value in a window. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/210002). Arrays - Search Rotated Array Search for a given number in a sorted array that has been rotated by some arbitrary number. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/100002). Linked List - Intersection Point of Two Lists Given the head nodes of two linked lists that may or may not intersect, find out if they intersect and return the point of intersection. Return null otherwise. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/70005). Linked List - Nth from Last Node Given a singly linked list, return the nth from last node. Return null if 'n' is out-of-bounds. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/70004). Linked List - Reverse k Elements Given a singly linked list and an integer 'k', reverse every 'k' element. If k <= 1, then the input list is unchanged. If k >= n (n is the length of linked list), then reverse the whole linked list. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/240005). String - Regular Expression Given a text and a pattern, determine if the pattern matches with the text completely or not at all by using regular expression matching. For simplicity, assume that the pattern may contain only two operators: '.' and '*'. Operator '*' in the pattern means that the character preceding '*' may not appear or may appear any number of times in the text. Operator '.' matches with any character in the text exactly once. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/240003). Trees - Write an In-Order Iterator for a Binary Tree Implement a class that implements an InOrder Iterator on a Binary Tree View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/140006). Dynamic Programming - Fibonacci Numbers Find the nth Fibonacci number. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/80003). Trees - Inorder Successor BST The inorder successor of a node in a binary Search Tree (BST) is the next node in an inorder traversal. Write a method to find the inorder successor of a given value "d" in a BST. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/220003). Dynamic Programming - Game Scoring: Find the Number of Ways a Player can Score 'n' Runs Imagine a game (like baseball) where a player can score 1, 2, or 4 runs. Given a score, "n", find the total number of ways score "n" can be reached. View the lesson [here](https://www.educative.io/collection/page/5642554087309312/5679846214598656/200001).

About the Coderust: Hacking the Coding Interview (Coderust) category
[Coderust: Hacking the Coding Interview (Coderust)]
(1)

How did we arrive at the recurrence relation shown in the solution
[Dynamic Programming - Game Scoring: Find the Number of Ways a Player can Score 'n' Runs]
(1)

Test does take into account the order in the output though it shouldn't
[Back Tracking - Find K-sum Subsets]
(1)

Definition of head is different from the data structure course?
[Linked List - Reverse a Singly Linked List]
(5)

Need to check whether index is within the bound after it runs out of the loop
[Arrays - Find Low/High index]
(2)

Permute String: confusion with Java code and corrosponding visual representation
[Math & Stats - Permute String]
(2)