Amazon Interview Question Interns
Country: United States
Interview Type: Phone Interview
I think without using quick sort we can do in o(N) TC bu using Boyer-Moore_Majority_Vote_Algorithm .. as i did please my comment...public class MajorityElement
N log N time complexity
Think about any number the array cannot have. For example we assume that the array may not have -1 as an element.
Following program gives the solution in nlogn time complexity.
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;
public class Repeating {
private static int[] numbers = {1,8,1,2, 3,9,7,6,5,3,2,3, 1};
/**
* This program finds second most repeating number in an array
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Arrays.sort(numbers);
for(int i=0; i<(numbers.length-1); i++){
if(numbers[i]==numbers[i+1]){
numbers[i]= -1;
}
}
TreeMap<Integer,Integer> occurence = new TreeMap<Integer,Integer>();
int k = 0;
for(int i=0; i<numbers.length; i++){
if(numbers[i] == -1){
k++;
//System.out.print(" "+numbers[i]);
}else{
k++;
occurence.put(k, numbers[i]);
k=0;
if(occurence.size()>2){
occurence.pollFirstEntry();
}
}
}
Map.Entry<Integer, Integer> entry = occurence.pollFirstEntry();
System.out.println(" "+entry.getValue());
}
}
s100banerjee, I'm afraid that your solution uses O(n) extra memory for the TreeMap occurrence.
@Ranan see the following code
if(occurence.size()>;2)
The extra memory is O(3) i.e. constant
@Sumit Polite, try the MajorityElement class wirtten by you using boyes-moore with array {2,5,3,5,5,3,5,3,1,2,5,1,1,1}. Second majority is 5, but it is returning 2
O(n) time Using heap sort:
1)max-Heap can be constructed in O(1) time.
2) remove the first element O(long n). The root element is now 2nd highest.
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] numbers = {1,8,1,2, 3,9,7,6,5,3,2,3, 1};
Arrays.sort(numbers);
Test t = new Test();
for(int n: numbers)
System.out.println(t.sL(numbers));
}
private int sL(int[] arr){
int max=Integer.MIN_VALUE;
int max2=Integer.MIN_VALUE;
int nmax=Integer.MIN_VALUE;
int smax=Integer.MIN_VALUE;
int count=0;
for(int i=0;i<arr.length;i++){
if(i==arr.length - 1 || arr[i]==arr[i+1]){
count++;
if(i==arr.length -1){
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
}
}else{
count++;
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
count = 0;
}
}
return smax;
}
}
Using Bit Manipulation
------------------------------
public class RepeatingNumber {
public static int findRepeatingNumber(int[] a, int min, int max) {
int n = max-min +1;
byte[] b = new byte[2];
for(int i : a) {
if( (b[(int)(i/8)] & (1 << (i%8))) == 0){
b[i/8] |= (1 << (i%8));
} else {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] a = {4,5,7,1,8,7,15};
//find min and max
int min = 1;
int max = 15;
System.out.println(findRepeatingNumber(a, min, max));
}
}
public class Example {
public static void main(String[] args) {
int[] arr = {0, 5, 1, 2, 2, 1, 1, 3, 5, 2, 1};
int mfCount = 0;
int smfCount = 0;
int mf = 0;
int sfm = 0;
for (int i = 0; i < arr.length - 1; i++) {
int count = 1;
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j]) {
count++;
}
}
if (count > mfCount) {
smfCount = mfCount;
mfCount = count;
sfm = mf;
mf = arr[i];
} else if (count > smfCount) {
smfCount = count;
sfm = arr[i];
}
}
System.out.println(sfm);
}
}
If you are coding in Java, you can implement a HashMap. Using these functions, can make your life a lot easier, in my opinion.
public static int SecondMostRepeated(int[] array){
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int value = 0,secondMax=0,max=0,number=0,current=0;
//populate hashMap
for(int i=0;i<array.length; i++){
//if the hashmap doesn't contain
//the item, add one instance of it.
if(map.get(array[i]) == null)
map.put(array[i], 1);
//otherwise, increment its value.
else{
value = map.get(array[i]);
map.put(array[i], ++value);
}
}
for(int i=0; i<array.length; i++){
current=map.get(array[i]);
//keep a track on the maximum number.
if(current > max){
secondMax=max;
max = current;
}else {//keep a track on the second-Maximum
if(current>=secondMax){
secondMax=current;
number = array[i];//what we are looking for.
}
}
}
return number;
}
public static int find(int[] numbers) {
int secondMostRepeating = 0;
Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
int count = 1;
for (int number : numbers) {
if (mp.containsKey(number)) {
count = mp.get(number);
mp.put(number, ++count);
} else {
mp.put(number, 1);
}
}
int max = Integer.MIN_VALUE;
int second = Integer.MIN_VALUE;
Set<Entry<Integer, Integer>> set = mp.entrySet();
for (Entry<Integer, Integer> entry : set) {
if (entry.getValue() >= max) {
max = entry.getValue();
} else if (entry.getValue() >= second) {
second = entry.getValue();
secondMostRepeating = entry.getKey();
}
}
return secondMostRepeating;
}
package com.aorg.MyPractice.DS.Array;
public class MajorityElement {
/**
* @param args
*/
public static void main(String[] args) {
try{
int[] a = {2,5,3,5,5,3,5};
int ele = new MajorityElement().getMajority(a);
System.out.println(ele);
}catch(Exception ex){
ex.printStackTrace();
}
}
public int getMajority(int[] a){
try{
int count = 0;
int count1 = 0;
int ele = a[0];
for(int i=1; i <a.length ; i++){
if(count == 0){
ele = a[i];
count = 1;
}else{
if(ele == a[i]){
count++;
}else{
count--;
}
}
}
int ele1 = 0;
count = 0;
for(int i = 0; i <a.length ; i++){
if(ele == a[i]){
count++;
}else if(count1 == 0){
ele1 = a[i];
count1 = 1;
}else if(ele1 == a[i] && count1 < count){
count1++;
}else{
count1--;
}
}
System.out.println("2nd Majority element > "+ele1);
if(count > (a.length/2)){
return ele;
}else{
return -1;
}
}catch(Exception ex){
ex.printStackTrace();
}
return -1;
}
}
package com.aorg.MyPractice.DS.Array;
public class MajorityElement {
/**
* @param args
*/
public static void main(String[] args) {
try{
int[] a = {2,5,3,5,5,3,5};
int ele = new MajorityElement().getMajority(a);
System.out.println(ele);
}catch(Exception ex){
ex.printStackTrace();
}
}
public int getMajority(int[] a){
try{
int count = 0;
int count1 = 0;
int ele = a[0];
for(int i=1; i <a.length ; i++){
if(count == 0){
ele = a[i];
count = 1;
}else{
if(ele == a[i]){
count++;
}else{
count--;
}
}
}
int ele1 = 0;
count = 0;
for(int i = 0; i <a.length ; i++){
if(ele == a[i]){
count++;
}else if(count1 == 0){
ele1 = a[i];
count1 = 1;
}else if(ele1 == a[i] && count1 < count){
count1++;
}else{
count1--;
}
}
System.out.println("2nd Majority element > "+ele1);
if(count > (a.length/2)){
return ele;
}else{
return -1;
}
}catch(Exception ex){
ex.printStackTrace();
}
return -1;
}
}
package com.aorg.MyPractice.DS.Array;
public class MajorityElement {
/**
* @param args
*/
public static void main(String[] args) {
try{
int[] a = {2,5,3,5,5,3,5};
int ele = new MajorityElement().getMajority(a);
System.out.println(ele);
}catch(Exception ex){
ex.printStackTrace();
}
}
public int getMajority(int[] a){
try{
int count = 0;
int count1 = 0;
int ele = a[0];
for(int i=1; i <a.length ; i++){
if(count == 0){
ele = a[i];
count = 1;
}else{
if(ele == a[i]){
count++;
}else{
count--;
}
}
}
int ele1 = 0;
count = 0;
for(int i = 0; i <a.length ; i++){
if(ele == a[i]){
count++;
}else if(count1 == 0){
ele1 = a[i];
count1 = 1;
}else if(ele1 == a[i] && count1 < count){
count1++;
}else{
count1--;
}
}
System.out.println("2nd Majority element > "+ele1);
if(count > (a.length/2)){
return ele;
}else{
return -1;
}
}catch(Exception ex){
ex.printStackTrace();
}
return -1;
}
}
}
Accomplish in Javascript
function qSort(arr){
if(arr.length == 0){
return [];
}
var lesser = [];
var greater = [];
var pivot = arr[0];
// pivot always pick the first value
for (var i = 1; i<arr.length; i++){
if(arr[i] < pivot){
lesser.push(arr[i]);
}else{
greater.push(arr[i]);
}
}
return qSort(lesser).concat(pivot,qSort(greater));
}
var a=[6,4,45,76,76,42,45,31,23];
console.log(a);
console.log();
b = qSort(a);
console.log(b);
function secondMax(arr){
max = 0;
preMax = 0;
index = arr.length-1;
if(index <=1 ){
if(arr[0]>=arr[1]){
max = arr[0];
preMax = arr[1];
}else if(arr[0]<arr[1]){
max = arr[1];
preMax = arr[0];
}
}else if(index > 1){
for(i=0; i<=arr.length-1; i++){
if(arr[i]>arr[i+1]){
Max = arr[i];
preMax = arr[i+1];
}else if(arr[i]<arr[i+1]){
Max = arr[i+1];
preMax = arr[i];
}else if(arr[i]==arr[i+1]){
Max = arr[i];
}
}
}
return preMax;
}
console.log(secondMax(b));
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CarrerCup1
{
class Program
{
//find the second most repeating number within an array, without using extra storage
static void Main(string[] args)
{
double [] numbers = new double[9];
numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 3;
numbers[3] = 1;
numbers[4] = 2;
numbers[5] = 1;
numbers[6] = 4;
numbers[7] = 4;
numbers[8] = 3;
Program p = new Program();
p.FindRepeatingNumber(numbers, 2);
Console.WriteLine(p.FindRepeatingNumber(numbers, 2));
Console.ReadLine();
}
double FindRepeatingNumber (double [] numbers, int RepeatLevel)
{
Array.Sort(numbers);
double numberFound = -1;
double secondRankedNumberFound = -1;
double currentNumber = numbers[0];
int counter = 1;
int higherCounter = 1;
int secondRankedCounter = 1;
for (int i= 1; i< numbers.Length; i++)
{
if (currentNumber == numbers[i])
{
counter++;
}
else
{
if (higherCounter < counter)
{
secondRankedCounter = higherCounter;
higherCounter = counter;
if (numberFound != -1)
{
secondRankedNumberFound = numberFound;
}
else
{
secondRankedNumberFound = currentNumber;
}
numberFound = currentNumber;
}
counter = 1;
currentNumber = numbers[i];
}
}
if (higherCounter < counter)
{
secondRankedCounter = higherCounter;
higherCounter = counter;
if (numberFound != -1)
{
secondRankedNumberFound = numberFound;
}
else
{
secondRankedNumberFound = currentNumber;
}
numberFound = currentNumber;
}
return secondRankedNumberFound;
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CarrerCup1
{
class Program
{
//find the second most repeating number within an array, without using extra storage
static void Main(string[] args)
{
double [] numbers = new double[9];
numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 3;
numbers[3] = 1;
numbers[4] = 2;
numbers[5] = 1;
numbers[6] = 4;
numbers[7] = 4;
numbers[8] = 3;
Program p = new Program();
p.FindRepeatingNumber(numbers, 2);
Console.WriteLine(p.FindRepeatingNumber(numbers, 2));
Console.ReadLine();
}
double FindRepeatingNumber (double [] numbers, int RepeatLevel)
{
Array.Sort(numbers);
double numberFound = -1;
double secondRankedNumberFound = -1;
double currentNumber = numbers[0];
int counter = 1;
int higherCounter = 1;
int secondRankedCounter = 1;
for (int i= 1; i< numbers.Length; i++)
{
if (currentNumber == numbers[i])
{
counter++;
}
else
{
if (higherCounter < counter)
{
secondRankedCounter = higherCounter;
higherCounter = counter;
if (numberFound != -1)
{
secondRankedNumberFound = numberFound;
}
else
{
secondRankedNumberFound = currentNumber;
}
numberFound = currentNumber;
}
counter = 1;
currentNumber = numbers[i];
}
}
if (higherCounter < counter)
{
secondRankedCounter = higherCounter;
higherCounter = counter;
if (numberFound != -1)
{
secondRankedNumberFound = numberFound;
}
else
{
secondRankedNumberFound = currentNumber;
}
numberFound = currentNumber;
}
return secondRankedNumberFound;
}
}
}
private string SecondMostHighest()
{
int[] nbrs = { 1, 2, 3, 1, 2, 3, 4, 5, 2, 4, 6, 3, 4 };
Dictionary<string,int> result=new Dictionary<string,int>();
foreach (int i in nbrs)
{
if (result.ContainsKey(i.ToString()))
{
result[i.ToString()] = Convert.ToInt32(result[i.ToString()]) + 1;
}
else
{
result.Add(i.ToString(), 1);
}
}
return result.Keys.ToList()[1];
}
static void secondMostRepititedNumber(int[] input){
HashMap<Integer, Integer> map = new HashMap<>();
for (int x: input){
if(map.containsKey(x)){
map.put(x, map.get(x) + 1);
}
else{
map.put(x,1);
}
}
List<Integer> temp = new ArrayList<Integer>( map.values());
Collections.sort(temp);
for (int z : map.keySet()){
if(map.get(z) == temp.get(temp.size() - 2)){
System.out.println("Key is " + z + " & its count " + map.get(z));
break;
}
}
}
static void secondMostRepititedNumber(int[] input){
HashMap<Integer, Integer> map = new HashMap<>();
for (int x: input){
if(map.containsKey(x)){
map.put(x, map.get(x) + 1);
}
else{
map.put(x,1);
}
}
List<Integer> temp = new ArrayList<Integer>( map.values());
Collections.sort(temp);
for (int z : map.keySet()){
if(map.get(z) == temp.get(temp.size() - 2)){
System.out.println("Key is " + z + " & its count " + map.get(z));
break;
}
}
}
static void secondMostRepititedNumber(int[] input){
HashMap<Integer, Integer> map = new HashMap<>();
for (int x: input){
if(map.containsKey(x)){
map.put(x, map.get(x) + 1);
}
else{
map.put(x,1);
}
}
List<Integer> temp = new ArrayList<Integer>( map.values());
Collections.sort(temp);
for (int z : map.keySet()){
if(map.get(z) == temp.get(temp.size() - 2)){
System.out.println("Key is " + z + " & its count " + map.get(z));
break;
}
}
}
import java.util.Arrays;
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
int[] numbers = {1,8,1,2, 3,9,7,6,5,3,2,3, 1};
Arrays.sort(numbers);
Test t = new Test();
for(int n: numbers)
System.out.print(n + " ");
System.out.println(t.sL(numbers));
}
private int sL(int[] arr){
int max=Integer.MIN_VALUE;
int max2=Integer.MIN_VALUE;
int nmax=Integer.MIN_VALUE;
int smax=Integer.MIN_VALUE;
int count=0;
for(int i=0;i<arr.length;i++){
if(i==arr.length - 1 || arr[i]==arr[i+1]){
count++;
if(i==arr.length -1){
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
}
}else{
count++;
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
count = 0;
}
}
System.out.println("\n" + "Max = "+ max + " "+nmax + " second max " + max2 + " " + smax );
return smax;
}
}
import java.util.Arrays;
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
int[] numbers = {1,8,1,2, 3,9,7,6,5,3,2,3, 1};
Arrays.sort(numbers);
Test t = new Test();
for(int n: numbers)
System.out.print(n + " ");
System.out.println(t.sL(numbers));
}
private int sL(int[] arr){
int max=Integer.MIN_VALUE;
int max2=Integer.MIN_VALUE;
int nmax=Integer.MIN_VALUE;
int smax=Integer.MIN_VALUE;
int count=0;
for(int i=0;i<arr.length;i++){
if(i==arr.length - 1 || arr[i]==arr[i+1]){
count++;
if(i==arr.length -1){
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
}
}else{
count++;
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
count = 0;
}
}
System.out.println("\n" + "Max = "+ max + " "+nmax + " second max " + max2 + " " + smax );
return smax;
}
}
import java.util.Arrays;
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
int[] numbers = {1,8,1,2, 3,9,7,6,5,3,2,3, 1};
Arrays.sort(numbers);
Test t = new Test();
for(int n: numbers)
System.out.print(n + " ");
System.out.println(t.sL(numbers));
}
private int sL(int[] arr){
int max=Integer.MIN_VALUE;
int max2=Integer.MIN_VALUE;
int nmax=Integer.MIN_VALUE;
int smax=Integer.MIN_VALUE;
int count=0;
for(int i=0;i<arr.length;i++){
if(i==arr.length - 1 || arr[i]==arr[i+1]){
count++;
if(i==arr.length -1){
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
}
}else{
count++;
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
count = 0;
}
}
System.out.println("\n" + "Max = "+ max + " "+nmax + " second max " + max2 + " " + smax );
return smax;
}
}
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] numbers = {1,8,1,2, 3,9,7,6,5,3,2,3, 1};
Arrays.sort(numbers);
Test t = new Test();
for(int n: numbers)
System.out.println(t.sL(numbers));
}
private int sL(int[] arr){
int max=Integer.MIN_VALUE;
int max2=Integer.MIN_VALUE;
int nmax=Integer.MIN_VALUE;
int smax=Integer.MIN_VALUE;
int count=0;
for(int i=0;i<arr.length;i++){
if(i==arr.length - 1 || arr[i]==arr[i+1]){
count++;
if(i==arr.length -1){
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
}
}else{
count++;
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
count = 0;
}
}
return smax;
}
}
private int sL(int[] arr){
int max=Integer.MIN_VALUE;
int max2=Integer.MIN_VALUE;
int nmax=Integer.MIN_VALUE;
int smax=Integer.MIN_VALUE;
int count=0;
for(int i=0;i<arr.length;i++){
if(i==arr.length - 1 || arr[i]==arr[i+1]){
count++;
if(i==arr.length -1){
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
}
}else{
count++;
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
count = 0;
}
}
return smax;
}
private int sL(int[] arr){
int max=Integer.MIN_VALUE;
int max2=Integer.MIN_VALUE;
int nmax=Integer.MIN_VALUE;
int smax=Integer.MIN_VALUE;
int count=0;
for(int i=0;i<arr.length;i++){
if(i==arr.length - 1 || arr[i]==arr[i+1]){
count++;
if(i==arr.length -1){
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
}
}else{
count++;
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
count = 0;
}
}
return smax;
}
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] numbers = {0, 5, 1, 2, 2, 1, 1, 3, 5, 2, 1};
Arrays.sort(numbers);
Test t = new Test();
System.out.println(t.sL(numbers));
}
private int sL(int[] arr){
int max=Integer.MIN_VALUE;
int max2=Integer.MIN_VALUE;
int nmax=Integer.MIN_VALUE;
int smax=Integer.MIN_VALUE;
int count=0;
for(int i=0;i<arr.length;i++){
if(i==arr.length - 1 || arr[i]==arr[i+1]){
count++;
if(i==arr.length -1){
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
}
}else{
count++;
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
count = 0;
}
}
return smax;
}
}
import java.util.HashMap;
public class MergeTwoArra {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = {2,5,8,9};
int b[] = {6,3,4,7,1};
int c[] = new int[a.length + b.length];
int i =0;
HashMap<Integer,Integer> int_map = new HashMap<Integer,Integer>();
int map_size = a.length;
map_size += b.length;
int value=0;
for(i=0;i<a.length;i++)
{
value = int_map.getOrDefault(a[i], 0);
int_map.put(a[i], ++value);
value = 0;
}
for(i=0;i<b.length;i++)
{
value = int_map.getOrDefault(b[i], 0);
int_map.put(b[i], ++value);
value=0;
}
int count= 0;
for(i=0;i<=map_size;i++)
{
value = int_map.getOrDefault(i, 0);
if (value > 0)
{
for(int j=0;j<value;j++)
{
c[count++] = i;
}
}
}
}
}
I will give a solution using Python.
Let's say you have an array of integers named "arr".
dic = {i:arr.count(i) for i in set(arr)}
sorted(dic.items(), key=lambda x: x[1])[-2][0]
This will give the second most repeating number in arr.
If this is not the solution you are looking for, please let me know.
import java.util.Arrays;
public class GetSecondLastEleemnt {
static int a[] = { 2, 2, 2, 2 ,3};
public static void main(String args[]) {
System.out.println(findSecondLastElement());
Arrays.sort(a);
for (int i : a)
System.out.print(" " + i);
}
public static int findSecondLastElement() {
int maxCount = 1;
int maxElement = a[0];
int secondMaxElement = a[0];
int secondMaxCount = 0;
for (int i = 1; i < a.length; i++) {
int maxCountInLoop = 1;
for (int j = i - 1; j >= 0; j--) {
if (a[i] == a[j])
maxCountInLoop++;
}
if ((maxCountInLoop > maxCount) && (maxElement != a[i])) {
secondMaxCount = maxCount;
maxCount = maxCountInLoop;
secondMaxElement = maxElement;
maxElement = a[i];
} else if (maxElement == a[i]) {
maxCount++;
} else if ((maxCountInLoop > secondMaxCount)) {
secondMaxElement = a[i];
secondMaxCount = maxCountInLoop;
}
}
return secondMaxElement;
}
}
import java.util.Arrays;
public class GetSecondLastEleemnt {
static int a[] = { 2, 2, 2, 2 ,3};
public static void main(String args[]) {
System.out.println(findSecondLastElement());
Arrays.sort(a);
for (int i : a)
System.out.print(" " + i);
}
public static int findSecondLastElement() {
int maxCount = 1;
int maxElement = a[0];
int secondMaxElement = a[0];
int secondMaxCount = 0;
for (int i = 1; i < a.length; i++) {
int maxCountInLoop = 1;
for (int j = i - 1; j >= 0; j--) {
if (a[i] == a[j])
maxCountInLoop++;
}
if ((maxCountInLoop > maxCount) && (maxElement != a[i])) {
secondMaxCount = maxCount;
maxCount = maxCountInLoop;
secondMaxElement = maxElement;
maxElement = a[i];
} else if (maxElement == a[i]) {
maxCount++;
} else if ((maxCountInLoop > secondMaxCount)) {
secondMaxElement = a[i];
secondMaxCount = maxCountInLoop;
}
}
return secondMaxElement;
}
}
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] numbers = {2,5,2,5,4,7,8,5,2,6,5,6,5,4,1,2,3,6,5,9,9,8,5,8,12};
int answer = -1;
if (numbers.length == 0 || numbers.length == 1)
System.out.println ("There are not enough elements in the array.");
Arrays.sort(numbers);
answer = numbers[numbers.length - 1];
for (int x = numbers.length - 2; x >= 0; x--) {
if (answer != numbers[x]) {
answer = numbers[x];
break;
}
}
if (answer == numbers[numbers.length-1])
System.out.println("There is only one number in the array : " + answer);
else
System.out.println ("The answer is :" + answer);
}
}
public int secondRepeating(int [] arr){
if(arr == null || arr.length == 0) //boundry
return -1;
Arrays.sort(arr);
int freq = 1;// count the freq of numbers
int maxFreq = 1;
int mostRepeating = arr[0];
int secondRepeating = -1;
for(int i = 1; i < arr.length; i++){
if(arr[i] == arr[i-1]){
freq++;
if(maxFreq < freq){
maxFreq = freq;
mostRepeating = arr[i];
}
}
else{//we start new numbers
freq = 1;
}
}
maxFreq = -1;
for(int i = 0; i < arr.length; i++){
if(arr[i] == mostRepeating){
continue;
}
else if(arr[i] == arr[i-1]){
freq++;
if(freq > maxFreq){
maxFreq = freq;
secondRepeating = arr[i];
}
}
else{
freq = 1;
}
}
return secondRepeating; //return -1 if there is no second Repeating
}
Sort the array using selection sort.
Go through the array and remove the biggest block of repeating numbers
GO through the array again and the biggest block of repeating numbers wills be the second highest number
We can use the fact that array[duplicateValue] is referenced to the same value when we traverse array. So if we mark array[duplicateValue] in the array as traversed in first time and figure out it in the next time then it's duplicate value. To mark value as traversed we can change it to negative one. O(n) algorithm without extra space
private static int FindDuplicatesWithoutExtraSpace()
{
int[] array = { 1, 3, 5, 2, 4, 1, 5, 6, 7, 3 };
int secondDuplicatedValue = -1;
int duplicateCount = 0;
for (int i = 0; i < array.Length; i++)
{
int value = Math.Abs(array[i]);
if (array[value] > 0)
{
array[value] = -array[value]; // mark value with negative sign as first time discovered
}
else
{
// Already negative value. It's duplicated value
if (++duplicateCount == 2)
{
// set as second duplicated value
secondDuplicatedValue = value;
break;
}
}
}
// Return values to original state
for (int i = 0; i < array.Length; i++)
{
array[i] = Math.Abs(array[i]);
}
return secondDuplicatedValue;
}
Limitations of input data: positive numbers and less than length of array
private int sL(int[] arr){
int max=Integer.MIN_VALUE;
int max2=Integer.MIN_VALUE;
int nmax=Integer.MIN_VALUE;
int smax=Integer.MIN_VALUE;
int count=0;
for(int i=0;i<arr.length;i++){
if(i==arr.length - 1 || arr[i]==arr[i+1]){
count++;
if(i==arr.length -1){
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
}
}else{
count++;
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
count = 0;
}
}
return smax;
}
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] numbers = {1,8,1,2, 3,9,7,6,5,3,2,3, 1};
Arrays.sort(numbers);
Test t = new Test();
for(int n: numbers)
System.out.println(t.sL(numbers));
}
private int sL(int[] arr){
int max=Integer.MIN_VALUE;
int max2=Integer.MIN_VALUE;
int nmax=Integer.MIN_VALUE;
int smax=Integer.MIN_VALUE;
int count=0;
for(int i=0;i<arr.length;i++){
if(i==arr.length - 1 || arr[i]==arr[i+1]){
count++;
if(i==arr.length -1){
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
}
}else{
count++;
if(max < count){
smax=nmax;
max2=max;
max = count;
nmax=arr[i];
}else if(count < max && count > smax){
smax=arr[i];
max2=count;
}
count = 0;
}
}
return smax;
}
}
Use quick sort to sort the array (no extra space used and complexity is nlogn, ofcourse worse case complexity is n^2). Loop through and find the max and pre_max (pre_max would be assinged when you get something count greater than current max, so current max would be pre_max). Ouput pre_max
- JK April 02, 2015