Entering edit mode

**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.

Click here to Practice

Submit Problem to OJ

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.

Click here to Practice

Submit Problem to OJ

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

**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.

Entering edit mode

**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 < r){
sum=array[l]+array[r];
if(sum < k){
l++;
}
else if(sum > k){
r--;
}
else{
cout << array[l]<<" "<
```

Entering edit mode

**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)

Loading Similar Posts

Hello Harsh Priyadarshi, I was trying this problem(

handle: code__raider), but it is giving WA at 2nd test case only. Way 1: If I store the array, failing at 2nd test because "6 12, 7 3 5 8 1" here no. of elements should be 6 instead on 5. Please check this once.Way2: If I don't store the array and just go with the HashMap, it is getting failed at 11th test. Approach seems alright. Please check this as well

No. of elements was a typo. It is fixed. Testcase 11 is fixed as well.

thanks Harsh, it's accepted now!!!