Round 1:
Ques1.you are given an array and you need to reach at the end with minimum no of jumps. From index i you can take at max arr[i] jumps.
int jump(vector<int>& nums) {
if(nums.size()==1){
return 0;
}
int position = nums[0];
int max_reach = nums[0];
int jumps = 1;
for(int i=1;i<nums.size();i++){
if(position<i){
jumps++;
position = max_reach;
}
max_reach = max(max_reach,i+nums[i]);
}
return jumps;
}Ques2.Train arrival and departure times are given. Find the minimum no of platforms required.
https://www.***.org/minimum-number-platforms-required-railwaybus-station/Ques3.you are given a Linked list with bottom and right pointer. You need to flatten the linked list. The order should be like the node which is closer should be accessebile first in the flatten linked list.
Round 2:
Ques 1. You are given an array find the range sum.
Further extension: You are multiple queries for get(range) and update(index) . Answer for the queries.
Solution for this is Segment Tree. Below is the code i wrote in the interview.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <limits.h>
using namespace std;
struct node {
int data;
struct node *left, *right;
int start_index;
int end_index;
};
struct node *getnode(int data, int start_index, int end_index) {
struct node *tmp = (struct node *)malloc(sizeof(struct node));
tmp->left = NULL;
tmp->right = NULL;
tmp->data = data;
tmp->end_index = end_index;
tmp->start_index = start_index;
return tmp;
}
struct node *buildTree(int arr[], int sum[], int low, int high) {
if (low == high) {
struct node *root = getnode(arr[low], low, low);
return root;
}
if (low<high) {
struct node *root = getnode(sum[high + 1] - sum[low], low, high);
int mid = (low + high) / 2;
root->left = buildTree(arr, sum, low, mid);
root->right = buildTree(arr, sum, mid + 1, high);
return root;
}
return NULL;
}
int get_query(struct node *root, int start_index, int end_index) {
if (root->start_index == start_index&&root->end_index == end_index) {
return root->data;
}
int mid = (root->start_index + root->end_index) / 2;
if (start_index > mid) {
return get_query(root->right, start_index, end_index);
}
else if (start_index <= mid&&end_index > mid) {
int left = get_query(root->left, start_index, mid);
int right = get_query(root->right, mid + 1, end_index);
return left + right;
}
else if(end_index<=mid) {
return get_query(root->left, start_index, end_index);
}
return INT_MAX;
}
void update_query(struct node *root, int index, int target, int arr[]) {
if (root == NULL) {
return;
}
if (root->start_index == index&&root->end_index == target) {
root->data = root->data - arr[index] + target;
return;
}
int mid = (root->start_index + root->end_index) / 2;
root->data = root->data - arr[index] + target;
if (index <= mid) {
update_query(root->left, index, target, arr);
}
else if (index > mid) {
update_query(root->right, index, target, arr);
}
}
int main() {
int n;
freopen("input.txt", "r", stdin);
cin >> n;
int *arr = new int[n];
int *sum = new int[n + 1];
sum[0] = 0;
for (int i = 0;i<n;i++) {
cin >> arr[i];
sum[i + 1] = sum[i] + arr[i];
}
struct node *root = buildTree(arr, sum, 0, n - 1);
cout << get_query(root, 3, 7)<<endl;
update_query(root, 7, 10, arr);
cout << get_query(root, 2, 8)<<endl;
return 0;
}Ques2. Find the max from all k sized window in array. As i took too much time he asked me to give the best possible solution which is O(n).
Further extension: Find max min and median from all the k sized windows in array. I did this using 2 deques.
I told him that for finding median we can use Self balancing binary tree. He was okay with the approach and didn't asked me to write the code.
Round 3:
After few days i recieved call for 3rd round.
Discussion about my current work and what projects i have worked on.
Design a compiler. Interviewer was interested in the part how interdependent files are compiled, Cyclic dependency. I tried to give solution with topological sort .
Round 4:
It was BR round. Interviewer asked me about my current project. Challenges faced during project. Amazon Principles related to project.
One ques i remeber is "Tell me about the situtation or about your work where you have delivered to enhance user's experience related to the product.