Amazon SDE 1 Coding Interview Questions

The four guiding principles of Amazon are: obsessing over the customer rather than the competition, being passionate about invention, being dedicated to operational excellence, and having a long-term perspective. Amazon is motivated by the thrill of developing technologies, creating goods, and offering services that transform lives. They are open to new approaches, act quickly, and are not afraid of making mistakes. Amazon possesses both the size and strength of a big business and the character and heart of a small one.

Additionally, you'll hear that at Amazon, every day is "Day 1."

Why do we mean that? The Amazon strategy of making quick, informed decisions, remaining adaptable, coming up with new ideas, and concentrating on delighting our customers is still in place today.

You can also read the Selenium interview question here.

Amazon Sde 1 Coding Questions

Amazon sde 1 coding questions is divided into 3 sections: easy, medium, and hard questions. Amazon Sde 1 coding questions are generally from topics such as arrays, graphs, dynamic programming, binary search, stacks, and Queues.

Easy Amazon SDE 1 Coding Questions

1. You have been given an array/list ARR of length N consisting of Os and 1s only. Your task is to find the number of subarrays(non-empty) in which the number of Os and 1s are equal.

Input: 1 0 0 1 0 1 1

Output: 8

We will follow the given algorithm to solve this question.

We will maintain 'RESULT' to count subarrays with equal 0s and 1s.
We will initialize 'CUMULATIVE' to 0 to store the cumulative sum.
Declare a hashtable 'FREQUENCY' that stores the frequency of the cumulative sum.
1. Initialize FREQUENCY[0] by 1 as the cumulative sum of the empty array is 0.
Now start iterating over the array and calculate the cumulative sum.
1. If ARR[i] == 1, we increment 'CUMULATIVE' by 1.
2. Else, we decrement it by 1.
3. Add FREQUENCY[CUMULATIVE] to RESULT. This is because the total subarrays ending on the current element with sum 0 are given by FREQUENCY[CUMULATIVE].
4. Increment FREQUENCY[CUMULATIVE] by 1.

#include<unordered_map>
int subarrays(vector<int>& arr, int n)
{
    int cumulative = 0;
    int result = 0;

    unordered_map<int, int> frequency;

    frequency[0] = 1;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 1)
        {
            cumulative += 1;
        }
        else
        {
            cumulative -= 1;
        }

        // Required subarrays ending on the current element.
        result += frequency[cumulative];

        frequency[cumulative]++;
    }

    return result;
}

You can also try this code with Online C++ Compiler

Run Code

Click here to know about, Servicenow Interview Questions

2. You are given a sentence 'S' in the form of the string s, and the word 'W', you need to check whether the given word is present in the sentence or not.

1.Input

S = “Hello World this is coding Ninjas”

W = “Ninjas”

Output: Yes

Explanation: The word is present in the given sentence

2. Input

S = “Hello World this is coding Ninjas”

W = “Coder”

Output: No

Explanation: The word is not present in the given sentence.

The basic idea of this approach is to check each word of the given sentence 'S' if it matches the given word 'W'

Consider the following steps:

Start iterating through each character of sentence string 'S' using a variable 'i' such that 0 <= 'i' < |S|
Create a string "temp" which stores the current word.
Add all the subsequent characters of the sentence till space is detected or if all end of the string is reached.
Check if the word 'W' matches with "temp". Return true if it matches.
After the loop ends return false because the word is not present in the sentence.

bool findWord(string &s, string w)
{
    int n = s.size();

    for (int i = 0; i < n; i++)
    {

        // To store the current word.
        string temp = "";

        // Processing the string to find individual words.
        while (i < n && s[i] != ' ')
        {
            temp += s[i];
            i++;
        }

        // Checking if the current word is equal to W or not.
        if (temp == w)
        {
            return true;
        }
    }

    // If no word matches, then return false.
    return false;
}

You can also try this code with Online C++ Compiler

Run Code

3. Write a program to implement topoSort in the graph.

Toposort in a graph is a linear ordering of vertices such that if there is an edge between u->v, u appears before v in that ordering.

We will do the DFS order traversal of the graph and use a stack data structure to store the topo sort of the graph.
We will push the last visited nodes into the graph first so that when we pop from the graph, it will be last in the output.
Finally, pop all the values from the stack, and print it.
We will get the topo sort of the given graph.

