Majority element in the array
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).
Problem: Given an array consisting of N integers, find the number with the maximum occurrences, i.e. majority element, given the assumption that the number occurs more than N/2 times in the array.
Example
I/P : 3 3 4 2 4 4 2 4 4
[Read More]atoi() in Java
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: Write a function to convert an ASCII string to integer, similar to atoi() function of C++.
Solution: The solution is too simple, it’s simple checks for erroneous inputs that makes writing such a function fun.
public class AsciiToInteger { public static void main(String\[\] args) { AsciiToInteger instance \= new AsciiToInteger(); int x \= instance.atoi("-683"); System.out.println("Conversion is: " + x); } private int atoi(String number) { // check for NULL or empty if(number \=\= null || number.
[Read More]In-Place Character Array Compression
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: Given a character stream as an array, compress the characters in place appending the number of continuous characters by the numerical value and then the character. The array is terminated by a 0x00 character.
Solution: Another classic interview problem which tests multiple skills in a single problem, namely,
Conversion from integer to ascii - the number returned is a integral value which needs to be converted to ascii and then put in place in stream Skills with pointers (not the real pointers) when operating on an array The following JAVA code illustrates how to work up the given problem.
[Read More]One duplicate , one missing element in an array
Posted on October 1, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
You have an array of size 100 which stores integers from 0 to 99.
In this array one number is a duplicate, that means one is missing.
How can we find duplicate and missing ?
Method 1
1. Since one element is missing , some element must be repeated once in the array.
2. Let x be the missing and y be the repeated element
3. Calculate the sum of all the elements and sum of squares of all the elements of array.
[Read More]Given numbers from 1 to N+1, with number being from 1 and N and one of the number being repeatative. Find the repeating element.
Posted on September 30, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?
[Read More]Spiral printing of a two dimensional array
Posted on September 19, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Given a 2D array, print it in spiral form.
Examples
See the following examples.
Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Output: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11 Code is :
[Read More]k largest(or smallest) elements in an array
Posted on September 15, 2011
(Last modified on August 7, 2020)
| 0 minutes
| Kinshuk Chandra
Median of 2 sorted arrays of equal size n
Posted on September 13, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Naman - May 6, 2014
This comment has been removed by a blog administrator.
This comment has been removed by the author.
Median of 2 sorted arrays of equal size n
Posted on September 13, 2011
(Last modified on August 7, 2020)
| 7 minutes
| Kinshuk Chandra
Question There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))
Solution Before going to solution what is the median.
What is Median? Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half.
[Read More]Given two sorted arrays of size m and n respectively (m >> n), how to merge them together?
Posted on May 11, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Given two sorted arrays of size m and n respectively (m » n), how to merge them together? (Note: if you try to insert n numbers to the larger array to obtain O(n \log m) complexity, pay attention that you have to move elements around for insertions. Also, simply merging those two arrays is not the optimal solution here.) Solution
Consider A[m+1] and B[n+1] and C[m+n] (m»n and indexing starts from 1)
[Read More]