MulticoreWare Coding Assessment 2025

The MulticoreWare Coding Assessment section of the test has 3 coding questions and the test duration given is 70 mins.

Language: C / C++ / Java / Python

Difficulty: Medium

Time Limit: 70 Mins

The MulticoreWare Complex Coding Round section is only for the candidates who opted for the Research Engineer role.

If a candidate passes the initial coding round but does not succeed in the Complex Coding Round, they will still be considered for the Software Engineer role.

Language: C / C++ / Java / Python

Difficulty: Hard

Time Limit: 60 Mins

Problem: Given a linked list a->b->c->d->e->f, rearrange it to b->a->d->c->f->e without extra nodes.
Approach: Use iterative pointer manipulation with O(n) time complexity.

Approach: Iterative Pointer Manipulation

• We traverse the list in pairs.
• For each pair of nodes (first, second), we swap their links.
• We keep track of the previous node to correctly link the swapped pairs.
• The process continues until the entire list is traversed.

Algorithm

1. Initialize a dummy node (prev) before the head to simplify edge cases.
2. Use a pointer (current) to traverse the list in pairs.
3. For each pair:
   • Store references to first (current node) and second (next node).
   • Swap their links (second->first instead of first->second).
   • Link the previous node to the swapped pair.
   • Move prev and current to the next pair.
4. Return the new head.

Code Implementation (C++)

#include <iostream>
using namespace std;

// Definition for singly-linked list node
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to reverse pairs in a linked list
ListNode* reversePairs(ListNode* head) {
    if (!head || !head->next) return head; // Base case: Empty list or single node

    ListNode dummy(0); // Dummy node to simplify head handling
    dummy.next = head;
    ListNode* prev = &dummy;
    ListNode* current = head;

    while (current && current->next) {
        ListNode* first = current;
        ListNode* second = current->next;

        // Swapping nodes
        first->next = second->next;
        second->next = first;
        prev->next = second;

        // Move pointers forward
        prev = first;
        current = first->next;
    }

    return dummy.next;
}

// Helper function to print the list
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

// Driver code
int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(6);

    cout << "Original List: ";
    printList(head);

    head = reversePairs(head);

    cout << "Modified List: ";
    printList(head);

    return 0;
}

Java Code Implementation

// Definition for singly-linked list node
class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class ReversePairsLinkedList {

    // Function to reverse pairs in a linked list
    public static ListNode reversePairs(ListNode head) {
        if (head == null || head.next == null) return head; // Base case: empty or single-node list

        ListNode dummy = new ListNode(0); // Dummy node for easy head management
        dummy.next = head;
        ListNode prev = dummy;
        ListNode current = head;

        while (current != null && current.next != null) {
            ListNode first = current;
            ListNode second = current.next;

            // Swapping nodes
            first.next = second.next;
            second.next = first;
            prev.next = second;

            // Moving pointers forward
            prev = first;
            current = first.next;
        }

        return dummy.next;
    }

    // Helper function to print the list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    // Driver code
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);

        System.out.println("Original List: ");
        printList(head);

        head = reversePairs(head);

        System.out.println("Modified List: ");
        printList(head);
    }
}

Python Code Implementation

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_pairs(head):
    if not head or not head.next:
        return head  # Base case: empty list or single-node list

    dummy = ListNode(0)  # Dummy node for easier head handling
    dummy.next = head
    prev = dummy
    current = head

    while current and current.next:
        first = current
        second = current.next

        # Swapping nodes
        first.next = second.next
        second.next = first
        prev.next = second

        # Moving pointers forward
        prev = first
        current = first.next

    return dummy.next

# Helper function to print the list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Driver code
if __name__ == "__main__":
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)
    head.next.next.next.next.next = ListNode(6)

    print("Original List: ")
    print_list(head)

    head = reverse_pairs(head)

    print("Modified List: ")
    print_list(head)

Output

Original List:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Modified List:

2 -> 1 -> 4 -> 3 -> 6 -> 5 -> NULL

Problem: Find if a cycle exists and return the starting node.
Solution: Use Floyd’s Cycle Detection Algorithm (Tortoise & Hare Method).

Approach: Floyd’s Cycle Detection Algorithm (Tortoise & Hare Method)

1. Use two pointers (slow and fast):
   • slow moves one step at a time.
   • fast moves two steps at a time.
2. If there is a cycle, slow and fast will eventually meet.
3. Once a cycle is detected, reset slow to the head and move both pointers one step at a time.
4. The node where they meet again is the starting node of the cycle.