#include <bits/stdc++.h>
using namespace std;
void findTopoSort(int node, vector<int> &vis, stack<int> &st, vector<int> adj[])
{
    vis[node] = 1;

    for (auto it : adj[node])
    {
        if (!vis[it])
        {
            findTopoSort(it, vis, st, adj);
        }
    }
    st.push(node);
}
vector<int> topoSort(int N, vector<int> adj[])
{
    stack<int> st;
    vector<int> vis(N, 0);
    for (int i = 0; i < N; i++)
    {
        if (vis[i] == 0)
        {
            findTopoSort(i, vis, st, adj);
        }
    }
    vector<int> topo;
    while (!st.empty())
    {
        topo.push_back(st.top());
        st.pop();
    }
    return topo;
}

You can also try this code with Online C++ Compiler

Run Code

Medium Amazon Sde 1 Coding Questions

1. You are given a string of lowercase letters, you have to rearrange the string in such a way that no two adjacent letters are the same.

1.Input: abba

Output: abab

2. Input: abba

Output: abab

We will follow the given steps to solve this problem.

At each stage, we'll require the most common character.
And the Max heap can be used to accomplish this.
We'll create a Max heap with all the characters and their frequencies arranged in descending frequency order.
We will now remove the top two pairs—first and second—from the pile.
Add the first character of the first pair to a new string, reduce its frequency by 1, and push it to the top of the heap if its frequency is greater than 0.
Add the character from the second pair to the new string, reduce its frequency by 1, and push it to the top of the heap if its frequency is greater than 0.
We will return the output string if the heap's size is zero.
If the heap's size is greater than zero, then there must be just one pair.
Add that character to the final string and return it if the frequency of the last pair is equal to 1.
There is no solution if the frequency of the final pair is greater than 1.

struct cmp {
    bool operator()(pair < char, int > a, pair < char, int > b) {
        if (a.second == b.second)
            return a.first < b.first;
        return a.second < b.second;
    }
};

string rearrangeString(string &str) {
    // Store the frequecy of characters.
    vector < int > hash(26, 0);
    // Max heap store the most frequent element at top.
    priority_queue < pair < char, int > , vector < pair < char, int >> , cmp > myPQ;

    for (int i = 0; i < str.size(); i++) {
        hash[str[i] - 'a'] += 1;
    }
    // Pushing the pairs to priority_queue.
    for (int i = 0; i < 26; i++) {
        if (hash[i] > 0) {
            myPQ.push({char(i + 'a'),hash[i]});
        }
    }
    // The resultant string.
    string ans = "";

    // Iterate while priority queue is having length greater than 1.
    while (myPQ.size() > 1) {
        pair < char, int > mostFreq = myPQ.top();
        myPQ.pop();
        pair < char, int > sec_mostFreq = myPQ.top();
        myPQ.pop();

        ans += mostFreq.first;
        ans += sec_mostFreq.first;

        mostFreq.second -= 1;
        sec_mostFreq.second -= 1;

        if (sec_mostFreq.second > 0) {
            myPQ.push(sec_mostFreq);
        }
        if (mostFreq.second > 0) {
            myPQ.push(mostFreq);
        }

    }
    // If priority queue is empty, return the resultant string.
    if (myPQ.size() == 0) {
        return ans;
    }
    // Else check if there is a solution or not.
    else {
        if (myPQ.top().second > 1) {
            return "NO SOLUTION";
        } else {
            return ans + myPQ.top().first;
        }
    }
}

You can also try this code with Online C++ Compiler

Run Code

2. You are given an 'N' * 'N matrix where all numbers are distinct from (1 toN*N). You are required to find the maximum length path (starting from any row) such that all cells along the path are always in increasing order with a difference of 1. Only four possible movements are allowed, i.e., Up, Down, Left, and Right.

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

Output: 4

Explanation: The longest path is 4-5-6-7

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

Output: 4

Explanation: The longest path is 4-5-6-7

We will follow the given steps to complete the

