Skip to content

Instantly share code, notes, and snippets.

View elderdigiuseppe's full-sized avatar

elderdigiuseppe

1 follower · 0 following
View GitHub Profile
@elderdigiuseppe
elderdigiuseppe / LongLimitedSubstring
Created October 31, 2013 17:38
Given a String s, find the longest substring such that the substring contains exactly 2 unique characters. This means if the string has less than 2 unique characters, do NOT return a substring. for ex aabbcbbadef --> bbcbb aaaaa --> not enough unique This can be done in linear time with constant memory. The basic idea is to walk through the arra…
import java.util.ArrayList;
public class LongLimitedSubstring{
public static void main(String[] args){
LongLimitedSubstring t = new LongLimitedSubstring();
@elderdigiuseppe
elderdigiuseppe / SwapWithZero
Created October 30, 2013 18:39
This is a fun exercise. Rearrange an array using swap with 0. You have two arrays src, tgt, containing two permutations of the numbers 0..n-1. You would like to rearrange src so that it equals tgt. The only allowed operations is “swap a number with 0”, e.g. {1,0,2,3} -> {1,3,2,0} (“swap 3 with 0”). Write a program that prints to stdout the list …
import java.util.Arrays;
public class SwapWithZero{
public static void main(String[] args){
SwapWithZero t = new SwapWithZero();
int[] x ={1,0,2,3};
@elderdigiuseppe
elderdigiuseppe / BSTceiling
Created October 30, 2013 18:01
This is a fun binary search tree exercise. Given a BST and an integer value X, find the ceiling value Y that is present in the BST for X. For example given the tree // 3 // / \ // 1 6 // \ / // 2 4 then given the keys... key 1 -> 2 key 3 -> 4 key 4 -> 6 key 8 -> Integer.MAX_VALUE (note that for this, if the key is larger than all values in the t…
public class BSTCeiling{
public static void main(String[] args){
BSTceiling t = new BSTceiling();
Node a = t.new Node(3);
Node b = t.new Node(1);
Node c = t.new Node(6);
@elderdigiuseppe
elderdigiuseppe / AnagramChecker
Created October 29, 2013 21:23
A colleague said that they got asked this on an interview and I was surprised because it is so easy. (with linear time and space) "Given two strings, determine if they are anagrams of each other, an anagram is a word with the same letters, though they may be rearranged" Simple use a hashmap! Iterate through the first string, incrementing how man…
import java.util.HashMap;
public class AnagramChecker{
public static void main(String[] args){
@elderdigiuseppe
elderdigiuseppe / Rotate
Created October 29, 2013 16:51
Given an NxM matrix, rotate it 90 degrees. I saw this the other day, and while it sounded incredibly simple, I found myself making some silly coding errors. The answer is fairly straight forward, walk up each column of the array moving right, and place them as descending rows in the new array. But it is quite easy to incorrectly use a counter or…
public class Rotate{
public static void main(String[] args){
Rotate t = new Rotate();
// 1,2,3 --> 7,4,1
// 4,5,6 --> 8,5,2
// 7,8,9 --> 9,6,3
@elderdigiuseppe
elderdigiuseppe / PairFinder
Created October 29, 2013 16:31
Given an unsorted array of Integers of size N, and an integer threshold, find the number of unique pairs (x,y) such that x+y <= threshold. This is a slightly more complex version of the problem where x+y= threshold (which can be solved in O(n) using a hash). This problem requires that you know the number of pairs that can be less than the thresh…
import java.util.HashSet;
import java.util.Iterator;
public class PairFinder{
public static void main(String[] args){
@elderdigiuseppe
elderdigiuseppe / MaxHeight
Last active December 25, 2015 19:59
Given a binary tree (using nodes) determine the max height with and without recursion. Doing this with recursion is fairly straight forward, just increment when you drop to a new child, and compare the depths of each sub tree upon returning to get the max. Without recursion though, it is also straight forward. Perform a breadth first search, and…
import java.util.ArrayList;
public class MaxHeight{
public static void main(String[] args){
MaxHeight t = new MaxHeight();
@elderdigiuseppe
elderdigiuseppe / Prover
Created October 16, 2013 17:18
Given a binary tree, prove it is a binary SEARCH tree. In other words, prove a given tree is or is not a binary search tree. This is fairly straight forward, but it is important to not simply check whether the children are greater or less than the current node's value. You need to keep track of the current "max" or "min" for given location. for …
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
public class Prover{
@elderdigiuseppe
elderdigiuseppe / largestContiniousInterval
Created August 15, 2013 19:27
I heard this problem and thought this solution was a clever and fun use of HashSets. It allows you to do this in O(n) time with O(n) space. Given a list of integers, find out the biggest interval that has all its members in the given list. e.g... [1, 7, 4, 6, 3, 10, 2] ---> [1, 4]. [1] ----> [1,1] [1,2,5,6,7] --->[5,7] The basic premise is to us…
/*
* this method takes as input an unsorted list of numbers and returns the largest continious interval of numbers that appeared in the array.
* by being clever with a hashSet, you can do this in O(n) time with O(n) memory. of course, if memory were more a concern, you could just sort
* it in place, and then walk through (making it O(n lg n)) time and O(1) memory).
* The idea is to take an element from the list, and walk backwards and forwards removing those elements from the set. if you ever dont see an
* element, stop walking that direction, and then check whether the current distance of your walk is longer than before.
* @param int[] x: the list of unsorted numbers
*/
public void fastLargestInterval(int[] x){
if (x == null || x.length==0)
@elderdigiuseppe
elderdigiuseppe / SelectKth
Created August 15, 2013 17:33
This is a quickSelect algorithm to find the k-th smallest element in an unsorted array of numbers. It is in place and non-recursive to save memory (meaning its extra memory is O(1)). Further, if the list is randomly sorted, it should ignore half the list each time it parses through it which results in an O(n) complexity. Here is a quick example …
/*
* given a list of numbers, select the Kth number. This means you can select the median, or smallest, or largest, or 10th largest, etc number from your list.
* This method uses in place sorting similar to in place quicksort. Because of this, its extra memory is done in O(1) time. AND because each time we go through the
* list we eliminate (on average) half the list, its expected time is O(n). however, if the pivot selected is always the max or min, you can have a worst case of
* O(n^2).
* @return int the kth value from the list you pass in
* @param int[] x: a list of numbers
* @param k: the kth element you want, can be median, biggest, smallest, etc. make sure k<x.length == true
*/
public int selectKth(int[] x, int k){