Coding Musings

Trying to share some code ideas

logo

Tag: Python

Testing for Unconnected Components in a Graph

Testing for Unconnected Components in an Undirected Graph

With a graph structure it is possible that parts of the graph will not be connected to each other.  An example of this would be with social networks, not all users are friends with other users.

The code will find the total number of connected components of the graph, or graph parts in an undirected graph.

See code below.

Read More

Finding an Exit from a Maze

Finding an Exit from a Maze using undirected graphs.

We can think of a maze as a rectangular grid of cells with paths between adjacent cells. If we want to find if there is a path from a given cell to a given exit from the maze, where the exit is represented by a cell, you can represent the maze as an undirected graph.

The nodes of the graph are cells of the maze, and two nodes are connected an undirected edge if they are adjacent and there is no wall between them. Therefore we can surmise we just need to see if a path, series of edges connecting the nodes, to determine if the two nodes are connected.

See code below.

Read More

Binary Search Tree – Is BST?

Binary Search Tree

Traverse the tree in natural order and test if each node is between the previous and the next node. Properly detect duplicate values. If a wrong sub-tree is encountered immediately stop the script and indicate the error.

See code below

Read More

Merging Tables

Simulates a sequence of merge operations with tables in a database.

See code below

Read More

Fractional Knapsack

Standard problem of trying to maximize the values of item with a constraint.  How many items can you put in a knapsack given the value and the weight of the items.

Uses python3
goal: maximize the value of items selected from the get_optimal_value
while the items selected combined weight is less than the inputted capacity

Read More

Binary Search

Binary Search Problem

Function below handles a simple search for a needle in a haystack using the binary search algorithm.

The function is called recursively to check if a value is inside the array

See python code below.

Read More

Pairwise Product

Function to take a vector of length n and multiply the two largest values in the vector.

See the code below

Read More

Powered by WordPress & Theme by Anders Norén