# Amazon Coding Questions

### Amazon Practice Coding Questions

NOTE:- Please comment down the code in other languages as well below –

###### Input Specification
• Input1: L, i distance. Find the length of the street covered with light. denoting the number of street lights.
• Input2: An array of L * 2 elements. For each row i, (Xi, Yi) denote that the street light i covers the distance from Xi to Yi.
###### Output Specification:

Your function should return the length of the street covered with light.

###### Example 1:
• Input1: 1
• Input2: {(5, 10)}
• Output:  5

Solution in C-

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int first;
int second;
} Pair;

int comparePairs(const void* a, const void* b) {
Pair* pairA = (Pair*)a;
Pair* pairB = (Pair*)b;
return pairA->first - pairB->first;
}

int main() {
int n;
scanf("%d", &n);

Pair* arr = (Pair*)malloc(n * sizeof(Pair));
for (int i = 0; i < n; i++) {
scanf("%d %d", &arr[i].first, &arr[i].second);
}

qsort(arr, n, sizeof(Pair), comparePairs);

int x = -1e9;
int y = -1e9;

long long ans = 0;
for (int i = 0; i < n; i++) {
int curX = arr[i].first;
int curY = arr[i].second;

if (y <= curX) {
ans += (curY - curX);
x = curX;
y = curY;
} else if (x <= curX && curX <= y && curY >= y) {
x = y;
y = curY;
ans += (y - x);
x = curX;
} else {
continue;
}
}

printf("%lld\n", ans);

free(arr);

return 0;
}

Solution in C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
pair<int, int> arr[n];
for (int i = 0; i < n; i++) { cin >> arr[i].first >> arr[i].second;
}
// sorting by x values
sort(arr, arr + n);

int x = INT_MIN;
int y = INT_MIN;

long long ans = 0;
for (int i =0;i<n;i++)
{
int curX = arr[i].first;
int curY = arr[i].second;

if(y<=curX)
{
ans+=(curY-curX);
x = curX;
y = curY;
}
else if(x<=curX && curX<=y && curY>=y)
{
x = y;
y = curY;
ans+=(y-x);
x = curX;
}
else // previous point completly overlaps new point
{
continue;
}
}
cout<<ans<<endl;
}

Solution in Java-

import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();

Pair[] arr = new Pair[n];
for (int i = 0; i < n; i++) {
int first = scanner.nextInt();
int second = scanner.nextInt();
arr[i] = new Pair(first, second);
}

Arrays.sort(arr);

int x = Integer.MIN_VALUE;
int y = Integer.MIN_VALUE;

long ans = 0;
for (int i = 0; i < n; i++) {
int curX = arr[i].first;
int curY = arr[i].second;

if (y <= curX) {
ans += (curY - curX);
x = curX;
y = curY;
} else if (x <= curX && curX <= y && curY >= y) {
x = y;
y = curY;
ans += (y - x);
x = curX;
} else {
continue;
}
}

System.out.println(ans);
scanner.close();
}

static class Pair implements Comparable {
int first;
int second;

public Pair(int first, int second) {
this.first = first;
this.second = second;
}

@Override
public int compareTo(Pair other) {
return Integer.compare(this.first, other.first);
}
}
}

Solution in Python-

l=int(input())
ar=[]
for i in range(l):
a,b=map(int,input().split())
ar.append((a,b))
ar.sort(key=lambda x: x[0])

ans=ar[0][1]-ar[0][0]
y=ar[0][1]
for i in range(1,l):
if(y>=ar[i][0]):
ans=max(ans, ans+(ar[i][1]-ar[i][0]) - (y - ar[i][0]) )

else:
ans+=(ar[i][1]-ar[i][0])

y=max(ar[i][1],y)
print(ans)
###### Input Specification:
• Input1: integer input ‘n'(1 <= input1 <= 1000)
• Input2: integer array ‘A’ input, containing ‘n’ integers.
###### Output Specification:

Return the length of its LIS.

###### Example1:
• Input1: 3
• Input2: (1,3,2)
• Output: 2
• Explanation: (1.2) and (1.3) are the Longest Increasing Subsequences of (1,3,2). The length of both LIS is 2.
###### Example 2:
• Input1: 5
• Input2: (41, 18467,6334 26500, 19169)
• Output: 3
• Explanation: (41,6334,26500), (41,18467 26500), etc are the Longest Increasing Subsequences of (41, 18487,6334 ,26500,19169).
In all of the cases, the length of LIS is 3.

Solution in C –

#include <stdio.>

int max(int a, int b) {
return (a > b) ? a : b;
}

int main() {
int n;
scanf("%d", &n);

int arr[n];
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);

int dp[n];
int ans = 0;