We will implement two functions namely, findLongestto find the longest path starting from cell ( ‘i’, ‘j’ ) and function ‘findLongestOverAll’ to find the overall longest path satisfying the constraints.
In function findLongest with parameters as indices ‘i’ and ‘j’, 2-D vector ‘MAT’ and an integer ‘n’.
1. Checking the base condition, if either ‘i’ or ‘j’ is less than zero or is greater than or equal to ‘N’, simply return.
Since all numbers are unique and in range from 1 to ‘N’ * ‘N’, there is at most one possible direction from any cell.
1. 1. If ‘j’ is less than ‘N’ - 1 and ( MAT[ i ][ j ] + 1 ) equals ( MAT[ i ][ j + 1 ] ), then return 1 + call the function findLongestwith parameters as ‘i’, ‘j+1’, ‘MAT’, ‘n’.
2. If ‘j’ is greater than zero and ( MAT[ i ][ j ] + 1 ) equals ( MAT[ i ][ j - 1 ] ), then return 1 + call the function findLongestwith parameters as ‘i’, ‘j-1’, ‘MAT’, ‘n’.
3. If ‘i’ is greater than zero and ( MAT[ i ][ j ] + 1 ) equals ( MAT[ i - 1 ][ j ] ), then return 1 + call the function findLongestwith parameters as ‘i-1’, ‘j’, ‘MAT’, ‘n’.
4. If ‘i’ is less than ‘N’ - 1 and ( MAT[ i ][ j ] + 1 ) equals ( MAT[ i + 1 ][ j ] ), then return 1 + call the function findLongestwith parameters as ‘i+1’, ‘j’, ‘MAT’, ‘n’.
5. Return 1.
In function ‘findLongestOverAll’ with parameters as 2-D vector ‘MAT’ and integer ‘N’.
1. Initialize ‘RESULT’ as 1.
2. Compute the longest path beginning from all cells.
3. Iterate from 0 to ‘N-1’ (say, iterator = ‘i’).
4. Iterate from 0 to ‘N-1’ (say, iterator = ‘j’).
Call function findLongestwith parameters as indices ‘i’ and ‘j’, 2-D vector ‘MAT’ and an integer ‘N’.
Update the ‘RESULT’ with a maximum of ‘RESULT’ and the value returned by calling the function ‘findLongestFromACell’.

// Function that returns the length of the longest path beginning with mat[i][j].
int findLongest(int i, int j, vector<vector<int>> &mat, int n)
{

    // Base case.
    if (j < 0 || i < 0 || i >= n || j >= n)
    {
        return 0;
    }

    if (((mat[i][j] + 1) == mat[i][j + 1]) && j < n - 1)
    {
        return 1 + findLongest(i, j + 1, mat, n);
    }

    if (((mat[i][j] + 1) == mat[i][j - 1]) && j > 0)
    {
        return 1 + findLongest(i, j - 1, mat, n);
    }

    if (((mat[i][j] + 1) == mat[i - 1][j]) && i > 0)
    {
        return 1 + findLongest(i - 1, j, mat, n);
    }

    if (((mat[i][j] + 1) == mat[i + 1][j]) && i < n - 1)
    {
        return 1 + findLongest(i + 1, j, mat, n);
    }

    // If none of the adjacent fours is one greater.
    return 1;
}

// Function that returns length of the longest path beginning with any cell.
int findLongestOverAll(vector<vector<int>> &mat, int n)
{

    // Initialize result.
    int result = 1;

    // Compute the longest path beginning from all cells.
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int ans = findLongest(i, j, mat, n);

            // Update result if needed.
            result = max(result, ans);
        }
    }
    return result;
}

You can also try this code with Online C++ Compiler

Run Code

3. You have been given a board where there are 2' rows and 'N’ columns. You have an infinite supply of 2x1 tiles, and you can place a tile in the following ways.

Horizontally as a 1x2 tile
Vertically as a 2x1 tile

Input: 4

Output: 5

We will follow the given algorithm to solve this

Try to place the tile to fill the unit column and calculate the number of ways from smaller sub-problems. We can use bottom-up DP with keeping the previous two values.
At any point, if we are at the ‘idx’ column, then we can place our tile in two ways to fill this column.
- Option 1 - 1 Horizontal Tile
We can place it in this way where we have the ‘idx-1’ column filled.
- Option 2 - 2 Vertical Tiles
We can place it in this way where we have the ‘idx-2’ column filled.
- So, numberOfWaysCur = numberOfWaysPre1 + numberOfWaysPre2
Where numberOfWaysCur is the number of ways to tile to the 'current' column in the board.
Where numberOfWaysPre1 is the number of ways to tile till the 'current-1' column in the board.
Where numberOfWaysPre2 is the number of ways to tile till the 'current-2' column in the board.
Base cases are: When n = 1, there is only one way - Placing 1 Vertical Tile

numberOfWaysPre2 = 1

When n = 2, there are two ways - Placing 2 Vertical Tile and Placing 2 Horizontal Tiles

numberOfWaysPre1 = 2

Now Iterate from i=3 to N and keep updating the three variables.
Also, take care of overflow using modulo 10^9 + 7.

#define MOD 1000000007
int numberOfWaysToTile(long long n)
{
    // Base Cases:
    if (n == 1 || n == 2)
        return n;

    //  Number of ways to tile till 'current' column in the board.
    long long numberOfWaysCur;

    //  Number of ways to tile till 'current-1' or 'previous 1' column in the board
    long long numberOfWaysPre1;

    //  Number of ways to tile till 'current-2' or 'previous 2' column in the board
    long long numberOfWaysPre2;

    //  Initializing for current  = 3;
    numberOfWaysPre2 = 1;
    numberOfWaysPre1 = 2;

    for (long long i = 3; i <= n; i++)
    {
        numberOfWaysCur = (numberOfWaysPre2 + numberOfWaysPre1) % MOD;
        numberOfWaysPre2 = numberOfWaysPre1;
        numberOfWaysPre1 = numberOfWaysCur;
    }

    return numberOfWaysCur;
}

You can also try this code with Online C++ Compiler

Run Code

Hard Amazon Sde 1 Coding Questions

1. You are given an array of positive integers. Find the GCD(Greatest Common Divisor) of a pair of elements such that it is maximum among all possible pairs. GCD(a, b) is the maximum number x, so both a and b are divisible by x.

Input: 5 2 4 3 1

Output: 2

We will follow the above approach

Make an array(of size M) containing the frequency of elements present in the given array. The numbers which are not present in the array will have zero frequency.
Iterate i from M to 1.
Iterate j on multiples of i up to M (i, 2i, 3i,.. <= M).
Count the frequency of j.
If the count is more than 1, then i will be the maximum GCD value.

int maxGCDPair(vector<int> &arr, int n)
{
    int m = 0;
    // Finding maximum element.
    for (int i = 0; i < n; i++)
    {
        m = max(m, arr[i]);
    }
    
    // Finding frequency of each element.
    vector<int> freq(m + 5, 0);
    for (int i = 0; i < n; i++)
    {
        freq[arr[i]]++;
    }


    for (int i = m; i > 0; i--)
    {
        int cnt = 0;
        for (int j = i; j <= m; j += i)
        {
            cnt += freq[j];
        }
        if (cnt > 1)
        {
            // i is a divisor of two or more elements.
            return i;
        }
    }
    return 1;
}

You can also try this code with Online C++ Compiler

Run Code

2. Find the maximum sum subarray of the given array.

Input: [-10,2,5,7,-2,3]

Output: 15

Explanation: There are many subarrays in the given array, but the maximum sum subarray is [2,5,7,-2,3].

As we know that we cannot have a negative sum, we can simply maintain two variables as maximum and local sum, where we would add every element to the local sum. If our local sum exceeds our maximum sum, we shall update our maximum sum and even note down the index. If, in any case, our local sum becomes negative, then it’s better not to consider any elements only, and we would again start from the next index with the local sum as 0.

Declare a variable ‘maxSum’ and initialize it with ‘minimum integer’
Declare a variable ‘localSum’ and initialize it with ‘0’
Declare 3 counter variables as ‘start’, ‘end’, and ‘newStart’ as 0, 0, 0
Run a loop from i = 0 to N
- Add a current element to ‘localSum’
- If 'localSum' is greater than 'maxSum'
  - Update ‘maxSum’ with 'localSum', update start with ‘newStart’ and end with loop counter ‘i’
- If 'localSum' is equal to ‘maxSum’ and the difference between ‘end’ and ‘start’ is less than the difference between ‘newStart’ and ‘i’
  - The update starts with ‘newStart’ and ends with ‘i’
