def move_zeros_to_left(A):
  if len(A) < 1:
    return

  lengthA = len(A)
  write_index = lengthA - 1
  read_index = lengthA - 1

  while(read_index >= 0):
    if A[read_index] != 0:
      A[write_index] = A[read_index]
      write_index -= 1

    read_index -= 1

  while(write_index >= 0):
    A[write_index]=0;
    write_index-=1

v = [1, 10, 20, 0, 59, 63, 0, 88, 0]
print("Original Array:", v)

move_zeros_to_left(v)

print("After Moving Zeroes to Left: ", v)

class Pair:
  def __init__(self, first, second):
    self.first = first
    self.second = second

def merge_intervals(v):
  if v == None or len(v) == 0 :
    return None

  result = []
  result.append(Pair(v[0].first, v[0].second))

  for i in range(1, len(v)):
    x1 = v[i].first
    y1 = v[i].second
    x2 = result[len(result) - 1].first
    y2 = result[len(result) - 1].second

    if y2 >= x1:
      result[len(result) - 1].second = max(y1, y2)
    else:
      result.append(Pair(x1, y1))

  return result;

v = [Pair(1, 5), Pair(3, 1), Pair(4, 6), 
     Pair(6, 8), Pair(10, 12), Pair(11, 15)]

result = merge_intervals(v)

for i in range(len(result)):
  print("[" + str(result[i].first) + ", " + str(result[i].second) + "]", end =" ")

# merge(fuse) two sorted linked lists
def concatenate_lists(head1, head2):

    if head1 == None:
      return head2

    if head2 == None:
        return head1

    # use left for previous.
    # use right for next.
    tail1 = head1.left
    tail2 = head2.left

    tail1.right = head2
    head2.left = tail1

    head1.left = tail2
    tail2.right = head1
    return head1

def convert_to_linked_list(root):

    if root == None:
        return None

    list1 = convert_to_linked_list(root.left)
    list2 = convert_to_linked_list(root.right)

    root.left = root.right = root
    result = concatenate_lists(list1, root)
    result = concatenate_lists(result, list2)

    return result

def get_list(head):
    r = []
    if head == None:
        return r

    temp = head
    while True:
        r.append(temp.data)
        temp = temp.right
        if temp == head:
          break

    return r

def test(orig_data):

  root = create_BST(orig_data)

  all_data = bst_to_list(root)
  #print(all_data);

  head = convert_to_linked_list(root)
  #print_list(all_data)
  #print_list(v)

  return head

def main():

  data = [100,50,200,25,75,350]
  res = test(data) 
  v = get_list(res)
  print_list(v)

main()

# Using two queues
def level_order_traversal_1(root):
  if root == None:
    return
  queues = [deque(), deque()]
  current_queue = queues[0]
  next_queue = queues[1]
  current_queue.append(root)
  level_number = 0
  while current_queue:
    temp = current_queue.popleft()
    print(str(temp.data) , end = " ")
    if temp.left != None:
      next_queue.append(temp.left)
    if temp.right != None:
      next_queue.append(temp.right)
    if not current_queue:
      print()
      level_number += 1
      current_queue = queues[level_number % 2]
      next_queue = queues[(level_number + 1) % 2]
  print()
arr = [100,50,200,25,75,350]
root = create_BST(arr)
print("InOrder Traversal:", end = "")
display_inorder(root)
print("\nLevel Order Traversal:\n", end = "")
level_order_traversal_1(root)

def str_rev(str, start, end):
  if str == None or len(str) < 2:
    return

  while start < end:
    temp = str[start]
    str[start] = str[end]
    str[end] = temp

    start += 1
    end -= 1


def reverse_words(sentence):

  # Here sentence is a null-terminated string ending with char '\0'.

  if sentence == None or len(sentence) == 0:
    return

  #  To reverse all words in the string, we will first reverse
  #  the string. Now all the words are in the desired location, but
  #  in reverse order: "Hello World" -> "dlroW olleH".

  str_len = len(sentence)
  str_rev(sentence, 0, str_len - 2)

  # Now, let's iterate the sentence and reverse each word in place.
  # "dlroW olleH" -> "World Hello"

  start = 0
  end = 0

  while True:

  # find the  start index of a word while skipping spaces.
    while start < len(sentence) and sentence[start] == ' ':
      start += 1

    if start == str_len:
      break

  # find the end index of the word.
    end = start + 1
    while end < str_len and sentence[end] != ' ':
      end += 1

  # let's reverse the word in-place.
    str_rev(sentence, start, end - 1)
    start = end


def get_array(t):
  s = array('u', t)
  return s


def print_array(s):
  i = 0
  while i != len(s):
    stdout.write(s[i])
    i += 1
  print ()


