Data Engineering Interview Series #1: Data Structures and Algorithms

my_list = [1, 2, 3, 4, 5]
# Accessing an element
element = my_list[2]  # element = 3

# Adding an element
my_list.append(6)  # my_list = [1, 2, 3, 4, 5, 6]

# Removing an element
my_list.remove(3)  # my_list = [1, 2, 4, 5, 6]
print(my_list)

# sort list in place
my_list.sort()


# Iterate through a list

for idx, elt in enumerate(my_list):
    print(f'Use enumerate to get index: {idx} and element: {elt}')

for elt in my_list:
    print(f'Use loop directly to loop through elements: {elt}')

my_dict = {'a': 1, 'b': 2, 'c': 3}
# Accessing a value
value = my_dict['b']  # value = 2

# Adding a key-value pair
my_dict['d'] = 4  # my_dict = {'a': 1, 'b': 2, 'c': 3, 'd': 4}

# Removing a key-value pair
del my_dict['a']  # my_dict = {'b': 2, 'c': 3, 'd': 4}
print(my_dict)

from collections import deque

queue = deque([1, 2, 3])
# Adding an element
queue.append(4)  # queue = deque([1, 2, 3, 4])

# Removing an element
element = queue.popleft()  # element = 1, queue = deque([2, 3, 4])
print(f'The popped element is {element} and the remaining queue is {queue}')

stack = [1, 2, 3]
# Adding an element (push)
stack.append(4)  # stack = [1, 2, 3, 4]

# Removing an element (pop)
element = stack.pop()  # element = 4, stack = [1, 2, 3]
print(f'The popped element is {element} and the remaining stack is {stack}')

# Creating a set
my_set = {1, 2, 3, 4, 5}

# Adding an element
my_set.add(6)  # my_set = {1, 2, 3, 4, 5, 6}

# Removing an element
my_set.remove(3)  # my_set = {1, 2, 4, 5, 6}

# Checking membership
is_in_set = 4 in my_set  # is_in_set = True

# Set operations: union, intersection, difference
other_set = {4, 5, 6, 7, 8}
union_set = my_set.union(other_set)  # union_set = {1, 2, 4, 5, 6, 7, 8}
intersection_set = my_set.intersection(other_set)  # intersection_set = {4, 5, 6}
difference_set = my_set.difference(other_set)  # difference_set = {1, 2}

print(f' Here is my_set {my_set} and other_set {other_set}')
print(f' Here is union_set {union_set}')
print(f' Here is intersection_set {intersection_set}')
print(f' Here is difference_set {difference_set}')

from collections import Counter

# Creating a Counter from a list
my_counter = Counter(['apple,' 'banana,' 'apple,' 'orange,' 'banana,' 'apple'])

print(my_counter)

import heapq

# by default, this is a min-heap. To get the max heap, multiply the number by -1 before inserting
a = []
heapq.heappush(a, 10)

heapq.heappop(a)

def iterative_dfs(graph, start_node):
    visited = set()
    stack = [start_node]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            # Add neighbors to the stack
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited


def recursive_dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            recursive_dfs(graph, neighbor, visited)
    
    return visited

# Define a simple graph using an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# Test case 1: Iterative DFS
iterative_result = iterative_dfs(graph, 'A')
print("Iterative DFS:", iterative_result)

# Test case 2: Recursive DFS
recursive_result = recursive_dfs(graph, 'A')
print("Recursive DFS:", recursive_result)

# Test case 3: Both methods should produce the same result for the same graph and start node
assert iterative_result == recursive_result, "Iterative and Recursive DFS results should match"

# Test case 4: Start from a different node
iterative_result_b = iterative_dfs(graph, 'B')
recursive_result_b = recursive_dfs(graph, 'B')
print("Iterative DFS from B:", iterative_result_b)
print("Recursive DFS from B:", recursive_result_b)

assert iterative_result_b == recursive_result_b, "Iterative and Recursive DFS results should match"

from collections import deque

def iterative_bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            # Add neighbors to the queue
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
    return visited

def recursive_bfs_aux(graph, queue, visited):
    if not queue:
        return visited
    
    node = queue.popleft()
    visited.add(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited and neighbor not in queue:
            queue.append(neighbor)
    
    return recursive_bfs_aux(graph, queue, visited)

def recursive_bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    return recursive_bfs_aux(graph, queue, visited)

# Define a simple graph using an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# Test case 1: Iterative BFS
iterative_result = iterative_bfs(graph, 'A')
print("Iterative BFS:", iterative_result)

# Test case 2: Recursive BFS
recursive_result = recursive_bfs(graph, 'A')
print("Recursive BFS:", recursive_result)

# Test case 3: Both methods should produce the same result for the same graph and start node
assert iterative_result == recursive_result, "Iterative and Recursive BFS results should match"

# Test case 4: Start from a different node
iterative_result_b = iterative_bfs(graph, 'B')
recursive_result_b = recursive_bfs(graph, 'B')
print("Iterative BFS from B:", iterative_result_b)
print("Recursive BFS from B:", recursive_result_b)

assert iterative_result_b == recursive_result_b, "Iterative and Recursive BFS results should match"

def iterative_binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # Target not found

def recursive_binary_search(arr, target, left, right):
    if left > right:
        return -1  # Target not found

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return recursive_binary_search(arr, target, mid + 1, right)
    else:
        return recursive_binary_search(arr, target, left, mid - 1)

arr = [1, 3, 5, 7, 9, 11, 13, 15]

# Test case 1: Iterative Binary Search
iterative_result = iterative_binary_search(arr, 7)
print("Iterative Binary Search for 7:", iterative_result)  # Should print index 3

# Test case 2: Recursive Binary Search
recursive_result = recursive_binary_search(arr, 7, 0, len(arr) - 1)
print("Recursive Binary Search for 7:", recursive_result)  # Should print index 3

# Test case 3: Target not found
iterative_not_found = iterative_binary_search(arr, 4)
recursive_not_found = recursive_binary_search(arr, 4, 0, len(arr) - 1)
print("Iterative Binary Search for 4:", iterative_not_found)  # Should print -1
print("Recursive Binary Search for 4:", recursive_not_found)  # Should print -1