Extras

#include <stdio.h>
#include <stdlib.h>

/* A node has some data and a pointer to the next node */
struct Node {
    int data;
    struct Node *next;
};

/* Create a new node using malloc */
struct Node *createNode(int value) {
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

/* Insert a node at the beginning of the list */
struct Node *insertAtBeginning(struct Node *head, int value) {
    struct Node *newNode = createNode(value);
    newNode->next = head;
    return newNode; /* new node becomes the head */
}

/* Insert a node at the end of the list */
struct Node *insertAtEnd(struct Node *head, int value) {
    struct Node *newNode = createNode(value);

    if (head == NULL) {
        return newNode;
    }

    struct Node *temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    return head;
}

/* Delete the first node that has the given value */
struct Node *deleteNode(struct Node *head, int value) {
    if (head == NULL) {
        printf("List is empty\n");
        return head;
    }

    /* If the head itself holds the value */
    if (head->data == value) {
        struct Node *temp = head;
        head = head->next;
        free(temp);
        printf("Deleted %d\n", value);
        return head;
    }

    struct Node *current = head;
    while (current->next != NULL && current->next->data != value) {
        current = current->next;
    }

    if (current->next == NULL) {
        printf("%d not found in the list\n", value);
        return head;
    }

    struct Node *temp = current->next;
    current->next = temp->next;
    free(temp);
    printf("Deleted %d\n", value);
    return head;
}

/* Reverse the linked list using three pointers */
struct Node *reverseList(struct Node *head) {
    struct Node *prev = NULL;
    struct Node *current = head;
    struct Node *next = NULL;

    while (current != NULL) {
        next = current->next;   /* save the next node */
        current->next = prev;   /* reverse the link */
        prev = current;         /* move prev one step ahead */
        current = next;         /* move current one step ahead */
    }
    return prev; /* prev is the new head */
}

/* Print all the nodes */
void display(struct Node *head) {
    struct Node *temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

/* Free all nodes before the program ends */
void freeList(struct Node *head) {
    struct Node *temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    struct Node *head = NULL;

    head = insertAtEnd(head, 10);
    head = insertAtEnd(head, 20);
    head = insertAtEnd(head, 30);
    head = insertAtBeginning(head, 5);

    printf("Linked List: ");
    display(head);

    head = deleteNode(head, 20);
    printf("After deletion: ");
    display(head);

    head = reverseList(head);
    printf("After reversing: ");
    display(head);

    freeList(head);
    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <string>
using namespace std;

/*
 * Two Sum: find the indices of two numbers that add up to target.
 * We store each number and its index in a map.
 * For every number, we check if (target - number) is already in the map.
 */
vector<int> twoSum(vector<int> nums, int target) {
    unordered_map<int, int> seen; /* number -> index */

    for (int i = 0; i < nums.size(); i++) {
        int needed = target - nums[i];

        if (seen.find(needed) != seen.end()) {
            return {seen[needed], i};
        }
        seen[nums[i]] = i;
    }
    return {}; /* no answer found */
}

/*
 * Valid Parentheses: every opening bracket must be closed
 * by the same type of bracket in the correct order.
 */
bool isValid(string s) {
    stack<char> st;

    for (int i = 0; i < s.length(); i++) {
        char ch = s[i];

        if (ch == '(' || ch == '{' || ch == '[') {
            st.push(ch);
        } else {
            if (st.empty()) {
                return false;
            }
            char top = st.top();
            if ((ch == ')' && top == '(') ||
                (ch == '}' && top == '{') ||
                (ch == ']' && top == '[')) {
                st.pop();
            } else {
                return false;
            }
        }
    }
    return st.empty(); /* valid only if nothing is left open */
}

int main() {
    /* ---------- Two Sum ---------- */
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;

    vector<int> result = twoSum(nums, target);

    cout << "Two Sum" << endl;
    if (result.size() == 2) {
        cout << "Indices: " << result[0] << " and " << result[1] << endl;
        cout << nums[result[0]] << " + " << nums[result[1]] << " = " << target << endl;
    } else {
        cout << "No two numbers add up to " << target << endl;
    }

    /* ---------- Valid Parentheses ---------- */
    cout << endl << "Valid Parentheses" << endl;
    vector<string> tests = {"()", "()[]{}", "(]", "([)]", "{[]}"};

    for (int i = 0; i < tests.size(); i++) {
        if (isValid(tests[i])) {
            cout << tests[i] << " -> Valid" << endl;
        } else {
            cout << tests[i] << " -> Not Valid" << endl;
        }
    }

    return 0;
}

# Check if two strings are anagrams
# (same letters, same count, different order)
def is_anagram(s1, s2):
    s1 = s1.replace(" ", "").lower()
    s2 = s2.replace(" ", "").lower()

    if len(s1) != len(s2):
        return False

    count = {}

    # Count letters of the first string
    for ch in s1:
        if ch in count:
            count[ch] = count[ch] + 1
        else:
            count[ch] = 1

    # Subtract letters of the second string
    for ch in s2:
        if ch not in count:
            return False
        count[ch] = count[ch] - 1

    # All counts must be zero
    for key in count:
        if count[key] != 0:
            return False
    return True


# Check if a string is a palindrome
# (reads the same forwards and backwards)
def is_palindrome(text):
    cleaned = ""
    for ch in text.lower():
        if ch.isalnum():
            cleaned = cleaned + ch

    left = 0
    right = len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left = left + 1
        right = right - 1
    return True


# Count how many times each word appears
def word_frequency(sentence):
    words = sentence.lower().split()
    freq = {}

    for word in words:
        if word in freq:
            freq[word] = freq[word] + 1
        else:
            freq[word] = 1
    return freq


# ---------- Main Program ----------
print("Valid Anagram")
print("listen, silent ->", is_anagram("listen", "silent"))
print("hello, world   ->", is_anagram("hello", "world"))

print()
print("String Palindrome")
print("madam   ->", is_palindrome("madam"))
print("racecar ->", is_palindrome("racecar"))
print("python  ->", is_palindrome("python"))

print()
print("Word Frequency")
sentence = "the cat and the dog and the bird"
result = word_frequency(sentence)
for word in result:
    print(word, ":", result[word])

# Binary Search (Iterative)
# The list must be sorted before searching.
def binary_search_iterative(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1     # search the right half
        else:
            high = mid - 1    # search the left half
    return -1  # not found


# Binary Search (Recursive)
def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1  # not found

    mid = (low + high) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)


# Merge two sorted lists into one sorted list
def merge(left, right):
    result = []
    i = 0
    j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1

    # Add the remaining elements
    while i < len(left):
        result.append(left[i])
        i = i + 1
    while j < len(right):
        result.append(right[j])
        j = j + 1

    return result


# Merge Sort: split the list into halves, sort each half, then merge
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)


# ---------- Main Program ----------
numbers = [38, 27, 43, 3, 9, 82, 10]
print("Original list:", numbers)

sorted_numbers = merge_sort(numbers)
print("Sorted list (Merge Sort):", sorted_numbers)

target = 43
index = binary_search_iterative(sorted_numbers, target)
print()
print("Binary Search (Iterative) for", target)
if index != -1:
    print("Found at index", index)
else:
    print("Not found")

index = binary_search_recursive(sorted_numbers, target, 0, len(sorted_numbers) - 1)
print()
print("Binary Search (Recursive) for", target)
if index != -1:
    print("Found at index", index)
else:
    print("Not found")