Skip to content

Instantly share code, notes, and snippets.

View viniru's full-sized avatar

viniru

1 follower · 1 following
View GitHub Profile
@viniru
viniru / karatsugaMulti.java
Last active May 25, 2018 19:53
import java.math.BigInteger;
class KaratsubaMulti{
public static BigInteger compute(String x,String y)
{
int n = 0;
int n1 = x.length();
int n2 = y.length();
if(n1>=n2)n=n2;
@viniru
viniru / ArrayInversions.java
Last active May 26, 2018 18:16
import java.util.Scanner;
import java.util.ArrayList;
public class Inversions {
static long total = 0;
public static int[] inversions(int a[],int s,int e)
{
if(a.length <= 1)
return a;
@viniru
viniru / Unimodal.java
Created May 28, 2018 09:10
You are a given a unimodal array of n distinct elements, meaning that its entries are in increasing order up until its maximum element, after which its elements are in decreasing order. Give an algorithm to compute the maximum element that runs in O(log n) time
public class Unimodal {
public static void unimodal(int a[],int l,int h)
{
int mid = (l+h)/2;
if(a[mid] < a[mid+1])
{
if(a[mid+1] > a[mid+2])
{
System.out.println("The max element is : "+a[mid+1]);
@viniru
viniru / IndexEEle.java
Created May 28, 2018 09:33
You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative, or zero. You want to decide whether or not there is an index i such that A[i] = i. Design the fastest algorithm that you can for solving this problem
public class IndexEEle {
static int a[] = {-3,-1,0,1,4,6,7,8};
static int flag = 0;
public static void find(int l,int h)
{
int mid=(l+h)/2;
if (mid<a[mid])
find(l,mid-1);
@viniru
viniru / SegmentTree.java
Created May 31, 2018 12:52
segment tree to find sum in a particular interval of an array and to update the value at a particular index of the array.
/*package whatever //do not write package name here */
import java.lang.Math;
public class segmentTree
{
static int a[] = {1,2,3,4,5};
static int tree[]; //segment tree that you will construct
public static void buildTree(int sb,int se)
{
int numOfLeaves=a.length;
@viniru
viniru / MinCuts.java
Last active June 12, 2018 12:53
Karger's MinCut Algo in java.Input : Adjacency list. delimiter used in the program : "\t" . Hard coded input : 200 rows ( 200 vertices).you can change it if you want. In main and construct method. The algorithm repeats 199 times. You can change that also if you want.
import java.util.HashMap;
import java.util.Scanner;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;
/*
* Karger's algorithm to compute the minimum cut of a connected graph.
* Takes as input an undirected connected graph and computes a cut
@viniru
viniru / CSQ.txt
Created June 19, 2018 07:06
Computer Science related questions
1. How are binary and text modes for files different ?
2.
@viniru
viniru / SegmentTree.java
Last active June 27, 2018 13:04
Segment tree for updating a random element in an array and to fetch the sum between two indices. In this program of mine , update and get sum methods do not use recursion.Even build tree can written without using recursion but that would need the use of either an explicit stack or a queue which would render the point of eliminating recursion use…
import java.lang.Math;
import java.util.*;
class SegmentTree
{
static int n;
static ArrayList<Integer> ar;
static int t[];
static int[] map;
SegmentTree(int n)
@viniru
viniru / MinHeap.java
Created July 3, 2018 11:45
Min Heap using java with build heap , delete by passing postion of the element to be deleted and insertion of an element.
import java.util.*;
import java.lang.Math;
public class MinHeap {
ArrayList<Integer> ar = new ArrayList<>();
int size = 0;
void delete(int pos)
{
ar.set(pos,ar.get(ar.size()-1));
@viniru
viniru / MaxHeap.java
Created July 3, 2018 11:50
Min Heap using java with build heap , delete by passing postion of the element to be deleted and insertion of an element.
import java.util.*;
import java.lang.Math;
public class MaxHeap {
ArrayList<Integer> ar = new ArrayList<>();
int size = 0;
void delete(int pos)
{
ar.set(pos,ar.get(ar.size()-1));