# Coderust: Hacking the Coding Interview (Coderust)

Math & Stats - All Subsets Find all subsets of a given set of integers. Arrays - Rotate Array Given an array of integers, rotate the array by ‘N’ elements. String - String Segmentation Given a dictionary of words and an input string tell whether the input string can be completely segmented into dictionary words. 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. 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. 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. 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. Arrays - Implement Quicksort Given an integer array, sort it in ascending order using quicksort. Linked List - Insertion Sort of a Linked List Given the head pointer of a linked list, sort it in ascending order using insertion sort. 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. Arrays - Merge Overlapping Intervals Merge Overlapping Intervals 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. 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. 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’. Trees - Iterative Inorder Traversal Write an inorder traversal of a binary tree iteratively. 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. Linked List - Reverse Even Nodes Given a singly linked list, reverse the nodes at even indices. Trees - Connect Same Level Siblings Given a binary tree, connect its siblings at each level. 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. 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. Appendix - Other Resources List of other resources that you can use to prepare for programming interviews. Trees - Print Tree Perimeter Given the root node of a binary tree, print the nodes that form the boundary (perimeter). String - XML to Tree Convert an XML string to an n-ary tree. String - Remove White Spaces Given a null terminated string, remove any white spaces (tabs or spaces). 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. 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. Math & Stats - Integer Division Divide two integers without using ‘/’ (division) or ‘*’ (multiplication) operators. Stacks and Queues - Queue Using Stacks Implement a queue using Stacks. Math & Stats - Is Number Valid? Given an input string, determine if it makes a valid number or not. Math & Stats - Calculate Square Root Given a double number, write a function to calculate its square root. Miscellaneous - Implement LRU Cache Implement a Least Recently Used (LRU) Cache. Discuss data structures involved. 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. Back Tracking - All Possible Braces Print all braces combinations for a given value ‘n’ so that they are balanced. Stacks and Queues - Expression Evaluation Given an arithmetic expression, evaluate it. Dynamic Programming - Largest Sum Subarray Given an array, find the contiguous subarray with the largest sum. String - Reverse Words in a Sentence Given a sentence(an array of characters), reverse the order of words. Graphs - Word Chaining Figure out whether the given words can form a circular chain. String - Remove Duplicates Remove duplicate characters from a string. 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. Trees - Delete Zero Sum Sub-Trees Given the root of a binary tree, delete any subtrees whose nodes sum up to zero. Miscellaneous - Host Endianness Determine the host byte order (endianness). Stacks and Queues - Stack Using Queues Implement a stack using Queues. Miscellaneous - Make Columns and Rows Zeros Given a two-dimensional array, if any element within is zero, make its whole row and column zero. Dynamic Programming - Fibonacci Numbers Find the nth Fibonacci number. Graphs - Minimum Spanning Tree Find the minimum spanning tree of a connected, undirected graph with weighted edges. Trees - Is Binary Search Tree? Given a binary tree, figure out whether it’s a BST. Trees - Mirror Binary Tree Nodes Given the root node of a binary tree, swap the ‘left’ and ‘right’ children for each node. 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. 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. Math & Stats - Find kth Permutation Given a set of n elements find their kth permutation. Arrays - Find Maximum in Sliding Window In this challenge, we must find the maximum value in a window. Dynamic Programming - Levenshtein Distance Compute the Levenshtein distance between two strings. 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. Trees - Nth Highest in BST Find the nth highest node in a Binary Search Tree(BST) Dynamic Programming - Coin Changing Problem Given coin denominations and the total amount, find the number of ways to make the change. 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. Trees - Write an In-Order Iterator for a Binary Tree Implement a class that implements an InOrder Iterator on a Binary Tree 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. 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’. Math & Stats - All Sum Combinations Given a positive integer, return all possible sum combinations for this number using positive integers. 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’. 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. String - Find all Palindrome Substrings Given a string, find all substrings that are palindromes. 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. 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. 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. 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. Trees - Check if Two Binary Trees are Identical Given the roots of two binary trees, determine if these trees are identical or not. Arrays - Search Rotated Array Search for a given number in a sorted array that has been rotated by some arbitrary number. 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 ‘<em>’. Operator '</em>’ 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. 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. Linked List - Merge Two Sorted Linked Lists Given two sorted linked lists, merge them so that the resulting linked list is also sorted. 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 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. Arrays - Binary Search Given a sorted array of integers, return the index of the given key. Return -1 if not found. 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. Math & Stats - Pythagorean Triplets Given an integer array, find all Pythagorean triplets. 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. Math & Stats - Permute String Implement a method to print all permutations of a given string. 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. 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.

About the Coderust: Hacking the Coding Interview (Coderust) category
[Coderust: Hacking the Coding Interview (Coderust)]
(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)