for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = max(dp[j] + 1, dp[i]);
}
}
ans = max(ans, dp[i]);
}

printf("%d\n", ans);
return 0;
}

Solution in C++ –

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) cin >> arr[i];

int dp[n];
int ans = 0;

for (int i = 0; i < n; i++)
{
dp[i] = 1;
for (int j = 0; j < i; j++)
{
if (arr[j] < arr[i])
{
dp[i] = max(dp[j] + 1, dp[i]);
}
}
ans = max(ans, dp[i]);
}
cout << ans << endl;
return 0;
}

Solution in Java –

import java.util.*;
public class Main
{

public  static int longestIncreasingSubsequence(int arr[], int n)
{
int dp[]=new int[n];
int res=0;
for(int i=0;i<n;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(arr[j]<arr[i])
dp[i]=Math.max(dp[i],dp[j]+1);
}
res=Math.max(res,dp[i]);
}
return res;
}

public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
System.out.println(longestIncreasingSubsequence(arr,n));
}
}

Solution in Python-

def ceilindex(t,l,r,key):
while(r-l>1):
m=l+(r-l)//2
if(key<=t[m]):
r=m
else:
l=m
return r

def lcs(a,n):
seq=[0 for i in range(n)]
seq[0]=ar[0]
l=1
for i in range(1,n):
if(seq[0]>a[i]):
seq[0]=a[i]
elif(a[i]>seq[l-1]):
seq[l]=a[i]
l+=1
else:
seq[ceilindex(seq,-1,l-1,a[i])]=a[i]
return l
n=int(input())
ar=list(map(int,input().split()))
print(lcs(ar,n))
###### Input Specification:
• Input1: Second element of series (Integer).
• Input2: Third element of series (Integer).
• Input3: Total number of elements in the series (Integer).
###### Output Specification:
• Return the nth element of the series.
• Input1: 1
• Input2: 2
• Input3: 4
• Output: 3
###### Example 2:
• Input1: 5
• Input2: 8
• Input3: 4
• Output: 11

Solution in C-

#include<stdio.h>
int main() {
long long sec, third, n;
scanf("%lld %lld %lld", &sec, &third, &n);

long long d = third - sec;
long long first = sec - d;

long long nth = first + (n - 1) * d;

printf("%lld\n", nth);
return 0;
}

Solution in C++ –

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll sec,third,n;
cin>>sec>>third>>n;

ll d = third - sec;
ll first = sec-d;

ll nth = first + (n-1)*d;

cout<<nth<<endl;
return 0;
}

Solution in Java –

import java.util.*;
public class Main{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int second=sc.nextInt();
int third=sc.nextInt();
int n=sc.nextInt();
int d=third-second;
int first=second-d;
int nth=first+(n-1)*d;

System.out.println(nth);
}
}

Solution in Python-

#pyhton program
secondTer=int(input())
ThirdTer=int(input())
n=int(input())
d=ThirdTer-secondTer
firstTer=secondTer-d
print(firstTer + (n-1)*d)
###### Ques-The Fibonacci series is a series in which each number is the sum preceding two numbers. For example 0, 1, 1, 2, 3, 5, 8, 13, 21, e. The first two numbers of the series are 0 and 1. Write a code to return the nth Fibonacci number The sequence Fn of Fibonacci numbers is defined by the following relation Fn = Fn-1 + Fn-2 with initial values Of F0= 0 and F1 = 1

Input Specification:
Input1: A number n

Output Specification:
Return the nth Fibonacci number

Solution in C-

// Fibonacci Series using Space Optimized Method
#include <stdio.h>
int fib(int n)
{
int a = 0, b = 1, c, i;
if (n == 0)
return a;
for (i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}

int main()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}

Solution in C++ –

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll fib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;

ll prev = 0, cur = 1;

for (int i = 2; i <= n; i++)
{
ll x = prev + cur;
prev = cur;
cur = x;
}

return cur;
}
int main()
{
int n;
cin >> n;
cout << fib(n) << endl;

return 0;
}

Solution in Java –

import java.util.*;
public class Main
{
public static int fib(int n)
{
double phi=(1+Math.sqrt(5))/2;
return (int)Math.round(Math.pow(phi,n)/Math.sqrt(5));
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.println(fib(n));
}
}

Solution in Python –

#fibonacci
n=int(input())
if(n==0):
print(0)
elif(n==1):
print(1)
else:
prev=0
curr=1
ans=0
for i in range(2,n+1):
ans=prev+curr
prev=curr
curr=ans
print(ans)
###### Input Specification:
• Input1: K, denoting the number of subjects
• Input2: An array of K elements each denoting the credits to take a subject.
• Input3: N, denoting the number of students.
• Input4: An array of N elements each denoting the credit limit of a student.
###### Output Specification:

