stephenpince
BAN USERpublic class LRUCache<K,V> {
int capacity;
LRUCache( int capacity ) {
this.capacity = capacity;
}
static class Element<K,V> implements Comparable<Element<K,V>>{
Element(K k, V v) {
this.k = k;
this.v = v;
timestamp = System.currentTimeMillis();
}
long timestamp;
K k;
V v;
public int compareTo(Element<K,V> other) {
return Long.compare(this.timestamp, other.timestamp);
}
public boolean equals(Object obj ) {
if ( !( obj instanceof Element ) ) return false;
Element<K,V> other =(Element<K,V>)obj;
return other.k.equals(this.k);
}
public int hashCode() {
return k.hashCode();
}
}
PriorityQueue<Element<K,V>> queue = new PriorityQueue<Element<K,V>>();
Map<K,Element<K,V>> elements = new HashMap<K,Element<K,V>>();
public V get(K k) {
if (elements.containsKey(k)) {
Element<K, V> e = elements.get(k);
queue.remove(e);
e.timestamp = System.currentTimeMillis();
queue.add(e);
return e.v;
} else {
return null;
}
}
void set(K k, V v) {
if (elements.containsKey(k)) {
Element<K, V> e = elements.get(k);
queue.remove(e);
e.v = v;
e.timestamp = System.currentTimeMillis();
queue.add(e);
}
else if ( queue.size() + 1 > capacity ) {
Element<K,V> e = queue.remove();
elements.remove(e.k);
Element<K,V> newE = new Element<K,V>(k,v);
queue.add(newE);
elements.put(k, newE);
}
else {
Element<K,V> newE = new Element<K,V>(k,v);
queue.add(newE);
elements.put(k, newE);
}
}
void remove (K k) {
if (elements.containsKey(k)) {
Element<K, V> e = elements.get(k);
queue.remove(e);
elements.remove(k);
}
}
public static void main(String[] args) {
}
}
do dfs and maintain a stack
check the stack for when you are backtracking
input file:
1:2
2:3
3:5
4:4
5:8
5:6
7:-2
15:2
package com.loadgeneral.projects;
import java.util.Map;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Iterator;
public class PathSum {
Node root = null;
Map<Integer, Node> nodes = new HashMap<Integer,Node>();
static class Node {
int value;
int id;
Node left;
Node right;
public Node ( int id, int val ){
this.id = id;
this.value = val;
}
public String toString(){
return id+":"+this.value;
}
}
public PathSum(String fileName) {
try (BufferedReader rdr = new BufferedReader(new FileReader(fileName))) {
String line = null;
while ((line = rdr.readLine()) != null) {
Node n = parseLine(line);
if ( root == null ) root = n;
}
}
catch (IOException ioe) {
System.err.println("error: " + ioe);
}
}
Node parseNode( int id, int val ) {
if ( nodes.containsKey(id) ) return nodes.get(id);
Node n = new Node(id,val);
nodes.put( id, n);
return n;
}
Node parseLine(String line) {
int idx = line.indexOf(":");
int id = Integer.parseInt(line.substring(0, idx).trim());
int val = Integer.parseInt(line.substring(idx+1).trim());
Node n = parseNode(id,val);
if ( id != 1 ) {
Node parentNode = nodes.get(id/2);
if ( id%2 == 0 ) parentNode.left = n;
if ( id%2 == 1 ) parentNode.right = n;
}
return n;
}
void dfsSum( Node node, Deque<Integer> stack, int sum ){
if ( node == null ) return;
stack.push(node.value);
dfsSum(node.left,stack,sum);
dfsSum(node.right,stack,sum);
checkStack(stack,sum);
stack.pop();
}
void checkStack( Deque<Integer> stack, int sum ){
int currSum = 0;
boolean found = false;
for ( Iterator<Integer> iter = stack.iterator() ; iter.hasNext(); ) {
currSum += iter.next();
if ( currSum == sum ) {
found = true;
break;
}
}
if ( found == false ) return;
currSum = 0;
List<Integer> l = new ArrayList<Integer>();
for ( Iterator<Integer> iter = stack.iterator() ; iter.hasNext(); ) {
int val = iter.next();
currSum += val;
l.add(0,val);
if ( currSum == sum ) {
break;
}
}
System.out.print(l + " ");
}
void printSum(int sum) {
dfsSum(this.root, new ArrayDeque<Integer>(), sum);
}
static public void main(String[] args) {
PathSum ps = new PathSum(args[0]);
ps.printSum(Integer.parseInt(args[1]));
}
}
function repeatPrint(str) {
var count = 0;
var arry = str.split('');
for ( var i = 1; i < arry.length; ++i ) {
if ( arry [i-1] == arry [i] ) {
++count;
}
else if ( count != 0 ) {
console.log( arry [i-1]+ " repeated " + (count+1) + " times" );
count = 0;
}
}
if ( count != 0 ) {
console.log( arry [i-1] + " repeated is " + (count+1) + " times" );
}
}
It is critical that you divide by 2 or you will get the same word, and you don't have to worry about the median or mid character
function reverseChars(char[] strArray) {
if ( strArray.length < 2 ) return;
int mid = strArray.length/2;
for ( int i = 0; i < mid; ++i ) {
char tmp = strArray[i];
strArray[i] = strArray[strArray.length-i-1];
strArray[strArray.length-i-1] = tmp;
}
}
Test cast should be
assert( node != null && node.next != null && node.next.next == null)
function printSecondLastNode(Node head) {
if ( head == null ) return;
Node node = head;
Node candidateSecondLast = null;
while ( node.next != null ) {
candidateSecondLast = node;
node = node.next;
}
if ( candidateSecondLast != null ) {
print candidateSecondLast.value;
}
}
There can no space in height, width or length.
function numberOfChocolates(a,b,c) {
if ( (a%2) != 0 ) return 0;
if ( (b%2) != 0 ) return 0;
if ( (c%2) != 0 ) return 0;
int heightNum = a/2;
int widthNum = b/2;
int lengthNum = c/2;
return heightNum * widthNum * lengthNum;
}
public class DiscoverIslands {
int[][] matrix;
public DiscoverIslands(int[][] matrix) {
this.matrix = matrix;
}
public DiscoverIslands(String filename) {
String line;
List<int[]> l = new ArrayList<int[]>();
try (BufferedReader rdr = new BufferedReader(new FileReader(filename))) {
while ((line = rdr.readLine()) != null) {
l.add(parseLine(line));
}
}
catch (IOException ioe) {
System.err.println("error: " + ioe);
return;
}
this.matrix = new int[l.size()][];
for ( int i = 0; i < this.matrix.length; ++i ) {
this.matrix[i] = l.get(i);
}
}
private class Position {
int row;
int col;
Position(int row, int col) {
this.row = row;
this.col = col;
}
public boolean equals(Object obj) {
if ( !(obj instanceof Position) ) return false;
Position other = (Position) obj;
return this.row == other.row && this.col == other.col;
}
public int hashCode() {
return this.row + this.col * matrix[this.row].length;
}
Position getDown() {
return (this.row + 1) >= matrix.length ? null : new Position(
this.row + 1, this.col);
}
Position getUp() {
return (this.row == 0) ? null
: new Position(this.row - 1, this.col);
}
Position getLeft() {
return this.col == 0 ? null : new Position(this.row, this.col - 1);
}
Position getRight() {
return (this.col + 1) >= matrix[this.row].length ? null
: new Position(this.row, this.col + 1);
}
public List<Position> getAdjancyList() {
List<Position> l = new ArrayList<Position>();
Position right = getRight();
if (isSet(right))
l.add(right);
Position up = getUp();
if (isSet(up))
l.add(up);
Position left = getLeft();
if (isSet(left))
l.add(left);
Position down = getDown();
if (isSet(down))
l.add(down);
return l;
}
public String toString() {
return this.row + ":" + this.col;
}
}
int[] parseLine(String line) {
String[] row = line.split("\\s");
int rowInt[] = new int[row.length];
for( int i =0; i < row.length; ++i ) {
rowInt[i] = Integer.parseInt(row[i].trim());
}
return rowInt;
}
boolean isSet(Position p) {
return (p != null) && (matrix[p.row][p.col] == 1);
}
void exploreIsland(Position p, Set<Position> visited) {
visited.add(p);
for (Position adj : p.getAdjancyList()) {
if (!visited.contains(adj)) {
exploreIsland(adj, visited);
}
}
}
public int getIslands() {
Set<Position> visited = new HashSet<Position>();
int islands = 0;
for (int row = 0; row < matrix.length; ++row) {
for (int col = 0; col < this.matrix[row].length; ++col ) {
if (matrix[row][col] == 1) {
Position p = new Position(row, col);
if (!visited.contains(p)) {
exploreIsland(p, visited);
++islands;
}
}
}
}
return islands;
}
public static void main(String[] args) {
String fileName = args[0];
DiscoverIslands d = new DiscoverIslands(fileName);
System.err.println("islands = " + d.getIslands());
}
}
package com.loadgeneral.projects;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Set;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.Queue;
import java.util.LinkedList;
public class FriendsGraph {
static class Node {
String name;
List<Node> friends = new ArrayList<Node>();
Node(String n) {
name = n;
}
}
Map<String,Node> graph = new HashMap<String,Node>();
FriendsGraph( String fileName ) {
String line;
try ( BufferedReader rdr = new BufferedReader(new FileReader(fileName))) {
while ( (line = rdr.readLine()) != null ) {
parseLine(line);
}
}
catch ( IOException ioe) {
System.err.println("error: " + ioe);
}
}
Node findNode(String name ){
Node n = graph.get(name);
if ( n == null ) {
n = new Node(name);
graph.put(name,n);
}
return n;
}
void parseLine(String line) {
int idx = line.indexOf(":");
String name = line.substring(0,idx).trim();
Node n = findNode(name);
String[] friends = line.substring(idx+1).split(",");
for( String f: friends) {
String friendName = f.trim();
Node friendNode = findNode(friendName);
n.friends.add(friendNode);
}
}
void processNode(Node node, Queue<Node> q, int level, Set<String> visited, Map<Integer, Set<String>> friendLevelMap){
for (Node n : node.friends) {
if ( ! visited.contains(n.name) ) {
Set<String> levelFriends = friendLevelMap.get(level);
if (levelFriends == null) {
levelFriends = new HashSet<String>();
friendLevelMap.put(level, levelFriends);
}
visited.add(n.name);
q.add(n);
levelFriends.add(n.name);
System.err.println(node.name + " adding: " + n.name);
}
}
}
Map<Integer, Set<String>> bfsFriends(Node node) {
int level = 1;
Map<Integer, Set<String>> friendLevelMap = new TreeMap<Integer, Set<String>>();
Set<String> visited = new HashSet<String>();
Queue<Node> q1 = new LinkedList<Node>();
Queue<Node> q2 = new LinkedList<Node>();
q1.add(node);
visited.add(node.name);
while ( !q1.isEmpty() || !q2.isEmpty() ) {
while ( !q1.isEmpty() ) {
node = q1.remove();
System.err.println("q1 removing node: " + node.name);
processNode(node, q2,level,visited,friendLevelMap);
}
++level;
while ( !q2.isEmpty() ) {
node = q2.remove();
processNode(node, q1,level,visited,friendLevelMap);
System.err.println("q2 removing node: " + node.name);
}
++level;
}
return friendLevelMap;
}
void printFriends ( String person ) {
Map<Integer,Set<String>> friendsLevel = bfsFriends( graph.get(person) ) ;
for ( Map.Entry<Integer,Set<String>> e: friendsLevel.entrySet() ) {
System.err.println( "Level " + e.getKey() + " - " + e.getValue() );
}
}
public static void main(String[] args) {
String fileName = args[0];
String person = args[1];
FriendsGraph g = new FriendsGraph(fileName);
g.printFriends(person);
}
}
cleaner version
public class ZigZagfs {
Node root = null;
Map<Integer, Node> nodes = new HashMap<Integer,Node>();
static class Node {
int value;
Node left;
Node right;
public Node ( int value ){
this.value = value;
}
public String toString(){
return ""+this.value;
}
}
public ZigZagfs(String fileName) {
try (BufferedReader rdr = new BufferedReader(new FileReader(fileName))) {
String line = null;
while ((line = rdr.readLine()) != null) {
Node n = parseLine(line);
if ( root == null ) root = n;
}
}
catch (IOException ioe) {
System.err.println("error: " + ioe);
}
}
Node parseNode( String str ) {
if ( str == null ) return null;
str = str.trim();
if ( str.length() == 0 ) return null;
int val = Integer.parseInt(str);
if ( nodes.containsKey(val) ) return nodes.get(val);
Node n = new Node(val);
nodes.put(val, n);
return n;
}
Node parseLine(String line) {
int idx = line.indexOf(":");
Node n = parseNode( line.substring(0, idx) );
String[] children = line.substring(idx + 1).split(",");
if ( children.length > 0 ) n.left = parseNode(children[0]);
if ( children.length > 1 ) n.right = parseNode(children[1]);
System.out.println(n.value + ": " + n.left + "," + n.right);
return n;
}
void print() {
Node node = root;
Deque<Node> q1 = new LinkedList<Node>();
q1.add(node);
Queue<Node> q2 = new LinkedList<Node>();
String comma = "";
while (!q1.isEmpty() || !q2.isEmpty()) {
while (!q1.isEmpty()) {
node = q1.removeLast();
System.out.print(comma + node.value);
if (node.left != null)
q2.add(node.left);
if (node.right != null)
q2.add(node.right);
comma = ",";
}
System.out.println("");
comma = "";
while (!q2.isEmpty()) {
node = q2.remove();
System.out.print(comma + node.value);
if (node.left != null)
q1.add(node.left);
if (node.right != null)
q1.add(node.right);
comma = ",";
}
System.out.println("");
comma = "";
}
}
static public void main(String[] args) {
ZigZagfs zigZag = new ZigZagfs(args[0]);
zigZag.print();
}
}
java Arrays is your friend
static class Row {
Object[] internalRow;
Row(Object[] row) {
this.internalRow = row;
}
public boolean equals( Object obj ) {
if ( ! obj instanceof Row ) return false;
Row other = (Row)obj;
return Arrays.deepEquals(this.internalRow, other.internalRow );
}
public int hashCode() {
return Arrays.deepHashCode(this.internalRow);
}
public String toString() {
return Arrays.toString(this.internalRow);
}
}
void printUniqueRows ( Object[][] matrix ) {
Set<Row> s = new HashSet<Row>();
for ( int i = 0; i < maxtrix.length; ++i ) {
Object[] row = matrix[i];
s.add( new Row(row) );
}
for ( Row r: s ) {
System.err.println(r.toString());
}
}
do a bfs on left and right
- stephenpince July 31, 2015