# 2/1 2024 Coding Practices

USEFUL WEBSITE
https://www.geeksforgeeks.org/google-internship-interview-experience-off-campus-2022/

>**My Coding Practices**
> https://jupyter.org/try-jupyter/lab/?path=notebooks%2FIntro.ipynb
> https://hackmd.io/id2JZD18S1KKbNrh89zU4A

**Round 1: Interview 1**

Warm-up problem – Given an array, create a new array that will have arr[i] and 2 * arr[i] from I iterating from 0 to array size. Return any shuffled version of this newly created array.

arr=[1,2,3,4,5,6]

import random 
def new_arr(arr):
    new_arr=[]
    for i in arr:
        new_arr.append(i)
        new_arr.append(2*i)
    random.shuffle(new_arr)
    return new_arr

shuffle_arr=new_arr(arr)
print(shuffle_arr)

Round 2: Interview 2
~~#### have not prepared and answer yet~~

Tree problem – A tree node can either be an internal node or a leaf node.
If it is an internal node then it stores the sum of lengths of strings present in its left and right child.
If it is a leaf node then it stores string as well as its length.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def is_leaf(node):
    return node.left is None and node.right is None

def create_tree(values):
    if not values:
        return None

    nodes = [TreeNode(val) for val in values]
    for i in range(len(nodes) // 2):
        nodes[i].left = nodes[2 * i + 1]
        nodes[i].right = nodes[2 * i + 2]

    return nodes[0]

def print_tree(root):
    if root:
        print_tree(root.left)
        print(root.val)
        print_tree(root.right)

# Example usage:
values = [10, 5, 15, "hello", 5, "world", 5]
root = create_tree(values)
print_tree(root)

### Binary Search
Binary search is a classic algorithm used to search for a target value within a sorted array or list. It works by repeatedly dividing the search interval in half until the target value is found or the interval is empty. Here's how it works:

Initialization: Binary search requires that the input array is sorted in ascending order. The algorithm also needs to know the value it's searching for, which we'll call the "target."

Search Process:

Begin with the entire array as the search interval.
Find the middle element of the current interval.
Compare the middle element with the target:
If the middle element is equal to the target, the search is successful, and the index of the target is returned.
If the middle element is greater than the target, the search continues in the lower half of the array.
If the middle element is less than the target, the search continues in the upper half of the array.
Repeat the process with the new search interval (either the lower or upper half), until the target is found or the interval becomes empty.
Termination:

If the target is found, return its index.
If the interval becomes empty (i.e., the lower index exceeds the upper index), the target is not in the array, and the search terminates.
Binary search is significantly more efficient than linear search (where elements are searched sequentially) for large sorted arrays because it eliminates half of the remaining elements at each step, resulting in a time complexity of O(log n), where n is the number of elements in the array

def binary_search(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
        else:
            high = mid - 1
    
    return -1  # Target not found

# Example usage:
arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(arr, target)
if index != -1:
    print("Target found at index:", index)
else:
    print("Target not found in the array.")

First Question: You are given an array A with N integers. you are required to answer Q queries of the following types.

Determine the count of distinct prime numbers which divides all the numbers in a given range L to R. NOTE:1 based Indexing.

1 <=N,Q<= 10^5;

def sieve_of_eratosthenes(limit):
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    
    primes = []
    for num in range(2, limit + 1):
        if sieve[num]:
            primes.append(num)
            for multiple in range(num * num, limit + 1, num):
                sieve[multiple] = False
                
    return primes

def count_distinct_prime_divisors(arr, l, r):
    limit = max(arr)
    primes = sieve_of_eratosthenes(limit)
    
    prime_divisors = set()
    for num in arr[l-1:r]:
        for prime in primes:
            if num % prime == 0:
                prime_divisors.add(prime)
    
    return len(prime_divisors)

# Example usage:
N = int(input("Enter the number of elements in the array: "))
arr = list(map(int, input("Enter the elements of the array separated by space: ").split()))
Q = int(input("Enter the number of queries: "))

for _ in range(Q):
    query_type, L, R = map(int, input("Enter query (type L R): ").split())
    if query_type == 1:
        print("Count of distinct prime divisors:", count_distinct_prime_divisors(arr, L, R))

### Questions.
Q1. Given an array of integers, you need to find the local maxima.

Example : [1 3 5 4 7 10 6]

Output: 5 or 10

Explanation: Any of the local maxima can be the output.
Here 5 is greater than 3 and 4, 10 is greater than 7 and 6.

def find_local_maxima(arr):
    local_maxima = []
    n = len(arr)
    
    for i in range(1, n-1):
        if arr[i] > arr[i-1] and arr[i] > arr[i+1]:
            local_maxima.append(arr[i])
    
    # Check the first and last elements separately
    if arr[0] > arr[1]:
        local_maxima.append(arr[0])
    if arr[-1] > arr[-2]:
        local_maxima.append(arr[-1])
    
    return local_maxima

# Example usage:
arr = [1, 3, 5, 4, 7, 10, 6]
output = find_local_maxima(arr)
print("Local Maxima:", output)

### Questions.
Given a sequence of brackets, how will you identify if its valid or not.

Example : ({[][]})

Output: Valid

Explanation: Every opening bracket has a closing bracket.

Example: ({[]]})

Output: Invalid

Explanation : Every opening bracket does not have a closing bracket.

To determine whether a sequence of brackets is valid, you can use a stack data structure. The idea is to iterate through each bracket in the sequence and push opening brackets onto the stack. When a closing bracket is encountered, pop the top element from the stack and check if it matches the corresponding opening bracket. If all brackets are properly matched, the stack will be empty at the end. Here's the code:

def is_valid_brackets(s):
    stack = []
    bracket_map = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in bracket_map.values():
            stack.append(char)
        elif char in bracket_map.keys():
            if not stack or bracket_map[char] != stack.pop():
                return "Invalid"
    
    return "Valid" if not stack else "Invalid"

# Example usage:
sequence1 = "({[][]})"
sequence2 = "({[]}])"

print("Output for sequence1:", is_valid_brackets(sequence1))
print("Output for sequence2:", is_valid_brackets(sequence2))

The expression stack.pop() if stack else '#' is a conditional expression, also known as a ternary operator. It is a concise way to write an if-else statement in Python.

Let's break down the expression:

stack.pop(): This is the value returned if the condition (stack) evaluates to True. It means that if the stack is not empty (i.e., it contains elements), the top element of the stack is popped off using the pop() method.

if stack: This is the condition being evaluated. It checks if the stack list is not empty. If the stack is not empty, the condition evaluates to True, and stack.pop() is executed.

else '#': This is the value returned if the condition (stack) evaluates to False. It means that if the stack is empty, the placeholder character '#' is returned instead of trying to pop from an empty stack, which would result in an error.

In summary, the expression stack.pop() if stack else '#' is used to safely pop the top element from the stack if it is not empty. If the stack is empty, it returns the placeholder character '#'. This ensures that the code does not attempt to pop from an empty stack, avoiding potential errors.

### Telephonic Interview 2. (Telephonic + Google Docs Shared)

Q1. There are 2 arrays. Smaller is of size m and has m elements in sorted order. The bigger array is
of size m+n, where there are only n elements in initial n positions in sorted order. So, last m
positions are empty in the bigger array. Insert smaller array’s m elements in m + n array has all numbers in sorted order.

Example :
Input Array N[]={5, 9, 15, 20,,,,,, } n=4
M[]={1, 3, 6, 8, 19, 35} m=6
Output array N[]={1, 3, 5, 6, 8, 9, 15, 19, 20, 35}