71 Amazon Interview Questions With Answers You Must Know!

Amazon operations are largely dependent upon technology, which is why the giant hires skilled professionals for numerous technical roles like software developers, etc. Naturally, the Amazon interview questions for such profiles will consist of coding/ tech questions. There are four blocks of interview rounds for tech profiles specifically software development engineer (SDE). These are classified on the basis of interviewers i.e. hiring manager, bar raiser, interviewers, and shadows. It is important to note that each of these interviewers will test you on both leadership competencies as well as technical competencies.

We have already elaborated on the leadership and behavioral questions. In this section, we will have a look at some common Amazon interview questions and answers that test tech competencies.

Q1. Give examples of greedy algorithms.

Q2. Define checked exception.

A checked exception also referred to as a compile-time exception, is a fault in the code that can be recovered, as against unchecked exceptions, something wrong in the code that cannot be recovered.

Q3. What is a data structure and its types?

A data structure refers to the relationship between the multiple data and the technique to manage, organize, and efficiently sort said data. There are two types- linear and non-linear data structure. Linear data structures are ones that store data linearly or sequentially. Some examples are queues, stacks, arrays, etc. Non-linear data structures are more complex structures that are connected to the multiple, previous, and next elements. Its examples are tree, graph, and hashmap.

Q4. Explain operator overloading.

Also referred to as operator ad hoc polymorphism, operator overloading is when different operators have different implementations in reference to the arguments. 

Q5. What does tree traversal mean?

Tree traversal refers to the process of visiting each tree node in the data structure, just once. This can be done in three ways i.e. inorder, preorder, and postorder.

Q6. What is the meaning of a database?

The database is the term used to refer to a collection of organized data stored in a computer system that be accessed electronically. 

The Amazon interview questions listed above were some of the most basic tech-related questions. Now let's have a look at some coding questions that will help you prepare for your interview.

Q7. How do you find the missing number in the array?

