## Amazon Interview Question for Software Engineer in Tests

Country: United States

Comment hidden because of low score. Click to expand.
6
of 6 vote

Algorithm:
1. store array1 in HashMap better to use LinkedHashMap and insert elements as in array1 example B, A, C
2. scan through array2 and increment the count for each B, A , C
3. and read HashMap/LinkedHashMap using array1 keys and print

Comment hidden because of low score. Click to expand.
0

@Anand... LinkedHashMap can be only used here as it will iterate in the order in which the entries were put into the map whereas HashMap makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.

Does anybody know equivalent of LinkedHashMap in C++?

Comment hidden because of low score. Click to expand.
0

@Anand: If you put array1 in hash map you will be missing the extra elements of array which are not present in array 1. So its better to put array 2 in hash map.

Comment hidden because of low score. Click to expand.
2
of 2 vote

it looks like we could use the count sort, the complexity should be linear

Comment hidden because of low score. Click to expand.
0
of 0 vote

Instead of Array.IndexOf I should have used Hashtable to make the complexity O(n).
Otherwise this is sorting based on the first array and adding extra elements(whose order is unknown) to the end.
Any improvements?

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace SortArrayUsingDiffRule
{
class Program
{
static char[] arr = new char[] {'B','A','C'};
static char[] Sort = new char[] {'D', 'A', 'B', 'A', 'C', 'A', 'B', 'B', 'C', 'A' };
static int[] Count = new int[arr.Length];
static List<char> Extras = new List<char>();
static void Main(string[] args)
{
for (int i = 0; i < Sort.Length; i++)
{
int index = Array.IndexOf(arr, Sort[i]);
if (index != -1)
{
Count[index]++;
}
else
{
}
}

int j = 0;
int k = 0;
while(j<Count.Length)
{
while (Count[j] > 0)
{
Sort[k]=arr[j];
Count[j]-- ;
k++;
}
j++;
}
for (int i = 0; i < Extras.Count; i++)
{
Sort[k++] = Extras[i];
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Pseudocode

``````orderArray = {"C","A","B"}
inputArray={"A", "C", "B", "B", C, A, B, C, C, A, A, B, A B, C B B}

create a counterarray of size orderArray

for each element in inputArray
counterarray[index of element in orderarray] ++ ; // assume no other inputs
end for

print orderArray[i] element countarray[i] times``````

Should be O(n) (unless the remainder array needs to be resorted (you can shift those to end and run quicksort)

Comment hidden because of low score. Click to expand.
0

Time complexity is O(m.n) not O(n)....because you are traversing the counterarray and for printing each element it is O(n)....please correct me if I am wrong

Comment hidden because of low score. Click to expand.
0

@Anuj is right finding index of element in orderarray will take m operation(m is length of orderArray) hence O(nm)

Comment hidden because of low score. Click to expand.
0
of 0 vote

The answer which interviewer will be looking for will be of O(size of a1)(sizeofa2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

If the sorting needs to be done based on only 3 character in a1, ideal solution is to go with 3 colored problem, wherein we sort the number based on 4 pointer. The algorithm says that any char that belongs to type 1 should go to initial part of array and type 3 should go towards end.

Code to explain this is as follow

``````private static char[] sortSecBasedOnFirst(char[] a1, String str) {
int len = str.length();
char[] output = new char[len];
Map<Character, Integer> map = new HashMap<Character, Integer>();
int index = 1;
for(char c : a1){
map.put(c, index++);
}
int indexForFirst = 0;
int indexForMiddle = 0;
int indexForLast = len - 1;
int indexForDefault = len -1;
for(int i = 0; i < len ; i++){
char c = str.charAt(i);
Integer ind = map.get(c);
if(ind == null ){
ind = -1;
}
switch (ind) {
case 1:
output[indexForMiddle++] = output[indexForFirst];
output[indexForFirst++] = c;

break;
case 2:
output[indexForMiddle++] = c;
break;
case 3:
output[indexForLast--] = c;
break;

default:
output[indexForLast-- ] = output[indexForDefault];
output[indexForDefault--] = c;
break;
}
}
return output;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class CountingSortAlpha {

public static char[] sort(char[] a, char[] b) {
char[] c = new char[a.length];
char[] ref = new char[b.length];

for (char ch : a) {
for(int i = 0; i < b.length; i++)
if (ch == b[i]) {
ref[i]++;
break;
}
}

for(int i = 1; i < ref.length; i++)
ref[i] += ref[i - 1];

for(int i = a.length - 1; i >= 0; i--) {
c[ref[index(a[i], b)] - 1] = a[i];
ref[index(a[i], b)]--;
}

return c;
}

private static int index(char ch, char[] b) {
for (int i = 0; i < b.length; i++)
if (b[i] == ch)
return i;
return 0;
}

public static void main(String args[]) {
char[] a = {'A', 'B', 'A', 'C', 'A', 'B', 'B', 'C', 'A'};
char[] b = {'B', 'A', 'C'};
for (char c : a)
System.out.print(c + " ");
System.out.println();
char[] c = sort(a, b);
for (char ch : c)
System.out.print(ch + " ");
System.out.println();
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi this solution could be easy adding to the solution :
public class Arry_Sort {
public static void main(String args[]){

char[] array1 = {'B', 'A', 'C'};
char[] array2 = {'A', 'B', 'A', 'C', 'A', 'B', 'B', 'C', 'A'};

for(int i=0;i<array1.length;i++){
for(int j=0;j<array2.length;j++){

if(array1[i]==array2[j]){
System.out.print(array2[j]);
}
}

}

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````function sort_rule(\$rule,\$subject) {
\$rule_length = count(\$rule);
\$subject_length = count(\$subject);
\$pos_to_insert = 0;
\$temp = '';

for(\$i=0; \$i<\$rule_length; \$i++) {
for(\$j=\$pos_to_insert; \$j<\$subject_length; \$j++) {
if(\$subject[\$j]==\$rule[\$i]) {
\$temp = \$subject[\$pos_to_insert];
\$subject[\$pos_to_insert] = \$subject[\$j];
\$subject[\$j] = \$temp;
\$pos_to_insert++;
}
}
}

print_r(\$subject);
}

sort_rule(['B','A','C'],['A','B','A','C','A','B','B','C','A']);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang.*;
public class ArraySort {
public static void main(String[] args) {
char[] ch1= {'A', 'B', 'A', 'C', 'A', 'B', 'B', 'C', 'A'};
char[] ch2= {'A', 'B', 'C'};
char[]ch3=new char[ch1.length];
int k=0;
for (int i=0;i<ch2.length;i++){
for(int j=0;j<ch1.length;j++){
if((Character.toUpperCase(ch2[i])==Character.toUpperCase(ch1[j]))){
ch3[k]=ch1[j];
k++;
}}}
System.out.println(ch3);}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

my @arr = (B,A,C);
my @array = (A,B,C,C,A,B,B,A,C);
my @sort;
my \$i=0;
for(\$i=0;\$i<scalar(@arr);\$i++)
{
push @sort, grep { \$_ eq \$arr[\$i] } @array;
}
print "Array: @sort \n";

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;
import java.util.Comparator;

public class CompareCharacter implements Comparator<Character> {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

Character[] c={'A','B','A','C','A','B','B','C','A','F','D','T'};
Arrays.sort(c, new CompareCharacter());
//System.out.println(c);
for (Character each : c)
{
System.out.println(each);
}

}

@Override
public int compare(Character o1, Character o2) {
if ((o1=='A' || o1== 'a') && (o2=='B' || o1== 'B')) return 1;
else if ((o1=='B' || o1== 'b') && (o2=='A' || o1== 'a')) return -1;
else {
return o1.compareTo(o2);
}

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.ArrayList;
import java.util.List;

public class OddIntegerArray{
public static void main(String[] args){
int[] a={1,2,2,4,1,3,6,6,6,7,7,7,7,7};
List aList1=new ArrayList();
List aList2=new ArrayList();
int j=0,k=0;
for(int i=0; i<a.length; i++) {
if(aList1.contains(a[i])){
k=aList1.indexOf(a[i]);
j=(Integer) aList2.get(k);
aList2.remove(k);
}
else{
j=aList1.size();
}
}

for(int i=0;i<aList2.size();i++){
int a1=(Integer) aList2.get(i);
if((a1%2)!=0){
System.out.println(aList1.get(i));

}

}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
// TODO Auto-generated method stub

int[]a=new int[]{1,2,2,4,1,3,6,6,6,7,7,7,7,7};
int b[]=new int[]{1,2,4,3,6,7};
int[]res=new int[a.length];
int i,j,k=0;
for(i=0;i<b.length;i++)
{
for(j=0;j<a.length;j++)
{

if(b[i]==a[j])
{
res[k]=a[j];
k++;
}
}

}
for( k=0;k<res.length;k++)
System.out.println(res[k]);
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

cannot understand what you want in output

Comment hidden because of low score. Click to expand.
0

according to the rule of array1, to sort the array2... i think it is not difficult to understand it...

Comment hidden because of low score. Click to expand.
-1
of 3 vote

1. hash in the range of 1 to length of array1
B => 3
A => 2
C => 1

2. Quick sort array2 with comparison based on hashed value of character.

complexity : O(n) + O(nlogn)

Comment hidden because of low score. Click to expand.
0

I agree. This should be the answer.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

STL sort algorithm can be used with third parameter providing a "less" function which does:

``````bool less(char &a, char &b)
{
return if index of a in the "ordering" vector is less then index of b in the "ordering" vector
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.