s = get_array('Hello World!')
print_array(s)
reverse_words(s)
print_array(s)

def can_segment_string(s, dictionary):
  for i in range(1, len(s) + 1):
    first = s[0:i]
    if first in dictionary:
      second = s[i:]
      if not second or second in dictionary or can_segment_string(second, dictionary):
        return True
  return False

s = "hellonow";
dictionary= set(["hello","hell","on","now"])
if can_segment_string(s, dictionary):
  print("String Can be Segmented")
else:
  print("String Can NOT be Segmented")

n = length of input string
for i = 0 to n - 1
  first_word = substring (input string from index [0, i] )
  second_word = substring (input string from index [i + 1, n - 1] )
  if dictionary has first_word
    if second_word is in dictionary OR second_word is of zero length, then return true
    recursively call this method with second_word as input and return true if it can be segmented

current_buy = array[0]
  global_sell = array[1]
  global_profit = global_sell - current_buy

  current_profit = -sys.maxsize - 1

  for i in range(1, len(array)):
    current_profit = array[i] - current_buy

    if current_profit > global_profit:
      global_profit = current_profit
      global_sell = array[i]

    if current_buy > array[i]:
      current_buy = array[i];

  result = global_sell - global_profit, global_sell                 

  return result

array = [1, 2, 3, 4, 3, 2, 1, 2, 5]  
result = find_buy_sell_stock_prices(array)
print("Buy Price: " + str(result[0]) + ", Sell Price: " + str(result[1]))

current profit = INT_MIN
current buy = stock_prices[0]
global sell = stock_prices[1]
global profit = global sell - current buy

for i = 1 to stock_prices.length:
  current profit = stock_prices[i] - current buy
  if current profit is greater than global profit 
    then update global profit to current profit and update global sell to stock_prices[i]
  if stock_prices[i] is less than current buy 
    then update current buy to stock_prices[i]

return global profit and global sell

