Amazon 6 months SDE Internship Interview Experience

Question

Oncampus Round CGPA Cutoff - 6 Branches Allowed - Circuital Offer type - Sde Intern + ppo opportunity Stipend - Rs 1,10,000 Round 1: The First round was an Online Assessment Round in which 3 questions were asked on Hackerank . Couldn't remember exact questions but 2 of them were from medium level and 1 from hard from DP and Graph Topics. After that some behavioural questions were asked in the Amazon's portal . 6 people got selected at this end of this round. Round 2: The next round was a technical interview round . It went of for around 1 hour. The interview started with basic introduction and little bit about my projects. Then Interviewer started with the DSA questions and in total 2 questions were asked in nearly 45 minutes. Level - Medium Question 1 : It was a question based on Binary Search and two pointers.The question was - https://www.geeksforgeeks.org/find-k-closest-elements-given-value/ I started with the first approach by using minHeap and then interviewer asked me to optimize the solution and then came up with the binary search and two pointers approach. And then he asked me to code the same and dry run it. 285 Question 2 : It was a variation of two sum problem of medium level . The interviewer got satisfied with my approach and dry run and I asked should I code it but he said he was satisfied with my solution and didn't need to code. 280 The question I asked at the end of interview in Q&A was:-In which team they were working and how is their experience regard to work-life balance And how is 6-month internship different from 2 months Verdict - Selected Tips And Unique Points from Interview. All the other people that interviewed with me had one interviewer in their panel but mine consisted of two. They asked me questions on each step that I wrote in my code . For example - They asked me questions about time complexity for each data structure that I took, why I took it, can the question be solved without using it, if yes then how etc . So be prepared for it. Always think out loud when coding because they need to know what exactly are you doing in each part of code . Also it will help you in debugging your problem . Always ask clarifications for any doubts. They will make you build your solution to the most optimized way possible and will help you in achieving that by giving hints so always listen carefully to them And the last one , keep your fundamentals clear as well along with the good dsa skills.

Harsh Priyadarshi · Accepted Answer

Question 2 (Round 2)
Overview

We are given an array A of N integers and an integer K
Find two integers from A whose sum is K

Approach

O(n^2) approach is pretty straightforward, try all possible pairs of integers then output the pair whose sum is K.

Better Approach

We can sort the array and appoint the first element as our left pointer and the last element as our right pointer as our current sum.
If the sum is less than K. Then we can move the left pointer one step to the right. The new sum would be greater than the previous as the array is sorted. Therefore A[i+1]>A[i].
If the sum is greater than K. Then we move the right pointer one step to the left. the new sum would be less than the previous because the array is sorted and A[i-1]<=A[i].
We keep doing this till we reach the answer.

Complexity

O(nlog(n)) from the sorting, as the two pointer approach iterates the array only once, so that would be O(n).

PseudoCode
while(l &lt; r){
    sum=array[l]+array[r];
    if(sum &lt; k){
        l++;
    }
    else if(sum &gt; k){
        r--;
    }
    else{
        cout &lt;&lt; array[l]&lt;&lt;" "&lt;

Gigaliths · Answer

Question 1 (Round 2)
Approach 1

Sort the array
Binary search the last index corresponding to the value 'X'
Keep a priority queue and push all probable values from array[idx-k .... idx+k] into the priority queue. (MinHeap)
Push the values in the form of a tuple : { (distance from X) , index }  
Now pop the first K values from the minHeap and print arr[index] for each popped element.

Approach 2 (Space optimized)

First two steps are same as Approach 1
Apply two pointers with preference of moving the pointer to the value closer to array[X]
If two pointers correspond to same distance, prefer the left pointer (smaller value).

Complexity

Time complexity is O(nlogn) in both approaches due to sorting of the array.
Space complexity for approach 2 is O(1) which dominates the first approach with space complexity of O(k)

Prasanna Rongala · Answer

def find_pair(n, k, arr):

    arr.sort()

    left, right = 0, n - 1

 

    while left < right:

        current_sum = arr[left] + arr[right]

 

        if current_sum == k:

            return [arr[left], arr[right]]

        elif current_sum < k:

            left += 1

        else:

            right -= 1

 

 

n, k = map(int, input().split())

arr = list(map(int, input().split()))

result = find_pair(n, k, arr)

print(*sorted(result))

Question: Amazon 6 months SDE Internship Interview Experience

Verdict - Selected

Question 2 (Round 2)

Question 1 (Round 2)

Approach 3

Complexity

Pseudocode