Amazon Coding Questions

Amazon Coding Questions

Amazon Coding Questions and Answers

On this page, the 2022–23 Amazon Coding Questions and Answers are discussed. One of the most crucial rounds for landing a job at Amazon is the coding round.

You can use this section to analyse the level of complexity of the Amazon problem. Understanding the level of complexity and question format for the coding phase is made easier by practising Amazon code questions and answers.

The Amazon Coding Round questions and their solutions in different languages can be found below. For a good grade, you must be prepared for the Amazon code problems.

Coding Test Format

  • Coding round contains 3 questions that will have to be attended in 3 hours.
  • Each questions have different difficulty level.
  • There is one Easy problem based on Algorithm , Aptitude and Data structures.
  • One of the problem is of Medium level and that problem is based on Greedy Algorithm.
  • One is of Hard difficulty level, and usually based on Dynamic Programming.
No. Of Questions Marks per question
Question 1 20
Question 2 30
Question 3 50

Question 1

Problem Statement: Check if strings are rotations of each other or not
Given two strings s1 and s2. The task is to check if s2 is a rotated version of the string s1. The characters in the strings are in lowercase.

Test Case 1:-
Input:

mightandmagic
andmagicmigth

Output:

0

Explanation:

Here with any amount of rotation s2 can’t be obtained by s1.

Your Task:

The task is to complete the function areRotations() which checks if the two strings are rotations of each other. The function returns true if string 1 can be obtained by rotating string 2, else it returns false.

  • Expected Time Complexity: O(N).
  • Expected Space Complexity: O(N).
  • Note: N = |s1|.

Constraints:

  • 1 <= |s1|, |s2| <= 107
Run
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int price[] = new int[n];
		for(int i=0;i diff = new Vector<>();
		for(int i=n-2;i>=0;i--) {
			diff.add(price[i+1]-price[i]);
		}
		int ans = solve(diff);
		if(ans<0) {
			System.out.println(0);
		}else {
			System.out.println(ans);
		}

	}
	private static int solve(Vector v) {
		int n = v.size();
		if(n==0) {
			return 0;
		}
		int mx = v.get(0);
		for(int i=1;i < n;i++) {
			mx = Math.max(mx, v.get(i));
		}
		if(mx<=0) {
			return 0;
		}
		int mxSum=0,csum=0;
		for(int i=0;i < n;i++) {
			csum+=v.get(i);
			if(csum < 0)
				csum=0;
			mxSum = Math.max(csum, mxSum);
		}
		return mxSum;
	}
}

Run
#include <bits/stdc++.h>
using namespace std;


class Main
{
    public:
    bool Rotation(string s1,string s2)
    {
         int a = s1.size() - 1;
       int b = s2.size() - 1;
       
       if (a != b) {
           return false;
       } 
       string temp = s1 + s1;
       if(temp.find(s2) <= a+b) { } return false; } }; int main() { int t; cin>>t;
    while(t--)
    {
        string s1;
        string s2;
        cin>>s1>>s2;
        Solution obj;
        cout<<obj.Rotation(s1,s2)<<endl;

    }
    return 0;
}

Question 2

Problem Statement:

Jarvis is weak in computing palindromes for Alphanumeric characters.While Ironman is busy fighting Thanos, he needs to activate sonic punch but Jarvis is stuck in computing palindromes.You are given a string S containing alphanumeric characters. Find out whether the string is a palindrome or not. If you are unable to solve it then it may result in the death of Iron Man.

Test Case 1:-

Input:

S = “I am :IronnorI Ma, i”

Output:

YES

Explanation:

Ignore all the symbols and whitespaces S = “IamIronnorIMai”. Now, Check for palindrome ignoring uppercase and lowercase English letter.

Test Case 2:-

Input:

S = Ab?/Ba

Output:

YES

Explanation:

Here with any amount of rotation s2 can’t be obtained by s1.

Your Task:

This is a function problem. The input is already taken care of by the driver code. You only need to complete the function saveIronman() that takes an string (ch), and return the true if the string is a palindrome and false if the string is not a palindrome. The driver code takes care of the printing.

  • Expected Time Complexity: O(N).
  • Expected Space Complexity: O(1).

