Skip to content

Instantly share code, notes, and snippets.

View jporcelli's full-sized avatar

James Porcelli jporcelli

1 follower · 4 following
View GitHub Profile
@jporcelli
jporcelli / KingdomConnectivity.java
Last active August 29, 2015 14:07
It has been a prosperous year for King Charles and he is rapidly expanding his empire. In fact, he recently invaded his neighbouring country and set up a new kingdom! This kingdom has many cities connected by one-way roads. To ensure higher connectivity, two cities are sometimes directly connected by more than one road also. In the new kingdom, …
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;
@jporcelli
jporcelli / BTcontainsSubtree.java
Last active August 29, 2015 14:07
Determine whether T1, a larger binary tree than t2, contains a rooted subtree that is identical to t2.
package findSubtreeEqualToBT;
import java.util.Stack;
public class Solution {
private static final class BtNode {
public BtNode left, right, parent;
public int val;
@jporcelli
jporcelli / Ksmallest.java
Created September 28, 2014 02:58
Find the k smallest element in O(N) time using partitioning
package orderstats;
import java.util.Arrays;
public class Solution {
public static int ksmallest(int[] a, int k){
return ksmallest(a, 0, a.length, k);
}
@jporcelli
jporcelli / Solution.java
Created September 27, 2014 22:23
Generate all permutations of a string
package stringpermutations;
import java.util.ArrayList;
import java.util.List;
public class Solution {
public static int count = 0;
public static void perms(final String s) {
@jporcelli
jporcelli / Rotate90.java
Last active August 29, 2015 14:06
Rotates a 2-D array 90 degrees, in place.
public static void rotate90(int[][] a){
int n = a.length - 1;
for(int i = 0; i < a.length/2; i++){
for(int j = i; j < a.length - i - 1; j++){
int x = a[i][j];
int y = a[j][n-i];
int z = a[n-i][n-j];
int w = a[n-j][i];
@jporcelli
jporcelli / rotatedBS.java
Created September 25, 2014 01:04
Given a sorted array of n integers that has been rotated(shifted) an unknown number of times (shifted left by x, note rotating left, or right, is no different than shifting left. Only the number of shift positions is different). Find an element in the array. Assume that the array was originally sorted in increasing order.
public static int findhead(int[] a){
return findhead(a, 0, a.length);
}
private static int findhead(int[] a, int l, int h){
if(a[0] > a[a.length - 1]){
while(h > l){
int m = (l+h)/2;
@jporcelli
jporcelli / BuySellStock.java
Created September 20, 2014 22:28
Best Time to Buy and Sell Stock
public int maxProfit(int[] prices) {
if(prices.length < 2){
return 0;
}
int sell = prices[prices.length - 1];
int buy = Integer.MAX_VALUE;
int max = 0;
@jporcelli
jporcelli / NextNode.java
Created September 18, 2014 02:09
An algorithm to find the 'next' node (i.e., in-order successor) of a given node in a bst
public static BstNode nextNode(BstNode n){
if(n.parent == null){
return n.right;
}
if(n.value > n.parent.value){
if(n.right != null){
return n.right;
}else{
BstNode o = n;
@jporcelli
jporcelli / MimimumCutTree.java
Created September 10, 2014 02:53
Find the edge in the tree which, upon removal, causes the two resulting trees to have the absolute value of the difference of their node weight sums minimized
private static class EdgeNode{
public EdgeNode next;
public int y; //edge node
public EdgeNode(int y){
this.y = y;
}
}
private static class Graph{
@jporcelli
jporcelli / SumOfFactorialDigits.java
Last active August 29, 2015 14:06
Factorial digit sum
public class BigFactorial {
private static int getdigits(int n){
// Using array list for convenience of not having to implement re-sizable array
List<Integer> digits = new ArrayList<Integer>();
//initialize our sum with n
int temp = n;
while(temp > 0){
digits.add(0, temp % 10);