C++ Implementation

#include <iostream>
using namespace std;

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;

    // Step 1: Detect if a cycle exists
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            // Step 2: Find the starting node of the cycle
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow; // Cycle start node
        }
    }
    return nullptr; // No cycle
}

// Helper function to create a cycle in the linked list
ListNode* createCycleList(int arr[], int size, int pos) {
    if (size == 0) return nullptr;

    ListNode* head = new ListNode(arr[0]);
    ListNode* curr = head;
    ListNode* cycleNode = (pos == -1) ? nullptr : head;

    for (int i = 1; i < size; i++) {
        curr->next = new ListNode(arr[i]);
        curr = curr->next;
        if (i == pos) cycleNode = curr;
    }

    if (cycleNode) curr->next = cycleNode; // Creating the cycle
    return head;
}

int main() {
    int arr[] = {3, 2, 0, -4};
    int cycle_start_index = 1; // Cycle starts at node with value 2

    ListNode* head = createCycleList(arr, 4, cycle_start_index);
    ListNode* cycleNode = detectCycle(head);

    if (cycleNode)
        cout << "Cycle detected at node with value: " << cycleNode->val << endl;
    else
        cout << "No cycle detected." << endl;

    return 0;
}

Java Implementation

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class DetectCycle {
    public static ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;

        // Step 1: Detect if a cycle exists
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                // Step 2: Find the starting node of the cycle
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow; // Cycle start node
            }
        }
        return null; // No cycle
    }

    // Helper function to create a cycle in the linked list
    public static ListNode createCycleList(int[] arr, int pos) {
        if (arr.length == 0) return null;

        ListNode head = new ListNode(arr[0]);
        ListNode curr = head;
        ListNode cycleNode = (pos == -1) ? null : head;

        for (int i = 1; i < arr.length; i++) {
            curr.next = new ListNode(arr[i]);
            curr = curr.next;
            if (i == pos) cycleNode = curr;
        }

        if (cycleNode != null) curr.next = cycleNode; // Creating the cycle
        return head;
    }

    public static void main(String[] args) {
        int[] nodes = {3, 2, 0, -4};
        int cycleStartIndex = 1; // Cycle starts at node with value 2

        ListNode head = createCycleList(nodes, cycleStartIndex);
        ListNode cycleNode = detectCycle(head);

        if (cycleNode != null)
            System.out.println("Cycle detected at node with value: " + cycleNode.val);
        else
            System.out.println("No cycle detected.");
    }
}

Python Implementation

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detect_cycle(head):
    slow, fast = head, head

    # Step 1: Detect if a cycle exists
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:  # Cycle detected
            break
    else:
        return None  # No cycle found

    # Step 2: Find the starting node of the cycle
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # Cycle starting node

# Helper function to create a linked list with a cycle
def create_cycle_list(arr, pos):
    if not arr:
        return None

    head = ListNode(arr[0])
    curr = head
    cycle_node = None if pos == -1 else head

    for i in range(1, len(arr)):
        curr.next = ListNode(arr[i])
        curr = curr.next
        if i == pos:
            cycle_node = curr

    if cycle_node:
        curr.next = cycle_node  # Creating the cycle

    return head

# Driver Code
if __name__ == "__main__":
    nodes = [3, 2, 0, -4]
    cycle_start_index = 1  # Cycle starts at node with value 2
    head = create_cycle_list(nodes, cycle_start_index)
    cycle_node = detect_cycle(head)

    if cycle_node:
        print(f"Cycle detected at node with value: {cycle_node.val}")
    else:
        print("No cycle detected.")

Explanation

1. Cycle Detection:
   • Uses the Tortoise & Hare method with two pointers.
   • If slow and fast meet, a cycle exists.
2. Finding the Start of the Cycle:
   • Reset slow to head.
   • Move both pointers one step at a time until they meet again.
   • The meeting point is the start of the cycle.

Time & Space Complexity

• Time Complexity: O(n) (Each node is visited at most twice)
• Space Complexity: O(1) (Only two pointers are used)

Example Run

Cycle detected at node with value: 2

This solution is efficient and works optimally for detecting cycles in a linked list.

Problem: Given an N x N matrix, rotate it in-place by 90 degrees clockwise.
Example:

Input: [[1,2,3], [4,5,6], [7,8,9]]

Output: [[7,4,1], [8,5,2], [9,6,3]]

Solution: First, transpose the matrix, then reverse each row.

