Support Engineer Amazon interview experience | Aakriti Sharma

Interview rounds

Round

Easy

Online Coding Interview

Duration90 minutes

Interview date10 Mar 2022

Coding problem2

1. Longest Alternating Subsequence

Moderate

15m average time

85% success

0/80

Asked in companies

You are given an array ‘ARR’ of integers. Your task is to find the length of the longest alternating subsequence.

Note:

A sequence a1, a2, .... an is called an alternating sequence if its elements satisfy one of the following relations : a1 < a2 > a3 < a4 > a5..... or  a1 > a2 < a3 > a4 < a5.

For example:

'ARR' = {3, 10, 1, 2, 30}, the longest alternating subsequence for this array can be {3, 10, 1, 30} or {3, 10, 2, 30}. Therefore, the answer will be 4.

Problem approach

This problem is an extension of longest increasing subsequence problem, but requires more thinking for finding optimal substructure property in this.
We will solve this problem by dynamic Programming method, Let A is given array of length n of integers. We define a 2D array las[n][2] such that las[i][0] contains longest alternating subsequence ending at index i and last element is greater than its previous element and las[i][1] contains longest alternating subsequence ending at index i and last element is smaller than its previous element, then we have following recurrence relation between them,

Try solving now

2. LCA Of Binary Tree

Moderate

10m average time

90% success

0/80

Asked in companies

You have been given a Binary Tree of distinct integers and two nodes ‘X’ and ‘Y’. You are supposed to return the LCA (Lowest Common Ancestor) of ‘X’ and ‘Y’.

The LCA of ‘X’ and ‘Y’ in the binary tree is the shared ancestor of ‘X’ and ‘Y’ that is located farthest from the root.

Note :

You may assume that given ‘X’ and ‘Y’ definitely exist in the given binary tree.

For example :

For the given binary tree

LCA of ‘X’ and ‘Y’ is highlighted in yellow colour.

Problem approach

The idea of this approach is to store the path from the root to n1 and root to n2 in two separate data structures. Then look simultaneously into the values stored in the data structure, and look for the first mismatch.

Try solving now

Round

Easy

Video Call

Duration60 minutes

Interview date8 Apr 2022

Coding problem3

the interviewer was friendly. He firstly ask me questions from my resume and then give coding problem to solve

1. Maximum Sum Subsequence

Hard

45m average time

55% success

0/120

Asked in companies

You are given an array “NUMS” consisting of N integers and an integer, K. Your task is to determine the maximum sum of an increasing subsequence of length K.

Note:

1. The array may contain duplicate elements.
2. The array can also contain negative integers.
3. Every element of the subsequence must be greater than or equal to the previous element.

The subsequence of an array is a sequence of numbers that can be formed by deleting some or no elements without changing the order of the remaining elements. For example, if the given array “NUMS” = {1, 2, 5, 4, 8}, then {1, 2, 5, 4, 8}, {1, 5, 8}, {2} are some of the valid subsequences whereas the sequence {4, 2} is not a valid subsequence as the order of the elements differ from the original array.

Problem approach

This problem is similar to Longest Increasing Subsequence (LIS) problem. and can be solved using Dynamic Programming.

Create two empty array that store result of maximum
sum of alternate sub-sequence
inc[] : inc[i] stores results of maximum sum alternating
subsequence ending with arr[i] such that arr[i]
is greater than previous element of the subsequence
dec[] : dec[i] stores results of maximum sum alternating
subsequence ending with arr[i] such that arr[i]
is less than previous element of the subsequence

Include first element of 'arr' in both inc[] and dec[]
inc[0] = dec[0] = arr[0]

// Maintain a flag i.e. it will makes the greater
// elements count only if the first decreasing element
// is counted.
flag = 0

Traversal two loops
i goes from 1 to n-1
j goes 0 to i-1
IF arr[j] > arr[i]
dec[i] = max(dec[i], inc[j] + arr[i])

// Denotes first decreasing is found
flag = 1

ELSE IF arr[j] < arr[i] && flag == 1
inc[i] = max(inc[i], dec[j]+arr[i]);

Final Last Find maximum value inc[] and dec[] .

Try solving now

2. Inplace rotate matrix 90 degree

Easy

12m average time

80% success

0/40

Asked in companies

You are given a square matrix of non-negative integers of size 'N x N'. Your task is to rotate that array by 90 degrees in an anti-clockwise direction without using any extra space.

For example:

For given 2D array :

    [    [ 1,  2,  3 ],
         [ 4,  5,  6 ],
         [ 7,  8,  9 ]  ]

After 90 degree rotation in anti clockwise direction, it will become:

    [   [ 3,  6,  9 ],
        [ 2,  5,  8 ],
        [ 1,  4,  7 ]   ]

Problem approach

To solve the question without any extra space, rotate the array in form of squares, dividing the matrix into squares or cycles. For example,
A 4 X 4 matrix will have 2 cycles. The first cycle is formed by its 1st row, last column, last row, and 1st column. The second cycle is formed by the 2nd row, second-last column, second-last row, and 2nd column. The idea is for each square cycle, to swap the elements involved with the corresponding cell in the matrix in an anti-clockwise direction i.e. from top to left, left to bottom, bottom to right, and from right to top one at a time using nothing but a temporary variable to achieve this

Try solving now

3. Convert A Given Binary Tree To Doubly Linked List

Moderate

15m average time

80% success

0/80

Asked in companies

Given a Binary Tree, convert this binary tree to a Doubly Linked List.

A Binary Tree (BT) is a data structure in which each node has at most two children.

A Doubly Linked List contains a previous pointer, along with the next pointer and data.

The order of nodes in Doubly Linked List must be the same as Inorder of the given Binary Tree.

The doubly linked list should be returned by taking the next pointer as right and the previous pointer as left.

You need to return the head of the Doubly Linked List.

For the given binary tree :

You need to return the head to the doubly linked list.
The doubly linked list would be: 1 2 3 4 5 and can be represented as:

Problem approach

we traverse the tree in inorder fashion. We add nodes at the beginning of current linked list and update head of the list using pointer to head pointer. Since we insert at the beginning, we need to process leaves in reverse order. For reverse order, we first traverse the right subtree before the left subtree. i.e. do a reverse inorder traversal.

Try solving now

Round

Easy

HR Round

Duration30 minutes

Interview date12 Apr 2022

Coding problem1