Friday, July 31, 2015

The Fake Geek's blog: The amazing maze



The Fake Geek's blog: The amazing maze

Here I use randomized Kruskal's algorithm with a disjoint set data structure to perform union method.  It works in the following way:

  1. Create a list of all walls that potentially can be destroyed;
  2. Randomly choose a wall index;
  3. Union the two adjacent cells that are separated by the wall;
  4. Repeat until all cells are in the same set.


The union method acts like knocking down the wall, i.e., if two cells are in the same set, they are connected. When all cells are in the same set, there must be one path from the start cell to the end cell. Moreover, since every time we union two cells that are in different sets, there is no path between the cell before union, and since after the union, no other wall will be knocked down between these two cells, so there will be a unique path from any cell to another cell in the maze. Thus fulfill the "perfect" maze requirement.

Read full article from The Fake Geek's blog: The amazing maze

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts