KodeKnight

Convert Binary tree to double linked list in inorder traversal

Posted on January 5, 2012 (Last modified on August 7, 2020) | 5 minutes | Kinshuk Chandra

Problem Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). 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 BT) must be head node of the DLL. Example Input [Read More]

Find the First Duplicated Integer in an Array containing numbers from 1 to N Without Using Extra Memory

Posted on January 5, 2012 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

let the array be 3 1 2 1 3 4 first repeated integ… Unknown - Mar 6, 2013let the array be 3 1 2 1 3 4 first repeated integer is 3 here start from the first and go till the end add n+1 to the a[a[i]] where i is the current index. iterate again dividing the values by n+1 if values comes 1 . the remainder is the repeated one. [Read More]

kodeknight ranged-array duplicate incomplete array integer-array

Find the First Duplicated Integer in an Array containing numbers from 1 to N Without Using Extra Memory

Posted on January 5, 2012 (Last modified on August 7, 2020) | 4 minutes | Kinshuk Chandra

Question: There is a size-N array of integers whose values range from 1 to N. Some integers are duplicated. Find the first duplicate and its index without using any extra memory (not even O(1)). Solution There are a few keys in the question that we should consider: The array size is a finite number N which is also the upper limit for any integer inside the array. Hence, if the array size is 10, then there are ten elements in the array and each of those elements is between 1 and 10. [Read More]

kodeknight ranged-array duplicate incomplete array integer-array

Sorting Array of Three Kinds or The Dutch National Flag Problem OR three color sort

Posted on January 5, 2012 (Last modified on August 7, 2020) | 4 minutes | Kinshuk Chandra

Question: given an array of three different kinds of value such as array(1, 2, 0, 2, 1) and array(a, b, a, c, b), write an algorithm to sort the array. For example, input array(1, 2, 0, 2, 1) becomes array(0, 1, 1, 2, 2) and input array(a, b, a, c, b) becomes array(a, a, b, b, c). This problem is also called three color sort. Solution: the Dutch National Flag Algorithm sorts an array of red, blue, and white objects by separating them from each other based on their colors. [Read More]

kodeknight quicksort binary array sorting incomplete array integer-sort zero

Shuffle a deck of cards perfectly

Posted on January 5, 2012 (Last modified on August 7, 2020) | 4 minutes | Kinshuk Chandra

Question Write a method to shuffle a deck of cards. It must be a perfect shuffle – in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect. OR How can you shuffle an array in O(n) time and O(1) space? For example, if input is an array of (1, 2, 3, 4, 5), one of the output can be (5, 4, 3, 2, 1) or (4, 2, 3, 1, 5). [Read More]

kodeknight probability shuffle array CrackingTheCodingInterview random

Find Local Maximum of a Function Using Bisection Method

Posted on January 5, 2012 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Question: implement the bisection method to find a function’s local maximum. Solution: bisection is one of the root-finding methods that are used to find real roots of a continuous function. More information about the method and mathematical analysis can be found here. For this question, we’ll modify the bisection method to find the local maximum of a function instead of its roots. The maximum of a function is a point where the value of the function is max. [Read More]

kodeknight incomplete

Least-Square Linear Regression of Data Using C++

Posted on January 5, 2012 (Last modified on August 7, 2020) | 4 minutes | Kinshuk Chandra

Question: implement the least-square method to determine the linear function that best fits the data. This method also needs to find the coefficient of determination (R^2) and standard error of estimation (E). Input to this method is a collection of data points (x, y) and the collection’s size, a.k.a. number of data points. Solution: the answer is straight forward. We basically just have to apply the statistics formulas for finding the least-square linear function to the data. [Read More]

kodeknight incomplete

Convert integers to roman numbers

Posted on January 5, 2012 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Question: write an algorithm to convert an integer into roman number. For example, 1 -> I, 2 -> II, or 4 -> IV. Solution: in order to solve this problem, we must know the rules of writing roman numerals. For example, I is 1 and V is 5 but IV is not 6 but 4 (5 -1). Moreover, there is no 0 number in roman numeral system. Here is the link to an article about roman numerals if you are unfamiliar with the system. [Read More]

conversion Algorithms kodeknight integer

Check If an Integer's Bit Representation Is a Palindrome

Posted on January 5, 2012 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Question: how can you determine if a positive integer is a palindrome. For example, 5 is a palindrome because 5 = 101. Also, 9 is a palindrome because 9 = 1001. Solution: an integer is palindrome when its bit representation is the same reading from left to right or from right to left. Thus, in order to know if it is a palindrome or not, we just have to check if the number’s value is still the same when we read the number’s bits backward (right to left). [Read More]

kodeknight reverse bits palindrome

Convert Binary Tree to Double Linked List in Zig-Zag Order

Posted on January 5, 2012 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Question: given a binary tree, write an algorithm to convert the tree into a double-linked list. The list must be as if the tree is traversed in zig-zag and level order. Solution: let’s first understand what the objective is. By zig-zag level order, the question means that we need to traverse the tree in level order, a.k.a breadth first, such that the next level is traversed in the oposite direction to the current level. [Read More]

conversion kodeknight binary-search-tree BST Doubly Linked List DLL