HCL Coding Questions: Coding Pattern with Questions & Solutions

class Node:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

# Function to construct a balanced BST from the sorted array

def construct(arr, lo, hi):

    if lo > hi:

        return None

    # Pick the middle element to make the current node

    mid = hi - ((hi - lo) // 2)

    node = Node(arr[mid])

    # Recursively construct the left and right subtrees

    node.left = construct(arr, lo, mid - 1)

    node.right = construct(arr, mid + 1, hi)

    return node

# Function to display the tree in the required format (pre-order traversal)

def display(node):

    if node is None:

        return

    # Format the current node and its left and right children

    str_val = ""

    str_val += "." if node.left is None else str(node.left.data)

    str_val += " <- " + str(node.data) + " -> "

    str_val += "." if node.right is None else str(node.right.data)

    print(str_val)

    # Recursively display the left and right subtrees

    display(node.left)

    display(node.right)

if __name__ == "__main__":

    # Input size of the array

    n = int(input())

    # Input the array

    arr = list(map(int, input().split()))

    # Sort the array to ensure it's in ascending order

    arr.sort()

    # Construct the balanced BST

    root = construct(arr, 0, len(arr) - 1)

    # Display the tree in the required format

    display(root)

import java.io.*;

import java.util.*;

public class Main {

    public static class Node {

        int data;

        Node left;

        Node right;

        Node(int data, Node left, Node right) {

            this.data = data;

            this.left = left;

            this.right = right;

        }

    }

    public static Node construct(int[] arr,int lo, int hi) {

        if(lo>hi)return null;

        int mid = hi-((hi-lo)/2);

        int data = arr[mid];

        Node left = construct(arr,lo,mid-1);

        Node right = construct(arr,mid+1,hi);

        Node node = new Node(data, left, right);

        return node;

    }

    public static void display(Node node) {

        if (node == null) {

            return;

        }

String str = "";

         str += node.left == null ? "." : node.left.data + "";

        str += " <- " + node.data + " -> ";

        str += node.right == null ? "." : node.right.data + "";

        System.out.println(str);

        display(node.left);

        display(node.right);

    }


    public static void main(String[] args) throws Exception {

        Scanner scn = new Scanner(System.in);

        int n = scn.nextInt();

        int arr[] = new int[n];

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

            arr[i]=scn.nextInt();

        }

        Arrays.sort(arr);

        Node root = construct(arr,0,arr.length-1);

        display(root);

    }

}

# Enter your code here. Read input from STDIN. Print output to STDOUT

def count_balls_brute_force(arr):

   def countBalls1(lowLimit, highLimit):

       # Array to count the number of coins in each box

       cnt = [0] * 46

       for i in range(lowLimit, highLimit + 1):

           # Calculate the sum of digits using string conversion

           sum_of_digits = sum(int(digit) for digit in str(i))

           cnt[sum_of_digits] += 1

       return max(cnt)

   # Finding low and high limits

   low = min(arr)

   high = max(arr)

   return countBalls1(low, high)

# Read input

n = int(input())  # Number of coins

arr = list(map(int, input().split()))  # Array of coin numbers

# Output the result of the brute-force function

print(count_balls_brute_force(arr))

import java.util.*;

public class Main {

   static int countBalls1(int lowLimit, int highLimit) {

       int[] cnt = new int[46];

       for (int i = lowLimit; i <= highLimit; ++i) {

           int sum = 0, n = i;

           while (n > 0) {

               sum += n % 10;

               n /= 10;

           }

           ++cnt[sum];

       }

       return Arrays.stream(cnt).max().getAsInt();

   }

   static int countBalls(List<Integer> arr) {

       Collections.sort(arr);

       int low = arr.get(0);

       int high = arr.get(arr.size() - 1);

       return countBalls1(low, high);

   }

   public static void main(String[] args) {

       Scanner sc = new Scanner(System.in);

       int n = sc.nextInt();

       List<Integer> arr = new ArrayList<>();

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

           arr.add(sc.nextInt());

       }

       System.out.println(countBalls(arr));

   }

}

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int k = scanner.nextInt();

        int[] arr = new int[n];

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

            arr[i] = scanner.nextInt();

        }

        System.out.println(findKthLargest(arr, k));

    }

    public static int findKthLargest(int[] nums, int k) {

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {

            minHeap.offer(num);

            if (minHeap.size() > k) {

                minHeap.poll();

            }

        }

        return minHeap.peek();

    }

}

import heapq

def num_largest(stream, K):

    min_heap = []

    for num in stream:

        if len(min_heap) < K:

            heapq.heappush(min_heap, num)

        else:

            if num > min_heap[0]:

                heapq.heapreplace(min_heap, num)

    if len(min_heap) == K:

        return min_heap[0]

    else:

        return None  

def get_stream_from_user():

    while True:

        try:

            num_elements = int(input())

            break

        except ValueError:

            print("Please enter a valid number.")

    while True:

        try:

            K = int(input().strip())  # Read K

            break

        except ValueError:

            print("Please enter a valid number for K.")

    while True:

        try:

            user_input = input().strip()

            stream = list(map(int, user_input.split()))

            if len(stream) != num_elements:

                raise ValueError("Number of elements entered does not match the specified count.")

            break

        except ValueError as e:

            print(e)

    return stream, K

# Example usage:

 # Ask user for the value of K

stream, K = get_stream_from_user()

fifth_largest = num_largest(stream, K)

