EMC Interview Question
Software Engineer / DevelopersIf an element is equal to the previous one, then output.
The variable pre in the above code is not necessary.
i think pre (or other form of extra information) is necessary as you only output the repeated number for once. the solution you suggested will print out '222' when it sees '2222'
This one is faster. It does a binary traversal of the sorted array and will prove better when a large array has a lot of duplicates. It does print the duplicates multiple times.
static void findDuplicate(int first,int last, int[] array){
int n=last-first+1;
if(n==2){
if(array[first]==array[last])
System.out.println(array[first]);
return;
} else if(n==1){
return;
} else{
if(n/2 == 1){
if(array[first]==array[first+1])
System.out.println(array[first]);
else if(array[first+1]==array[last])
System.out.println(array[last]);
return;
}else{
if(array[first]==array[last]){
System.out.println(array[first]);
}else{
if(array[n/2]==array[(n/2)-1]){
System.out.println(array[n/2]);
findDuplicate(0,(n/2)-2,array);
findDuplicate(n/2,n-1,array);
}else{
findDuplicate(0,(n/2)-1,array);
findDuplicate(n/2,n-1,array);
}
}
}
}
O(log n) solution..
map<int, int> blist;
void count_dup(int* arr, int start, int end)
{
if(end == 0)
blist[arr[start]]+=1;
if(start<end) {
if(arr[start] == arr[end]) {
blist[arr[end]] += end - start + 1;
return;
}
int mid = abs((start+end)/2);
if(end - start == 2 && arr[start] < arr[mid] && arr[mid] < arr[end]) {
blist[arr[start]] +=1;
blist[arr[mid]] +=1;
blist[arr[end]] +=1;
return;
}
if(arr[start] != arr[mid] && start == mid) {
blist[arr[start]]+=1;
blist[arr[mid]] += 1;
return;
}
if(arr[start] < arr[mid]) {
count_dup(arr, start, mid);
}
else {
blist[arr[mid]] += mid - start + 1;
}
if(arr[mid+1] != arr[end] && mid+1 == end) {
blist[arr[mid+1]]+=1;
blist[arr[end]] += 1;
return;
}
if(arr[mid+1] < arr[end]) {
count_dup(arr, mid+1, end);
}
else {
blist[arr[end]] += end - mid;
}
}
}
void main()
{
int A[] = {1,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,6,7,7,8,9};
count_dup(A, 0,20);
}
for explanation check here: analgorithmaday <dot> blogspot <dot> com
<slash> 2011<slash> 05 <slash> count-duplicates-in-integer-arraygoogle <dot> html
package arraytest;
import java.util.*;
public class Test3
{
public static void main(String [] argv)
{
int [] numArray = {1,4,3,6,8,9,4,2,3,8 };
Arrays.sort(numArray); // ascending sort
HashSet<Integer> uniqueNumSet = new HashSet<Integer>();
for (int i=0; i<numArray.length; i++)
{
if (uniqueNumSet.contains(numArray[i]))
{
System.out.println ("Found duplicate entry: " +numArray[i]);
}
else
{
System.out.println("First occurence of entry: " + numArray[i]);
uniqueNumSet.add(numArray[i]);
}
}
}
}
public class DuplicateNumbers
{
public TreeSet<Integer> removeDuplicates(int[] numbers){
TreeSet<Integer> unique = new TreeSet<Integer>();
for(int i=0; i< numbers.length; i++){
unique.add(numbers[i]);
}
return unique;
}
public static void main(String[] args){
DuplicateNumbers dn = new DuplicateNumbers();
int[] numbers={1,1,1,1,1,2,3,4,4,4};
TreeSet<Integer> unique = dn.removeDuplicates(numbers);
Iterator it = unique.iterator();
while(it.hasNext()){
System.out.println("Element is: " + it.next());
}
}
}
Small Correction to the above code....
public class DuplicateNumbers
{
public TreeSet<Integer> removeDuplicates(int[] numbers){
TreeSet<Integer> unique = new TreeSet<Integer>();
for(int i=0; i< numbers.length-1; i++){
if(numbers[i] == numbers[i+1])
{
unique.add(numbers[i]);
}
}
return unique;
}
public static void main(String[] args){
DuplicateNumbers dn = new DuplicateNumbers();
int[] numbers={1,1,1,1,1,2,3,4,4,4};
TreeSet<Integer> unique = dn.removeDuplicates(numbers);
Iterator it = unique.iterator();
while(it.hasNext()){
System.out.println("Element is: " + it.next());
}
}
}
public class dup_count {
public static int lastVal = Integer.MIN_VALUE;
public static void main(String[] args) {
// Testing with the following test data
int[] a = { 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 9, 9, 9,
10, 10 };
// int[] a = { 1, 2, 3, 4, 5 };
// int[] a = { 3, 3, 3 };
// int[] a = { 1, 1, 3 };
// int[] a = { 1, 1 };
new dup_count().count_dupicates(a, 0, a.length - 1);
}
void count_dupicates(int[] a, int start, int end) {
int mid = (start + end) / 2;
if (end <= start || mid == start && a.length > 2 || mid == end
&& a.length > 2)
return;
// if the mid element == start element, then the start element was
// repeated all
// the way through start to mid location
// a[start] > lastVal: This comparision is just to prevent
// printing the same number again and again
if (a[mid] == a[start] && a[start] > lastVal) {
System.out.println(a[start] + " , ");
lastVal = a[start];
}
else if (a[mid] > a[start]) {
count_dupicates(a, start, mid);
}
if (a[end] == a[mid] && a[end] > lastVal) {
System.out.println(a[end] + " , ");
lastVal = a[end];
return;
}
else if (a[end] > a[mid]) {
count_dupicates(a, mid, end);
}
}
}
Jave code for the above problem statement. Very similar to Binary Search algorithm. Additional ifs had to be put for the case when the array has only 2 and 3 elements.
- syrus August 13, 2010