# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# +
'''
12.  Insert in singly Linked-List
'''

class Node:
    def __init__(self):
        self.data = None
        self.next = None
     
    def setData(self,data):
        self.data = data
      
    def getData(self):
        return self.data
     
    def setNext(self,next):
        self.next = next
     
    def getNext(self):
        return self.next

    
class SinglyLinkedList:

    def __init__(self):
        self.head = None
        
    def setHead(self,head):
        self.head = head
                      
    def insert_at_front(self,data):
        
        newHead = Node()
        newHead.setData(data)
        newHead.setNext(self.head)
        
        self.setHead(newHead)


# +
'''
13. Bubble sort 
'''

def bubble_sort(a_list):

  not_done = True
  
  while not_done: 
    not_done = False 
    
    for i in range(0, len(a_list) - 1):
      # Swap two adjacent elements if in the wrong order
      if a_list[i] > a_list[i + 1]:
        a_list[i], a_list[i + 1] = a_list[i + 1], a_list[i]
        not_done = True
    
  return a_list


# +
'''
14. Transpose square matrix

You are given a square 2D image matrix (List of Lists) where each integer represents a pixel.
Write a method transpose_matrix to transform the matrix into its Transpose - in-place. 
The transpose of a matrix is a matrix which is formed by
turning all the rows of the source matrix into columns and vice-versa. 
'''

def transpose_matrix(matrix):
  n = 0
  for i in range(n, len(matrix)):
    for j in range(n, len(matrix)):
      matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    n+=1



# +
'''
15. Given a string, recursively compute a new string 
where identical, adjacent characters 
get separated with a "*". 
'''

def insert_star_between_pairs(a_string):  
  if len(a_string) <= 1: 
    return a_string
  elif a_string[0] == a_string[1]:
    return a_string[0] + "*" + insert_star_between_pairs(a_string[1:])
  else: 
    return a_string[0] + insert_star_between_pairs(a_string[1:])


# -

'''
16. Given a sorted list and an input number as inputs, 
write a function to return a tuple, consisting of the indices of the first and last
occurrences of the input number in the list. 

'''
def find_range(input_list, input_number):
  indices = []
  
  for i in range(0, len(input_list)):
    if input_list[i] == input_number:
      indices.append(i)

  start, end = indices[0], indices[-1]
  return (start, end)


# +
'''
17. Write a function to find the total number of leaf nodes in a binary tree. 
A node is described as a leaf node if it doesn't have any children. 
If there are no leaf nodes, return 0
'''
class TreeNode:
  def __init__(self, data,left_child = None, right_child = None):
    self.data = data
    self.left_child = left_child
    self.right_child = right_child

class BinaryTree:
  def __init__(self, root_node = None):
    self.root = root_node

  def number_of_leaves(self,root):
    if root is None:
      return 0 
    elif root.left_child is None and root.right_child is None: 
      return 1 
    else:
      return self.number_of_leaves(root.left_child) + self.number_of_leaves(root.right_child)                      


# +
'''
18. Given a sorted list of integer ranges, merge all overlapping ranges.

'''
class Range(object):
  def __init__(self):
    self.lower_bound = -1
    self.upper_bound = -1
    
  def __init__(self,lower_bound,upper_bound):
    self.lower_bound = lower_bound
    self.upper_bound = upper_bound
 
  def __str__(self):
    return "["+str(self.lower_bound)+","+str(self.upper_bound)+"]"


def merge_ranges(input_range_list):
    
  merged_range_list = []
  
  x, i = input_range_list[0], 1
  lb, ub = x.lower_bound, x.upper_bound
  
  while True:

    y = input_range_list[i]
    
    if ub >= y.lower_bound: 
      ub = y.upper_bound
    else: 
      merged_range_list.append(Range(lb, ub))
      x = input_range_list[i]
      lb, ub = x.lower_bound, x.upper_bound

    i+=1

    if i == len(input_range_list): 
      break
  
  merged_range_list.append(Range(lb, ub))
  return merged_range_list


# +
'''
19. Given an list of integers, write a method - max_gain - 
that returns the maximum gain. Maximum Gain is defined as 
the maximum difference between 2 elements in a list such 
that the larger element appears after the smaller element. 
If no gain is possible, return 0.
'''

def max_gain(input_list):
  best_gain = 0
  for i in range(0, len(input_list)):
    for j in range(i + 1, len(input_list)):
      current_gain = input_list[j] - input_list[i]
      if best_gain < current_gain:
        best_gain = current_gain 

  return best_gain


# +
'''
20. Write a method to determine whether a given integer 
(zero or positive number) is a power of 4 without using the 
multiply or divide operator. 
If it is, return True, else return False
'''
def is_power_of_four1(number):
  
  if number == 1:
    return True

  n = bin(number)
  
  if n[-1] == '1' or n[-2] == '1':
    return False
    
  if n[2]== '1' and int(n[3:]) == 0 and len(n) % 2 == 1:
    return True
  else:
    return False

def is_power_of_four(number):
    test = 1
    while test < number:
        test = test << 2
    return test == number


# +
'''
21. Given a binary tree, write a function to recursively traverse it in the preorder manner.
Mark a node as visited by adding its data to the list - pre_ordered_list
(defined globally at the top of the editor).
'''

pre_ordered_list = []

class BinaryTree:
 
    def __init__(self, root_data):
        self.data = root_data
        self.left_child = None
        self.right_child = None

    def preorder(self):
        pre_ordered_list.append(self.get_root_val())
          
        if self.get_left_child():
            self.get_left_child().preorder()
        if self.get_right_child():
            self.get_right_child().preorder()
        
    def get_right_child(self):
        return self.right_child

    def get_left_child(self):
        return self.left_child

    def set_root_val(self, obj):
        self.data = obj

    def get_root_val(self):
        return self.data


# +
'''
22. Given a singly linked list, write a method to perform In-place reversal.
'''

class Node:
    def __init__(self):
        self.data = None
        self.next = None
     
    def setData(self,data):
        self.data = data
      
    def getData(self):
        return self.data
     
    def setNext(self,next):
        self.next = next

class SinglyLinkedList:

    def __init__(self):
        self.head = None
        
    def setHead(self,head):
        self.head = head
                      
    def reverse(self):
        previous_node = self.head
        current_node = previous_node.getNext()
        previous_node.setNext(None)
        
        while current_node is not None: 
            next_node = current_node.getNext()
            current_node.setNext(previous_node)
            previous_node = current_node
            current_node = next_node
            
        self.setHead(previous_node)


# +
'''
23. Given a binary tree, implement a method to populate the list post_ordered_list 
with the data of the nodes traversed in postorder, recursively.
'''

post_ordered_list = []
class BinaryTree:
 
    def __init__(self, root_data):
        self.data = root_data
        self.left_child = None
        self.right_child = None

    def postorder(self):
        
        if self.get_left_child() is not None: 
            self.get_left_child().postorder()
        
        if self.get_right_child() is not None: 
            self.get_right_child().postorder()
        
        post_ordered_list.append(self.data)

    def get_right_child(self):
        return self.right_child

    def get_left_child(self):
        return self.left_child

    def set_root_val(self, obj):
        self.data = obj
# -



StarcoderdataJupyterScriptsDedupFiltered