Amazon Interview Question
Applications DevelopersCountry: United States
Interview Type: In-Person
import java.util.HashMap;
public class Pyramid {
public static void main(String[] args) {
int a[] = { 4, 5, 6, 7, 8, 9, 5, 5, 3, 4, 12, 5 };
HashMap<Integer, Boolean> hm = new HashMap<Integer, Boolean>();
for (int x : a) {
if (hm.get(x) == null) {
hm.put(x, false);
} else {
Boolean b = hm.get(x);
if (b == true)
hm.put(x, false);
else
hm.put(x, true);
}
}
System.out.println("here");
for (int y : a) {
if (hm.get(y)) {
System.out.println("First Even " + y);
break;
}
}
}
}
import java.util.HashMap;
public class Pyramid {
public static void main(String[] args) {
int a[] = { 4, 5, 6, 7, 8, 9, 5, 5, 3, 4, 12, 5 };
HashMap<Integer, Boolean> hm = new HashMap<Integer, Boolean>();
for (int x : a) {
if (hm.get(x) == null) {
hm.put(x, false);
} else {
Boolean b = hm.get(x);
if (b == true)
hm.put(x, false);
else
hm.put(x, true);
}
}
System.out.println("here");
for (int y : a) {
if (hm.get(y)) {
System.out.println("First Even " + y);
break;
}
}
}
}
instead of writing code that is unreadable, it would be better if you can write logic in plain text so that everyone can understand
Balaji, that's not going to work because a HashMap doesn't guarantee storage of the items in the same order that you inserted them. You should use LinkedHashMap.
with a bit more complex data structure it can be solved in O(n) not o(n+k). however the space will be O(n+2k). we need to store the order of items in the hash map somehow.it can be done by having a hashMap<Integer, Node> evenNums as well as a linkedList. the hashMap points to the linked list. every time we see an even number we add it to the evenNums. if we see an odd num, we remove it from the even num (O(1) for updating the hash map and linkedlist). so the answer will be the first item in the linked list.
public static int GetFirstWithEvenAppearance(int[] arr)
{
arr = new int[] { 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 };
var hash = new Hashtable();
foreach (var item in arr)
{
int count = hash[item] != null ? (int)hash[item] : 1;
if (!hash.Contains(item))
hash[item] = count;
else
hash[item] = count + 1;
}
foreach (int item in arr)
{
if ((int)hash[item] % 2 == 0)
return item;
}
return -1;
}
package coding;
import java.util.HashMap;
import java.util.Map;
/**
* Given an array, find the first element that appears an even number of times.
*
* Runtime : O(N)
*/
public class FirstElementWithEvenOccurences {
public static void main(String[] args) {
int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
int[] array2 = {8, 9, 7};
System.out.println(getFirstElementWithEvenOccurences(array1)); // Prints 9
System.out.println(getFirstElementWithEvenOccurences(array2)); // Prints null
}
private static Integer getFirstElementWithEvenOccurences(int[] array) {
Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();
// Compute a map of elements and their even occurences bit
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if ( evenBoolean != null) {
if (evenBoolean) {
evenOccurencesMap.put(array[i], false);
} else {
evenOccurencesMap.put(array[i], true);
}
} else {
evenOccurencesMap.put(array[i], false);
}
}
// Look for the first one
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if (evenBoolean != null && evenBoolean) {
return array[i];
}
}
return null;
}
}
package coding;
import java.util.HashMap;
import java.util.Map;
/**
* Given an array, find the first element that appears an even number of times.
*
* Runtime : O(N)
*/
public class FirstElementWithEvenOccurences {
public static void main(String[] args) {
int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
int[] array2 = {8, 9, 7};
System.out.println(getFirstElementWithEvenOccurences(array1)); // Prints 9
System.out.println(getFirstElementWithEvenOccurences(array2)); // Prints null
}
private static Integer getFirstElementWithEvenOccurences(int[] array) {
Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();
// Compute a map of elements and their even occurences bit
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if ( evenBoolean != null) {
if (evenBoolean) {
evenOccurencesMap.put(array[i], false);
} else {
evenOccurencesMap.put(array[i], true);
}
} else {
evenOccurencesMap.put(array[i], false);
}
}
// Look for the first one
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if (evenBoolean != null && evenBoolean) {
return array[i];
}
}
return null;
}
}
package coding;
import java.util.HashMap;
import java.util.Map;
/**
* Given an array, find the first element that appears an even number of times.
*
* Runtime : O(N)
*/
public class FirstElementWithEvenOccurences {
public static void main(String[] args) {
int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
int[] array2 = {8, 9, 7};
System.out.println(getFirstElementWithEvenOccurences(array1)); // Prints 9
System.out.println(getFirstElementWithEvenOccurences(array2)); // Prints null
}
private static Integer getFirstElementWithEvenOccurences(int[] array) {
Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();
// Compute a map of elements and their even occurences bit
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if ( evenBoolean != null) {
if (evenBoolean) {
evenOccurencesMap.put(array[i], false);
} else {
evenOccurencesMap.put(array[i], true);
}
} else {
evenOccurencesMap.put(array[i], false);
}
}
// Look for the first one
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if (evenBoolean != null && evenBoolean) {
return array[i];
}
}
return null;
}
}
package coding;
import java.util.HashMap;
import java.util.Map;
/**
* Given an array, find the first element that appears an even number of times.
*
* Runtime : O(N)
*/
public class FirstElementWithEvenOccurences {
public static void main(String[] args) {
int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
int[] array2 = {8, 9, 7};
System.out.println(getFirstElementWithEvenOccurences(array1)); // Prints 9
System.out.println(getFirstElementWithEvenOccurences(array2)); // Prints null
}
private static Integer getFirstElementWithEvenOccurences(int[] array) {
Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();
// Compute a map of elements and their even occurences bit
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if ( evenBoolean != null) {
if (evenBoolean) {
evenOccurencesMap.put(array[i], false);
} else {
evenOccurencesMap.put(array[i], true);
}
} else {
evenOccurencesMap.put(array[i], false);
}
}
// Look for the first one
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if (evenBoolean != null && evenBoolean) {
return array[i];
}
}
return null;
}
}
package coding;
import java.util.HashMap;
import java.util.Map;
/**
* Given an array, find the first element that appears an even number of times.
*
* Runtime : O(N)
*/
public class FirstElementWithEvenOccurences {
public static void main(String[] args) {
int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
int[] array2 = {8, 9, 7};
System.out.println(getFirstElementWithEvenOccurences(array1)); // Prints 9
System.out.println(getFirstElementWithEvenOccurences(array2)); // Prints null
}
private static Integer getFirstElementWithEvenOccurences(int[] array) {
Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();
// Compute a map of elements and their even occurences bit
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if ( evenBoolean != null) {
if (evenBoolean) {
evenOccurencesMap.put(array[i], false);
} else {
evenOccurencesMap.put(array[i], true);
}
} else {
evenOccurencesMap.put(array[i], false);
}
}
// Look for the first one
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if (evenBoolean != null && evenBoolean) {
return array[i];
}
}
return null;
}
}
package coding;
import java.util.HashMap;
import java.util.Map;
/**
* Given an array, find the first element that appears an even number of times.
*
* Runtime : O(N)
*/
public class FirstElementWithEvenOccurences {
public static void main(String[] args) {
int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
int[] array2 = {8, 9, 7};
System.out.println(getFirstElementWithEvenOccurences(array1)); // Prints 9
System.out.println(getFirstElementWithEvenOccurences(array2)); // Prints null
}
private static Integer getFirstElementWithEvenOccurences(int[] array) {
Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();
// Compute a map of elements and their even occurences bit
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if ( evenBoolean != null) {
if (evenBoolean) {
evenOccurencesMap.put(array[i], false);
} else {
evenOccurencesMap.put(array[i], true);
}
} else {
evenOccurencesMap.put(array[i], false);
}
}
// Look for the first one
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if (evenBoolean != null && evenBoolean) {
return array[i];
}
}
return null;
}
}
c++ code:
void even_occurance_in_array(void)
{
vector<int> arr;
int n;
int counter;
cout << "\nEnter array numbers:(Insert -1 to exit)\n";//assumed -1 can not be in array. It can be replaced with any invalid number
do{
cin >> n;
if (n != -1)
arr.push_back(n);
} while (n != -1);
for (int i = 0; i < arr.size(); i++)
{
counter = 1;
for (int j = i + 1; j < arr.size() && (arr[i] != -1); j++)
{
if ((arr[j] != -1) && (arr[i] == arr[j]))
{
counter++;
arr[j] = -1;
}
}
if (counter % 2 == 0)
{
cout << "First number " << arr[i] << " has even occurance in the array" << endl;
break;
}
}
import java.util.HashMap;
public class Pyramid {
public static void main(String[] args) {
int a[] = { 4, 5, 6, 7, 8, 9, 5, 5, 3, 4, 12, 5 };
HashMap<Integer, Boolean> hm = new HashMap<Integer, Boolean>();
for (int x : a) {
if (hm.get(x) == null) {
hm.put(x, false);
} else {
Boolean b = hm.get(x);
if (b == true)
hm.put(x, false);
else
hm.put(x, true);
}
}
System.out.println("here");
for (int y : a) {
if (hm.get(y)) {
System.out.println("First Even " + y);
break;
}
}
}
}
C++:
void even_occurance_in_array(void)
{
vector<int> arr;
int n;
int counter;
cout << "\nEnter array numbers:(Insert -1 to exit)\n";//assumed -1 can not be in array. It can be replaced with any invalid number
do{
cin >> n;
if (n != -1)
arr.push_back(n);
} while (n != -1);
for (int i = 0; i < arr.size(); i++)
{
counter = 1;
for (int j = i + 1; j < arr.size() && (arr[i] != -1); j++)
{
if ((arr[j] != -1) && (arr[i] == arr[j]))
{
counter++;
arr[j] = -1;
}
}
if (counter % 2 == 0)
{
cout << "First number " << arr[i] << " has even occurance in the array" << endl;
break;
}
}
}
getFirstEvenIntegerInArray: function(array) {
var hash = {};
for(var i = 0; i < array.length; i++) {
if(hash.hasOwnProperty(array[i])) {
hash[array[i]].count ++;
} else {
hash[array[i]] = { count: 1 };
}
}
for(var i = 0; i < array.length; i ++) {
if(hash[array[i]].count % 2 === 0)
return array[i];
}
return null;
}
public class FirstEvenOccurences {
public static void main(String args[]){
int[] arr = {1,4,3,5,6,2,4,2};
HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
for(int element: arr){
if(map.get(element) == null)
map.put(element, false);
else{
if(map.get(element) == true)
map.put(element, false);
else
map.put(element, true);
}
}
for(int element: arr){
if(map.get(element) == true){
System.out.println("First even occurence: " + element);
break;
}
}
}
}
I think firstly we should ask what type of elements are in array, if it is small integer numbers, we can create a boolean array X with size equal to maximum element, and iterate through given array and make X[arr[i] - 1] = true if its false, otherwise return arr[i].
If the length of given array is greater than the maximum element in array and if elements are nonnegative integers, we can just iterate through given array and check if a[i] < 0 then return i, else a[a[i]] = -a[a[i]],
if elements are not integers or contain negative numbers etc, we can use hashmap to solve it.
package com.concurrency.pkg;
import java.util.LinkedHashMap;
import java.util.Map;
public class FirstElementWithEvenOccurences {
public static void main(String[] args) {
int[] array1 = { 8, 9, 11, 2, 11, 11, 16, 9, 16 };
System.out.println(getFirstElementWithEvenOccurences(array1)); // Prints
// 9
}
private static Integer getFirstElementWithEvenOccurences(int[] array) {
Map<Integer, Integer> allOcurrence = new LinkedHashMap<>();
for (int i = 0; i < array.length; i++) {
Integer keyValue = new Integer(array[i]);
Integer value = allOcurrence.get(keyValue);
value = null != value ? value + keyValue : keyValue;
allOcurrence.put(keyValue, value);
}
Integer parityElement = null;
for (Integer key : allOcurrence.keySet()) {
int div = (allOcurrence.get(key) / key);
if ((div & 1) != 1) {
parityElement = key;
break;
}
}
return parityElement;
}
}
(Java) This function returns all the numbers that appear an even number of times in the array. Time complexity = O(N), space complexity = O(N)
public Set<Integer> evenTimes(List<Integer> arr) {
Set<Integer> result = new HashSet<>();
for (int n : arr) {
if (result.contains(n)) { result.remove(n): }
else { result.add(n): }
}
return result;
}
Ops, just realized that the previous function returns the numbers that appear an odd number of times...
This one returns the first number that appears even times:
public Integer evenTimes(List<Integer> arr) {
HashMap<Integer, boolean> map = new HashMap<>();
for (int n : arr) {
map.put(n, map.contains(n) && !map.get(n));
}
// map values are false (if odd times number) or true (if even times number)
for (int n : map.keySet()) {
if (map.get(n)) {
return n;
}
}
return null;
}
Ops, just realized that the previous function returns the numbers that appear an odd number of times...
This one returns the first number that appears even times:
public Integer evenTimes(List<Integer> arr) {
HashMap<Integer, boolean> map = new HashMap<>();
for (int n : arr) {
map.put(n, map.contains(n) && !map.get(n));
}
// map values are false (if odd times number) or true (if even times number)
for (int n : map.keySet()) {
if (map.get(n)) {
return n;
}
}
return null;
}
import java.util.LinkedHashMap;
import java.util.Map;
public class SearchingElement {
public static void main(String[] args){
LinkedHashMap<Integer,Integer> lh = new LinkedHashMap<Integer, Integer>();
int[] a ={1,2,3,4,5,6,2,3,2,4,3,2,3};
for(int element:a){
if(lh.get(element)==null){
lh.put(element,1);
}
else
lh.put(element,lh.get(element)+1);
}
//for (Map.Entry<Integer,Integer> e: lh.entrySet()){
for (Map.Entry<Integer, Integer> entry : lh.entrySet()){
if(entry.getValue()%2==0)
System.out.println(entry.getKey());
}
}
}
//First even occurence in a array
//Using visited array
#include <iostream>
using namespace std;
# define size 256
int firstEven(int a[],int n){
int num;
int arr[size];
for(int i=0;i<size;i++){
arr[i]=0;
}
for(int j=0;j<n;j++){
if(arr[a[j]]==0) arr[a[j]]=1;
else arr[a[j]]+=1;
if (arr[a[j]]==2) {num=a[j]; break;}
}
return num;
}
int main(){
int a[10] = {1,2,3,2,2,3,2};
int n = sizeof(a)/sizeof(a[0]);
int num = firstEven(a,n);
cout<<num;
}
//First even occurence in a array
//Using visited array
#include <iostream>
using namespace std;
# define size 256
int firstEven(int a[],int n){
int num;
int arr[size];
for(int i=0;i<size;i++){
arr[i]=0;
}
for(int j=0;j<n;j++){
if(arr[a[j]]==0) arr[a[j]]=1;
else arr[a[j]]+=1;
if (arr[a[j]]==2) {num=a[j]; break;}
}
return num;
}
int main(){
int a[10] = {1,2,3,2,2,3,2};
int n = sizeof(a)/sizeof(a[0]);
int num = firstEven(a,n);
cout<<num;
}
public static int findFirstEvenOccuringNumber(int[] numbers) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int number : numbers) {
if(!map.containsKey(number)) {
map.put(number,1);
} else {
map.put(number, map.get(number) + 1);
if(map.get(number)%2 == 0) {
return number;
}
}
}
return -1;
}
public static int findFirstEvenOccuringNumber(int[] numbers) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int number : numbers) {
if(!map.containsKey(number)) {
map.put(number,1);
} else {
map.put(number, map.get(number) + 1);
if(map.get(number)%2 == 0) {
return number;
}
}
}
return -1;
}
public static int findFirstEvenOccuringNumber(int[] numbers) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int number : numbers) {
if(!map.containsKey(number)) {
map.put(number,1);
} else {
map.put(number, map.get(number) + 1);
if(map.get(number)%2 == 0) {
return number;
}
}
}
return -1;
}
public static int findFirstEvenOccuringNumber(int[] numbers) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int number : numbers) {
if(!map.containsKey(number)) {
map.put(number,1);
} else {
map.put(number, map.get(number) + 1);
if(map.get(number)%2 == 0) {
return number;
}
}
}
return -1;
}
We create a hash map with the numbers and have a bit value to each number. So when the number is added for the first time bit will be 1 and then every time we find that number again we will toggle the bit. Then once the hashMap is created will parse through array once again whichever element has bit as 0 will be our number.
HashMap<Integer, boolean>
for each number in array{
if does not exists in hash map then add (num, true)
else toggle the bit associated(if 1 the 0, vice versa)
}
for each number in array{
if bit is 0 in hashmap then return number
}
The only reason I used bit is for storing the even not even part and as it occupies only one bit it saves space as well.
import java.util.LinkedHashMap;
import java.util.Objects;
import java.util.Optional;
import java.util.Set;
public class ArrayUtil {
public static Optional<Integer> getFirstEvenNumber(int[] arr) {
if (Objects.isNull(arr))
throw new NullPointerException("Array Shouldn't be null");
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
for (int data : arr) {
if (!map.containsKey(data)) {
map.put(data, 1);
continue;
}
map.put(data, map.get(data) + 1);
}
Set<Integer> keys = map.keySet();
for (int key : keys) {
if (map.get(key) % 2 == 0) {
return Optional.of(key);
}
}
return Optional.empty();
}
}
C# implementation, it runs in big O (N). More exactly, o (n + k) space and in o(n+k) time where k is the count of even numbers.
- aurelian.lica December 14, 2015