Note: N = |s1|.

Constraints:

  • 1 ≤ |S| ≤ 100000

Note: Consider alphabets and numbers only for palindrome check. Ignore symbols and whitespaces.

 

Run
import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
s = s.toLowerCase();
s = s.replaceAll(" [,?/:;!]", "");
char ch[] = s.toCharArray();
int i = 0;
int j = s.length() - 1;
boolean check = true;
while (i < j) {
if (check(ch[i]) == false) {
i++;
continue;
}
if (check(ch[j]) == false) {
j--;
continue;
}
if ((ch[i] != ch[j])) {
check = false;
break;
}
i++;j--;
}
if (check)
System.out.println("YES");
else
System.out.println("NO");
}


public static boolean check(char c) {
boolean f = false;
byte b = (byte) c;
if (b >= 97 && b <= 122) {
return true;
} else {
if (c == '1' || c == '2' || c == '3' || c == '4' || c == '5' || c == '6' || c == '7' || c == '8' || c == '9'
|| c == '0')
return true;
}
return f;
}
}

Run
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int i,j,n,t;
	cin>>t;
	cin.ignore();
	while(t--)
	{
		string s;
		getline(cin,s);
		stacks1;
		for(i=0;i < s.length();i++)
		{   if(isalpha(s[i])) 
			{ 
				s[i]=tolower(s[i]);
			  s1.push(s[i]);
			}
		}
		for(i=0;i < s.length();i++)
		{  
            if(isalpha(s[i]))
			{
				if(!s1.empty()&&s1.top()!=s[i])
				 {
					 cout<<"NO";
					 break;
				 }
				 s1.pop();
			} 
		}
         if(i==s.length())
		   cout << "YES";
		   cout << endl;
	}
}

Question 3

Problem Statement:

Given a binary tree, print the bottom view from left to right.

A node is included in bottom view if it can be seen when we look at the tree from bottom.

                    20

                 / \

               8   22

                  /   \    \

                 5  3   25

                /   \  

              10 14

For the above tree, the bottom view is 5 10 3 14 25.

If there are multiple bottom-most nodes for a horizontal distance from root, then print the later one in level traversal. For example, in the below diagram, 3 and 4 are both the bottommost nodes at horizontal distance 0, we need to print 4.

                   20

                 / \

               8   22

             /   \     /   \

           5  3  4   25

              /        \  

                  10          14

For the above tree the output should be 5 10 4 14 25.

Example 1:

Input:

       1

     /   \

    3     2

Output: 3 1 2

Explanation:

First case represents a tree with 3 nodes and 2 edges where root is 1, left child of 1 is 3 and right child of 1 is 2.

Example 2:

Input:

         10

       /    \

      20    30

     /  \

    40   60

Output: 40 20 60 30

Your Task:

This is a functional problem, you don’t need to care about input, just complete the function bottomView() which takes the root node of the tree as input and returns an array containing the bottom view of the given tree.

  • Expected Time Complexity: O(N).
  • Expected Auxiliary Space: O(N).

Constraints:

  • 1 <= Number of nodes <= 105
  • 1 <= Data of a node <= 105

 

 

Run
#include<bits/stdc++.h>
using namespace std;
 
struct Node
{
    int data; 
    int hor; 
    Node *left, *right;
    Node(int key)
    {
        data = key;
        hor = INT_MAX;
        left = right = NULL;
    }
};
void bottom(Node *root)
{
    if (root == NULL)
        return;
    int hor = 0;
    map m;
    queue q;
    root->hor = hor;
    q.push(root);  
    while (!q.empty())
    {
        Node *temp = q.front();
        q.pop();   
        hor = temp->hd;
        m[hor] = temp->data;
        if (temp->left != NULL)
        {
            temp->left->hor = hor-1;
            q.push(temp->left);
        }
        if (temp->right != NULL)
        {
            temp->right->hor = hor+1;
            q.push(temp->right);
        }
    }
    for (auto i = m.begin(); i != m.end(); ++i)
        cout << i->second << " ";
}
int main()
{
    Node *root = new Node(10);
    root->left = new Node(9);
    root->right = new Node(8);
    root->left->left = new Node(7);
    root->left->right = new Node(6);
    root->right->left = new Node(4);
    root->right->right = new Node(3);
    root->left->right->left = new Node(2);
    root->left->right->right = new Node(1);
    cout << "Bottom view of the binary tree :\n";
    bottom(root);
    return 0;
}

