This blog contains all the Amazon Online Coding questions asked in on-campus and off-campus Placements 2020.
Question-1: Amazon warehouses have a complex line of machines which enable very quick item selection, packaging and delivery. These machines usually pass an item off to the next machine in the line, but sometimes the item is redirected to some where else in the line. The delivery line has been modeled and now the Amazon Fulfillment Team would like to run some experiments to identity how the machine line can be more efficient. Since there are many different experiments the team would like to run, the model of the machine line needs to be copied. Given a linked list where each node is a machine ('value'), a reference to the next machine in the line ('next') and a reference to the next machine sometimes used ('arbitrary').
Input: The input to the function/method consists of an arguments-head representing the head of the linked list.
Output: Return the head of the new linked list to copy the given linked list with the same data and structure at a different memory address.
Code:
unordered_map<ALNode* , ALNode*> mp;
ALNode* solve(ALNode* A)
{
if(!A) return NULL;
if(mp[A]) return mp[A];
mp[A] = new ALNode(A->value);
mp[A]->next = solve(A->next);
mp[A]->arbitary = solve(A->arbitary);
return mp[A];
}
ALNode* deepCopy(ALNode* head)
{
mp.clear();
return solve(head);
}
Question-2:Customer reviews are very important to Amazon. Every day, reviews written for a product are collected, sorted in ascending order by their rating and sent for review. We have more products than reviewers, but we want to make sure all reviews with a low rating are looked at so we can address any issues with the products in our catalog. We need you to help us write an algorithm that combines two singly linked lists of reviews (in ascending order and combine these lists into a merged single list of reviews, sorted in ascending order, to make sure our reviewers look at low rated reviews first regardless of which product the review was written for. Input The input to the function consists of two arguments: head1-representing the head of the linked list of the first list of customer reviews. head2-representing the head of the linked list of the second list of customer reviews.
Output: Return a node of the head of a linked list representing a merged linked list of reviews formed from the two singly linked list given as input.
Code:
LNode* mergeLists(LNode* head1 , Lnode* head2)
{
if(!head1)
return head2;
if(!head2)
return head1;
LNode* res = NULL;
if(head1->data<=head2->data)
{
head1->next = mergeLists(head1->next , head2);
return head1;
}
else
{
head2->next = mergeLists(head1 , head2->next);
return head2;
}
}
Question-3:Amazon prodes itself on protecting customers and sellers from fraud. Amazon assigns fraud ratings to actions taken on the website. We scan these ratings values to try and determine when to accept a given request. Fraud ratings are assigned in a complementary manner. When two ratings add up to a certain value, it increases the risk that the request may be fraudlent.
Write an algorithm to find the number of distinct pairs of ratings from an array of all fraud ratings for the request that sum to a target value.
Input: The input to the function/method consists of three arguments: n: an integer representing the number of rating. arr: a list of integers representing the value of fraud ratings. target: an integer representing the target value.
Output: Return an integer representing the number of distinct pairs of ratings from a list of all fraud ratings for the request that sum to a target value.
Code:
int countPair(int arr[], int n,int target)
{
unordered_set<int> us;
int cnt = 0;
for(int i=0;i<n;i++)
{
if (us.find(target-arr[i])!=us.end())
cnt++;
else
us.insert(arr[i]);
}
return cnt;
}
Question-4:Amazon is coming up with an automated system to help create email aliases that contain all the people under a certain manager. Each organization is modeled as a binary tree corresponding to their employee id. Greg is writing a program that will determine if a set of workers should be added to the email alias by seeing if the smaller tree the set of workers creates is a subtree of the larger tree of the organization. A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T. You will help Greg by writing a method that takes in objects of the root nodes of the two binary trees, where root is the root node of the parent organization tree of all employees, and root2 is the root node of the smaller tree Return 1, if root2 Is a subtree of root1. Otherwise return -1. Compare the trees using the integer values of the nodes and NOT the objects of the node themselves. Assume the integer values in the node are unique in each of the trees.
Input: The input to the function/method consists of two arguments: root1- a node of the head of the binary tree representing the larger tree of the organization. root2- a node of the head of the second binary tree Representing the smaller tree.
Ouput: Return an integer '1' if root2 is a subtree of root1. Otherwise, return -1.
Code:
int check(vector<int> &parent,vector<int> &child)
{
string s1="";
string s2="";
for(int i=0;i<parent.size();i++)
s1+=to_string(parent[i]);
for(int i=0;i<child.size();i++)
s2+=to_string(child[i]);
if(s1.find(s2)!=-1)
return 1;
return 0;
}
void inorder(tnode *root,vector<int> &v)
{
if(!root)
{
v.push_back(-1);
return;
}
inorder(root->left,v);
v.push_back(root->value);
inorder(root->right,v);
}
void preorder(tnode *root,vector<int> &v)
{
if(!root)
{
v.push_back(-1);
return;
}
v.push_back(root->value);
preorder(root->left,v);
preorder(root->right,v);
}
int isSubtree(tnode *root1,tnode *root2)
{
vector<int> in1;
vector<int> in2;
vector<int> pre1;
vector<int> pre2;
inorder(root1,in1);
inorder(root2,in2);
preorder(root1,pre1);
preorder(root2,pre2);
if(check(in1,in2)&&check(pre1,pre2))
return 1;
return -1;
}
Question-5:Amazon is working on creating a road network to connect all their warehouses to help in transferring products between them. The proposed road network guarantees that all the warehouses will be connected to each other directly or indirectly. A road can be classified as "critical" or "non-critical". A road is considered "critical" if its removal results in a disconnected network of warehouses. Amazon wants to significantly increase the efficiency of their warehouse network by investing in better infrastructure to build those roads.
Write a method that returns the critical connections from the proposed connections.
Input: The input to the function/method consists of three arguments: n, an integer representing the number of warehouses in the proposed plan. edges, an integer representing the number of roads between the warehouses. connections, a list of pairs of integers representing the roads between two warehouses.
Output: Return a list of integer pairs representing the critical connections. If there are no critical connections, return a list with empty pair-not just an empty list.
Code:
vector<pair<int,int>> ans;
int *in, *low, *visited;
vector<int> *adj;
int timer = 1;
void dfs(int node, int parent){
in[node] = low[node] = timer;
visited[node] = 1;
timer++;
for(int child: adj[node])
{
if(child == parent) continue;
if(visited[child] == 1)
low[node] = min(low[node], low[child]);
else{
dfs(child, node);
low[node] = min(low[node], low[child]);
if(in[node] < low[child])
{
ans.push_back({node+1, child+1});
}
}
}
}
vector<pair<int,int>> criticalConnections(int n, int edges, vector<pair<int,int>>& connections) {
adj = new vector<int>[n];
for(int i=0; i<connections.size(); i++)
{
int a = connections[i].first-1, b = connections[i].second-1;
adj[a].push_back(b);
adj[b].push_back(a);
}
ans.clear();
in = new int[n];
low = new int[n];
visited = new int[n];
for(int i=0; i<n; i++) visited[i] = 0;
timer = 0;
dfs(0, -1);
return ans;
}
Question-6:Amazon wants to improve the Audible experience for its customers by offering better book recommendations based on what the user has already listened to. To make this possible, Amazon needs to ldentify users favorite book genre(s). This is done by identifying the most listened to book genres from the user history and giving them recommendations from the same. A user can have more than one favorite genre if he/she has listened to the same number of books per each of the genres.
Amazon has following information to identify a user's interest(s):
The name of the user mapped to the collection of all the books that he/she has listened to, and
b)A list of all books and their associated genres. For the scenario, imagine that a book can belong to only one genre.
Write an algorithm that will produce a map/dictionary of users and their favorite book genres.
Input: The input to the function/method consists of four arguments: numUsers: an integer number of users. UserBooksListenedTo: a map with user names as keys and a list of all the books that the user has listened to as values. numGenres: an integer number of all genres available. bookGenres: a map with book genre as keys with a list of all the books within that genre as values.
Output: Return a map/dictionary with the preferences of all users, Key represents the user name and value represents a list of his/her favorite genres.
Example:
Input: numUsers=3
userBooksListenedTo={ "Fred":["mass","world","stress"], "Jenie":["happy","pride"], "Rone":["alexender"] }
numGenres=3
bookGenres={ "Horror":["mass","stress"], "Comedy":["happy"], "Romance":["world","alexender","pride"] }
Output:
{ "Fred":["Horror"], "Jenie":["Comedy","Romance"], "Rone":["Romance"] }
Code:
map<string,vector<string>> favoriteVideoGenre(int numUsers,map<string,vector<string>> userBooksListenedTo,int numGenres,map<string,vector<string>> bookGenres)
{
unordered_map<string,string> umap;
for(auto cur:bookGenres)
{
for(string s:cur.second)
umap[s]=cur.first;
}
map<string,vector<string>> ans;
for(auto cur:userBooksListenedTo)
{
string name=cur.first;
map<string,int> mp;
for(string s:cur.second)
{
if(umap.find(s)!=umap.end())
mp[umap[s]]++;
}
int mx=0;
for(auto x:mp)
{
mx=max(mx,x.second);
}
for(auto x:mp)
{
if(x.second==mx)
ans[name].push_back(x.first);
}
}
return ans;
}
Question-7:Amazon Local wants to show deals where customers can hike to an area of a given altitude and get a great deal on a local product. To do that, we want to see if there's a deal at a customer's desired altitude. Remember that some destinations are below sea level. To store the altitudes, we have a two-dimensional integer matrix The top-left position in the matrix is and the bottom right corner is . The altitudes in each column and row are sorted in ascending order from top to bottom and left to right, respectively.
Write an algorithm to find the pair containing the location of the target altitude in order.
Input
The input to the function/method consists of four arguments. rowCount, an integer representing the number of rows in the matrix. columnCount, an integer representing the number of columns in the matrix. matrix, representing a two-dimensional integer matrix. targetValue, an integer representing the target altitude.
Output:
Return a pair of integers representing the location of the target altitude in order. If there are no deals at a given altitude return {-1,-1}. You may assume that there will be at most one deal at the target altitude.
Code:
pair<int, int> isPresent(int matrix[MAX][MAX], int n, int m, int x){
int row = 0, col = m-1;
pair<int, int> p;
while(row < n && col >= 0){
if(matrix[row][col] == x){
p.first = row;
p.second = col;
return p;
}
else if(x > matrix[row][col]){
row++;
}
else{
col--;
}
}
p.first = -1;
p.second = -1;
return p;
}
Question-8:Given a sorted array, arr[] of N integers, and a value X. Find the K closest elements to X in arr[]. Keep the following points in mind:
If X is present in the array, then it need not be considered. If there are two elements with the same difference with X, the greater element is given priority. If sufficient elements are not present on the right side then take elements from left and vice versa.
Example:
Input: N = 13 arr[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56} K = 4, X = 35 Output: 30 39 42 45 Explanation: First closest element to 35 is 30. Second closest element to 35 is 39. Third closest element to 35 is 42. And fourth closest element to 35 is 45.
Code:
class Solution{
public:
int findCrossOver(vector<int>arr, int low, int high, int x) {
if (arr[high] <= x)
return high;
if (arr[low] > x)
return low;
int mid = (low + high) / 2;
if (arr[mid] <= x && arr[mid + 1] > x)
return mid;
else if (arr[mid] < x)
return findCrossOver(arr, mid + 1, high, x);
else
return findCrossOver(arr, low, mid - 1, x);
}
vector<int> printKClosest(vector<int> arr, int n, int k, int x) {
int l = findCrossOver(arr, 0, n - 1, x);
int r = l + 1;
int count = 0;
if (arr[l] == x) l--;
vector<int> closest;
while (l >= 0 && r < n && count < k) {
if (x - arr[l] < arr[r] - x)
closest.push_back(arr[l--]);
else
closest.push_back(arr[r++]);
count++;
}
while (count < k && l >= 0) closest.push_back(arr[l--]), count++;
while (count < k && r < n) closest.push_back(arr[r++]), count++;
return closest;
}
};
#Happy_Coding 💻
Thank you for reading the article. Follow CodoPedia for More. 😃
For regular updates and more interesting stuff Join us on Telegram