Magic Cows | Dynamic Programming | Adhoc | Interview problem

WilliamFiset · Intermediate ·⚡ Algorithms & Data Structures ·6y ago

Key Takeaways

The video covers the dynamic programming problem Magical Cows from the MAPS 2020 programming competition, providing a walkthrough and example solution using Java.

Original Description

Walkthrough of the dynamic programming problem Magical Cows featured in the MAPS 2020 programming competition. This problem is a good example of an adhoc interview problem you could encounter. Problem: https://open.kattis.com/problems/magicalcows Source code: https://github.com/williamfiset/Algorithms/tree/master/src/main/java/com/williamfiset/algorithms/dp/examples/magicalcows Algorithms repository: https://github.com/williamfiset/algorithms Video slides: https://github.com/williamfiset/algorithms/tree/master/slides Website: http://www.williamfiset.com
☆ Save to playlist Watch on YouTube ↗
AI explanation not available for this lesson yet
This lesson is still being prepared for the AI tutor. In the meantime, explore lessons that are ready.
Browse explainer-ready lessons →

Playlist

Uploads from WilliamFiset · WilliamFiset · 0 of 60

← Previous Next →
1 JES Image Manipulation - 2 - Installation
JES Image Manipulation - 2 - Installation
WilliamFiset
 2 JES Image Manipulation - 3 - User Interface
JES Image Manipulation - 3 - User Interface
WilliamFiset
 3 JES Image Manipulation - 5 - Negative
JES Image Manipulation - 5 - Negative
WilliamFiset
 4 JES Image Manipulation - 6 - Black & White
JES Image Manipulation - 6 - Black & White
WilliamFiset
 5 JES Image Manipulation - 4 - Grayscale
JES Image Manipulation - 4 - Grayscale
WilliamFiset
 6 JES Image Manipulation - 8 - Blur
JES Image Manipulation - 8 - Blur
WilliamFiset
 7 JES Image Manipulation - 7 - Edge Detection
JES Image Manipulation - 7 - Edge Detection
WilliamFiset
 8 JES Image Manipulation - 9 - Blend
JES Image Manipulation - 9 - Blend
WilliamFiset
 9 JES Image Manipulation - 10 - Matte
JES Image Manipulation - 10 - Matte
WilliamFiset
 10 JES Image Manipulation - 13 - Rotate90
JES Image Manipulation - 13 - Rotate90
WilliamFiset
 11 JES Image Manipulation - 12 - Mirroring Picture
JES Image Manipulation - 12 - Mirroring Picture
WilliamFiset
 12 JES Image Manipulation - 11 - Crop Image
JES Image Manipulation - 11 - Crop Image
WilliamFiset
 13 JES Image Manipulation - 14 - Stretch picture
JES Image Manipulation - 14 - Stretch picture
WilliamFiset
 14 Java Fractal Explorer [6/8]
Java Fractal Explorer [6/8]
WilliamFiset
 15 Java Fractal Explorer [4/8]
Java Fractal Explorer [4/8]
WilliamFiset
 16 Java Fractal Explorer [8/8]
Java Fractal Explorer [8/8]
WilliamFiset
 17 Java Fractal Explorer [5/8]
Java Fractal Explorer [5/8]
WilliamFiset
 18 Java Fractal Explorer [2/8]
Java Fractal Explorer [2/8]
WilliamFiset
 19 Java Fractal Explorer [7/8]
Java Fractal Explorer [7/8]
WilliamFiset
 20 Java Fractal Explorer [1/8]
Java Fractal Explorer [1/8]
WilliamFiset
 21 Java Fractal Explorer [3/8]
Java Fractal Explorer [3/8]
WilliamFiset
 22 Introduction [Programming Competition Problems]
Introduction [Programming Competition Problems]
WilliamFiset
 23 String Manipulation 1 [Programming Competition Problems]
String Manipulation 1 [Programming Competition Problems]
WilliamFiset
 24 String Manipulation 2 [Programming Competition Problems]
String Manipulation 2 [Programming Competition Problems]
WilliamFiset
 25 Graph Theory 1 [Programming Competition Problems]
Graph Theory 1 [Programming Competition Problems]
WilliamFiset
 26 Logic 1 [Programming Competition Problems]