Question 4

An expression is called the postfix expression if the operator appears in the expression after the operands.

Example :

Infix expression: A + B  *  C – D 

Postfix expression:  A B + C D – *

Given a postfix expression, the task is to evaluate the expression. The answer could be very large, output your answer modulo (10^9+7). Also, use modular division when required.

Note:

  • Operators will only include the basic arithmetic operators like ‘*’, ‘/’, ‘+’, and ‘-‘.
  • The operand can contain multiple digits. 
  • The operators and operands will have space as a separator between them.
  • There won’t be any brackets in the postfix expression.

Input Format:

  • The first line of input contains an integer ‘T’ denoting the number of test cases.
  • The next ‘T’ lines represent the ‘T’ test cases.
  • The first and only line of each test case contains a postfix expression.

Output Format:

  • The first line of input contains an integer ‘T’ denoting the number of test cases.
  • For each test case, print an integer obtained by evaluating the given postfix expression.

Note:

You are not required to print the expected output; it has already been taken care of, Just implement the function.

Constraints
  • 1 <= T <= 100
  • 1 <= N <= 10^3
  • 1 <= NUM <= 100

Where ‘N’ denotes the length of postfix expression and ‘NUM’ denotes the operand.

Time Limit: 1 sec

Sample input 1

2
2 3 1 * + 9 –
1 2 3 + * 8 –

Sample output 1

-4
-3

Explanation of sample input 1:

Test case 1:

2 3 1 * + 9 –
– : ( ) – ( )
9 : ( ) – (9)
+ : ( ( ) + ( ) ) – (9)
‘*’:  ( ( ) + ( ( ) * ( ) ) ) – (9)
1 : ( ( ) + ( ( ) * (1) ) ) – (9)
3 : ( ( ) + ( (3) * (1) ) ) – (9)
2 : ( (2) + ( (3) * (1) ) ) – (9) 

Result = (2 + 3) – 9 = 5 – 9 = -4

Test case 2:

1 2 3 + * 8 –
 – : ( ) – ( )
8 : ( ) – (8)
* : ( ( ) * ( ) ) – (8)
+ : ( ( ) * ( ( ) + ( ) ) ) – (8)
3 : ( ( ) * ( ( ) + (3) ) ) – (8)
2 : ( ( ) * ( (2) + (3) ) ) – (8)
1 : ( (1) * ( (2) + (3) ) ) – (8) 
Result = (1 * 5) – 8 = 5 – 8 = -3

Sample input 2

1
100 200 + 2 / 5 * 7 +

Sample output 2

757

Explanation of sample input 2:

100 + 200 = 300
300 / 2 = 150
150 * 5 = 750
750 + 7 = 757

Run
#include<iostream>
#include<cmath>
#include<stack>
#include<climits>
using namespace std;
float scan(char ch) {
   int data;
   data = ch;
   return float(data-'0');  
}
int isOperator(char ch) {
   if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
      return 1;    
   return -1;   
}
int isOperand(char ch) {
   if(ch >= '0' && ch <= '9')
      return 1;   
   return -1;   
}
float operation(int a, int b, char op) {
   if(op == '+')
      return b+a;
   else if(op == '-')
      return b-a;
   else if(op == '*')
      return b*a;
   else if(op == '/')
      return b/a;
   else if(op == '^')
      return pow(b,a); 
   else
      return INT_MIN; 
}
float postfixfun(string postfix) {
   int a, b;
   stack stk;
   string::iterator it;
   for(it=postfix.begin(); it!=postfix.end(); it++) {
      if(isOperator(*it) != -1) {
         a = stk.top();
         stk.pop();
         b = stk.top();
         stk.pop();
         stk.push(operation(a, b, *it));
      }else if(isOperand(*it) > 0) {
         stk.push(scan(*it));
      }
   }
   return stk.top();
}
int main() {
   string post = "22+18/*12*+";
   cout << "The result is: "<< postfixfun(post);
}

 Question 5

