Amazon Coding Questions

Amazon Practice Coding Questions

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

Ques- One of the streets in your city has a total of L street lots. Each light covers the street from Xi to Y

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)

Ques-Given an integer array ‘A’, find the length of its Longest Increasing Subsequence(LIS). LIS is a sub-array of the given integer array where the elements are sorted in a monotonic/ strict increasing order.
You need to fill in a function that takes two inputs – integer ‘n’ and an integer array ‘A’ containing ‘n integers and returns the length of its LIS.

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))

Ques-Given the second and the third terms of an AP (-106 <= a2, a3 <= 106), find the n’th (1 <= n<= 1000) term of the sequence.

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.

Example 1:

• 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)

Ques-In a university, there is a certain system of credits. Each student is given a ‘credit limit which specifies the maximum credits of a subject they can take. A student can take any number of subjects that are under his/her credit limit. There are N students and K subjects. Each subject has a specified number of credits. When a student chooses a subject, it becomes a (student, subject) pair.
Find the maximum number of possible (subject, student) pairs for the given credit limits and subject credit requirements.

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)

#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;
}

#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;
}

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);
} 
}

#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):>