Maximum profit from the stock sale.

Maximum profit from a single buy and sale of stock data

	def maxProfit(arr):
	max_profit = 0
	diff = 0
	mlen = len(arr)
	for i in range(mlen):
	for j in range( i+1 ,mlen):
	if arr[i] < arr[j]:
	diff = arr[j] - arr[i]
	if max_profit < diff:
	max_profit = diff
	return max_profit
	arr = [0, 6, 10, 3, 2, 80, -1, 10, 1]
	print(maxProfit(arr))

view raw maximum_proft.py hosted with ❤ by GitHub

Merge two sorted arrays

Problem Merge One Sorted Array Into Another First array has n positive numbers, and they are sorted in the non-descending order. Second array has 2n numbers: first n are also positive and sorted in the same way but the last n are all zeroes. Merge the first array into the second and return the latter. You should get 2n positive integers sorted in the non-descending order. Example { "first": [1, 3, 5], "second": [2, 4, 6, 0, 0, 0] } Output: [1, 2, 3, 4, 5, 6]

	def merge_one_into_another(first, second):
	"""
	Args:
	first(list_int32)
	second(list_int32)
	Returns:
	list_int32
	"""
	# Write your code here.
	sindex = findex = len(first) - 1
	s_end_index = len(second) - 1
	while( sindex >= 0 and findex >=0 ):
	if (first[findex] < second[sindex]):
	second[s_end_index] = second[sindex]
	sindex -= 1
	else:
	second[s_end_index] = first[findex]
	findex -= 1
	s_end_index -= 1
	print(findex)
	print(sindex)
	print(s_end_index)
	while(sindex >= 0):
	second[s_end_index] = second[sindex]
	sindex -= 1
	s_end_index -= 1
	while(findex >= 0):
	second[s_end_index] = first[findex]
	findex -= 1
	s_end_index -= 1
	return second

view raw mergearr.py hosted with ❤ by GitHub

Mergesort algorithm in python

Mergesort algorithm is a divide and conquer algorithm. Its not efficient as Quicksort algorithm but in some cases Mergesort is better than Quicksort. For example if the data to be sorted is in a linked list then Quicksort is costly since in a linkedlist accessing random elements is costly and in Quicksort we have to access data randomly.

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	O (n log n)
Best Case Performance	O (n log n )
Average Case Performance	O(n log n)
Worst Case space Complexity		O (n)

	def merge(arr, start , end):
	if (start >= end):
	return
	mid = (end+start)//2
	merge(arr, start, mid)
	merge(arr, mid+1, end)
	left = start
	right = mid+1
	aux = []
	while( left<=mid and right<=end):
	if (arr[left] <= arr[right]):
	aux.append(arr[left])
	left += 1
	elif(arr[right] <= arr[left]):
	aux.append(arr[right])
	right += 1
	while (left <= mid):
	aux.append(arr[left])
	left += 1
	while (right <= end) :
	aux.append(arr[right])
	right += 1
	arr[start: end+1] = aux
	def merge_sort(arr):
	"""
	Args:
	arr(list_int32)
	Returns:
	list_int32
	"""
	# Write your code here.
	merge(arr, 0, len(arr)-1)
	return arr

view raw merge_sort.py hosted with ❤ by GitHub

	def mergeSort(alist):
	print("Splitting ",alist)
	if len(alist)>1:
	mid = len(alist)//2
	lefthalf = alist[:mid]
	righthalf = alist[mid:]
	mergeSort(lefthalf)
	mergeSort(righthalf)
	i=0
	j=0
	k=0
	while i<len(lefthalf) and j<len(righthalf):
	if lefthalf[i]<=righthalf[j]:
	alist[k]=lefthalf[i]
	i=i+1
	else:
	alist[k]=righthalf[j]
	j=j+1
	k=k+1
	while i<len(lefthalf):
	alist[k]=lefthalf[i]
	i=i+1
	k=k+1
	while j<len(righthalf):
	alist[k]=righthalf[j]
	j=j+1
	k=k+1
	print("Merging ",alist)
	alist = [54,26,93,17,77,31,44,55,20]
	mergeSort(alist)
	print(alist)

view raw MerSort.py hosted with ❤ by GitHub