Amazon Interview Question
Quality Assurance EngineersTeam: Amazon Wireless
Country: India
Interview Type: Written Test
public void test() {
int intArray[] = { 1, 2, 3, 3, 4, 5, 5, 5, 6 };
Set<Integer> setInterger = new HashSet<Integer>();
int countOfInteger = 1;
int repeatIntegerValue = 0;
for (int j : intArray) {
Boolean bool = setInterger.add(j);
if (!bool) {
repeatIntegerValue = j;
countOfInteger++;
} else if (bool && countOfInteger > 1) {
System.out.println(" value " + repeatIntegerValue + " count "
+ countOfInteger);
countOfInteger = 1;
}
}
}
public void test() {
int intArray[] = { 1, 2, 3, 3, 4, 5, 5, 5, 6 };
Set<Integer> setInterger = new HashSet<Integer>();
int countOfInteger = 1;
int repeatIntegerValue = 0;
for (int j : intArray) {
Boolean bool = setInterger.add(j);
if (!bool) {
repeatIntegerValue = j;
countOfInteger++;
} else if (bool && countOfInteger > 1) {
System.out.println(" value " + repeatIntegerValue + " count "
+ countOfInteger);
countOfInteger = 1;
}
}
}
Code uses BST and uses Log(n) time. Can be done in contant time using hash tables, but will need extra space.
class RepeatedCount{
private static class BST{
private static class Node{
private int value;
private int count;
private Node left;
private Node right;
private Node(int val){
value = val;
count = 1;
}
}
private Node root = null;
private void put(int val){
root = put(root, val);
}
private Node put(Node rt, int val){
if(rt == null){
Node node = new Node(val);
return node;
}
if(val < rt.value){
rt.left = put(rt.left, val);
}
else if(val > rt.value){
rt.right = put(rt.right, val);
}
else if(val == rt.value){
rt.count++;
}
return rt;
}
private void traverse(){
traverse(root);
}
private void traverse(Node rt){
if(rt == null) return;
traverse(rt.left);
System.out.println("Value:" + rt.value + " present " + rt.count + "times");
traverse(rt.right);
}
}
public static void printRepeats(Integer[] arr){
System.out.println("printing repeats");
BST bst = new BST();
for(int x:arr){
bst.put(x);
}
bst.traverse();
}
}
How can you write this algo in logn time when you have to read entire array to create BST in On time.
you are reading all values in linear time
+
for each item read, you are going through each node of "linked list" (not a tree - array is sorted already and you are not creating balanced binary tree here)
Worst case is O(n^2)
public static void findReps(int array[])
{
int prev = -1;
int counter = 1;
for( int i : array)
{
if( i != prev )
{
if(counter > 1)
{
System.out.println("bla bla " + prev + " bla " + counter);
counter = 1;
}
}
else
{
++counter;
}
prev = i;
}
//check last item:
if(counter > 1)
{
System.out.println("bla bla " + prev + " bla " + counter);
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int J = 1 ;//initialize
int i= 0;
int Array[] = new int[]{1,2,2,3,3,3,4,5,6,7,7,8,9,9};
for( i=0; i< (Array.length-1); i++)
{
if(Array[i] == Array[i+1])
{ J = J+1;
if( (i+1) == (Array.length-1)) // for the last-1 item if true
{
System.out.println(Array[i] + " is repeated" + J + " times " );
}
continue;
}
if(J>1 )
{
System.out.println(Array[i] + " is repeated" + J + " times " );
J = 1;
}
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int J = 1 ;//initialize
int i= 0;
int Array[] = new int[]{1,1,1,2,3,4,5,6,7,7,8,9,9,10,11,12,13,14,15,15,15,16,16};
for( i=0; i< (Array.length-1); i++)
{
if(Array[i] == Array[i+1])
{
J = J+1;
if( (i+1) == (Array.length-1)) // for the last-1 item if true
{
System.out.println(Array[i] + " is repeated" + J + " times " );
}
continue;
}
if(J>1 )
{
System.out.println(Array[i] + " is repeated" + J + " times " );
J = 1;
}
}
}
}
hello dear what if input is {1111,2,3,4,11,5,6,7}
i think this will print result
1 is repeated 4 times
1 is repeated 2 times
function repeatPrint(str) {
var count = 0;
var arry = str.split('');
for ( var i = 1; i < arry.length; ++i ) {
if ( arry [i-1] == arry [i] ) {
++count;
}
else if ( count != 0 ) {
console.log( arry [i-1]+ " repeated " + (count+1) + " times" );
count = 0;
}
}
if ( count != 0 ) {
console.log( arry [i-1] + " repeated is " + (count+1) + " times" );
}
}
@Test
public void testNumberCount() {
System.out.println("Enter number comma seperated to count ..");
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
System.out.println("entered is :: " + str);
String[] strArr = str.split(",");
List numList = new ArrayList(Arrays.asList(strArr));
List repeatList = new ArrayList();
for(int i=0; i < numList.size(); i++) {
if(Collections.frequency(numList, numList.get(i)) > 1 && !repeatList.contains(numList.get(i))) {
repeatList.add(numList.get(i));
System.out.println("The number " + numList.get(i) + " repeats " + Collections.frequency(numList, numList.get(i)) + " times..");
}
}
}
Array can be sorted or random, For such condition it may be solution like:
var data = [2,9,2,3,4,5,4,5,6,6,7,7,4,7,6,7,5,6,5,7,7,9,8,8,9,2,9,9];
var count = {};
for (var i = 0; i <= data.length-1; ++i) {
var key = data[i];
if(!count.hasOwnProperty(key)){
var num =0;
for(var j=i; j<=data.length-1; j++){
if(data[i]==data[j]){
num += 1;
}
}
count[key]=num;
}
}
console.log(count)
Array can be sorted or random, For such condition it may be solution like:
var data = [2,9,2,3,4,5,4,5,6,6,7,7,4,7,6,7,5,6,5,7,7,9,8,8,9,2,9,9];
var count = {};
for (var i = 0; i <= data.length-1; ++i) {
var key = data[i];
if(!count.hasOwnProperty(key)){
var num =0;
for(var j=i; j<=data.length-1; j++){
if(data[i]==data[j]){
num += 1;
}
}
count[key]=num;
}
}
console.log(count)
var data = [2,9,2,3,4,5,4,5,6,6,7,7,4,7,6,7,5,6,5,7,7,9,8,8,9,2,9,9];
var count = {};
for (var i = 0; i <= data.length-1; ++i) {
var key = data[i];
if(!count.hasOwnProperty(key)){
var num =0;
for(var j=i; j<=data.length-1; j++){
if(data[i]==data[j]){
num += 1;
}
}
count[key]=num;
}
}
console.log(count)
var data = [2,2,3,4,5,4,5,6,6,7,7,4,7,6,7,5,6,5,7,7,9,8,8,9,2,9,9];
var count = {};
for (var i = 0; i <= data.length-1; ++i) {
var key = data[i];
if(!count.hasOwnProperty(key)){
var num =0;
for(var j=i; j<=data.length-1; j++){
if(data[i]==data[j]){
num += 1;
}
}
count[key]=num;
}
}
console.log(count)
This is done in O(n) but uses extra space(HashMap)
public static void main(String[] args) {
int arr[] = {1,2,3,4,5,5,5,6,7,7};
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < arr.length; i++) {
if(map.get(arr[i]) == null){
map.put(arr[i], 1);
}else{
int count = map.get(arr[i]);
map.put(arr[i], ++count);
}
}
Iterator<Integer> it = map.keySet().iterator();
while (it.hasNext()) {
Integer integer = (Integer) it.next();
int count = map.get(integer);
if(count > 1){
System.out.println(integer + " is repeated "+ count+" times");
}
}
}
We can take advantage of the fact that some patterns repeat. So we can check in chunks of say 3 or 5 etc. For example for chunk of 3 if arr[0]==arr[2] we can directly say that the number repeats at least 3 times and skip i to i+3, if not we can go linear. The performance may be a little better than O(N)
public class PrintRepeatPattern {
private static int[] arr = {1,1,1,1,2,3,4,5,5,6,7,7,7,8,8,8};
public static void main(String[] args) {
doPrint(3);
}
private static void doPrint(int skip) {
int cnt = 1, i = 0;
for(; i < arr.length; ) {
if(i > 0 && arr[i] != arr[i-1]) {
print(arr[i-1],cnt);
cnt = 1;
}
if(chunk(i,skip)) {
cnt = cnt + skip - 1;
i += skip;
} else {
if(arr[i] == arr[i - 1]) ++cnt;
++i;
}
}
print(arr[i-1],cnt);
}
private static boolean chunk(int i, int skip) {
return (i + skip - 1 < arr.length && arr[i] == arr[i + skip - 1]);
}
private static void print(int number, int cnt) {
if(cnt > 1) {
System.out.printf("%d occurs %d times\n",number,cnt);
}
}
}
public class RepeatedElements {
public static void main(String args[]) {
int[] array = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
find(array);
}
public static void find(int[] array) {
int i = 0;
int count = 1;
while (i < array.length) {
if (((i+1) != array.length) && array[i] == array[i + 1]) {
count++;
} else {
System.out.println(array[i] + " is repeated " + count
+ " times");
count = 1;
}
i++;
}
}
}
public class RepeatedElements {
public static void main(String args[]) {
int[] array = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
find(array);
}
public static void find(int[] array) {
int i = 0;
int count = 1;
while (i < array.length) {
if (((i+1) != array.length) && array[i] == array[i + 1]) {
count++;
} else {
System.out.println(array[i] + " is repeated " + count
+ " times");
count = 1;
}
i++;
}
}
}
public void findDuplicatesWithoutCollections(int[] intArray)
{
int uniqueIntLocator=0;
int arrayWalker=uniqueIntLocator+1;
int noOfTimesRepeated=1;
while ((uniqueIntLocator<=(intArray.length-1)) && (arrayWalker<=(intArray.length)))
{
if ((intArray.length==1) || (arrayWalker==intArray.length))
{
System.out.println(intArray[uniqueIntLocator] + ":" + "is not repeated");
uniqueIntLocator=arrayWalker;
arrayWalker++;
noOfTimesRepeated=1;
}
else
{
while ((arrayWalker<=(intArray.length-1)) && (intArray[uniqueIntLocator]==intArray[arrayWalker]))
{
noOfTimesRepeated++;
arrayWalker++;
}
if (noOfTimesRepeated>1)
{
System.out.println(intArray[uniqueIntLocator] + ":" + "repeated" + ":" + (noOfTimesRepeated));
uniqueIntLocator=arrayWalker;
arrayWalker++;
noOfTimesRepeated=1;
}
else
{
System.out.println(intArray[uniqueIntLocator] + ":" + "is not repeated");
uniqueIntLocator=arrayWalker;
arrayWalker++;
}
}
}
}
public void findDuplicatesWithoutCollections(String[] stringArray)
{
int uniqueIntLocator=0;
int arrayWalker=uniqueIntLocator+1;
int noOfTimesRepeated=1;
while ((uniqueIntLocator<=(stringArray.length-1)) && (arrayWalker<=(stringArray.length)))
{
if ((stringArray.length==1) || (arrayWalker==stringArray.length))
{
System.out.println(stringArray[uniqueIntLocator] + ":" + "is not repeated");
uniqueIntLocator=arrayWalker;
arrayWalker++;
noOfTimesRepeated=1;
}
else
{
while ((arrayWalker<=(stringArray.length-1)) && (stringArray[uniqueIntLocator]==stringArray[arrayWalker]))
{
noOfTimesRepeated++;
arrayWalker++;
}
if (noOfTimesRepeated>1)
{
System.out.println(stringArray[uniqueIntLocator] + ":" + "repeated" + ":" + (noOfTimesRepeated));
uniqueIntLocator=arrayWalker;
arrayWalker++;
noOfTimesRepeated=1;
}
else
{
System.out.println(stringArray[uniqueIntLocator] + ":" + "is not repeated");
uniqueIntLocator=arrayWalker;
arrayWalker++;
}
}
}
public void findDuplicatesWithoutCollections(int[] intArray)
{
int uniqueIntLocator=0;
int arrayWalker=uniqueIntLocator+1;
int noOfTimesRepeated=1;
while ((uniqueIntLocator<=(intArray.length-1)) && (arrayWalker<=(intArray.length)))
{
if ((intArray.length==1) || (arrayWalker==intArray.length))
{
System.out.println(intArray[uniqueIntLocator] + ":" + "is not repeated");
uniqueIntLocator=arrayWalker;
arrayWalker++;
noOfTimesRepeated=1;
}
else
{
while ((arrayWalker<=(intArray.length-1)) && (intArray[uniqueIntLocator]==intArray[arrayWalker]))
{
noOfTimesRepeated++;
arrayWalker++;
}
if (noOfTimesRepeated>1)
{
System.out.println(intArray[uniqueIntLocator] + ":" + "repeated" + ":" + (noOfTimesRepeated));
uniqueIntLocator=arrayWalker;
arrayWalker++;
noOfTimesRepeated=1;
}
else
{
System.out.println(intArray[uniqueIntLocator] + ":" + "is not repeated");
uniqueIntLocator=arrayWalker;
arrayWalker++;
}
}
}
}
public void findDuplicatesWithoutCollections(String[] stringArray)
{
int uniqueIntLocator=0;
int arrayWalker=uniqueIntLocator+1;
int noOfTimesRepeated=1;
while ((uniqueIntLocator<=(stringArray.length-1)) && (arrayWalker<=(stringArray.length)))
{
if ((stringArray.length==1) || (arrayWalker==stringArray.length))
{
System.out.println(stringArray[uniqueIntLocator] + ":" + "is not repeated");
uniqueIntLocator=arrayWalker;
arrayWalker++;
noOfTimesRepeated=1;
}
else
{
while ((arrayWalker<=(stringArray.length-1)) && (stringArray[uniqueIntLocator]==stringArray[arrayWalker]))
{
noOfTimesRepeated++;
arrayWalker++;
}
if (noOfTimesRepeated>1)
{
System.out.println(stringArray[uniqueIntLocator] + ":" + "repeated" + ":" + (noOfTimesRepeated));
uniqueIntLocator=arrayWalker;
arrayWalker++;
noOfTimesRepeated=1;
}
else
{
System.out.println(stringArray[uniqueIntLocator] + ":" + "is not repeated");
uniqueIntLocator=arrayWalker;
arrayWalker++;
}
}
}
var data = [2,2,3,4,5,4,5,6,6,7,7,4,7,6,7,5,6,5,7,7,9,8,8,9,2,9,9];
var count = {};
for (var i = 0; i <= data.length-1; ++i) {
var key = data[i];
if(!count.hasOwnProperty(key)){
var num =0;
for(var j=i; j<=data.length-1; j++){
if(data[i]==data[j]){
num += 1;
}
}
count[key]=num;
}
}
console.log(count)
var data = [2,2,3,4,5,4,5,6,6,7,7,4,7,6,7,5,6,5,7,7,9,8,8,9,2,9,9];
var count = {};
for (var i = 0; i <= data.length-1; ++i) {
var key = data[i];
if(!count.hasOwnProperty(key)){
var num =0;
for(var j=i; j<=data.length-1; j++){
if(data[i]==data[j]){
num += 1;
}
}
count[key]=num;
}
}
console.log(count)
var data = [2,2,3,4,5,4,5,6,6,7,7,4,7,6,7,5,6,5,7,7,9,8,8,9,2,9,9];
var count = {};
for (var i = 0; i <= data.length-1; ++i) {
var key = data[i];
if(!count.hasOwnProperty(key)){
var num =0;
for(var j=i; j<=data.length-1; j++){
if(data[i]==data[j]){
num += 1;
}
}
count[key]=num;
}
}
console.log(count)
var data = [2,2,3,4,5,4,5,6,6,7,7,4,7,6,7,5,6,5,7,7,9,8,8,9,2,9,9];
var count = {};
for (var i = 0; i <= data.length-1; ++i) {
var key = data[i];
if(!count.hasOwnProperty(key)){
var num =0;
for(var j=i; j<=data.length-1; j++){
if(data[i]==data[j]){
num += 1;
}
}
count[key]=num;
}
}
console.log(count)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace consoleApp
{
class Program
{
static void Main(string[] args)
{
int[] array = new int[] {0,1,2,3,4,5,6,7,8,1,2,3,3,3,3,4,4,4,5,6,77,88,9,0,0,9,9 };
int[] array1 = new int[array.Length];
List<int> list = new List<int> (array.Length) ;
for (int i = 0; i < array.Length; i++ )
{
bool found = false;
for (int j = 0; j < i; j++ )
{
if(array[j] == array[i])
{
found = true;
break;
}
}
if (!found)
{
list.Add(array[i]);
}
}
array1 = list.ToArray();
for (int i = 0; i < array1.Length; i++)
{
Console.WriteLine(array1[i]);
}
RepeatNumebr(array,array1);
Console.ReadKey();
}
static void RepeatNumebr(int [] num, int [] unique)
{
int count = 0;
for (int i = 0; i < unique.Length;i++ )
{
count = 0;
for (int j = 0; j < num.Length;j++ )
{
if(unique[i] == num[j])
{
count++;
}
}
Console.WriteLine("This number {0} has repitition :{1}",unique[i],count);
}
}
}
}
class Program
{
static void Main(string[] args)
{
int[] array = new int[] {0,1,2,3,4,5,6,7,8,1,2,3,3,3,3,4,4,4,5,6,77,88,9,0,0,9,9 };
int[] array1 = new int[array.Length];
List<int> list = new List<int> (array.Length) ;
for (int i = 0; i < array.Length; i++ )
{
bool found = false;
for (int j = 0; j < i; j++ )
{
if(array[j] == array[i])
{
found = true;
break;
}
}
if (!found)
{
list.Add(array[i]);
}
}
array1 = list.ToArray();
for (int i = 0; i < array1.Length; i++)
{
Console.WriteLine(array1[i]);
}
RepeatNumebr(array,array1);
Console.ReadKey();
}
static void RepeatNumebr(int [] num, int [] unique)
{
int count = 0;
for (int i = 0; i < unique.Length;i++ )
{
count = 0;
for (int j = 0; j < num.Length;j++ )
{
if(unique[i] == num[j])
{
count++;
}
}
Console.WriteLine("This number {0} has repitition :{1}",unique[i],count);
}
}
#Python Solution
s = [1, 2, 3, 3, 4, 5, 5, 5, 6]
x = []
for i in range (0, len(s)):
count = 0
if s[i] not in x:
x.append(s[i])
for j in range (0, len(s)):
if s[i] == s[j] :
count = count + 1
#print ("%s is repeated %d times" % (s[i],count))
e = "Salesforce is the best company to work fo"
d=e.lower()
z = []
for i in range (0, len(d)):
count = 0
if d[i] not in z:
z.append(d[i])
for j in range (0, len(d)):
if d[i] == d[j] :
count = count + 1
if count == 1:
print (d[i])
break
else:
print (d[i], count)
Below code is working fine.
public class SampleTest {
public static void main(String[] args) {
try{
int[] a = {1,2,3,3,4};
Map<Integer,Integer> n = new HashMap<>();
for(int i=0;i<a.length;i++){
int b = a[i];
if(n.containsKey(b)){
n.put(b, n.get(b)+1);
} else {
n.put(b, 1);
}
}
System.out.println(n);
} catch(Exception e) {
System.out.println("Exception "+e);
}
}
public static void main(String[] args) {
// Sorted array
int [] array = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };;
int counter = 0;
for( int i = 0; i < array.length; i++ ){
if( ( counter != 0 && ( i + 1) < array.length && array[i] != array[i+1]) || ( counter != 0 && i == array.length -1 ) ){
System.out.println( array[i] + " appread " + ++counter + " times");
counter = 0;
}else if( (i + 1) < array.length && array[i] == array[i+1]){
++counter;
}
}
}
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5, 5, 5, 6, 7, 7, 8};
LinkedHashMap<Integer, Integer> lhm = new LinkedHashMap<>();
for(int i:a) {
if(lhm.containsKey(i)) {
lhm.put(i, lhm.get(i) + 1);
} else {
lhm.put(i, 1);
}
}
Set<Integer> keySet = lhm.keySet();
for(int j:keySet) {
if(lhm.get(j)>1) {
System.out.println(j + " is repeated " + lhm.get(j) + " times.");
}
}
}
- sarbjot singh July 26, 2015