## Amazon Interview Question for Data Engineers

Country: United States
Interview Type: In-Person

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

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

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

This is a typical dp problem very similar to edit distance etc. O(N) is the right complexity.

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

``````def swap(A,B,i):
temp=A[i]
A[i]=B[i]
B[i]=temp

def minswaps(A,B):
n=len(A)
if n==0:
return Null
if n==1:
return 0
counter =0
for i in xrange(0,n-1):
if A[i+1]<=A[i]:
swap(A,B,i+1)
counter+=1
if B[i+1]<=B[i]:
return -1
return counter

A=[5,3,7,7,10]
B=[1,6,6,9,9]
print(minswaps(A,B))``````

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

``````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[index]
sequences[index] = sequences[index]
sequences[index] = temp

isSequenceOneIncreasing = Process.checkStrictlyIncreasing(sequences)
isSequenceTwoIncreasing = Process.checkStrictlyIncreasing(sequences)

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) 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),
isSequenceTwoIncreasing=Process.checkStrictlyIncreasing(sequences))

if sequenceResultsBaseStep["is_sequence_one_increasing"] and \
sequenceResultsBaseStep["is_sequence_two_increasing"]:
return sequences, 0

sequenceResultsSteps = [sequenceResultsBaseStep]

for i in range(len(sequences)):
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
sequenceTwo = sequences
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
sequenceTwo = sequences
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")``````

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

You can run this code on Create.run().

Test cases:
1. [5, 8, 8, 9, 10], [2, 7, 9, 10, 11]
2. [5, 3, 7, 7, 10], [1, 6, 6, 9, 9]
3. [1, 2, 3, 4, 5], [5, 6, 7, 8, 9]
4. [1, 8, 8, 11, 14, 17, 17, 19], [2, 3, 9, 9, 13, 15, 18, 20]
5. , 
6. [3, 2], [1, 4]

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.