Scribd
Upload
5 views5 pages

Array Test

The document outlines a 2-hour array test covering topics such as Two Pointers, Precomputational Techniques, Sorting, ArrayList, and Hashing. It includes five problems with specific inputs and outputs, focusing on tasks like finding pairs that sum to a target, calculating prefix sums, implementing insertion sort, performing dynamic array operations, and counting element frequencies using hashing. The difficulty level ranges from easy to medium, with constraints provided for each problem.

Uploaded by

tyash3397
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views5 pages

Array Test

The document outlines a 2-hour array test covering topics such as Two Pointers, Precomputational Techniques, Sorting, ArrayList, and Hashing. It includes five problems with specific inputs and outputs, focusing on tasks like finding pairs that sum to a target, calculating prefix sums, implementing insertion sort, performing dynamic array operations, and counting element frequencies using hashing. The difficulty level ranges from easy to medium, with constraints provided for each problem.

Uploaded by

tyash3397
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Array Test (2 Hours)

This test covers the following topics:


- Two Pointers
- Precomputational Techniques
- Sorting (Bubble Sort, Selection Sort, Insertion Sort)
- ArrayList
- Hashing

Each question has sample inputs and outputs for better understanding.
Difficulty level: Easy to Medium

1. Pair Sum Problem (Two Pointers)

Given a sorted array of integers and a target value, find if there exists a pair of elements that
sum up to the target value.

Input:
- n (1 ≤ n ≤ 10^5) — number of elements
- array[] (sorted array with |array[i]| ≤ 10^9)
- target (|target| ≤ 10^9)

Output:
- "YES" if such a pair exists, otherwise "NO"

Examples:
Input:
5
12345
7
Output: YES

Input:
4
1239
8
Output: NO

Input:
6
-5 -2 0 3 6 10
1
Output: YES

2. Prefix Sum Problem

Given an array of integers and multiple queries, each query asks for the sum of elements
between two given indices.

Input:
- n (1 ≤ n ≤ 10^5) — number of elements
- array[] (|array[i]| ≤ 10^9)
- q (1 ≤ q ≤ 10^5) — number of queries
- Each query contains two integers l and r (1 ≤ l ≤ r ≤ n)

Output:
- For each query, print the sum of elements from index l to r.

Examples:
Input:
5
12345
3
13
24
15
Output:
6
9
15

Input:
4
-1 0 2 3
2
12
24
Output:
-1
5
Input:
3
10 20 30
2
11
13
Output:
10
60

3. Insertion Sort Implementation

Implement the Insertion Sort algorithm to sort an array in ascending order.

Input:
- n (1 ≤ n ≤ 10^4) — number of elements
- array[] (|array[i]| ≤ 10^9)

Output:
- Sorted array

Examples:
Input:
5
53412
Output:
12345

Input:
4
10 5 8 2
Output:
2 5 8 10

Input:
6
-3 -1 0 7 4 2
Output:
-3 -1 0 2 4 7
4. Dynamic Array Operations (ArrayList)

You are given a dynamic array supporting the following operations:


1. Insert x — Add element x to the array.
2. Delete x — Remove the first occurrence of x from the array if present.
3. Print — Print the current array.

Input:
- q (1 ≤ q ≤ 10^5) — Number of operations
- Followed by q lines containing the operations

Output:
- Array state after all operations

Examples:
Input:
5
Insert 3
Insert 5
Insert 2
Delete 3
Print
Output:
52

Input:
4
Insert 1
Insert 2
Delete 1
Print
Output:
2

Input:
6
Insert 10
Insert 20
Insert 30
Delete 40
Insert 50
Print
Output:
10 20 30 50

5. Frequency Counter using Hashing

Given an array of integers, count the frequency of each distinct element.

Input:
- n (1 ≤ n ≤ 10^5) — number of elements
- array[] (|array[i]| ≤ 10^9)

Output:
- Each unique element followed by its frequency

Examples:
Input:
6
122333
Output:
11
22
33

Input:
5
10 10 20 30 30
Output:
10 2
20 1
30 2

Input:
4
5555
Output:
54

You might also like