COGNIZANT CODING QUESTIONS
1. You are given one number as input. Find all the possible pairs that would sum up to give
the given number.
Example: input: 10
output: (1,9), (2,8), (3,7), (4,6), (9,1), (8,2), (7,3), (6,4), (5,5)
2. You are given one String S consisting of lowercase English letters. You have to generate a
new string where each character in S repeats as per their first index occurrence. The
characters should be separated by hyphens.
Example: input: abcaba
output: a-bb-ccc-a-bb-a
3. Find all the prime numbers within the range of the given number.
4. Check if the given number prime or not.
5. BUBBLE SORT (Bubble = Swap neighbors again & again)
Bubble Sort repeatedly swaps adjacent elements if they are in the wrong order.
Largest element "bubbles" to the end in each pass.
After n-1 passes, the array is sorted.
It's simple but very slow for large datasets.
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
✅ Time Complexity:
Worst: O(n²)
Best (already sorted): O(n)
Average: O(n²)
✅ Space Complexity: O(1) (In-place)
6. INSERTION SORT (Insert each element in its place)
Insertion Sort builds the final sorted array one element at a time.
It takes each element and inserts it into its correct position in the left part of the array.
Efficient for small datasets and nearly sorted data.
Used in hybrid sorting algorithms like Timsort for small partitions.
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}
✅ Time Complexity:
Worst: O(n²)
Best (already sorted): O(n)
Average: O(n²)
✅ Space Complexity: O(1) (In-place)
7. SELECTION SORT (Select the smallest & swap)
Selection Sort finds the smallest element in the unsorted part and swaps it with the first
unsorted element.
This process repeats until the array is sorted.
It performs minimum number of swaps compared to bubble/insertion.
Still inefficient for large datasets.
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
✅ Time Complexity:
Worst: O(n²)
Best: O(n²)
Average: O(n²)
✅ Space Complexity: O(1) (In-place)
8. MERGE SORT (Merge halves)
Merge Sort is a divide and conquer algorithm.
It splits the array into halves, sorts each half recursively, then merges them.
It guarantees O(n log n) time complexity.
Uses extra space for merging, but is very efficient for large datasets.
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
}
✅ Time Complexity:
Worst: O(n log n)
Best: O(n log n)
Average: O(n log n)
✅ Space Complexity: O(n) (extra space for merging)
9. HEAP SORT (Heapify + Extract Max)
Heap Sort uses a binary heap data structure.
It builds a max heap and repeatedly extracts the maximum element, placing it at the end.
Runs in O(n log n) and does not need extra space.
Widely used in priority queues.
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
}
✅ Time Complexity:
Worst: O(n log n)
Best: O(n log n)
Average: O(n log n)
✅ Space Complexity: O(1) (In-place)
11. You are out shopping in a grocery mall, and you have listed all the items you want to buy
in an integer array A of length N in one operation, you can swap any two items on the list.
Your task is to find and return an integer value representing the minimum possible sum of
any two consecutive items on the list after performing the operation any number of times.
Input Specification:
input1: An integer value N representing the number of items on the list. input2: An integer
array A containing the items.
Output Specification:
Return an integer value representing the minimum possible sum of any two consecutive
items on the list after performing the operation any number of times.
Example 1:
input1:3 input2: (3.5.1)
Output: 4
[CLUE : FIND LOWEST AND SECOND LOWEST AND RETURN THEIR SUM]
import java.util.*;
class Solution {
private static int secondHighest(int[] arr) {
int min = Integer.MAX_VALUE;
int sMin = Integer.MAX_VALUE;
for(int num: arr) {
if(num < min) {
sMin = min;
min = num;
}
else if(num < sMin && num > min) {
sMin = num;
}
}
return sMin+min;
}
12. Question
You are given control of a retro game controller which has 6 buttons, each represented by a
6-bit integer value. Each bit indicates whether a button is pressed or unpressed represented
by 1 and 0 respectively.
When Party Mode is activated, the 1st, 3rd, and 5th bits (from the right, 1-based indexing)
toggle their state from 0 to 1 and 1 to 0.
Your task is to find and return an integer value representing the new button state after
applying the Party Mode.
Input Specification:
input1 : An integer value representing the current button state.
Output Specification:
Return an integer representing the new button state after applying the Party Mode.
Example 2
Input:
input1 = 15
(Binary representation = 001111)
Output:
26
(Binary after toggling = 011010)
APPROACH - 1
import java.util.*;
class Solution {
private static int binaryToDecimal(String s) {
int d = 0;
int rem = 0;
for(int i = 0; i < s.length(); i++) {
rem = s.charAt(s.length() - 1 - i) - '0';
if(i == 0 || i == 2 || i == 4) {
rem = 1 - rem;
}
d += rem * (int)Math.pow(2, i);
}
return d;
}
private static String decimalToBinary(int n) {
if (n == 0) return "000000"; // handle zero case explicitly
String s = "";
while(n > 0) {
int rem = n % 2;
n = n / 2;
s = rem + s;
}
return s;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int t = n;
String s = decimalToBinary(n);
while(s.length() < 6) {
s = "0" + s;
}
int d = binaryToDecimal(s);
System.out.println("Party Mode: " + t + " --> " + d);
}
}
APPROACH – 2
import java.util.Scanner;
public class Main {
public static int applyPartyMode(int input1) {
int mask = 0b010101; // Binary mask where bits 1, 3, 5 are set: 010101 = 21
return input1 ^ mask; // Toggle the bits using XOR
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int input1 = sc.nextInt(); // Read input
int result = applyPartyMode(input1); // Apply Party Mode
System.out.println(result); // Output the result
sc.close();
}
}
13. *Minimum Index
You are given an integer array A. Your need to find a special number in the array such that
the XOR of all the elements from the start till the special number is greater than the XOR of
all elements after that special number. Your task is to find and return an integer value
representing the position of that special number in the array.
Note:
The special number will also be included for the XOR operation with the elements that are
before that special number.
The XOR of the first and last element will be performed with [].
Input Specification:
input1: An integer value, representing the size of the array.
input2: An integer array A.
Output Specification:
Return an integer value representing the position of that special number in the array.
import java.util.Scanner;
class Main {
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();
}
int xorAll = 0;
for(int num: arr) {
xorAll ^= num;
}
int xorSome = 0;
int i = 0;
for(i = 0; i < n; i++) {
xorSome ^= arr[i];
xorAll ^= arr[i];
if(xorSome > xorAll)
break;
}
System.out.println(i);
sc.close();
}
}