if fifth_largest is None:

    print("There are not enough unique numbers in the stream to find the K-th largest.")

else:

    print(fifth_largest)

#include <cmath>

#include <cstdio>

#include <vector>

#include <bits/stdc++.h>

#include <algorithm>

using namespace std;


int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 

     int n,k;

     cin>>n>>k;

     vector<int>a(n);

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

       cin>>a[i];

     }

     priority_queue<int>pq;

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

       pq.push(a[i]);

     }

     k--;

     while(k--){

       pq.pop();

     }

     cout<<pq.top()<<endl;

    return 0;

}

def findMiddleEarth(a1, a2):

    n1, n2 = len(a1), len(a2)

    # We want to perform binary search on the smaller array

    if n2 < n1:

        return findMiddleEarth(a2, a1)

    low, high = 0, n1

    while low <= high:

        cut1 = (low + high) // 2

        # +1 because, if it's even suppose n1 = 4, n2 = 6, then cut2 will be 5

        # If it's odd suppose n1 = 3, n2 = 4, then cut2 will be 4 because we need +1 of mid

        cut2 = ((n1 + n2 + 1) // 2) - cut1

        left1 = float('-inf') if cut1 == 0 else a1[cut1 - 1]

        left2 = float('-inf') if cut2 == 0 else a2[cut2 - 1]

        right1 = float('inf') if cut1 == n1 else a1[cut1]

        right2 = float('inf') if cut2 == n2 else a2[cut2]

        if left1 <= right2 and left2 <= right1:

            if (n1 + n2) % 2 == 0:

                return (max(left1, left2) + min(right1, right2)) / 2.0

            else:

                return max(left1, left2)

        elif left1 > right2:

            high = cut1 - 1

        else:

            low = cut1 + 1

    return 0.0

def solution():

    m, n = map(int, input().split())

    a1 = list(map(int, input().split()))

    a2 = list(map(int, input().split()))

    print(findMiddleEarth(a1, a2))

if __name__ == "__main__":

    solution()

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

class Main {

    public static void main(String[] args) {

        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();

        int n = sc.nextInt();

        int[] a1 = new int[m];

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

            a1[i] = sc.nextInt();

        }

        int[] a2 = new int[n];

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

            a2[i] = sc.nextInt();

        }

        // Call the optimized function to find the median

        double result = findMedianSortedArrays(a1, a2);

        if(result==(int)result){

            System.out.println((int)result);

        }else{

        System.out.println(result);

        }

    }

    public static double findMedianSortedArrays(int[] a1, int[] a2) {

        // Ensure that a1 is the smaller array

        if (a1.length > a2.length) {

            return findMedianSortedArrays(a2, a1);

        }

        int m = a1.length;

        int n = a2.length;

        int low = 0, high = m;

        while (low <= high) {

            int partitionA1 = (low + high) / 2;

            int partitionA2 = (m + n + 1) / 2 - partitionA1;

            int maxLeftA1 = (partitionA1 == 0) ? Integer.MIN_VALUE : a1[partitionA1 - 1];

            int minRightA1 = (partitionA1 == m) ? Integer.MAX_VALUE : a1[partitionA1];

            int maxLeftA2 = (partitionA2 == 0) ? Integer.MIN_VALUE : a2[partitionA2 - 1];

            int minRightA2 = (partitionA2 == n) ? Integer.MAX_VALUE : a2[partitionA2];

            if (maxLeftA1 <= minRightA2 && maxLeftA2 <= minRightA1) {

                // Found the correct partition

                if ((m + n) % 2 == 0) {

                    return (Math.max(maxLeftA1, maxLeftA2) + Math.min(minRightA1, minRightA2)) / 2.0;

                } else {

                    return Math.max(maxLeftA1, maxLeftA2);

                }

            } else if (maxLeftA1 > minRightA2) {

                // Move towards the left in a1

                high = partitionA1 - 1;

            } else {

                // Move towards the right in a1

                low = partitionA1 + 1;

            }

        }

        throw new IllegalArgumentException("Input arrays are not sorted.");

    }

}

#include <bits/stdc++.h>

using namespace std;


int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   

    deque<int> dq;

    int n,k;

    cin>>n>>k;

    int a[n];

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

        cin>>a[i];

        if(dq.empty() || a[dq.front()]<=a[i]){

            dq.push_front(i);

        }else{

            while(!dq.empty() && (a[i]>=a[dq.back()] || dq.back()<=i-k)){

                dq.pop_back();

            }

            dq.push_back(i);

        }

                while(!dq.empty() && dq.front()<=i-k)dq.pop_front();


        if(i>=k-1){

            cout<<a[dq.front()]<<" ";

        }               

    }

    return 0;

}

from collections import deque

def sliding_window_maximum(N, K, heights):

    if K > N:

        return

    max_in_windows = []

    deq = deque()

    for i in range(N):

        if deq and deq[0] < i - K + 1:

            deq.popleft()

        while deq and heights[deq[-1]] <= heights[i]:

            deq.pop()

        deq.append(i)

        if i >= K - 1:

            max_in_windows.append(heights[deq[0]])

    return max_in_windows

if __name__ == "__main__":

    import sys

    input = sys.stdin.read

    data = input().split()

    N = int(data[0])

    K = int(data[1])

    heights = list(map(int, data[2:]))

    result = sliding_window_maximum(N, K, heights)

    print(" ".join(map(str, result)))