package com.devglan;
import java.util.Arrays;
public class FindMissingNumber {
 public static int calculateSumOfNNumbers(int n){
 return (n * (n + 1))/2;
 }
 public static int calculateSum(int [] array){
 return Arrays.stream(array).sum();
 }
 public static void main(String [] args){
 int n = 9;
 int[] numbers = {1, 2, 4, 9, 7, 8, 5, 6};
 int nNumberSum = FindMissingNumber.calculateSumOfNNumbers(n);
 int sumOfArray = calculateSum(numbers);
 int missingNumber = nNumberSum - sumOfArray;
 System.out.println(String.format(

import java.util.*;
 public class Exercise52 {
 public static void main(String[] args)
 {
 Scanner in = new Scanner(System.in);
 System.out.print(

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode() : val(0), next(nullptr) {}
 * ListNode(int x) : val(x), next(nullptr) {}
 * ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
 
 }
};

/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;

public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/

class Solution {
public Node copyRandomList(Node head) {

}
}

boolean isBST(Node node)

{

if (node == null)

return true;

/* False if left is > than node */

if (node.left != null && node.left.data > node.data)

return false;

/* False if right is < than node */

if (node.right != null && node.right.data < node.data)

return false;

/* False if, recursively, the left or right is not a BST */

if (!isBST(node.left) || !isBST(node.right))

return false;

/* Passing all that, it's a BST */

return true;

}

class Solution {
public boolean wordBreak(String s, List<String> wordDict) {

}
}

import java.util.*;

class GFG

{

// Returns the count of ways we can

// sum S[0...m-1] coins to get sum n

static int count(int S[], int m, int n)

{

// If n is 0 then there is 1 solution

// (do not include any coin)

if (n == 0)

return 1;

// If n is less than 0 then no

// solution exists

if (n < 0)

return 0;

// If there are no coins and n

// is greater than 0, then no

// solution exist

if (m <= 0)

return 0;

// count is sum of solutions (i)

// including S[m-1] (ii) excluding S[m-1]

return count(S, m - 1, n) +

count(S, m, n - S[m - 1]);

}

// Driver code

public static void main(String args[])

{

int arr[] = { 1, 2, 3 };

int m = arr.length;

System.out.println(count(arr, m, 4));

}

}

public class Solution {
 private static final int[] FACT = { // 479001600 < 2147483647 < 6227020800
 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600
 };
 public List<List<Integer>> permute(int[] nums) {
 Arrays.sort(nums);
 List<List<Integer>> result = new ArrayList<>(nums.length);
 for (int k = 0; k < FACT[nums.length]; ++k) {
 result.add(permutation(nums, k));
 }
 return result;
 }
 List<Integer> permutation(int[] nums, int k) {
 // k %= FACT[nums.length]; // in case you want to use it elsewhere
 List<Integer> source = toList(nums);
 List<Integer> result = new ArrayList(nums.length);
 while (!source.isEmpty()) {
 int f = FACT[source.size() - 1];
 result.add(source.remove(k / f));
 k %= f;
 }
 return result;
 }
 List<Integer> toList(int[] nums) {
 List<Integer> result = new LinkedList<>();
 for (int num : nums) {
 result.add(num);
 }
 return result;
 }
}

import java.io.IOException;

class Main

{

// Print all subsets of given set[]

static void printSubsets(char set[])

{

int n = set.length;

// Run a loop for printing all 2^n

// subsets one by one

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

{

System.out.print(

import java.io.IOException;

class Main

{

// Print all subsets of given set[]

static void printSubsets(char set[])

{

int n = set.length;

// Run a loop for printing all 2^n

// subsets one by one

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

{

System.out.print(

/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/

class Solution {
public Node cloneGraph(Node node) {

}
}

class Solution {
public int[] searchRange(int[] nums, int target) {

}
}

class Solution {
public int search(int[] nums, int target) {

}
}

import java.util.Arrays;

import java.util.Collections;

import java.util.ArrayList;

class GFG {

public static void kLargest(Integer[] arr, int k)

{

// Sort the given array arr in reverse order

// This method doesn't work with primitive data

// types. So, instead of int, Integer type

// array will be used

Arrays.sort(arr, Collections.reverseOrder());

// Print the first kth largest elements

for (int i = 0; i < k; i++)

System.out.print(arr[i] + " ");

}

public static ArrayList<Integer> kLargest(int[] arr, int k)

{

//Convert using stream

Integer[] obj_array = Arrays.stream( arr ).boxed().toArray( Integer[] :: new);

Arrays.sort(obj_array, Collections.reverseOrder());

ArrayList<Integer> list = new ArrayList<>(k);

for (int i = 0; i < k; i++)

list.add(obj_array[i]);

return list;

}

public static void main(String[] args)

{

Integer arr[] = new Integer[] { 1, 23, 12, 9,

30, 2, 50 };

int k = 3;

kLargest(arr, k);

//This code is contributed by Niraj Dubey

//What if primitive datatype array is passed and wanted to return in ArrayList<Integer>

int[] prim_array = { 1, 23, 12, 9, 30, 2, 50 };

System.out.print(kLargest(prim_array, k));

}

}

// A Java program for in-place conversion of Binary Tree to DLL

// A binary tree node has data, left pointers and right pointers

class Node

{

int data;

Node left, right;

public Node(int data)

{

this.data = data;

left = right = null;

}

}

class BinaryTree

{

Node root;

// head --> Pointer to head node of created doubly linked list

Node head;

// Initialize previously visited node as NULL. This is

// static so that the same value is accessible in all recursive

// calls

static Node prev = null;

// A simple recursive function to convert a given Binary tree

// to Doubly Linked List

// root --> Root of Binary Tree

void BinaryTree2DoubleLinkedList(Node root)

{

// Base case

if (root == null)

return;

// Recursively convert left subtree

BinaryTree2DoubleLinkedList(root.left);

// Now convert this node

if (prev == null)

head = root;

else

{

root.left = prev;

prev.right = root;

}

prev = root;

// Finally convert right subtree

BinaryTree2DoubleLinkedList(root.right);

}

/* Function to print nodes in a given doubly linked list */

void printList(Node node)

{

while (node != null)

{

System.out.print(node.data + " ");

node = node.right;

}

}

// Driver program to test above functions

public static void main(String[] args)

{

// Let us create the tree as shown in above diagram

BinaryTree tree = new BinaryTree();

tree.root = new Node(10);

tree.root.left = new Node(12);

tree.root.right = new Node(15);

tree.root.left.left = new Node(25);

tree.root.left.right = new Node(30);

tree.root.right.left = new Node(36);

// convert to DLL

tree.BinaryTree2DoubleLinkedList(tree.root);

// Print the converted List

tree.printList(tree.head);

}

}

class Node {

int data;

Node left, right;

public Node(int item) {

data = item;

left = right = null;

}

}

// An object of Res is passed around so that the

// same value can be used by multiple recursive calls.

class Res {

public int val;

}

class BinaryTree {

// Root of the Binary Tree

Node root;

// This function returns overall maximum path sum in 'res'

// And returns max path sum going through root.

int findMaxUtil(Node node, Res res)

{

// Base Case

if (node == null)

return 0;

// l and r store maximum path sum going through left and

// right child of root respectively

int l = findMaxUtil(node.left, res);

int r = findMaxUtil(node.right, res);

// Max path for parent call of root. This path must

// include at-most one child of root

int max_single = Math.max(Math.max(l, r) + node.data,

node.data);

// Max Top represents the sum when the Node under

// consideration is the root of the maxsum path and no

// ancestors of root are there in max sum path

int max_top = Math.max(max_single, l + r + node.data);

// Store the Maximum Result.

res.val = Math.max(res.val, max_top);

return max_single;

}

int findMaxSum() {

return findMaxSum(root);

}

// Returns maximum path sum in tree with given root

int findMaxSum(Node node) {

// Initialize result

// int res2 = Integer.MIN_VALUE;

Res res = new Res();

res.val = Integer.MIN_VALUE;

// Compute and return result

findMaxUtil(node, res);

return res.val;

}

/* Driver program to test above functions */

public static void main(String args[]) {

BinaryTree tree = new BinaryTree();

tree.root = new Node(10);

tree.root.left = new Node(2);

tree.root.right = new Node(10);

tree.root.left.left = new Node(20);

tree.root.left.right = new Node(1);

tree.root.right.right = new Node(-25);

tree.root.right.right.left = new Node(3);

tree.root.right.right.right = new Node(4);

System.out.println("maximum path sum is : " +

tree.findMaxSum());

}

}

import java.io.*;

class GFG {

// An Inplace function to

// rotate a N x N matrix

// by 90 degrees in

// anti-clockwise direction

static void rotateMatrix(int N, int mat[][])

{

// Consider all squares one by one

for (int x = 0; x < N / 2; x++) {

// Consider elements in group

// of 4 in current square

for (int y = x; y < N - x - 1; y++) {

// Store current cell in

// temp variable

int temp = mat[x][y];

// Move values from right to top

mat[x][y] = mat[y][N - 1 - x];

// Move values from bottom to right

mat[y][N - 1 - x]

= mat[N - 1 - x][N - 1 - y];

// Move values from left to bottom

mat[N - 1 - x][N - 1 - y]

= mat[N - 1 - y][x];

// Assign temp to left

mat[N - 1 - y][x] = temp;

}

}

}

// Function to print the matrix

static void displayMatrix(int N, int mat[][])

{

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

for (int j = 0; j < N; j++)

System.out.print(" " + mat[i][j]);

System.out.print("\n");

}

System.out.print("\n");

}

/* Driver program to test above functions */

public static void main(String[] args)

{

int N = 4;

// Test Case 1

int mat[][] = { { 1, 2, 3, 4 },

{ 5, 6, 7, 8 },

{ 9, 10, 11, 12 },

{ 13, 14, 15, 16 } };

// Test Case 2

/* int mat[][] = {

{1, 2, 3},

{4, 5, 6},

{7, 8, 9}

};

*/

// Test Case 3

/*int mat[][] = {

{1, 2},

{4, 5}

};*/

// displayMatrix(mat);

rotateMatrix(N, mat);

// Print rotated matrix

displayMatrix(N, mat);

}

}

import java.io.*;

class GFG

{

static int NUM_LINE = 2;

static int NUM_STATION = 4;

// Utility function to find minimum of two numbers

static int min(int a, int b)

{

return a < b ? a : b;

}

static int carAssembly(int a[][], int t[][], int e[], int x[])

{

int T1[]= new int [NUM_STATION];

int T2[] =new int[NUM_STATION] ;

int i;

// time taken to leave first station in line 1

T1[0] = e[0] + a[0][0];

// time taken to leave first station in line 2

T2[0] = e[1] + a[1][0];

// Fill tables T1[] and T2[] using

// the above given recursive relations

for (i = 1; i < NUM_STATION; ++i)

{

T1[i] = min(T1[i - 1] + a[0][i],

T2[i - 1] + t[1][i] + a[0][i]);

T2[i] = min(T2[i - 1] + a[1][i],

T1[i - 1] + t[0][i] + a[1][i]);

}

// Consider exit times and return minimum

return min(T1[NUM_STATION-1] + x[0],

T2[NUM_STATION-1] + x[1]);

}

// Driver code

public static void main (String[] args)

{

int a[][] = {{4, 5, 3, 2},

{2, 10, 1, 4}};

int t[][] = {{0, 7, 4, 5},

{0, 9, 2, 8}};

int e[] = {10, 12}, x[] = {18, 7};

System.out.println(carAssembly(a, t, e, x));

}

}

import java.util.Arrays;

class GFG {

public static void main(String args[])

{

int[] arr = { 5, -2, 23, 7, 87, -42, 509 };

System.out.println(

import java.util.*;

import java.lang.*;

import java.io.*;

class Array_Rotation

{

// Function to rightRotate array

static void RightRotate(int a[],

int n, int k)

{

// If rotation is greater

// than size of array

k=k%n;

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

{

if(i<k)

{

// Printing rightmost

// kth elements

System.out.print(a[n + i - k]

+

public class Cell {

private final int row, col;

private CellType cellType;

public Cell(int row, int col)

{

this.row = row;

this.col = col;

}

public CellType getCellType()

{

return cellType;

}

public void setCellType(CellType cellType)

{

this.cellType = cellType;

}

public int getRow()

{

return row;

}

public int getCol()

{

return col;

}

}

#include <bits/stdc++.h>

using namespace std;

// Function to print permutations of string

// This function takes three parameters:

// 1. String

// 2. Starting index of the string

// 3. Ending index of the string.

void permute(string a, int l, int r)

{

// Base case

if (l == r)

cout<<a<<endl;

else

{

// Permutations made

for (int i = l; i <= r; i++)

{

// Swapping done

swap(a[l], a[i]);

// Recursion called

permute(a, l+1, r);

//backtrack

swap(a[l], a[i]);

}

}

}

// Driver Code

int main()

{

string str = "ABC";

int n = str.size();

permute(str, 0, n-1);

return 0;

}

class QNode {

int key;

QNode next;

// constructor to create a new linked list node

public QNode(int key)

{

this.key = key;

this.next = null;

}

}

// A class to represent a queue

// The queue, front stores the front node of LL and rear stores the

// last node of LL

class Queue {

QNode front, rear;

public Queue()

{

this.front = this.rear = null;

}

// Method to add an key to the queue.

void enqueue(int key)

{

// Create a new LL node

QNode temp = new QNode(key);

// If queue is empty, then new node is front and rear both

if (this.rear == null) {

this.front = this.rear = temp;

return;

}

// Add the new node at the end of queue and change rear

this.rear.next = temp;

this.rear = temp;

}

// Method to remove an key from queue.

void dequeue()

{

// If queue is empty, return NULL.

if (this.front == null)

return;

// Store previous front and move front one node ahead

QNode temp = this.front;

this.front = this.front.next;

// If front becomes NULL, then change rear also as NULL

if (this.front == null)

this.rear = null;

}

}

// Driver class

public class Test {

public static void main(String[] args)

{

Queue q = new Queue();

q.enqueue(10);

q.enqueue(20);

q.dequeue();

q.dequeue();

q.enqueue(30);

q.enqueue(40);

q.enqueue(50);

q.dequeue();

System.out.println("Queue Front : " + q.front.key);

System.out.println("Queue Rear : " + q.rear.key);

}

}

class LIS {

static int max_ref; // stores the LIS

/* To make use of recursive calls, this function must

return two things: 1) Length of LIS ending with element

arr[n-1]. We use max_ending_here for this purpose 2)

Overall maximum as the LIS may end with an element

before arr[n-1] max_ref is used this purpose.

The value of LIS of full array of size n is stored in

*max_ref which is our final result */

static int _lis(int arr[], int n)

{

// base case

if (n == 1)

return 1;

// 'max_ending_here' is length of LIS ending with

// arr[n-1]

int res, max_ending_here = 1;

/* Recursively get all LIS ending with arr[0],

arr[1] ... arr[n-2]. If arr[i-1] is smaller

than arr[n-1], and max ending with arr[n-1] needs

to be updated, then update it */

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

res = _lis(arr, i);

if (arr[i - 1] < arr[n - 1]

&& res + 1 > max_ending_here)

max_ending_here = res + 1;

}

// Compare max_ending_here with the overall max. And

// update the overall max if needed

if (max_ref < max_ending_here)

max_ref = max_ending_here;

// Return length of LIS ending with arr[n-1]

return max_ending_here;

}

// The wrapper function for _lis()

static int lis(int arr[], int n)

{

// The max variable holds the result

max_ref = 1;

// The function _lis() stores its result in max

_lis(arr, n);

// returns max

return max_ref;

}

// driver program to test above functions

public static void main(String args[])

{

int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };

int n = arr.length;

System.out.println("Length of lis is " + lis(arr, n)

+ "\n");

}

}

class Node

{

int data;

Node left, right;

Node(int item)

{

data = item;

left = right = null;

}

}

class BinaryTree

{

Node root;

/* Function to find LCA of n1 and n2. The function assumes that both

n1 and n2 are present in BST */

Node lca(Node node, int n1, int n2)

{

if (node == null)

return null;

// If both n1 and n2 are smaller than root, then LCA lies in left

if (node.data > n1 && node.data > n2)

return lca(node.left, n1, n2);

// If both n1 and n2 are greater than root, then LCA lies in right

if (node.data < n1 && node.data < n2)

return lca(node.right, n1, n2);

return node;

}

/* Driver program to test lca() */

public static void main(String args[])

{

// Let us construct the BST shown in the above figure

BinaryTree tree = new BinaryTree();

tree.root = new Node(20);

tree.root.left = new Node(8);

tree.root.right = new Node(22);

tree.root.left.left = new Node(4);

tree.root.left.right = new Node(12);

tree.root.left.right.left = new Node(10);

tree.root.left.right.right = new Node(14);

int n1 = 10, n2 = 14;

Node t = tree.lca(tree.root, n1, n2);

System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);

n1 = 14;

n2 = 8;

t = tree.lca(tree.root, n1, n2);

System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);

n1 = 10;

n2 = 22;

t = tree.lca(tree.root, n1, n2);

System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);

}

}

class LinkedList {

Node head; // head of list

/* Linked list Node*/

class Node {

int data;

Node next;

Node(int d)

{

data = d;

next = null;

}

}

// This function rotates a linked list counter-clockwise

// and updates the head. The function assumes that k is

// smaller than size of linked list. It doesn't modify

// the list if k is greater than or equal to size

void rotate(int k)

{

if (k == 0)

return;

// Let us understand the below code for example k = 4

// and list = 10->20->30->40->50->60.

Node current = head;

// current will either point to kth or NULL after this

// loop. current will point to node 40 in the above example

int count = 1;

while (count < k && current != null) {

current = current.next;

count++;

}

// If current is NULL, k is greater than or equal to count

// of nodes in linked list. Don't change the list in this case

if (current == null)

return;

// current points to kth node. Store it in a variable.

// kthNode points to node 40 in the above example

Node kthNode = current;

// current will point to last node after this loop

// current will point to node 60 in the above example

while (current.next != null)

current = current.next;

// Change next of last node to previous head

// Next of 60 is now changed to node 10

current.next = head;

// Change head to (k+1)th node

// head is now changed to node 50

head = kthNode.next;

// change next of kth node to null

kthNode.next = null;

}

/* Given a reference (pointer to pointer) to the head

of a list and an int, push a new node on the front

of the list. */

void push(int new_data)

{

/* 1 & 2: Allocate the Node &

Put in the data*/

Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

new_node.next = head;

/* 4. Move the head to point to new Node */

head = new_node;

}

void printList()

{

Node temp = head;

while (temp != null) {

System.out.print(temp.data + " ");

temp = temp.next;

}

System.out.println();

}

/* Driver program to test above functions */

public static void main(String args[])

{

LinkedList llist = new LinkedList();

// create a list 10->20->30->40->50->60

for (int i = 60; i >= 10; i -= 10)

llist.push(i);

System.out.println("Given list");

llist.printList();

llist.rotate(4);

System.out.println("Rotated Linked List");

llist.printList();

}

} /*

import java.io.*;

class countSetBits {

/* Function to get no of set

bits in binary representation

of positive integer n */

static int countSetBits(int n)

{

int count = 0;

while (n > 0) {

count += n & 1;

n >>= 1;

}

return count;

}

// driver program

public static void main(String args[])

{

int i = 9;

System.out.println(countSetBits(i));

}

}

// Java program to find smallest

// window containing

// all characters of a pattern.

public class GFG {

static final int no_of_chars = 256;

// Function to find smallest

// window containing

// all characters of 'pat'

static String findSubString(String str, String pat)

{

int len1 = str.length();

int len2 = pat.length();

// Check if string's length is

// less than pattern's

// length. If yes then no such

// window can exist

if (len1 < len2) {

System.out.println("No such window exists");

return "";

}

int hash_pat[] = new int[no_of_chars];

int hash_str[] = new int[no_of_chars];

// Store occurrence ofs

// characters of pattern

for (int i = 0; i < len2; i++)

hash_pat[pat.charAt(i)]++;

int start = 0, start_index = -1,

min_len = Integer.MAX_VALUE;

// Start traversing the string

// Count of characters

int count = 0;

for (int j = 0; j < len1; j++) {

// Count occurrence of characters

// of string

hash_str[str.charAt(j)]++;

// If string's char matches

// with pattern's char

// then increment count

if (hash_str[str.charAt(j)]

<= hash_pat[str.charAt(j)])

count++;

// If all the characters are matched

if (count == len2) {

// Try to minimize the window

while (hash_str[str.charAt(start)]

> hash_pat[str.charAt(start)]

|| hash_pat[str.charAt(start)]

== 0) {

if (hash_str[str.charAt(start)]

> hash_pat[str.charAt(start)])

hash_str[str.charAt(start)]--;

start++;

}

// update window size

int len_window = j - start + 1;

if (min_len > len_window) {

min_len = len_window;

start_index = start;

}

}

}

// If no window found

if (start_index == -1) {

System.out.println("No such window exists");

return "";

}

// Return substring starting

// from start_index

// and length min_len

return str.substring(start_index,

start_index + min_len);

}

// Driver Method

public static void main(String[] args)

{

String str = "this is a test string";

String pat = "tist";

System.out.print("Smallest window is :\n "

+ findSubString(str, pat));

}

}

class GFG {

// This function updates indexes

// of elements 'a' and 'b'

static void updateindex(int index[], int a,

int ai, int b, int bi)

{

index[a] = ai;

index[b] = bi;

}

// This function returns minimum number

// of swaps required to arrange

// all elements of arr[i..n] become arranged

static int minSwapsUtil(int arr[], int pairs[],

int index[], int i, int n)

{

// If all pairs processed so

// no swapping needed return 0

if (i > n)

return 0;

// If current pair is valid so

// DO NOT DISTURB this pair

// and move ahead.

if (pairs[arr[i]] == arr[i + 1])

return minSwapsUtil(arr, pairs, index, i + 2, n);

// If we reach here, then arr[i] and

// arr[i+1] don't form a pair

// Swap pair of arr[i] with arr[i+1]

// and recursively compute minimum swap

// required if this move is made.

int one = arr[i + 1];

int indextwo = i + 1;

int indexone = index[pairs[arr[i]]];

int two = arr[index[pairs[arr[i]]]];

arr[i + 1] = arr[i + 1] ^ arr[indexone] ^

(arr[indexone] = arr[i + 1]);

updateindex(index, one, indexone, two, indextwo);

int a = minSwapsUtil(arr, pairs, index, i + 2, n);

// Backtrack to previous configuration.

// Also restore the previous

// indices, of one and two

arr[i + 1] = arr[i + 1] ^ arr[indexone] ^

(arr[indexone] = arr[i + 1]);

updateindex(index, one, indextwo, two, indexone);

one = arr[i];

indexone = index[pairs[arr[i + 1]]];

// Now swap arr[i] with pair of arr[i+1]

// and recursively compute minimum swaps

// required for the subproblem

// after this move

two = arr[index[pairs[arr[i + 1]]]];

indextwo = i;

arr[i] = arr[i] ^ arr[indexone] ^ (arr[indexone] = arr[i]);

updateindex(index, one, indexone, two, indextwo);

int b = minSwapsUtil(arr, pairs, index, i + 2, n);

// Backtrack to previous configuration. Also restore

// the previous indices, of one and two

arr[i] = arr[i] ^ arr[indexone] ^ (arr[indexone] = arr[i]);

updateindex(index, one, indextwo, two, indexone);

// Return minimum of two cases

return 1 + Math.min(a, b);

}

// Returns minimum swaps required

static int minSwaps(int n, int pairs[], int arr[])

{

// To store indices of array elements

int index[] = new int[2 * n + 1];

// Store index of each element in array index

for (int i = 1; i <= 2 * n; i++)

index[arr[i]] = i;

// Call the recursive function

return minSwapsUtil(arr, pairs, index, 1, 2 * n);

}

// Driver code

public static void main(String[] args) {

// For simplicity, it is assumed that arr[0] is

// not used. The elements from index 1 to n are

// only valid elements

int arr[] = {0, 3, 5, 6, 4, 1, 2};

// if (a, b) is pair than we have assigned elements

// in array such that pairs[a] = b and pairs[b] = a

int pairs[] = {0, 3, 6, 1, 5, 4, 2};

int m = pairs.length;

// Number of pairs n is half of total elements

int n = m / 2;

// If there are n elements in array, then

// there are n pairs

System.out.print("Min swaps required is " +

minSwaps(n, pairs, arr));

}

}

/* Class containing left and right child of current

node and key value*/

class Node

{

int data;

Node left, right;

public Node(int item)

{

data = item;

left = right = null;

}

}

public class BinaryTree

{

//Root of the Binary Tree

Node root;

int minimumDepth()

{

return minimumDepth(root);

}

/* Function to calculate the minimum depth of the tree */

int minimumDepth(Node root)

{

// Corner case. Should never be hit unless the code is

// called on root = NULL

if (root == null)

return 0;

// Base case : Leaf Node. This accounts for height = 1.

if (root.left == null && root.right == null)

return 1;

// If left subtree is NULL, recur for right subtree

if (root.left == null)

return minimumDepth(root.right) + 1;

// If right subtree is NULL, recur for left subtree

if (root.right == null)

return minimumDepth(root.left) + 1;

return Math.min(minimumDepth(root.left),

minimumDepth(root.right)) + 1;

}

/* Driver program to test above functions */

public static void main(String args[])

{

BinaryTree tree = new BinaryTree();

tree.root = new Node(1);

tree.root.left = new Node(2);

tree.root.right = new Node(3);

tree.root.left.left = new Node(4);

tree.root.left.right = new Node(5);

System.out.println("The minimum depth of "+

"binary tree is : " + tree.minimumDepth());

}

}

class stairs {

// A simple recursive program to find

// n'th fibonacci number

static int fib(int n)

{

if (n <= 1)

return n;

return fib(n - 1) + fib(n - 2);

}

// Returns number of ways to reach s'th stair

static int countWays(int s)

{

return fib(s + 1);

}

/* Driver program to test above function */

public static void main(String args[])

{

int s = 4;

System.out.println("Number of ways = " + countWays(s));

}

}

public int maxSubArray(int[] nums) {
 int n = nums.length;
 int maximumSubArraySum = Integer.MIN_VALUE;
 int start = 0;
 int end = 0;
 for (int left = 0; left < n; left++) {
 int runningWindowSum = 0;
 for (int right = left; right < n; right++) {
 runningWindowSum += nums[right];
 if (runningWindowSum > maximumSubArraySum) {
 maximumSubArraySum = runningWindowSum;
 start = left;
 end = right;
 }
 }
 }
 logger.info("Found Maximum Subarray between {} and {}", start, end);
 return maximumSubArraySum;
}

// Palindrome PartitioningProblem

public class GFG

{

static boolean isPalindrome(String string, int i, int j)

{

while(i < j)

{

if(string.charAt(i) != string.charAt(j))

return false;

i++;

j--;

}

return true;

}

static int minPalPartion(String string, int i, int j)

{

if( i >= j || isPalindrome(string, i, j) )

return 0;

int ans = Integer.MAX_VALUE, count;

for(int k = i; k < j; k++)

{

count = minPalPartion(string, i, k) +

minPalPartion(string, k + 1, j) + 1;

ans = Math.min(ans, count);

}

return ans;

}

// Driver code

public static void main(String args[])

{

String str = "ababbbabbababa";

System.out.println("Min cuts needed for "

+ "Palindrome Partitioning is " + minPalPartion(str, 0, str.length() - 1));

}

}