Your function should return the maximum number of possible required pairs.

Solution in C-

#include <stdio.h>
#include <stdlib.h>

int compareIntegers(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}

int findUpperBound(int arr[], int size, int target) {
int i;
for (i = 0; i < size; i++) {
if (arr[i] > target) {
break;
}
}
return i;
}

int main() {
int k;
scanf("%d", &k);

int* subject = (int*)malloc(k * sizeof(int));
for (int i = 0; i < k; i++) {
scanf("%d", &subject[i]);
}

qsort(subject, k, sizeof(int), compareIntegers);

int n;
scanf("%d", &n);

int credit, ans = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &credit);
int idx = findUpperBound(subject, k, credit);
ans += idx;
}

printf("%d\n", ans);

free(subject);

return 0;
}

Solution in C++

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int k;
cin >> k;

int subject[k];
for (int i = 0; i < k; i++) cin >> subject[i];

sort(subject,subject+k);
int n;
cin >> n;
int credit, ans = 0;
for (int i = 0; i < n; i++) { cin >> credit;
int idx = upper_bound(subject,subject+k,credit)-subject;
ans+=idx;
}

cout<<ans<<endl;

return 0;
}

Solution in Java-

import java.util.*;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int k = scanner.nextInt();

int[] subject = new int[k];
for (int i = 0; i < k; i++) {
subject[i] = scanner.nextInt();
}

Arrays.sort(subject);

int n = scanner.nextInt();

int credit, ans = 0;
for (int i = 0; i < n; i++) {
credit = scanner.nextInt();
int idx = findUpperBound(subject, credit);
ans += idx;
}

System.out.println(ans);

scanner.close();
}

private static int findUpperBound(int[] arr, int target) {
int left = 0;
int right = arr.length;

while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}

return left;
}
}

Solution in Python

#pyhton program
import bisect
k = int(input())
subject = list(map(int,input().split()))
n = int(input())
credit = list(map(int,input().split()))
subject.sort()
ans = 0
for i in range(n):
ans += bisect.bisect_right(subject,credit[i])

print(ans)
###### Input Specification:
• Input1: The value of M

#### Output Specification:

Return to the location where the boy should go first. If there are multiple answers, then return the largest one.

• Input1: 5
• Output: 3

#### Explanation:

If he selects 3, then he can go to: 3->10->5->16->8->4->2->1.

Solution in C –

#include <stdio.h>

int main()
{
int m;
scanf("%d", &m);

int ans = 1;
int mxSteps = 0;

for (int i = 1; i <= m; i++)
{
int num = i;
int steps = 0;

while (num != 1)
{
if (num % 2 == 0)
num /= 2;
else
num = 3 * num + 1;
steps++;
}

if (steps > mxSteps)
{
mxSteps = steps;
ans = i;
}
}

printf("%d\n", ans);

return 0;
}

Solution in C++ –

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000000;
const int mx = 1000;
int dp[N];
int solve(int m)
{
if (m == 1)
{
return 0;
}
if (dp[m] != -1)
return dp[m];

if (m % 2 == 0)
{
return dp[m] = 1 + solve(m / 2);
}
else
{
return dp[m] = 1 + solve(3 * m + 1);
}
}
int main()
{
memset(dp, -1, sizeof dp);
int m;
cin >> m;

int ans = 1;
int mxSteps = 0;

for (int i = 1; i < mx; i++)
{
int x = solve(i);
if (i <= m && x > mxSteps)
{
mxSteps = x;
ans = i;
}
}

cout << ans << endl;

return 0;
}

Solution in Java –

import java.util.*;
public class Main
{
static int solve(int n)
{
int count=1;
while (n != 1)
{
count++;

if (n % 2 == 1)
n = 3 * n + 1;

else
n = n / 2;
}

return count;
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int res=0,max=-1,j=0;
for(int i=1;i<=m;i++)
{
res=solve(i);
max=Math.max(res,max);
if(max==res)
j=i;
}
System.out.println(j);
}
}

Solution in Python –

#pyhton program
dp=[-1]*1000001
def noloc(po):
if(po==1):
return 0
if(dp[po]!=-1):
return dp[po]

elif(po %2 ==0):
po=po//2
dp[po]=1 + noloc(po)
return dp[po]

else:
dp[po]=1+ noloc(3*po + 1)
return dp[po]

m=int(input())
mmx=100
ans=1
mxstep=0
i=1
while(i<mmx): x="noloc(i)" if(i<="m" and="">mxstep):
mxstep=x
ans=i
i+=1
print(ans) </mmx):>