def power_rec(x, n):
  if n == 0:
    return 1
  if n == 1:
    return x

  temp = power_rec(x, n//2)
  if n % 2 == 0:
    return temp * temp
  else:
    return x * temp * temp

def power(x, n):
  is_negative = False
  if n < 0:
    is_negative = True
    n *= -1

  result = power_rec(x, n)

  if is_negative:
    return 1 / result

  return result

def main():
  pass_count = 0
  fail_count = 0
  for x in range(-10, 5, 1):
    for n in range(-4, 6):
      if x == 0 and n < 0:
        continue
      r1 = power(x * 1.0, n)
      r2 = pow(x, n)
      diff = r1 - r2
      if diff < 0:
        diff *= -1

      if diff > 0.0000000001:
        msg = "r1 = %f, r2 = %f, difference = %f" % (r1, r2, diff)
        print("Failed for (%d, %d) - %s" % (x, n, msg))
        fail_count += 1
      else:
        pass_count += 1
      assert diff <= 0.0000000001

main()
print(pow(2, 5))

def get_bit(num, bit):
    temp = (1 << bit)
    temp = temp & num
    if temp == 0:
      return 0
    return 1

def get_all_subsets(v, sets):
    subsets_count = 2 ** len(v)
    for i in range(0, subsets_count):
      st = set([])
      for j in range(0, len(v)):
         if get_bit(i, j) == 1:
            st.add(v[j])
      sets.append(st)

def main():
    v = [8,13,3,22,17,39,87,45,36]
    subsets = []
    get_all_subsets(v, subsets);
    print("****Total*****" + str(len(subsets)))
    for i in range(0, len(subsets)):
        print("{", end = "")
        print(subsets[i], end = "")
        print("}")
    print("****Total*****" + str(len(subsets)))

main()

n = size of given integer set
subsets_count = 2^n
for i = 0 to subsets_count
    form a subset using the value of 'i' as following:
        bits in number 'i' represent index of elements to choose from original set,
        if a specific bit is 1 choose that number from original set and add it to current subset,
        e.g. if i = 6 i.e 110 in binary means that 1st and 2nd elements in original array need to be picked.
    add current subset to list of all subsets

class Node:
  def __init__(self, d):
    self.data = d
    self.neighbors = []

def clone_rec(root, nodes_completed):
  if root == None:
    return None

  pNew = Node(root.data)
  nodes_completed[root] = pNew

  for p in root.neighbors:
    x = nodes_completed.get(p)
    if x == None:
      pNew.neighbors += [clone_rec(p, nodes_completed)]
    else:
      pNew.neighbors += [x]
  return pNew

def clone(root):
  nodes_completed = {}
  return clone_rec(root, nodes_completed)


# this is un-directed graph i.e.
# if there is an edge from x to y
# that means there must be an edge from y to x
# and there is no edge from a node to itself
# hence there can maximim of (nodes * nodes - nodes) / 2 edgesin this graph
def create_test_graph_undirected(nodes_count, edges_count):
  vertices = []
  for i in range(0, nodes_count):
    vertices += [Node(i)]

  all_edges = []
  for i in range(0, nodes_count):
    for j in range(i + 1, nodes_count):
      all_edges.append([i, j])

  shuffle(all_edges)

  for i in range(0, min(edges_count, len(all_edges))):
    edge = all_edges[i]
    vertices[edge[0]].neighbors += [vertices[edge[1]]]
    vertices[edge[1]].neighbors += [vertices[edge[0]]]

  return vertices


def print_graph(vertices):
  for n in vertices:
    print(str(n.data), end = ": {")
    for t in n.neighbors:
      print(str(t.data), end = " ")
    print()

def print_graph_rec(root, visited_nodes):
  if root == None or root in visited_nodes:
    return

  visited_nodes.add(root)

  print(str(root.data), end = ": {")
  for n in root.neighbors:
    print(str(n.data), end = " ")
  print("}")

  for n in root.neighbors:
    print_graph_rec(n, visited_nodes)

def print_graph(root):
  visited_nodes = set()
  print_graph_rec(root, visited_nodes)

def main():
  vertices = create_test_graph_undirected(7, 18)
  print_graph(vertices[0])
  cp = clone(vertices[0])
  print()
  print("After copy.")
  print_graph(cp)


main()

MARKER = sys.maxsize
def serialize(node, stream):
  if node == None:
    stream.dump(MARKER);
    return
  stream.dump(node.data);
  serialize(node.left, stream)
  serialize(node.right, stream)

def deserialize(stream):
    try:
      data = pickle.load(stream)
      if data == MARKER:
        return None

      node = BinaryTreeNode(data);
      node.left = deserialize(stream)
      node.right = deserialize(stream)
      return node
    except pickle.UnpicklingError:
      return None


root = create_random_BST(15)
display_level_order(root)
output = open('data.class', 'wb')
p = pickle.Pickler(output)
serialize(root, p)
output.close()
input2 = open('data.class','rb')
root_deserialized = deserialize(input2)
display_level_order(root_deserialized)
assert is_identical_tree(root, root_deserialized), "Trees should be identical"

1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6

def find_low_index(arr, key):

  low = 0
  high = len(arr) - 1
  mid = int(high / 2)

  while low <= high:

    mid_elem = arr[mid]

    if mid_elem < key:
      low = mid + 1
    else:
      high = mid - 1

    mid = low + int((high - low) / 2)

  if low < len(arr) and arr[low] == key:
    return low

  return -1

def find_high_index(arr, key):
  low = 0
  high = len(arr) - 1
  mid = int(high / 2)

  while low <= high:
    mid_elem = arr[mid]

    if mid_elem <= key:
      low = mid + 1
    else:
      high = mid - 1

    mid = low + int((high - low) / 2);

  if high == -1:
    return high

  if high < len(arr) and arr[high] == key:
    return high

  return -1


array = [1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6]
key = 5
low = find_low_index(array, key)
high = find_high_index(array, key)
print("Low Index of " + str(key) + ": " + str(low))
print("High Index of " + str(key) + ": " + str(high))

key = -2
low = find_low_index(array, key)
high = find_high_index(array, key)
print("Low Index of " + str(key) + ": " + str(low))
print("High Index of " + str(key) + ": " + str(high))

def binary_search(arr, start, end, key):
  # assuming all the keys are unique.

  if (start > end):
    return -1;

  mid = int(start + (end - start) / 2)

  if arr[mid] == key:
    return mid

  if arr[start] <= arr[mid] and key <= arr[mid] and key >= arr[start]:
    return binary_search(arr, start, mid - 1, key)

  elif arr[mid] <= arr[end] and key >= arr[mid] and key <= arr[end]: 
    return binary_search(arr, mid + 1, end, key)

  elif arr[end] <= arr[mid]:
    return binary_search(arr, mid + 1, end, key)

  elif arr[start] >= arr[mid]:
    return binary_search(arr, start, mid - 1, key)

  return -1;

def binary_search_rotated(arr, key):
  return binary_search(arr, 0, len(arr)-1, key)

v1 = [6, 7, 1, 2, 3, 4, 5];

print("Key(3) found at: " + str(binary_search_rotated(v1, 3)))
print("Key(6) found at: " + str(binary_search_rotated(v1, 6)))

v2 = [4, 5, 6, 1, 2, 3];

print("Key(3) found at: " + str(binary_search_rotated(v2, 3)))
print("Key(6) found at: " + str(binary_search_rotated(v2, 6)))