ryangurney
BAN USERYou can expand fib into a tail recursive function, and then from that into a simple iterative loop. From there it's pretty straightforward. O(n).
public static int fibTermsBeforeN(int n)
{
int val = 0;
int prev = 1;
int count = 0;
for(; val < n; ++count)
{
val = val + prev;
prev = val  prev;
}
return count;
}

ryangurney
January 13, 2016 Also, you could also do this using a single queue with two counters, which would be more efficient. In this case you would only have a space complexity of O(n).
 ryangurney December 08, 2015import java.util.LinkedList;
/**
* Created by Ryan on 12/8/2015.
*/
public class Test
{
public static class Node
{
int data;
Node[] children;
public Node( int data, Node[] children )
{
this.data = data;
this.children = children;
}
}
public static void main(String args[])
{
//Testy test
/*
0
/\
1 2 3
/ /\
4 5 6
/ /\
7 8 9 10
*/
Node leaf1 = new Node(4, null);
Node leaf2 = new Node(7, null);
Node leaf3 = new Node(8, null);
Node leaf4 = new Node(9, null);
Node leaf5 = new Node(10, null);
Node inner5 = new Node(6, new Node[]{leaf3, leaf4, leaf5});
Node inner4 = new Node(5, new Node[]{leaf2});
Node inner3 = new Node(3, null);
Node inner2 = new Node(2, new Node[]{inner4, inner5});
Node inner1 = new Node(1, new Node[]{leaf1});
Node root = new Node(0, new Node[]{inner1, inner2, inner3});
printTree(root);
}
public static void printTree(Node root)
{
LinkedList<Node> current = new LinkedList<>();
if(root == null)
return;
current.add(root);
while(current.size() > 0)
{
printLevel(current);
LinkedList<Node> parents = current;
current = new LinkedList<>();
for(Node parent : parents)
{
if( parent.children != null)
{
for (Node c : parent.children)
{
current.add(c);
}
}
}
}
}
public static void printLevel( LinkedList<Node> level)
{
if(level.size() <= 0)
{
return;
}
StringBuilder str = new StringBuilder();
for(Node c : level)
{
if (str.length() > 0)
{
str.append(", ");
}
str.append(c.data);
}
System.out.println(str);
}
}

ryangurney
December 08, 2015 Hi!
I'm a little confused by some of the answers I'm seeing here.
Are we assuming then that the nodes in the tree already contain a level property in them?
So if I am iterating through the nodes, I could check the current node's level by
curr.level
? That seems too easy.
 ryangurney December 08, 2015This isn't O(n) time.
 ryangurney November 05, 2015static class Coord
{
public final int X;
public final int Y;
public Coord(int x, int y)
{
this.X = x;
this.Y = y;
}
}
public static void exploreAdjLand(int[][] world, int landX, int landY, int[][] map)
{
Stack<Coord> toVisit = new Stack<>();
toVisit.push( new Coord(landX, landY));
map[landX][landY] = 1;
while( !toVisit.isEmpty() ) //Loop through adj. land discovery
{
Coord currCoords = toVisit.pop();
int x = currCoords.X;
int y = currCoords.Y;
if( x1 >= 0 && map[x1][y] != 1 && world[x1][y] == 'X' ) // bounds, already discovered, and type check
{
map[x1][y] = 1;
toVisit.push(new Coord(x1,y));
}
if( x+1 < map.length && map[x+1][y] != 1 && world[x+1][y] == 'X' )
{
map[x+1][y] = 1;
toVisit.push(new Coord(x+1,y));
}
if( y1 >= 0 && map[x][y1] != 1 && world[x][y1] == 'X' ) // bounds, already discovered, and type check
{
map[x][y1] = 1;
toVisit.push(new Coord(x,y1));
}
if( y+1 < map[x].length && map[x][y+1] != 1 && world[x][y+1] == 'X' )
{
map[x][y+1] = 1;
toVisit.push(new Coord(x,y+1));
}
}
}
public static int findIslands(int[][] world)
{
int[][] map = new int[world.length][world[0].length];
int islandCount = 0;
for(int x = 0; x < world.length; x++)
{
for(int y = 0; y < world[x].length; y++)
{
if(map[x][y] != 1 && world[x][y] == 'X')
{
islandCount++;
exploreAdjLand(world, x, y, map);
}
}
}
return islandCount;
}

ryangurney
November 05, 2015 string = "ddoge" substring = "dog"
 ryangurney October 20, 2015Yep, I was pretty surprised this wasn't mentioned earlier.
 ryangurney October 20, 2015
Repsheenaamajors, System Administrator at Achieve Internet
Teach art classes to a diverse array of students of varying ages and abilities. Strong desire to incorporate a multidimensional ...
RepShirleyCWest, Software Engineer at Agilent Technologies
Hello, me Shirley and I from Savage. I am an artist and I love to doing art and I am ...
Open Chat in New Window
2. in ruby
 ryangurney October 23, 2017