Introduction
This article will discuss the most common Amazon interview questions and answers that will help you prepare well for your upcoming interview. Amazon was founded by Jeff Bezos on July 5, 1994, in his garage in Washington. Amazon is an American global technology business focusing on many industries, including E-Commerce, Cloud Computing, Artificial Intelligence, Digital Streaming, and so on.
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. So today, we will discuss some of the most essential amazon interview questions generally asked in amazon interviews.
Amazon Interview Questions
1.Given a Binary Tree, find the sum of all left leaves in it.
Solution (Depth First Traversal)
Algorithm
- Traverse the binary tree in a depth-first manner.
- Push the values of the binary tree in the stack.
-
A left leaf node should be present, so verify that. A binary tree node is a leaf node if and only if:
- if the current node is the parent's left child.
- if the current node's left and right child pointers are NULL.
- Add its value to the variable sum if the current node is a leaf node on the left.
-
Recursively calculate the sum of the left leaf nodes in the left and right subtrees and return if the current node is not a left leaf node.
Implementation
#include<bits/stdc++.h>
using namespace std;
class Node
{
public:
int key;
Node* left, *right;
Node(int key_)
{
key = key_;
left = NULL;
right = NULL;
}
};
int getleftLeafsSum(Node* root)
{
if(root == NULL)
return 0;
stack<Node*> stack_;
stack_.push(root);
int sum = 0;
while(stack_.size() > 0)
{
Node* currentNode = stack_.top();
stack_.pop();
if (currentNode->left != NULL)
{
stack_.push(currentNode->left);
if(currentNode->left->left == NULL && currentNode->left->right == NULL)
{
sum = sum + currentNode->left->key ;
}
}
if (currentNode->right != NULL)
stack_.push(currentNode->right);
}
return sum;
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
For other approaches, you can visit Find the sum of all left leaves in a given Binary Tree.
2.Find the majority element in the array. A majority element in an array Arr[] of size n is an element that appears more than n/2 times.
Solution(Using Hashmap)
Algorithm
- Create a hashmap to store a key-value pair, such as an element-frequency pair.
- Traverse the array.
- If the element does not already exist as a key, insert it into the hashmap; otherwise, get the value of the key (array[i]) and increase the value by one.
- If the count exceeds half, print the majority element and then break.
- If there isn't a majority element, print "No Majority element."
Implementation
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {8, 2, 2, 8, 1, 2, 2, 6, 2};
int n = sizeof(arr) / sizeof(arr[0]);
unordered_map<int, int> m; //defining hashmap
for(int i = 0; i < n; i++)
m[arr[i]]++; //inserting elements in hashmap
int count = 0;
for(auto i : m)
{
if(i.second > n / 2) //printing the majority element
{
count =1;
cout << i.first<<endl;
break;
}
}
if(count == 0)
cout << "No Majority element" << endl;
return 0;
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
You can visit Majority Element in an Array for in-depth and more optimised solutions.
3.Given are N ropes of different lengths. Your task is to connect these ropes into one rope with minimum cost where the cost of connecting two ropes is equal to the sum of their lengths.
Solution(Using Heap)
Algorithm
- Create a min Heap
- At any time, take two ropes of minimum lengths and combine them.
- Pop the two minimal lengths taken above and insert a new length(sum of lengths) into the min-heap.
-
Find the most optimal Cost.
Implementation
#include <bits/stdc++.h>
using namespace std;
int main() {
//Cost is to find the optimal result to connect all ropes.
//n is for the number of ropes.
//ropeLength is for the length of each rope.
int cost=0,n, ropeLength;
cout<<"Enter the number of ropes";
cin>>n;
//Declaring min-heap
priority_queue<int, vector<int>, greater<int>>minh;
//Taking input from the user about the rope's length.
for(int i=0; i<n; i++){
cin>>ropeLength;
minh.push(ropeLength);
}
//Run the loop till the size of the minheap becomes less than 2.
while(minh.size()>=2){
int first=minh.top();
minh.pop();
int second=minh.top();
minh.pop();
cost=cost+first+second;
minh.push(first+second);
}
//Returning the result
cout<<cost<<endl;
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
More detailed problem explanations and solutions are provided here Connect N Ropes with minimum cost.
4. Count the number of Longest Palindromic Substrings.Given a string s, find the length of the longest palindromic substring of the string and also see the number of palindromic substrings of that length.
Solution( Dynamic Programming)
Algorithm
The idea is to store the information of a substring from index i to index j in a dp array. So basically, the value of dp[i][j] will be 1 if the substring from index i to j is a palindrome. Otherwise, it will be 0.
-
The recurrence relation will be that, for dp[i][j], we will check if s[i]==s[j] and dp[i+1][j-1]==1. Because for the substring from index i to j to be a palindrome, the last two characters should be equal, and also, the substring from i+1 and j-1 should be a palindrome in itself. In this way, we can find the value of all dp[i][j] for all i from 0 to n and all j from 0 to n (where n is the length of the string).
-
The base case is all dp[i][i] =1 because the substring from index i to i will be a one character substring, and it will be a palindrome for sure. Also, we will have to initially find the value of dp[i][i+1] as a base case since the recurrence relation is not applicable here. So, we will traverse the whole string once, and, for each index i, we will see if s[i]==s[i+1]. If yes, then, dp[i][i+1]=1, otherwise 0.
Implementation
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string temp){
int n = temp.length();
for (int i = 0; i < n/ 2; i++) {
/* if the charcters at index i and n-i-1 are not equal, return false*/
if (temp[i] != temp[n - i - 1]) {
return false;
}
}
/* Else return true*/
return true;
}
/* This is the function that return the maximum length of the palindromic substring of this string */
int maxLengthOfPalindromicSubstring(string s) {
int sz = s.size();
// Base Case Length 1
if(sz == 1) return 1;
// Base Case Length 2
if(sz == 2 && s[0] == s[1]) return 2;
if(sz == 2 && s[0] != s[1]){
return 2;
}
int longest = 1;
/* Dp array for storing if the substring from index i to j is a palindrome or not*/
bool dp[1000][1000] = {0,};
/* For all length 2 substrings */
for(int i = 1;i<sz;++i){
if(s[i-1]==s[i]){
dp[i-1][i] = 1;
longest = 2;
}
else{
dp[i-1][i] = 0;
}
}
for(int i = sz-1;i>=0;i--){
for(int j = i+1;j<sz;j++){
if(s[j] == s[i] && dp[i+1][j-1] == 1){
dp[i][j] = 1;
if(longest<(j-i+1)){
longest = j-i+1;
}
}
}
}
return longest;
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
You can visit Count the number of Longest Palindromic Substrings for other approaches to the problem.
5.We have been given an integer array/list(ARR) of size 'N'. It only contains 0s, 1s and 2s. Write a solution to sort this array/list.
Solution(Dutch National Flag Algorithm)
Approach
- Maintain three indices as low = 0,mid = 0 and high = n-1
- Traverse the array from start to end while mid is less than equals to high
- If the element at index mid is 0, then swap it with the element at index low. Simultaneously increment the index of low and mid-index.
- If the element at index mid is 1,then shrink the unknown range, i.e , increment the mid index(mid = mid + 1).
- If the element at index mid is 2, then swap it with the element at index high. simultaneously decrease the index of high(high = high - 1).
Implementation
// c++ program to sort the array of 0,1,2 in one go.
#include <bits/stdc++.h>
using namespace std;
// function to sort the array of 0,1,2.
void sortArr(int arr[], int n)
{
int low = 0, mid = 0, high = n - 1;
while (mid <= high)
{
// if the middle element is 0.
if (arr[mid] == 0)
{
swap(arr[mid++], arr[low++]);
}
// if the middle element is 1.
else if (arr[mid] == 1)
{
mid++;
}
// if the middle element is 2.
else
{
swap(arr[mid], arr[high--]);
}
}
}
// main function.
int main()
{
// input array arr.
int arr[] = {1, 0, 0, 2, 1, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
// call of sort function
sortArr(arr, n);
// printing the resultant array after sorting.
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
For other approaches, you can visit Sort Array of 0,1 and 2.
6.Given an array consisting of "n" non-negative integers and an integer "k" denoting the length of the subarray. Find the maximum element in each subarray of size k.
Solution(Using Priority Queue)
Algorithm
- Create a priority queue that stores the elements in descending order of priority.
- Add the first k numbers in the priority queue.
- Print the maximum element in the first subarray.
- Remove the first element from the priority queue.
-
Similarly, update the priority queue in every iteration and display the maximum element in each window.
Implementation
import java.util.Collections;
import java.util.PriorityQueue;
public class Main {
// function to calculate the maximum number in the subarray
private static void maxOfSubarray(int[] arr, int k) {
// create a priority queue which stores the maximum element at the front end
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
int i;
// add first k numbers in the priority queue
for(i = 0 ; i < k ; i++)
priorityQueue.add(arr[i]);
// print the maximum number in the first subarray with size k
System.out.print(priorityQueue.peek()+" ");
// remove the first element from priority queue
priorityQueue.remove(arr[0]);
// add one element in every iteration and find the maximum element
for( ; i < arr.length ; i++) {
priorityQueue.add(arr[i]);
System.out.print(priorityQueue.peek()+" ");
priorityQueue.remove(arr[i - k + 1]);
}
}
// driver Code
public static void main(String[] args) {
int[] arr = new int[] {11 ,3 ,9 ,6};
int k = 3;
maxOfSubarray(arr, k);
}
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
For the solution, you can visit the Maximum of all Subarrays of Size K.
7.We are given a reference or a pointer to the root of a binary search tree. Our task is to find the Lowest Common Ancestor in a Binary Search Tree.
Solution(Recursion)
Algorithm
- Recursively visit the nodes.
- If both given nodes are smaller than the root node, traverse the left subtree.
- If both given nodes are greater than the root node, traverse the right subtree.
- If cases (1) and (2) don’t satisfy, return the current subtree root node.
- If root is Null return Null.
Implementation
//C++ program to find the Lowest Common Ancestor of 2 nodes in a BST
#include <bits/stdc++.h>
using namespace std;
// struct Node to create Nodes in the Binary search tree
struct Node{
int data; // value of the node
Node *left; // left child
Node *right; // right child
Node(int d)
{
this->data = d;
this->left = nullptr;
this->right = nullptr;
}
};
// function that finds the LCA of given 2 nodes present in the binary search tree
Node* findLCAinBST(Node* root, Node *nodeA, Node *nodeB){
if(root==nullptr) // base case
return root;
// if both nodes a and b are smaller than root node
if(nodeA->data < root->data and nodeB->data < root->data)
return findLCAinBST(root->left, nodeA, nodeB); // go to the left subtree
// if both nodes a and b are greater than root node
if(nodeA->data > root->data and nodeB->data > root->data)
return findLCAinBST(root->right, nodeA, nodeB); // go to the right subtree
// return the root since this is the LCA
return root;
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
You can visit Lowest Common Ancestor in a Binary Search Tree for the solution.
8. The next greater element is to find the greater element from the previous one. You will be given an array of numbers. Now, the task is to find the element greater than the element present in the current index of the array.
Solution(Using Stack)
Algorithm
- Mark current element as next greater element.
- Compare the top element of the stack if not empty with next greater element.
- If the top element is less than next greater element, then pop element from the stack. Popped element will have the next greater element in next greater element.
- Keep following the above step while the popped element is smaller than next greater element. Next greater element will be the next greater element for all those elements.
- After that, push the next greater element element in the stack. After the loop is finished, pop each element and print -1 as their next greater element for them.
Implementation
#include <bits/stdc++.h>
using namespace std;
void nextGreaterEle(int numArr[])
{
stack<int> st;
st.push(numArr[0]);
for (int i = 1; i < 5; i++)
{
if (st.empty()) {
st.push(numArr[i]);
continue;
}
while (st.empty() == false && st.top() < numArr[i])
{
cout << st.top()<< " -> " << numArr[i] << endl;
st.pop();
}
st.push(numArr[i]);
}
while (st.empty() == false) {
cout << st.top() << " -> " << -1 << endl;
st.pop();
}
}
/* Driver code */
int main()
{
int arr[] = {5, 10, 4, 12, 2};
nextGreaterEle(arr);
return 0;
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
For the solution, you can visit Next Greater Element.
9.An elevation map of Flatland is given as an array. Every element represents the height of the building. The width of the buildings can be considered 1. Find the volume of trapped rainwater between these buildings.
Solution(Two Pointers Technique)
Algorithm
- Initialize left = 0 (Index of current where min(right-max, left-max) =left-max ).
- Initialize right = heights.size() - 1(Index of current where min(right-max, left-max) =right-max).
- Set right_max and left_max equal to 0.
-
While left < right, do:
-
If heights[left] < heights[right], then:
- Set left_max = max(left_max, heights[left]).
- Add left_max - heights[left] to volume.
- Increment left.
-
Else:
- Set right_max = max(right_max, heights[right]).
- Add right_max - heights[right] to volume.
- Decrement right.
-
If heights[left] < heights[right], then:
Implementation
#include <bits/stdc++.h>
using namespace std;
int rainWaterVol(vector<int> heights) {
int total_volume = 0;
// left and right pointer to track current left_max and right_max.
int left = 0 , right = heights.size() - 1;
int right_max = 0, left_max = 0;
while(left < right) {
/* If current left_max is less than current right_max,
water level depends on left_max.*/
if(heights[left] < heights[right]) {
left_max = max(heights[left], left_max);
total_volume += left_max - heights[left];
left++;
}
else {
/* If current right_max is less than current left_max.
Water level depends on right_max.*/
right_max = max(heights[right], right_max);
total_volume += right_max - heights[right];
right--;
}
}
return total_volume;
}
int main() {
int size;
cout << "Size of the array: ";
cin >> size;
vector<int> heights(size);
cout << "Enter the elements:\n";
for (int i = 0; i < size; i++) {
cin >> heights[i];
}
cout << "Volume of trapped rainwater: " << rainWaterVol(heights);
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
For the solution, you can visit Trapping Rainwater.
5.For a given integer array of size 'N' containing all distinct values, find the total number of Inversions. Note: if a[i] and a[j] are the two elements from the given array, they form an inversion if a[i] > a[j] and i < j.
Solution(Merge Sort)
Algorithm
- In the merge sort algorithm, we divide the given array into two halves (left half, right half) and sort both the halves using recursion. After that, we merge both the sorted halves to get our final sorted array.
- Divide the given array into two equal or almost equal halves in each step until the base case is reached.
- Create a merge_inv function that counts the number of inversions when the left and right halves are merged. if a[i] is greater than b[j] at any point in merge(), there are (half – i) inversions. Because the left and right subarrays are sorted, the remaining elements in the left half (a[i+1], a[i+2],... a[half]) will all be greater than b[j].
- Create a recursive function to split the array in half and find the answer by adding the number of inversions in the first half, the number of inversions in the second half, and the number of inversions by merging the two halves.
- The base case is when there is only one element in the given subarray.
- Print the result.
Implementation
#include <bits/stdc++.h>
using namespace std;
int mergesort_inv(int a[], int tmp[], int l, int r);
int merge_inv(int a[], int tmp[], int l, int half, int r);
// sorts nd returns the inversions
int mergeSort(int a[], int n)
{
int tmp[n];
return mergesort_inv(a, tmp, 0, n - 1);
}
int mergesort_inv(int a[], int tmp[], int l, int r) // merges and returns the inversions
{
int half, inv_cnt = 0;
if (r > l)
{
half = (r + l) / 2;
/*divide and call mergesort_inv function for both the parts*/
inv_cnt = inv_cnt + mergesort_inv(a, tmp, l, half);
inv_cnt = inv_cnt + mergesort_inv(a, tmp, half + 1, r);
// merge the two parts
inv_cnt += merge_inv(a, tmp, l, half + 1, r);
}
return inv_cnt;
}
// merge and return the inversions
int merge_inv(int a[], int tmp[], int l, int half, int r)
{
int i, j, k;
int inv_cnt = 0;
i = l; // index for left subarray
j = half; // index for right subarray
k = l; // index for resultant merged subarray
while ((i <= half - 1) && (j <= r))
{
if (a[i] <= a[j])
{
tmp[k] = a[i];
i++;
k++;
}
else
{
tmp[k] = a[j];
k++;
j++;
inv_cnt = inv_cnt + (half - i); // merge inversion count
}
}
/*Copy the remaining elements of the left
subarray (if there are any) to temp*/
while (i <= half - 1)
{
tmp[k] = a[i];
k++;
i++;
}
/*Copy the remaining elements of the right
subarray (if there are any) to temp*/
while (j <= r)
{
tmp[k] = a[j];
k++;
j++;
}
/*Copy back the merged elements to the
original array*/
for (i = l; i <= r; i++)
a[i] = tmp[i];
return inv_cnt;
}
int main()
{
int a[] = { 7, 5, 9, 3, 4 };
int n = sizeof(a) / sizeof(a[0]);
int res = mergeSort(a, n);
cout << "Inversions: " << res;
return 0;
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
For the solution, you can visit Count Inversions.
10.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;
}
11.Given a text and a wildcard pattern, determine whether that pattern can be matched with the text. The matching should cover the entire text. Return true if the pattern can be equal to the text; otherwise, false.
Note:
- The wildcard pattern can include characters ‘?’ and ‘*.’
- ‘?’: matches any single character.
- ‘*’: matches any sequence of characters (including the empty line)
-
Each occurrence of ‘?’ can be replaced with any character, and each occurrence of ‘*’ can be replaced with a sequence of characters such that the wildcard pattern becomes identical to the input string after replacement.
Solution(Dynamic Programming)
Algorithm
- If the length of the text string is m and pattern length is n, declare a 2-D bool vector named dp of size (n+1)*(m+1) and initialise the values to 0.
-
Base cases:
- dp[0][0] = 1 because empty strings always match.
- Whenever the text string is empty, the pattern string can only be matched if it equals ‘*” because the ‘*’ can be replaced by an empty string. So, if text string s ==” “, if p==’*’, we can write for all i from 0 to n dp[i][0] = 1. Else, dp[i][0] = 0.
- If the pattern string is empty and the text string is not empty, it can never be matched. Therefore, for all i from 0 to m, dp[0][i] = 0;
-
Start from i=1 to n and j=1 to n. Recurrence relation is:
- If p[i-1] == ‘*’, replace this with an empty sequence and check for dp[i][j-1] or replace this with current character s[j-1] move ahead in s and check for dp[i-1][j].
- Else If p[i-1] ==’?’, replace this with the current character and check for the rest, i.e; check for dp[i-1][j-1].
- Else p[i-1] is a character other than the above two, just check if that character is equal to s[j-1] or not. If it is, check for dp[i-1][j-1], otherwise dp[i][j] = false.
- Return dp[n-1][m-1].
Implementation
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
bool isMatch(string s, string p) {
int m = s.length(); //length of string s
int n = p.length(); //length of string p
vector<vector<bool>> dp(n+1, vector<bool>(m+1, false)); //declaration of dp vector
dp[0][0] = true;
bool flag = true;
for (int i = 1; i < dp.size(); ++i) {
if (p[i-1] != '*'){
flag = false;
}
dp[i][0] = flag;
}
for (int i = 1; i <= p.size(); ++i) {
for (int j = 1; j <= s.size(); ++j) {
if (p[i-1] == '*') {
if (dp[i-1][j] || dp[i][j-1]){
dp[i][j] = true;
}
}
else if (p[i-1] == '?') {
if (dp[i-1][j-1] == true){
dp[i][j] = true;
}
}
else {
if(dp[i-1][j-1] == true && p[i-1] == s[j-1]) {
dp[i][j] = true;
}
}
}
}
return dp[dp.size()-1][dp[0].size()-1];
}
int main(){
string s,p;
cin>>s>>p;
if(isMatch(s,p)){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
return 0;
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
For the solution, you can visit Wildcard Matching.
12.Consider a board of size 2 * N and tiles of size “2 * 1”. You have to count the number of ways in which tiling this board is possible. You may place the tile vertically or horizontally, as per your choice.
Solution(Dynamic Programming)
Algorithm
- We declare a DP array of size N before calling the recursive function to store the results of the calculations.
- We find a base case for the recursion and then store the result at every step in this DP array.
- If the result is already present in the array, we need not calculate it again,
- Else we use the DP array to calculate our answer.
Implementation
/* C++ program to count the number of ways to place 2*1 size tiles on a 2 * n size board using the bottom-up approach.*/
#include <iostream>
using namespace std;
// Function to calculate the total number of possible ways of tiling a board.
int numOfWays(int n)
{
// Memoization array to store the total possibilities.
int dp[n + 2];
int i;
// The first 2 numbers of the sequence are 0 and 1.
dp[0] = 0;
dp[1] = 1;
// To calculate the result using the previous 2 results and to store it in the array.
for (i = 2; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
// Returning the nth number.
return dp[n];
}
int main()
{
int n;
// Taking user input.
cout << "Enter the value of N: ";
cin >> n;
// Calling the function to predict the output.
cout << "The total number of possible ways to place the tiles on the board are " << numOfWays(n);
return 0;
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
For the solution, you can visit Tiling Problem.
13.You are given an integer N. For a given N x N chessboard, find a way to place 'N' queens such that no queen can attack any other queen on the chessboard.
A queen can be attacked when it lies in the same row, column, or the same diagonal as any of the other queens. You have to print one such configuration.
Solution(Backtracking)
Algorithm
- Start with the first row.
- Check the number of queens placed. If it is N, then return true.
-
Check all the columns for the current row one by one.
- If the cell [row, column] is safe then mark this cell and recursively call the function for the remaining queens to find if it leads to the solution.
- If it leads to the solution, return true, else unmark the cell [row, column] ( that is, backtrack) and check for the next column.
- If the cell [row, column] is not safe, skip the current column and check for the next one.
- If none of the cells in the current row is safe, then return false.
Implementation
/*C++ code to solve N queen problem by backtracking*/
#include <bits/stdc++.h>
using namespace std;
/*function to check if a cell[i][j] is safe from attack of other queens*/
bool isSafe(int i, int j, int board[4][4], int N)
{
int k, l;
// checking for column j
for (k = 0; k <= i - 1; k++)
{
if (board[k][j] == 1)
return 0;
}
// checking upper right diagonal
k = i - 1;
l = j + 1;
while (k >= 0 && l < N)
{
if (board[k][l] == 1)
return 0;
k = k + 1;
l = l + 1;
}
// checking upper left diagonal
k = i - 1;
l = j - 1;
while (k >= 0 && l >= 0)
{
if (board[k][l] == 1)
return 0;
k = k - 1;
l = l - 1;
}
return 1; //the cell[i][j] is safe
}
int n_queen(int row, int numberOfqueens, int N, int board[4][4])
{
if (numberOfqueens == 0)
return 1;
int j;
for (j = 0; j < N; j++)
{
if (isSafe(row, j, board, N))
{
board[row][j] = 1;
if (n_queen(row + 1, numberOfqueens - 1, N, board))
return 1;
board[row][j] = 0; //backtracking
}
}
return 0;
}
int main()
{
int board[4][4];
int i, j;
for (i = 0; i < 4; i++)
{
for (j = 0; j < 4; j++)
board[i][j] = 0;
}
n_queen(0, 4, 4, board);
//printing the board
for (i = 0; i < 4; i++)
{
for (j = 0; j < 4; j++)
cout << board[i][j] << "\t";
cout << endl;
}
return 0;
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
For the solution, you can visit the N Queens.
14.The median of the stream of integers, or running integers median problem, is that we need to find the effective median of all the incoming integers in the array.
Solution(Heap)
Algorithm
- Check if the input array length is >1. If not, return the first element of the array if the array length is 1. Else return None if the size of the input array is 0.
- Initiate a min-heap and a max-heap with the first two values in the array. Push the smaller value in the max-heap and the bigger value in the min-heap. Initiate curr_med as the average of top elements of both the heaps.
- If the incoming element is greater than the curr_med, push it in the min-heap. Otherwise, in max-heap
- If the sizes of both the heaps are equal, store the median value as the average of the top elements of both the heaps.
- If the sizes of both the heaps differ by 1, store the median value as the top element of the bigger heap.
- If the sizes differ by more than one, pop the top element from the larger heap and push it into the smaller heap to balance the heaps. Store the median value as the average of the top elements of the heaps.
- Repeat steps 3-7 until the end of the input array.
Implementation
import heapq
def medianOfInt(arr,size):
#creating a min-heap and max-heap as well as a list medians to store all the
#effective medians.
Minheap=[]
Maxheap=[]
medians = []
if size==0:
return None
if size==1:
return [arr[0]] #need atleast one element in the input array.
med = arr[0]
medians.append(med) #append the medians in the median array.
heapq.heappush(Maxheap, -med)
for i in range(1, size):
x = arr[i]
if len(Maxheap) > len(Minheap):
if x < med:
heapq.heappush(Minheap, -(heapq.heappop(Maxheap)))
heapq.heappush(Maxheap, -x)
else:
heapq.heappush(Minheap, x)
med = ((-Maxheap[0]) + Minheap[0]) / 2.0
elif len(Maxheap) < len(Minheap):
if x > med:
heapq.heappush(Maxheap, -(heapq.heapop(Minheap)))
heapq.heappush(Minheap, x)
else:
heapq.heappush(Maxheap, -x)
med = ((-Maxheap[0]) + Minheap[0]) / 2.0
else:
if x < med:
heapq.heappush(Maxheap, -x)
med = int(-Maxheap[0])
else:
heapq.heappush(Minheap, x)
med = int(Minheap[0])
medians.append(med)
return medians
arr=[int(x) for x in input().split(" ")]
size=len(arr)
ans=medianOfInt(arr,len(arr))
print(ans)
Before moving on, first, try this Problem on Coding Ninjas Studio.
For the solution, you can visit the Median of Stream of Integers.
15.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.
- 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.
- If ARR[i] == 1, we increment 'CUMULATIVE' by 1.
- Else, we decrement it by 1.
- Add FREQUENCY[CUMULATIVE] to RESULT. This is because the total subarrays ending on the current element with sum 0 are given by FREQUENCY[CUMULATIVE].
-
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;
}
Click here to know about, Servicenow Interview Questions
16.You are given a linked list of 'N' nodes and an integer 'K'. You have to reverse the given linked list in groups of size K i.e if the list contains x nodes numbered from 1 to x, then you need to reverse each of the groups (1,K),(K+1,2*K), and so on.
For example, if the list is [1, 2, 3, 4, 5, 6] and K = 2, then the new list will be [2, 1, 4, 3, 6, 5].
Solution (Iterative)
Algorithm
-
In this approach, we reverse one block at a time while traversing through the list. Let the block size be denoted by K. We need to follow the following steps to reverse the linked list as required :
- Reverse the subsequent K consecutive nodes or the remaining nodes in the list, whichever is smaller. In the meanwhile, keep track of the information of four nodes, the node before head, head, tail, and the node after tail.
- At last, put the reversed sub-list back to the correct position, in between the node before head (former head) and the node after the tail (former tail).
- Move forward to reverse the next sub-list.
- Repeat the above steps till we reach the end of the linked list or we have considered the entire block array.
Implementation
/*
Time Complexity : O(L)
Space Complexity : O(1)
Where L is the number of nodes in the Linked-List.
*/
Node *getListAfterReverseOperation(Node *head, int n, int b[]) {
// If linked list is empty, return head of the linked list.
if (head == NULL) {
return NULL;
}
// Variable to keep track of the current index in the block array.
int idx = 0;
Node *prev = NULL, *cur = head, *temp = NULL;
Node *tail = NULL, *join = NULL;
bool isHeadUpdated = false;
// Reverse nodes until the list is empty or entire block array has been considered.
while (cur != NULL && idx < n) {
// K represents the size of the current block
int K = b[idx];
// Just move to the next block if size of the current block is zero
if (K == 0) {
idx++;
continue;
}
join = cur;
prev = NULL;
// Reverse nodes until end of list is reached or current block has been reversed
while (cur != NULL && K--) {
temp = cur->next;
cur->next = prev;
prev = cur;
cur = temp;
}
// Update the head pointer when reversing the first block.
if (isHeadUpdated == false) {
head = prev;
isHeadUpdated = true;
}
// Tail pointer keeps track of the last node before the current K-reversed linked list.
// We join the tail pointer with the current K-reversed linked list's head.
if (tail != NULL) {
tail->next = prev;
}
// The tail is then updated to the last node of the current K-reversed linked list.
tail = join;
idx++;
}
// If entire block is iterated and reached at end, then we append the remaining nodes to the tail of the partial modified linked list.
if (tail != NULL) {
tail->next = cur;
}
// Return the head of the linked list.
return head;
}
Before moving on, first, try this Problem on Coding Ninjas Studio.
For the solution, you can visit the Reverse Nodes in k-Group.