Rotate a Matrix by 90 Degrees Clockwise

Approach:

1. Transpose the matrix (swap matrix[i][j] with matrix[j][i]).
2. Reverse each row to get the final rotated matrix.

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm> // Required for std::reverse

using namespace std;

void rotateMatrix(vector<vector<int>>& matrix) {
    int n = matrix.size();

    // Step 1: Transpose the matrix
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }

    // Step 2: Reverse each row
    for (int i = 0; i < n; i++) {
        reverse(matrix[i].begin(), matrix[i].end());
    }
}

// Function to print the matrix
void printMatrix(const vector<vector<int>>& matrix) {
    for (const auto& row : matrix) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3}, 
        {4, 5, 6}, 
        {7, 8, 9}
    };

    cout << "Original Matrix:\n";
    printMatrix(matrix);

    rotateMatrix(matrix);

    cout << "\nRotated Matrix:\n";
    printMatrix(matrix);

    return 0;
}

Java Implementation

import java.util.Arrays;

public class RotateMatrix {

    public static void rotate(int[][] matrix) {
        int n = matrix.length;

        // Step 1: Transpose the matrix
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // Step 2: Reverse each row
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }

    // Function to print the matrix
    public static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        System.out.println("Original Matrix: ");
        printMatrix(matrix);

        rotate(matrix);

        System.out.println("\nRotated Matrix: ");
        printMatrix(matrix);
    }
}

Python Implementation

def rotate_matrix(matrix):
    n = len(matrix)

    # Step 1: Transpose the matrix
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Step 2: Reverse each row
    for row in matrix:
        row.reverse()


# Function to print the matrix
def print_matrix(matrix):
    for row in matrix:
        print(row)


# Test Case
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

print("Original Matrix: ")
print_matrix(matrix)

rotate_matrix(matrix)

print("\nRotated Matrix:")
print_matrix(matrix)

Time & Space Complexity

• Time Complexity: O(N²) (Both transpose and row reversal take O(N²))
• Space Complexity: O(1) (In-place rotation)

This approach ensures efficient in-place rotation of the matrix without using extra space.

Complex Coding Round (Research Engineer Role)

1. Matrix Chain Multiplication Optimization

Problem: Find the minimum scalar multiplications for [10][20][30][40].
Dynamic Programming Formula:
dp[i][j]=min⁡i≤k<j(dp[i][k]+dp[k+1][j]+p_{i-1}×p_k×p_j)
Expected Output: 60000 operations for dimensions [20][30][40][50].

Matrix Chain Multiplication Optimization

Problem: Given a sequence of matrices, find the most efficient way to multiply them by minimizing the number of scalar multiplications.

Dynamic Programming Approach:

• Define dp[i][j] as the minimum number of multiplications needed to multiply matrices from i to j.
• Use the recurrence relation: dp[i][j]=min⁡i≤k<j(dp[i][k]+dp[k+1][j]+p_{i-1}×p_k×p_j) where p[i-1] and p[j] represent matrix dimensions.
• Fill the DP table in a bottom-up manner.

C++ Implementation

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

int matrixChainMultiplication(vector<int>& p) {
    int n = p.size() - 1;
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // Compute minimum multiplication costs
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;

            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}

int main() {
    vector<int> dimensions = {10, 20, 30, 40};
    
    cout << "Minimum multiplications: " << matrixChainMultiplication(dimensions) << endl;

    return 0;
}

Java Implementation

public class MatrixChainMultiplication {

    public static int matrixChainMultiplication(int[] p) {
        int n = p.length - 1;
        int[][] dp = new int[n][n];

        // Compute minimum multiplication costs
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;

                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }

        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        int[] dimensions = {10, 20, 30, 40};
        System.out.println("Minimum multiplications: " + matrixChainMultiplication(dimensions));
    }
}

Python Implementation

import sys

def matrix_chain_multiplication(p):
    n = len(p) - 1
    dp = [[0] * n for _ in range(n)]

    # Compute minimum multiplication costs
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = sys.maxsize

            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]

# Test case
dimensions = [10, 20, 30, 40]
print("Minimum multiplications: ", matrix_chain_multiplication(dimensions))

Expected Output:

Minimum multiplications: 18000

Time & Space Complexity

• Time Complexity: O(N³) (Iterating through all subproblems and partitions)
• Space Complexity: O(N²) (DP table storage)

This approach ensures efficient matrix multiplication with dynamic programming, reducing redundant calculations.