## Amazon Interview Question

Data Engineers**Country:**United States

**Interview Type:**In-Person

```
from abc import ABC, abstractmethod
import copy
class Process(ABC):
@abstractmethod
def is_swap_required(self, sequences, index):
pass
@staticmethod
def checkStrictlyIncreasing(sequence):
try:
for i in range(0, len(sequence)-1):
if sequence[i] >= sequence[i+1]:
return False
return True
except IndexError:
return True
@staticmethod
def form_sequence_results_step(index, sequences, isSwapped, lookupIndex, swapCount, isSequenceOneIncreasing,
isSequenceTwoIncreasing):
return {
"index": index,
"sequences": sequences,
"is_swapped": isSwapped,
"lookup_index": lookupIndex,
"swap_count": swapCount,
"is_sequence_one_increasing": isSequenceOneIncreasing,
"is_sequence_two_increasing": isSequenceTwoIncreasing
}
@staticmethod
def sequence_results_steps_iteration(sequenceResultsSteps, index):
sequenceResultCurrentIndexSteps = []
sequenceStrictlyIncreasing = False
for step in sequenceResultsSteps:
sequences = copy.deepcopy(step["sequences"])
lookupIndex = copy.deepcopy(step["index"])
swapCount = copy.deepcopy(step["swap_count"])
swapRequiredWithPreviousIndexValues = False
swapRequiredWithNextIndexValues = False
if CompareWithPreviousIndex().is_swap_required(sequences, index):
swapRequiredWithPreviousIndexValues = True
if CompareWithNextIndex().is_swap_required(sequences, index):
swapRequiredWithNextIndexValues = True
if swapRequiredWithPreviousIndexValues and swapRequiredWithNextIndexValues:
temp = sequences[0][index]
sequences[0][index] = sequences[1][index]
sequences[1][index] = temp
isSequenceOneIncreasing = Process.checkStrictlyIncreasing(sequences[0])
isSequenceTwoIncreasing = Process.checkStrictlyIncreasing(sequences[1])
swapCount = swapCount + 1
sequenceResultCurrentIndexSteps \
.append(Process.form_sequence_results_step(index=0,
sequences=sequences,
isSwapped=True,
lookupIndex=lookupIndex,
swapCount=swapCount,
isSequenceOneIncreasing=isSequenceOneIncreasing,
isSequenceTwoIncreasing=isSequenceTwoIncreasing))
if isSequenceOneIncreasing and isSequenceTwoIncreasing:
sequenceStrictlyIncreasing = True
break
sequenceResultsSteps.extend(sequenceResultCurrentIndexSteps)
return sequenceResultsSteps, sequenceStrictlyIncreasing
@staticmethod
def process(sequences):
if len(sequences[0]) in [0, 1]:
return sequences, 0
sequenceResultsBaseStep = Process.form_sequence_results_step(index=0,
sequences=sequences,
isSwapped=False,
lookupIndex=None,
swapCount=0,
isSequenceOneIncreasing=Process.checkStrictlyIncreasing(sequences[0]),
isSequenceTwoIncreasing=Process.checkStrictlyIncreasing(sequences[1]))
if sequenceResultsBaseStep["is_sequence_one_increasing"] and \
sequenceResultsBaseStep["is_sequence_two_increasing"]:
return sequences, 0
sequenceResultsSteps = [sequenceResultsBaseStep]
for i in range(len(sequences[0])):
sequenceResultsSteps, isStrictlyIncreasing = Process.sequence_results_steps_iteration(sequenceResultsSteps=sequenceResultsSteps, index=i)
if isStrictlyIncreasing:
return sequenceResultsSteps[len(sequenceResultsSteps)-1]["sequences"], sequenceResultsSteps[len(sequenceResultsSteps)-1]["swap_count"]
return None, 0
class CompareWithPreviousIndex(Process):
def is_swap_required(self, sequences, index):
sequenceOne = sequences[0]
sequenceTwo = sequences[1]
swapRequired = False
try:
if index == len(sequenceOne) - 1:
if sequenceOne[index] <= sequenceOne[index-1]:
swapRequired = True
if sequenceTwo[index] <= sequenceTwo[index-1]:
swapRequired = swapRequired and True
if sequenceOne[index] > sequenceTwo[index-1]:
swapRequired = swapRequired and True
if sequenceTwo[index] > sequenceOne[index-1]:
swapRequired = swapRequired and True
return swapRequired
return True
except IndexError:
return True
class CompareWithNextIndex(Process):
def is_swap_required(self, sequences, index):
sequenceOne = sequences[0]
sequenceTwo = sequences[1]
swapRequired = False
try:
if index < len(sequenceOne) - 1:
if sequenceOne[index] >= sequenceOne[index + 1]:
swapRequired = True
if sequenceTwo[index] >= sequenceTwo[index + 1]:
swapRequired = True
if sequenceOne[index] < sequenceTwo[index + 1]:
swapRequired = swapRequired and True
if sequenceTwo[index] < sequenceOne[index + 1]:
swapRequired = swapRequired and True
return swapRequired
return True
except IndexError:
return True
class Create:
@staticmethod
def run(sequences):
result_sequence, total_swaps = Process.process(sequences)
if result_sequence is not None:
print("Strictly Increasing Array - ")
print(result_sequence)
print("Total minimal swaps took: " + str(total_swaps))
else:
print("Strictly Increasing Array is not possible")
```

You can find the Answer from < geeksforgeeks > try Searching < Find the smallest positive number missing from an unsorted array >

- NotaGeek March 09, 2018