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 

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 

Heap Sort in java

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

The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. Heap sort Algorithm This algorithm assumes understanding of heap - Heap - Introduction. Also, it also uses ExtractMin from Heap. Algorithm The essence of heap sort (in-place) is this: Convert the array to be sorted into a heap. (see BuildHeap, it uses O(n) time) Build the sorted array back to front by repeatedly removing the minimum value in the heap (the value at position 1), putting that value into the sorted array, and rebuilding the heap with one fewer element. [Read More]
kodeknight  time complexity  sorting  incomplete  heap 

K – Reverse a linked list

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

This is one of the questions asked in Microsoft Interview. Given a linked list, we need to write a function that reverses the nodes of a linked list ‘k’ at a time and returns modified linked list. The following are the constraints given: If the no. of nodes in a link list is not a multiple of k then left-out nodes in the end should remain as it is You have to retain the memory address of the nodes without modifying it i. [Read More]
kodeknight  Microsoft  link list  reverse  Amazon  Single Link List  incomplete 

DFS (Depth First Search) on tree or graph

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

Consider this tree (which is a graph without a cycle) : Now DFS means traversing to the depth…and then going up, so here DFS traversal will result in 5 2 -4 3 21 19 25. We can use non recursive as well recursive approach to solve this problem. A depth first search (DFS) through a tree starts at the root and goes straight down a single branch until a leaf is reached. [Read More]
backtracking  Graph  search  tree  kodeknight  sorting  DFS  incomplete  traversal  binary-search-tree  BST  graph-search