Hello Everyone!
On Day 3 of Week 7, the focus was on Divide and Conquer again and the difficulties that tried my problem-solving abilities to the limit today. From building quad trees through to merging two or more sorted lists, the emphasis was placed on how to decompose a problem into sub-problems and come up with solutions to each step and combine them.
Day Events
-
Construct Quad Tree (Medium Skill Level)
- Task: Organize your map using a quad recursion to organize a 2D grid which can have one of the two values: 0 or 1.
- The Strategy: Overlap every cell in the grid with four quadrants of cells of a given value by continuing to divide the grid into four quadrants until every cell within each quadrant corresponded with other of the same value. In the present approach, each quadrant was as well portrayed as a node endowed with pointers to its subfields, if these were further subfield nodes or mere subfields nodes.
- The Fun Part: Observing the tendency for the grid to sub divide into four different individual squares was like solving a complex multi-layered jigsaw puzzle. Appreciating how each quadrant applies simultaneously to the organization’s structure made the task interesting and worthwhile.
-
Merge k Sorted Lists (분급하기 Amp;.Difficulty)
- Task: Convert a list of k sorted linked list into a single sorted linked list.
- The Strategy: Used the concept of recursion where in when solving a problem the problem is divided and conquered by compiling and merging pairs of lists progressively. Lastly, examined a novel solution where the authors implemented a priority queue, more specifically a min-heap, to maintain the possibility of the smallest numbers at each stage.
- The Fun Part: Combining two lists and maintaining the order was as challenging as attempting to establish different strands into one silhouette. To see the list of genes / mutants to be sorted at the end was really satisfying.
Todays Special
Tackling Multidimensional Data:
Construct Quad Tree was another novel one, which adds 2D grids to the list of data structures that can be addressed using divide and conquer approach, which goes beyond arrays and lists.Alternative Approaches:
In Merge k Sorted Lists, when testing for recursive pairing, as well as attempting a heap-based solution, clarity versus speed was highlighted.Layered Problem Solving:
Both problems included processes of gradual construction where neither a grid was divided into regions nor lists merged bit by bit. Serial engagement helped develop the solution through each layer.
Key Takeaways
Divide and Conquer for Grids:
; Some examples are Construct Quad Tree, revealing that divide and conquer can easily solve problems in case they are built on a multi-dimensional platform.Leverage Heaps for Efficiency:
While using min-heap in Merge k Sorted Lists helps in eliminating the need to merge across several sorted sequences both time & space complexities are reduced.Precision in Recursion:
These problems could be solved recursively Same as before boundary counters for Grids and pointers for lists has to be implement with maximum precision.
Reflections
The Construct Quad Tree was a pleasing problem to solve, as it imposed the new concept of 2D hierarchical data transformations. At the same time, Merge k Sorted Lists demonstrated how simple it can be to apply divide and conquer approach; the heap based approach was also efficient. Combined, these problems illustrated the usefulness of this problem solving approach.
What’s Next?
The next day, I’m going to solve ** tsp and longest increasing subsequence** and I’ll understand ** Kadane’s Algorithm and Binary search. These tasks will get me to practice search and optimization so that in the future there will be higher tasks from my employer.
We are glad that you joined this process, and hope to see you in the next stages of our development too. Let us go on doing learning, development, and addressing issues as a team.
Best regards,
Somuya
Top comments (0)