Searching Questions

 Posted on April 4, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Here are some questions on searching Search types Linear Search on Array Binary search on Array - Recursive and iterative Special case of Ranged array By ranged array, I mean that array has some specific size, say N, and numbers in that array can occur in a range of 0 to N-1. I don’t know if some other special name exists for such arrays. But lets go ahead with this name. [Read More]
search  kodeknight  Page  duplicate  incomplete 

Find the duplicate element most number of times in array of 0 to n-1

 Posted on April 4, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Given an array of n numbers from 0 to n-1, find the element occurring most number of times Solution This problem is similar to following problem : Find the two repeating elements in a given array We can use some of the method used there. Method 1 - Brute force Here we will match the adjacent elements, and increment the count accordingly. Here is the code public int maxDuplicateItemBruteForce(int A){ int n = A. [Read More]
search  kodeknight  ranged-array  duplicate 

Check if array contains duplicates

 Posted on March 31, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

**Problem ** Given an array of n elements, check if it has duplicates Solution This problem is similar to following problem : Find the two repeating elements in a given array We can use some of the method used there. Method 1 - Brute force Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop. [Read More]
search  kodeknight  ranged-array  duplicate 

Find duplicates in the ranged array

 Posted on March 31, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Follow UP - Find these repeating numbers in O(n) and using only constant memory space. Example Input : array = {1, 2, 3, 1, 3, 6, 6}, n = 7 Output = 1,3,6 Solution This problem is an extended version of following problem. Find the two repeating elements in a given array [Read More]
search  kodeknight  ranged-array  duplicate 

Find the two repeating elements in ranged array

 Posted on March 31, 2014  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Problem You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers. Example Input : array = {4, 2, 4, 5, 2, 3, 1} and n = 5, array.length = n+2 = 7 Output : 4,2 Solution This can be achieved by various methods. [Read More]
search  kodeknight  ranged-array  duplicate 

Find the two non-repeating elements in a ranged array of repeating elements

 Posted on March 31, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way. Example Input : {2,4,7,9,2,4} Output : 7,9 Solution Method 1 - Use Sorting First sort all the elements. In the sorted array, by comparing adjacent elements we can easily get the non-repeating elements. [Read More]
search  kodeknight  ranged-array  duplicate 

Find Nth largest element in the rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Please give review to this post http://rawjava.blo…

Unknown - Apr 1, 2015

Please give review to this post
http://rawjava.blogspot.com/2015/04/java-program-to-find-maximum-number.html

Good question and equally good answer..Enjoyed your post :)

search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  kth-largest  min  sorted-array 

Find Nth largest element in the rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**Question : **Find Nth largest element in the rotated sorted array So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Solution So, to find the Nth largest element in normal sorted array is a[N]. But in this case it is rotated k, which we don’t know. [Read More]
search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  kth-largest  min  sorted-array 

Finding an integer that repeats odd number of times in an array of positive integers

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

Question: In an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity? Solutions Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0. [Read More]
search  Algorithms  ArraySearch  kodeknight  duplicate  Interview Question  array  integer-sort  bits