- If 'localSum' is below ‘0’
  - Update ‘localSum’ as 0 and set ‘newStart' as ‘i’ + 1
Return the part of the array starting from ‘start’ and ending at ‘end’

vector<int> maximumsumSubarray(vector<int> &arr, int n)

{
    // Declare a variable 'maxSum' and initialize it as minimum integer
           int maxSum = INT_MIN;
            // Declare a variable 'localSum' and initialize it as 0
        int localSum = 0;
    // Declare and initialize three variables as 'start', 'end' and 'newStart' and initialize them as 0, 0, 0 respectively.
    int start = 0;
    int end = 0;
    int newStart = 0;
    // Run a loop i = 0 to 'N' traversing all the elements
    for (int i = 0; i < n; i++)
    {
        // Add the current element to the localSum
        localSum = localSum + arr[i];
        // If the 'localSum' is greater than the maxSum update all variables
        if (localSum > maxSum)
        {
            maxSum = localSum;
            start = newStart;
            end = i;
        }
        else if (localSum == maxSum)
        {
            if (end - start < i - newStart)
            {
                start = newStart;
                end = i;
            }
        }
        if (localSum < 0)
        {
            localSum = 0;
            newStart = i + 1;
        }
    }
    vector<int> ans;
    for (int i = start; i <= end; i++)
    {
        ans.push_back(arr[i]);
    }
    return ans;
}

You can also try this code with Online C++ Compiler

Run Code

3. You are given an unsorted array/list 'ARR' of 'N' integers. Your task is to return the length of the longest consecutive sequence. The consecutive sequence is in the form ['NUM', NUM' + 1, 'NUM' +2, "NUM' + L], where 'NUM' is the starting integer of the sequence and L' + 1 is the length of the sequence.

Input: [9,5,4,9,10,10,6]

Output: 3

Explanation: The longest consecutive sequence is [4,5,6].

We will follow the given algorithm to solve this

The idea is to sort the array, then iterate through the array and find the longest subarray containing consecutive elements.
We first initialize the variable ‘COUNT’ = 0, which stores the length of the consecutive sequence, and ‘MX’ = 0, which stores the longest length of the consecutive subsequence.
Now run a loop and check if ‘ARR[i - 1]’ + 1 is equal to ‘ARR[i]’ then it will include in the current consecutive subsequence by increment ‘COUNT’ by 1.
If ‘ARR[i - 1]’ is equal to ‘ARR[i]’, then it means it shouldn’t be considered in consecutive sequence because the consecutive sequence is of the form ['NUM', 'NUM' + 1, 'NUM' + 2,...,'NUM' + L].
Else If ‘ARR[i - 1]’ + 1 is not equal to ‘ARR[i]’, then we set ‘COUNT’ to 1. For finding the longest length, we update ‘MX’ with a maximum of ‘COUNT’ and ‘MX’.

#include <algorithm>
int lengthOfLongestConsecutiveSequence(vector<int> &arr, int n) {
    // Sort the given array in ascending order.
    sort(arr.begin(), arr.end());
    // To store length of longest consecutive sequence.
    int mx = 0;
    // To store the length of the current consecutive Sequence.
    int count = 0
    for (int i = 0; i < n; i++) {
        // Check if previous value is consecutive to the current value.
        if (i > 0 && (arr[i] == arr[i - 1] + 1)) {
            count++;
        }
        // Skip if the current value is equals to the previous value.
        else if (i > 0 && arr[i] == arr[i - 1]) {
            continue;
        }
        // Reseting count for next upcoming consecutive sequence.
        else {
            count = 1;
        }
        mx = max(mx, count);        
    }
    return mx;
}

You can also try this code with Online C++ Compiler

Run Code

Conclusion

In this blog, we discussed an introduction to Amazon and amazon sde 1 coding questions, along with code in c++ and sample test cases.

Check out the Amazon Interview Experience to learn about Amazon’s hiring process.

For more interview experience and amazon sde 1 coding questions, you can refer to these links:

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available; look at the Top 150 Interview Puzzles, interview experiences, and interview bundle for placement preparations. Read our blogs on aptitude, competitive programming, interview questions, IT certifications, and data structures and algorithms for the best practice.