anil477’s gists

anil477 / duplicateBinarySearch.py

Created January 21, 2017 11:37

Finding the first and last occurrence of a duplicate item in a sorted array using binary search. Also finds the count of duplicate element( and indices)

	#searchFirst is a flag not for finding the first/last occurence
	def binarySearch(arr, l, r, x, searchFirst):

	result = -1
	while l <= r:

	mid = (l + r ) / 2

	# Check if x is present at mid
	if arr[mid] == x:

anil477 / search_sorted_rotated_array.py

Created January 21, 2017 20:00

Search for an element in a sorted rotated array without finding the pivot

	class Search:
	def __init__(self):
	self.array = [3, 4, 5, 1, 2]

	def search(self, low, high, key):
	if low > high:
	return -1

	mid = (low + high) / 2

anil477 / pivot_sorted_rotated_array.py

Last active January 21, 2017 20:05

Find pivot and minimum element in a sorted rotated array. Also find how many times was the sorted array rotated.

	class Search:
	def __init__(self):
	# self.array = [3, 4, 5, 6, 7, 8, 1, 2]
	# self.array = [3, 4, 5, 6, 7, 8,9, 10,11,12, 0,1,2]
	self.array = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14]

	def search(self, low, high):

	# if the entire array is sorted then pivot point is 0
	if self.array[low] < self.array[high]:

anil477 / insertion_sort.py

Created January 27, 2017 19:00

Insertion Sort

	def insertionSort(alist):
	for index in range(1, len(alist)):

	currentvalue = alist[index]
	position = index

	while position > 0 and alist[position - 1] > currentvalue:
	alist[position] = alist[position - 1]
	position = position - 1

anil477 / ceil.py

Last active January 28, 2017 06:33

Ceil of a number using binary search


	# http://www.geeksforgeeks.org/search-floor-and-ceil-in-a-sorted-array/


	def binarySearch(arr, l, r, x):

	if x < arr[l]:
	return arr[l]

	if x > arr[r]:

anil477 / largestSumContiguousSubarray.java

Created April 10, 2017 09:35

Largest Sum Contiguous Subarray - Kadane Algorithm


	import java.io.*;
	import java.util.*;
	import java.lang.Math;

	class Kadane
	{
	public static void main (String[] args)
	{
	int [] a = {-2, -3, 4, -1, -2, 1, 5, -3};

anil477 / mergeSortedLL.java

Last active April 12, 2017 15:19

Merge two sorted linked list - iterative

	// https://github.com/careermonk/DataStructureAndAlgorithmsMadeEasyInJava/blob/master/src/chapter03linkedlists/MergeSortedListsRecursion.java
	public class MergeSortedListsIterative {
	public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
	ListNode head = new ListNode(0);
	ListNode curr = head;
	while(head1 != null && head2 != null){
	if(head1.data <= head2.data){
	curr.next = head1;
	head1 = head1.next;
	}else{

anil477 / sort012.java

Created April 14, 2017 06:15

Sort an array of 0,1 and 2. Dutch National Flag Problem

	// Java program to sort an array of 0, 1 and 2
	import java.io.*;

	class countzot {

	// Sort the input array, the array is assumed to
	// have values in {0, 1, 2}
	static void sort012(int a[], int arr_size)
	{
	int lo = 0;

anil477 / intersectionSortedLinkedList.java

Created April 14, 2017 07:17

Intersection of two sorted linked list

	private Node getIntersectedLinkedList(Node first, Node second){
	Node ptr = first;
	Node ptr1 = second;
	Node previous = null;
	Node firstIntersectedNode = null;
	while (ptr != null) {
	ptr1=second;
	while (ptr1!= null && ptr.getValue() != ptr1.getValue() ) {
	ptr1 = ptr1.getNext();
	}

anil477 / NextGreater.java

Last active May 28, 2017 14:07

Next greater element in an array

	// The idea is to insert the newly arrived element in the sorted manner and
	// pop all element that is smaller then the newly arrived element.
	// https://www.youtube.com/watch?v=8P-Z7Oc8x9I
	// don't use stack.peek() == null for checking is the stack is empty. It will throw and error. use stack.isEmpty()

	import java.util.*;

	class great{

	public static void main(String args[]) {

Anil Singh anil477