Logic 1 [Programming Competition Problems]
WilliamFiset
 27 Grid Problems 1 [Programming Competition Problems]
Grid Problems 1 [Programming Competition Problems]
WilliamFiset
 28 Dynamic Programming 1 [Programming Competition Problems]
Dynamic Programming 1 [Programming Competition Problems]
WilliamFiset
 29 Introduction to Big-O
Introduction to Big-O
WilliamFiset
 30 Dynamic and Static Arrays
Dynamic and Static Arrays
WilliamFiset
 31 Dynamic Array Code
Dynamic Array Code
WilliamFiset
 32 Linked Lists Introduction
Linked Lists Introduction
WilliamFiset
 33 Doubly Linked List Code
Doubly Linked List Code
WilliamFiset
 34 Stack Introduction
Stack Introduction
WilliamFiset
 35 Stack Implementation
Stack Implementation
WilliamFiset
 36 Stack Code
Stack Code
WilliamFiset
 37 Queue Introduction
Queue Introduction
WilliamFiset
 38 Queue Implementation
Queue Implementation
WilliamFiset
 39 Queue Code
Queue Code
WilliamFiset
 40 Priority Queue Introduction
Priority Queue Introduction
WilliamFiset
 41 Priority Queue Min Heaps and Max Heaps
Priority Queue Min Heaps and Max Heaps
WilliamFiset
 42 Priority Queue Inserting Elements
Priority Queue Inserting Elements
WilliamFiset
 43 Priority Queue Removing Elements
Priority Queue Removing Elements
WilliamFiset
 44 Priority Queue Code
Priority Queue Code
WilliamFiset
 45 Union Find Introduction
Union Find Introduction
WilliamFiset
 46 Union Find Kruskal's Algorithm
Union Find Kruskal's Algorithm
WilliamFiset
 47 Union Find - Union and Find Operations
Union Find - Union and Find Operations
WilliamFiset
 48 Union Find Path Compression
Union Find Path Compression
WilliamFiset
 49 Union Find Code
Union Find Code
WilliamFiset
 50 Binary Search Tree Introduction
Binary Search Tree Introduction
WilliamFiset
 51 Binary Search Tree Insertion
Binary Search Tree Insertion
WilliamFiset
 52 Binary Search Tree Removal
Binary Search Tree Removal
WilliamFiset
 53 Binary Search Tree Traversals
Binary Search Tree Traversals
WilliamFiset
 54 Binary Search Tree Code
Binary Search Tree Code
WilliamFiset
 55 Fenwick Tree range queries
Fenwick Tree range queries
WilliamFiset
 56 Fenwick Tree point updates
Fenwick Tree point updates
WilliamFiset
 57 Fenwick Tree construction
Fenwick Tree construction
WilliamFiset
 58 Fenwick tree source code
Fenwick tree source code
WilliamFiset
 59 Hash table hash function
Hash table hash function
WilliamFiset
 60 Hash table separate chaining
Hash table separate chaining
WilliamFiset

The video teaches how to approach and solve the Magical Cows problem using dynamic programming, providing a valuable example for interview preparation and algorithmic problem-solving.

Key Takeaways
  1. Read and understand the problem statement
  2. Identify the dynamic programming approach
  3. Define the state and transition functions
  4. Implement the solution in Java
  5. Test and optimize the solution
💡 Dynamic programming can be used to solve complex problems by breaking them down into smaller sub-problems and storing the solutions to sub-problems to avoid redundant computation.

Related Reads

📰
Trapping Rain Water: Understanding Data Structure Choices from a Beginner’s Perspective
Learn to solve the Trapping Rain Water problem by understanding optimal data structure choices and array traversal techniques
Medium · Programming
 📰
The Grid Problem That Looks Easy Until You Need the Lexicographically Smallest Path
Learn to find the lexicographically smallest path in a grid, a problem that seems easy but requires careful consideration of path construction and comparison
Medium · Programming
 📰
The Algorithm That’s Practically O(1) — But Provably Isn’t
Learn about an algorithm that behaves like O(1) but isn't, and how to analyze its complexity
Medium · Programming
 📰
Knight Attack Made BFS Feel Like a Recipe, Not a Template
Learn how to apply BFS to solve the Knight Attack problem with a Python solution
Medium · Python
Up next
Quant Interview Question #quant
quantprof
Watch →