Amazon Interview Question Quality Assurance Engineers
Country: India
Solution with PriorityQueue is not the best solution, since you using additional space. It can be done without PrirorityQueue using two indexes for pos and neg - O(n) time
def sort_positive_negative(arr):
i = 0
while i<len(arr)-1:
if arr[i]>0 and arr[i+1]<0:
i += 2
elif arr[i]<0 and arr[i+1]>0:
arr[i], arr[i+1] = arr[i+1], arr[i]
i += 2
else:
postive = 1
if arr[i]>0:
postive = -1
for j in range(i+2, len(arr)):
if postive*arr[j]>0:
arr[j-1], arr[j] = arr[j], arr[j-1]
break
return arr
if __name__=='__main__':
data = [
[
[-1, 6, 9, -4, -10, -9, 8, 8, 4],
[6, -1, 9, -4, 8, -10, 8, -9, 4]
]
]
for d in data:
print('input', d[0], 'sort postive-negetive', sort_positive_negative(d[0]), 'expected', d[1])
def sort_pos_neg(il):
for i in range(len(il)):
if i % 2 == 0:
# @i expects a positive num
if il[i] < 0:
for j in range(i+1, len(il)):
if il[j] >= 0:
# Swap the items @ i and j
il[j], il[i] = il[i], il[j]
break
else:
# @i expects a negative num
if il[i] >= 0:
for j in range(i+1, len(il)):
if il[j] < 0:
# Swap the items @ i and j
il[j], il[i] = il[i], il[j]
break
return il
public static int[] sortPositiveNegative(int []arr) {
int pos=0,neg=0;
int sortedArr[] = Arrays.copyOf(arr,arr.length);
for(int i=0;i<arr.length-1;i++) {
while(arr[pos]<0) {
pos++;
}
sortedArr[i]=arr[pos++];
i++;
while(arr[neg]>0 ) {
neg++;
}
if(i<arr.length)
sortedArr[i]=arr[neg++];
}
return sortedArr;
}
def function1() :
for i in range(0,len(a)):
#print("Element ",a[i])
if (i % 2 == 0):
#print("Positive index",i)
if(a[i]<0) :
#print("Negative element .. Finding next positive...")
find_next_positive_swap(i)
elif (i%2 ==1):
#print("Negative index",i)
if(a[i]>0):
#print("Positive element .. Finding next negative...")
find_next_negative_swap(i)
return
def find_next_negative_swap(i) :
for j in range(i,len(a)):
if(a[j]<0):
ele=a[j]
del a[j]
a.insert(i,ele)
#print(a)
return
return
def find_next_positive_swap(i):
for j in range(i,len(a)):
if(a[j]>0) :
ele=a[j]
del a[j]
a.insert(i,ele)
#print(a)
return
return
a=[-1, 6, 9, -4, -10, -9, 8, 8, 4]
function1()
a
[6, -1, 9, -4, 8, -10, 8, -9, 4]
Ruby
def sort_positive_negative(array)
pos_arr = []
neg_arr = []
while array.size > 0
if array.first >= 0
pos_arr << array.shift
else
neg_arr << array.shift
end
end
until pos_arr.size == 0 && neg_arr.size == 0
array << pos_arr.shift if pos_arr.size > 0
array << neg_arr.shift if neg_arr.size > 0
end
end
arr = Array.new(10000000) { rand(-10...10) }
Benchmark: 1.310000 0.040000 1.350000 ( 1.409556)
def sort_positive_negative(array)
pos_arr = []
neg_arr = []
while array.size > 0
if array.first >= 0
pos_arr << array.shift
else
neg_arr << array.shift
end
end
until pos_arr.size == 0 && neg_arr.size == 0
array << pos_arr.shift if pos_arr.size > 0
array << neg_arr.shift if neg_arr.size > 0
end
end
#Ascending and descending sorting functionality for neg to positive numbers
def myThirdQ():
print('given mixed elements are getting displayed in sortted order')
a=[1,-5,8,-3,0,7,3,8,9,10]
b = [1,1,0,1,0,1,1,1,1,0,0,1,0,1]
a.sort()
print(a)
b.sort()
print(b)
a.sort(reverse=True)
print(a)
b.sort(reverse=True)
print(b)
myThirdQ()
#Ascending and descending sorting functionality for neg to positive numbers
def myThirdQ():
print('given mixed elements are getting displayed in sortted order')
a=[1,-5,8,-3,0,7,3,8,9,10]
b = [1,1,0,1,0,1,1,1,1,0,0,1,0,1]
a.sort()
print(a)
b.sort()
print(b)
a.sort(reverse=True)
print(a)
b.sort(reverse=True)
print(b)
myThirdQ()
List<Integer> list = new ArrayList<>( );
list.add( -1 );list.add( 6 );
list.add( 9 );list.add( -4 );
list.add( -10 );list.add( -9 );
list.add( 8 );list.add( 8 );list.add( 4 );
List<Integer> tempList = new ArrayList<>( list );
List<Integer> result = new ArrayList<>( );
Collections.sort( tempList , (o1, o2) -> (o1>0)? -1:1 );
int firstNegativeElementIndex = 0;
for(int i=0; i<tempList.size();i++){
if(tempList.get( i )<0){
firstNegativeElementIndex = i;
break;
}
}
for(int i=0;firstNegativeElementIndex -i>0;i++){
result.add( tempList.get( firstNegativeElementIndex-1 -i ) );
if(firstNegativeElementIndex +i < tempList.size())
result.add( tempList.get( firstNegativeElementIndex +i ) );
}
System.out.println(result);
let array = [-1,6,9,-4,-10,-9,8,8,4];
function positiveNegativeArray(originalArray){
let positiveArray = [];
for(let i of originalArray){
if(i > 0) positiveArray.push(i);
}
let negativeArray = [];
for(let i of originalArray){
if(i < 0) negativeArray.push(i);
}
let pos = 0, neg = 0;
for(let i=0; i < originalArray.length; i++){
if(positiveArray && pos > positiveArray.length - 1) positiveArray = null;
if(negativeArray && neg > negativeArray.length - 1) negativeArray = null;
if((i % 2 === 0 || !negativeArray) && positiveArray){
originalArray[i] = positiveArray[pos];
++pos;
}else{
originalArray[i] = negativeArray[neg];
++neg;
}
}
return originalArray;
}
positiveNegativeArray(array);
def main():
pos_neg_order()
def pos_neg_roder():
l = [-1, 6, 9, -4, -10, -9, 8, 8, 4, -5,-11]
posList =[]
negList =[]
for i in range(len(l)):
if l[i] > 0 : posList.append(l[i])
else: negList.append(l[i])
myL = zip(posList, negList)
print(posList)
print(negList)
myL = list(myL)
if len(posList)>len(negList): [myL.append(posList[x]) for x in range(len(negList), len(posList))]
if len(negList)>len(posList): [myL.append(negList[x]) for x in range(len(posList), len(negList))]
print(list(myL))
main()
{def main():
pos_neg_order()
def pos_neg_roder():
l = [-1, 6, 9, -4, -10, -9, 8, 8, 4, -5,-11]
posList =[]
negList =[]
for i in range(len(l)):
if l[i] > 0 : posList.append(l[i])
else: negList.append(l[i])
myL = zip(posList, negList)
print(posList)
print(negList)
myL = list(myL)
if len(posList)>len(negList): [myL.append(posList[x]) for x in range(len(negList), len(posList))]
if len(negList)>len(posList): [myL.append(negList[x]) for x in range(len(posList), len(negList))]
print(list(myL))
main() }
def main():
pos_neg_order()
def pos_neg_roder():
l = [-1, 6, 9, -4, -10, -9, 8, 8, 4, -5,-11]
posList =[]
negList =[]
for i in range(len(l)):
if l[i] > 0 : posList.append(l[i])
else: negList.append(l[i])
myL = zip(posList, negList)
print(posList)
print(negList)
myL = list(myL)
if len(posList)>len(negList): [myL.append(posList[x]) for x in range(len(negList), len(posList))]
if len(negList)>len(posList): [myL.append(negList[x]) for x in range(len(posList), len(negList))]
print(list(myL))
main()
def main():
pos_neg_order()
def pos_neg_roder():
l = [-1, 6, 9, -4, -10, -9, 8, 8, 4, -5,-11]
posList =[]
negList =[]
for i in range(len(l)):
if l[i] > 0 : posList.append(l[i])
else: negList.append(l[i])
myL = zip(posList, negList)
print(posList)
print(negList)
myL = list(myL)
if len(posList)>len(negList): [myL.append(posList[x]) for x in range(len(negList), len(posList))]
if len(negList)>len(posList): [myL.append(negList[x]) for x in range(len(posList), len(negList))]
print(list(myL))
main()
def main():
pos_neg_order()
def pos_neg_roder():
l = [-1, 6, 9, -4, -10, -9, 8, 8, 4, -5,-11]
posList =[]
negList =[]
for i in range(len(l)):
if l[i] > 0 : posList.append(l[i])
else: negList.append(l[i])
myL = zip(posList, negList)
print(posList)
print(negList)
myL = list(myL)
if len(posList)>len(negList): [myL.append(posList[x]) for x in range(len(negList), len(posList))]
if len(negList)>len(posList): [myL.append(negList[x]) for x in range(len(posList), len(negList))]
print(list(myL))
main()
def main():
pos_neg_order()
def pos_neg_roder():
l = [-1, 6, 9, -4, -10, -9, 8, 8, 4, -5,-11]
posList =[]
negList =[]
for i in range(len(l)):
if l[i] > 0 : posList.append(l[i])
else: negList.append(l[i])
myL = zip(posList, negList)
print(posList)
print(negList)
myL = list(myL)
if len(posList)>len(negList): [myL.append(posList[x]) for x in range(len(negList), len(posList))]
if len(negList)>len(posList): [myL.append(negList[x]) for x in range(len(posList), len(negList))]
print(list(myL))
main()
Recursive Approach
def algo(n=0,p=0,flist=[]):
if n==len(neg)-1:
flist.extend(pos[n:])
return flist
if p==len(pos)-1:
flist.extend(neg[p:])
return flist
if n<len(neg) and p < len(pos):
flist.append(pos[n])
flist.append(neg[n])
return algo(n+1,p+1,flist)
l = [-1,6,9,-4,-10,-9,8,8,4]
neg = [ _ for _ in l if _ <0 ]
pos = [ _ for _ in l if _ >=0 ]
print(algo())
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = { -1, 6, 9, -4, -10, -9, 8, 8, 4 };
int len = arr.length;
int k[] = new int[len];
int pos = 0;
int neg = 1;
for (int i = 0; i < len; i++) {
if (arr[i] > 0) {
k[pos] = arr[i];
pos = pos + 2;
}
if (arr[i] < 0) {
k[neg] = arr[i];
neg = neg + 2;
}
}
System.out.println(Arrays.toString(k));
}
list_positive = [x for x in list_m if x > 0]
list_nagative = [x for x in list_m if x < 0]
print(list_positive)
def list_nag_order(list_po,list_na):
ln = len(list_po) + len(list_na)
result_list = [None] * ln
if len(list_na)<len(list_po):
for i in range(len(list_na)*2):
if i % 2 == 0:
result_list[i] = list_po[int(i/2)]
else:
result_list[i] = list_na[int(i/2)]
for x in range(len(list_na)*2,len(result_list)):
result_list[x] = list_po[int(x/2)]
if len(list_na) == len(list_po):
for i in range(len(list_na)*2):
if i % 2 == 0:
result_list[i] = list_po[int(i/2)]
else:
result_list[i] = list_na[int(i/2)]
if len(list_na) > len(list_po):
for i in range(len(list_po)*2):
if i % 2 == 0:
result_list[i] = list_po[int(i/2)]
result_list[i] = list_na[int(i/2)]
for x in range(len(list_po)*2,len(result_list)):
result_list[x] = list_po[int(x/2)]
return result_list
print(list_nag_order(list_positive,list_nagative))
public static int[] sortArrays(int[] arr) {
int i = 0;
int j = 1;
while(i<arr.length && j<arr.length) {
while(i<arr.length && arr[i]<0) {
i+=2;
}
while(j<arr.length && arr[j]>=0) {
j+=2;
}
if (i<arr.length && j<arr.length) {
int temp =arr[i];
arr[i] = arr[j];
arr[j] = temp;
i+=2;
j+=2;
}
}
return arr;
}
public static int[] sortArrays(int[] arr) {
int i = 0;
int j = 1;
while(i<arr.length && j<arr.length) {
while(i<arr.length && arr[i]<0) {
i+=2;
}
while(j<arr.length && arr[j]>=0) {
j+=2;
}
if (i<arr.length && j<arr.length) {
int temp =arr[i];
arr[i] = arr[j];
arr[j] = temp;
i+=2;
j+=2;
}
}
return arr;
}
array =[-1, 6, 9, -4, -10, -9, 8, 8, 4]
def sort_positive_negative(array)
pos_arr = []
neg_arr = []
while array.size > 0
if array.first >= 0
pos_arr << array.shift
else
neg_arr << array.shift
end
end
until pos_arr.size == 0 && neg_arr.size == 0
array << pos_arr.shift if pos_arr.size > 0
array << neg_arr.shift if neg_arr.size > 0
end
return array
end
res = sort_positive_negative(array)
puts res
public class ArrangeNum{
public static void main(String []args){
int arr[] = {-1,6,9,-4,-10,-9,8,8,4};
int arrsize = arr.length;
int newarr[] = new int [arrsize];
int pos = 0;
int neg = 1;
for (int i=0; i<arrsize; i++){
if (arr[i]>0){
newarr[pos] = arr[i];
pos+=2;
}
else if (arr[i]<0){
newarr[neg] = arr[i];
neg+=2;
}
}
for (int j=0; j<arrsize; j++){
System.out.print(+newarr[j]+",");
}
}
}
public class HelloWorld{
public static void main(String []args){
int arr[] = {-1,6,9,-4,-10,-9,8,8,4};
int arrsize = arr.length;
int newarr[] = new int [arrsize];
int pos = 0;
int neg = 1;
for (int i=0; i<arrsize; i++){
if (arr[i]>0){
newarr[pos] = arr[i];
pos+=2;
}
else if (arr[i]<0){
newarr[neg] = arr[i];
neg+=2;
}
}
for (int j=0; j<arrsize; j++){
System.out.print(+newarr[j]+",");
}
}
}
public class HelloWorld{
public static void main(String []args){
int arr[] = {-1,6,9,-4,-10,-9,8,8,4};
int arrsize = arr.length;
int newarr[] = new int [arrsize];
int pos = 0;
int neg = 1;
for (int i=0; i<arrsize; i++){
if (arr[i]>0){
newarr[pos] = arr[i];
pos+=2;
}
else if (arr[i]<0){
newarr[neg] = arr[i];
neg+=2;
}
}
for (int j=0; j<arrsize; j++){
System.out.print(+newarr[j]+",");
}
}
}
import java.util.*;
import java.io.*;
public class ArrangeNum{
public static void main(String []args){
int arr[] = {-1,6,9,-4,-10,-9,8,8,4};
int arrsize = arr.length;
int newarr[] = new int [arrsize];
int pos = 0;
int neg = 1;
for (int i=0; i<arrsize; i++){
if (arr[i]>0){
newarr[pos] = arr[i];
pos+=2;
}
else if (arr[i]<0){
newarr[neg] = arr[i];
neg+=2;
}
}
for (int j=0; j<arrsize; j++){
System.out.print(+newarr[j]+",");
}
}
}
const a = [-1, 6, 9, -4, -10, -9, 8, 8, 4];
let tmp_pos = [];
let tmp_neg = [];
let result = [];
for(let i = 0; i < a.length; i++) {
if (a[i] > 0)
tmp_pos.push(a[i])
else
tmp_neg.push(a[i])
}
console.log(tmp_pos, tmp_neg);
let addPos = true;
while(tmp_neg.length > 0 || tmp_pos.length > 0) {
if(addPos) {
result.push(tmp_pos[0]);
tmp_pos.shift();
addPos = false;
} else {
result.push(tmp_neg[0]);
tmp_neg.shift();
addPos = true;
}
}
console.log(result);
const a = [-1, 6, 9, -4, -10, -9, 8, 8, 4];
let tmp_pos = [];
let tmp_neg = [];
let result = [];
for(let i = 0; i < a.length; i++) {
if (a[i] > 0)
tmp_pos.push(a[i])
else
tmp_neg.push(a[i])
}
console.log(tmp_pos, tmp_neg);
let addPos = true;
while(tmp_neg.length > 0 || tmp_pos.length > 0) {
if(addPos) {
result.push(tmp_pos[0]);
tmp_pos.shift();
addPos = false;
} else {
result.push(tmp_neg[0]);
tmp_neg.shift();
addPos = true;
}
}
console.log(result);
def sort_array(my_array):
neg_arr = []
pos_arr = []
sorted_arr = []
for my_int in my_array:
if my_int > 1:
pos_arr.append(my_int)
elif my_int < 1:
neg_arr.append(my_int)
for i in range(len(pos_arr)):
if i < len(pos_arr):
sorted_arr.append(pos_arr[i])
if i < len(neg_arr):
sorted_arr.append(neg_arr[i])
return sorted_arr
public static int[] sortPositiveNegative(int []arr) {
int pos=0,neg=0;
int sortedArr[] = Arrays.copyOf(arr,arr.length);
for(int i=0;i<arr.length-1;i++) {
while(arr[pos]<0) {
pos++;
}
sortedArr[i]=arr[pos++];
i++;
while(arr[neg]>0 ) {
neg++;
}
if(i<arr.length)
sortedArr[i]=arr[neg++];
}
return sortedArr;
}
public static int[] sortPositiveNegative(int []arr) {
- Vinod November 15, 2019int pos=0,neg=0;
int sortedArr[] = Arrays.copyOf(arr,arr.length);
for(int i=0;i<arr.length-1;i++) {
while(arr[pos]<0) {
pos++;
}
sortedArr[i]=arr[pos++];
i++;
while(arr[neg]>0 ) {
neg++;
}
if(i<arr.length)
sortedArr[i]=arr[neg++];
}
return sortedArr;
}