Asked in Infosys Placment Paper – Feb 2022

Problem Statement :

You are given a binary tree, the task is to find out the length of the longest path which contains nodes with the exact same value. It is not necessary for the path to pass through the root of the binary tree.Between two nodes, the length of the path can be defined as the number of edges contained between them.

For example, consider the following binary tree:

                    7

                /     \

               7         7

            /   \         \

           8     3         7

For the above tree, the length of the longest path where each node in the path has the same value is 3 and path is 7 -> 7 -> 7 -> 7

   Input format:

  • The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.
  • The only line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 on its place.
  • For example, the input for the tree depicted in the below image would be:

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation:

  • Level 1:
    • The root node of the tree is 1
  • Level 2:
    • Left child of 1 = 2
    • Right child of 1 = 3
  • Level 3:
    • Left child of 2 = 4
    • Right child of 2 = null (-1)
    • Left child of 3 = 5
    • Right child of 3 = 6
  • Level 4:
    • Left child of 4 = null (-1)
    • Right child of 4 = 7
    • Left child of 5 = null (-1)
    • Right child of 5 = null (-1)
    • Left child of 6 = null (-1)
    • Right child of 6 = null (-1)
  • Level 5:
    • Left child of 7 = null (-1)
    • Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null(-1).

Note:

The above format was just to provide clarity on how the input is formed for a given tree. The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

 

Output Format:

For each test case, a single integer denoting the length of the longest path where each node in the path has the same value is printed. The output for each test case is to be printed on a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

 

Constraints:

  • 1 <= T <= 100
  • 1 <= N <= 3000
  • -10^9 <= data <= 10^9 and data != -1

 Where ‘T’ is the number of test cases, ‘N’ is the total number of nodes in the binary tree, and “data” is the value of the binary tree node.

Time Limit: 1sec

 

Sample Input 1:

2
7 7 7 1 1 -1 7 -1 -1 -1 -1 -1 -1
10 3 4 3 3 -1 5 -1 -1 -1 -1 -1 -1

 

Sample Output 1:

3
2 

Explanation of Sample Input 1:

           7

           / \

          7   7

         / \   \

        1  1    7

 

For the first test case, the length of the longest path where each node in the path has the same value is 3 and path is 7 -> 7 -> 7 -> 7.

            10

           / \

          3   4

         / \   \

        3  3    5

 For the second test case, the length of the longest path where each node in the path has the same value is 2 and path is 3 -> 3 -> 3.

 

Sample Input 2:

2
1 4 5 4 4 -1 5 -1 -1 -1 -1 -1 -1
5 4 5 1 1 -1 5 -1 -1 -1 -1 -1 -1

 

Sample Output 2:

2
2

Run
class Main {
    
    static class Node{
    int val;
    Node left, right;
};
static Node newNode(int data)
{
    Node temp = new Node();
    temp.val = data;
    temp.left = temp.right = null;
    return temp;
}
    public static void main(String[] args){
    Node root = null;
    root = newNode(1);
    root.left = newNode(4);
    root.right = newNode(5);
    root.left.left = newNode(4);
    root.left.right = newNode(4);
    root.right.right = newNode(5);
    System.out.print(longestSamevaluePath(root));
}
   static int res = 0;
    public static int longestSamevaluePath(Node root){
        if(root == null) return 0;
        solve(root);
        return res;
    }
    
    public static int solve(Node root) {
        if(root == null) return 0;
        
        int lHeight = solve(root.left);
        int rHeight = solve(root.right);
        int lchk = 0;
        int rchk = 0;
        if(root.left != null && root.left.val == root.val){
            lchk = lHeight + 1;
        }
        
        if(root.right != null && root.right.val == root.val){
            rchk = rHeight + 1;
        }
        
        res = Math.max(res, lchk + rchk);
        return Math.max(lchk, rchk);
      
    }
}

Get over 150+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription