Skip to main content

Posts

GREEDY ALGORITHMS

Greedy Algorithms A greedy algorithm builds up a solution by choosing the option that looks the best at every step.Say you're a cashier and need to give someone 67 cents (US) using as few coins as possible. How would you do it?Whenever picking which coin to use, you'd take the highest-value coin you could. A quarter, another quarter, then a dime, a nickel, and finally two pennies. That's a greedy algorithm, because you're always greedily choosing the coin that covers the biggest portion of the remaining amount.Some other places where a greedy algorithm gets you the best solution:Trying to fit as many overlapping meetings as possible in a conference room? At each step, schedule the meeting that ends earliest.Looking for a minimum spanning tree in a graph? At each step, greedily pick the cheapest edge that reaches a new vertex.Careful: sometimes a greedy algorithm doesn't give you an optimal solution:When filling a duffel bag with cakes of different weights and values

QUEUE

QueueData Structure Quick referenceWorst CasespaceO(n)O(n)enqueueO(1)O(1)dequeueO(1)O(1)peekO(1)O(1

MUTABLE VS IMMUTABLE

Mutable vs Immutable Objects A mutable object can be changed after it's created, and an immutable object can't.In Java, everything (except for strings) is mutable by default: publicclassIntegerPair{int x;int y;IntegerPair(int x,int y){this.x = x;this.y = y;}} IntegerPair p =newIntegerPair(5,10);// p.x = 5, p.y = 10 p.x =50;// p.x = 50, p.y = 10Java There's no way to make existing objects immutable. Even if an object is declared final, its fields can still be changed: publicclassIntegerPair{int x;int y;IntegerPair

INTEGER OVERFLOW

Integer Overflow When you create an integer variable, your computer allocates a fixed number of bits for storing it. Most modern computers use 32 or 64 bits. But some numbers are so big they don't fit even in 64 bits, like sextillion (a billion trillion), which is 70 digits in binary.Sometimes we might have a number that does fit in 32 or 64 bits, but if we add to it (or multiply it by something, or do another operation) the result might not fit in the original 32 or 64 bits. This is called an integer overflow.For example, let's say we have just 2 bits to store integers with. So we can only hold the unsigned (non-negative) integers 0-3 in binary: 00 (0) 01 (1) 10 (2) 11 (3) What happens if we have 3 (11) and we try to add 1 (01)? The answer is 4 (100) but that requires 3 bits and we only have 2.What happens next depends on the language:Some languages, like Python or Ruby, will notice that the result won't fit and automatically allocate space for a larger number.In other langu…

DEPTH-FIRST SEARCH

Depth-First Search (DFS) and Depth-First Traversal Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as deep as possible down one path before backing up and trying a different one.Depth-first search is like walking through a corn maze. You explore one path, hit a dead end, and go back and try a different one.Here's a how a DFS would traverse this tree, starting with the root: We'd go down the first path we find until we hit a dead end: Then we'd do the same thing again—go down a path until we hit a dead end: And again: And again: Until we reach the end.Depth-first search is often compared with breadth-first search.Advantages:Depth-first search on a binary tree generally requires less memory than breadth-first.Depth-first search can be easily implemented with recursion.DisadvantagesA DFS doesn't necessarily find the shortest path to a node, while breadth-first search does. See also:Breadth-First Search (BFS) and Breadth-First TraversalBinary …

BREADTH-FIRST SEARCH

Breadth-First Search (BFS) and Breadth-First Traversal Breadth-first search (BFS) is a method for exploring a tree or graph. In a BFS, you first explore all the nodes one step away, then all the nodes two steps away, etc.Breadth-first search is like throwing a stone in the center of a pond. The nodes you explore "ripple out" from the starting point.Here's a how a BFS would traverse this tree, starting with the root: We'd visit all the immediate children (all the nodes that're one step away from our starting node): Then we'd move on to all those nodes' children (all the nodes that're two steps away from our starting node): And so on: Until we reach the end.Breadth-first search is often compared with depth-first search.Advantages:A BFS will find the shortest path between the starting point and any other reachable node. A depth-first search will not necessarily find the shortest path.DisadvantagesA BFS on a binary tree generally requires more memory than a DF…

GRAPH

GraphData Structuregraph organizes items in an interconnected network.Each item is a node (or vertex). Nodes are connected by edges Strengths:Representing links. Graphs are ideal for cases where you're working with things that connect to other things. Nodes and edges could, for example, respectively represent cities and highways, routers and ethernet cables, or Facebook users and their friendships.Weaknesses:Scaling challenges. Most graph algorithms are O(n*lg(n))O(n∗lg(n)) or even slower. Depending on the size of your graph, running algorithms across your nodes may not be feasible. TerminologyDirected or undirectedIn directed graphs, edges point from the node at one end to the node at the other end. In undirected graphs, the edges simply connect the nodes at each end. Cyclic or acyclicA graph is cyclic if it has a cycle—an unbroken series of nodes with no repeating nodes or edges that connects back to itself. Graphs without cycles are acyclic. Weighted or unweightedIf a graph is we…