Python: Solved Interview Ques on Algorithms, Data Structures

Below are the programs for each of the tasks listed. Please note that due to the extensive list, I will provide examples for some of the tasks. For all tasks, you can adapt the logic to handle specific cases or additional requirements.

Single Link List Programs

1. Delete Node at Beginning

struct Node {
    int data;
    struct Node* next;
};

void deleteNode(struct Node** head) {
    struct Node* temp = (*head);
    if (temp != NULL) {
        *head = temp->next; // Change head to next node
        free(temp);           // Free memory
    }
}

2. Delete Node at End

void deleteNodeAtEnd(struct Node** head, int data) {
    struct Node* temp = *head;
    struct Node *prev = NULL;
    while (temp != NULL && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return; // Element not found
    if (prev == NULL) { // Deleting the last node
        *head = temp->next;
    } else {
        prev->next = temp->next; // Unlink the node
    }
    free(temp);
}

3. Insert Node at Beginning of Double Link List

struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

void insertAtBeginning(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->prev = NULL;
    newNode->next = (*head);
    if ((*head) != NULL) {
        (*head)->prev = newNode; // Link the old head to point to the new node
    }
    *head = newNode; // Update the head
}

Array and Other Programs

1. Find Missing Number in a Rotated Array

int findMissingNumber(int arr[], int n) {
    int x = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] >= x) {
            return x; // If next number is greater than current missing no., it's the missing one.
        }
        x = arr[i];
    }
    return n; // If missing, it's the next number after the last element.
}

2. Find Element with a Given Value in a Rotated Array

int searchInRotatedArray(int arr[], int n, int target) {
    if (n == 0) return -1; // Empty array case
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid; // Target found
        if (arr[left] <= arr[mid]) { // Left half is sorted
            if (arr[left] <= target && target < arr[mid]) {
                left = mid + 1; // Target must be in right half
            } else {
                right = mid - 1; // Target must be in left half
            }
        } else { // Right half is sorted
            if (arr[mid] < target && target <= arr[right]) {
                right = mid - 1; // Target must be in left half
            } else {
                left = mid + 1; // Target must be in right half
            }
        }
    }
    return -1; // Target not found
}

3. Binary Search Using Iteration

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) return mid; // Element found
        if (arr[mid] < x) l = mid + 1; // Search in the right half
        else r = mid - 1; // Search in the left half
    }
    return -1; // Element not found
}

4. Get Frequency of Every Number in a Array

void getFrequencies(int arr[], int n, int output[][2]) {
    for (int i = 0; i < n; i++) {
        int count = 1;
        for (int j = i + 1; j < n; j++) {
            if (arr[i] == arr[j]) count++;
        }
        output[arr[i]][0] = arr[i];
        output[arr[i]][1] = count;
    }
}

5. Two Elements from Two Sorted Arrays that Form a Sum

int findPairWithGivenSum(int arr1[], int arr2[], int n, int m, int sum) {
    int i = 0, j = m - 1;
    while (i < n && j >= 0) {
        if (arr1[i] + arr2[j] == sum) {
            return 1; // Pair found
        } else if (arr1[i] + arr2[j] < sum) {
            i++; // Look for larger elements in arr1
        } else {
            j--; // Look for smaller elements in arr2
        }
    }
    return 0; // No such pair exists
}

6. Element Forming Sum from Two Sorted Arrays

int findSingleElementWithTargetSum(int arr1[], int arr2[], int n, int m, int targetSum) {
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (arr1[i] + arr2[j] == targetSum) {
            return 1; // Element found
        } else if (arr1[i] + arr2[j] < targetSum) {
            i++; // Move to the next element in arr1
        } else {
            j++; // Move to the next element in arr2
        }
    }
    return 0; // No such element exists
}

7. Find Non-Repeating Character in a String

char findNonRepeatingChar(char str[]) {
    int counts[256] = {0};
    for (int i = 0; str[i]; i++) {
        counts[str[i]]++;
        if (counts[str[i]] == 1) return str[i]; // First non-repeating char found
    }
    return '\0'; // No non-repeating char found
}

8. Sort an Array Using Bubble Sort

void bubbleSort(int arr[], int n) {
    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;
            }
        }
    }
}

9. Check if a String is a Valid Parentheses

bool isValidParentheses(char str[]) {
    int bal = 0;
    for (int i = 0; str[i]; i++) {
        if (str[i] == '(') bal++;
        else if (str[i] == ')') bal--;
        if (bal < 0) return false; // Parentheses are not balanced
    }
    return bal == 0; // Parentheses are balanced
}

10. Implement Binary Search on a String

int binarySearchString(const char *str, char target[], int n) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (str[mid] == target[0]) {
            for (int i = 0; str[i] && target[i] != '\0' && str[i] == target[i]; i++) {
                if (i == strlen(target) - 1) return mid; // String found
            }
            low = mid + 1; // Continue searching in the right half
        } else if (str[mid] < target[0]) {
            low = mid + 1; // Continue searching in the right half
        } else {
            high = mid - 1; // Continue searching in the left half
        }
    }
    return -1; // String not found
}

Please note that these are just a few examples among many possible tasks. The complexity of the problem, programming language, and approach can vary greatly depending on the requirements and constraints provided in each case.