DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workkloads.

Secure your stack and shape the future! Help dev teams across the globe navigate their software supply chain security challenges.

Releasing software shouldn't be stressful or risky. Learn how to leverage progressive delivery techniques to ensure safer deployments.

Avoid machine learning mistakes and boost model performance! Discover key ML patterns, anti-patterns, data strategies, and more.

Related

  • Universal Implementation of BFS, DFS, Dijkstra, and A-Star Algorithms
  • Doubly Linked List in Data Structures and Algorithms
  • Linked List in Data Structures and Algorithms
  • Queue in Data Structures and Algorithms

Trending

  • Evolution of Cloud Services for MCP/A2A Protocols in AI Agents
  • Java's Quiet Revolution: Thriving in the Serverless Kubernetes Era
  • AI, ML, and Data Science: Shaping the Future of Automation
  • Docker Model Runner: Streamlining AI Deployment for Developers
  1. DZone
  2. Data Engineering
  3. Data
  4. Solving Three Medium-Level Coding

Solving Three Medium-Level Coding

In this article, we will explore three medium-level coding problems and provide solutions for each of them.

By 
Volha Kurcheuskaya user avatar
Volha Kurcheuskaya
·
May. 26, 23 · Tutorial
Likes (1)
Comment
Save
Tweet
Share
4.4K Views

Join the DZone community and get the full member experience.

Join For Free

In this article, we will explore three medium-level coding problems and provide solutions for each of them. The problems we will discuss are:

  1. Minimum Number of Vertices to Reach All Nodes
  2. Maximum Twin Sum of a Linked List
  3. Swap Nodes in Pairs

While these problems may appear unrelated at first, they share common characteristics and can enhance our understanding of various programming concepts. Furthermore, by exploring their solutions, we can gain insights into graph theory, linked list manipulation, and algorithmic problem-solving techniques. Therefore, this article aims to provide readers with a comprehensive overview of these problems and their solutions.

Problem 1: Minimum Number of Vertices to Reach All Nodes Description

The problem involves a directed acyclic graph (DAG) represented by an array of edges. The task is to find the smallest set of vertices from which all nodes in the graph are reachable. It is guaranteed that a unique solution exists.

Solution

To solve this problem, we can utilize the concept of in-degree and out-degree vertices in a DAG. We iterate through all the edges and identify the vertices with zero in-degree. These vertices will form the minimum set of vertices needed to reach all other nodes in the graph.

C++
 
fun findSmallestSetOfVertices(n: Int, edges: List<List<Int>>): List<Int> {

    val inDegree = IntArray(n)

    for (edge in edges) {

        val to = edge[1]

        inDegree[to]++

    }

    

    val result = mutableListOf<Int>()

    for (i in 0 until n) {

        if (inDegree[i] == 0) {

            result.add(i)

        }

    }

    

    return result

}


Similarities With Other Problems

The Minimum Number of Vertices problem shares similarities with graph traversal and topological sorting algorithms. Therefore, by understanding its solution, we can gain insights into concepts like in-degree, out-degree, and graph connectivity.

Problem 2: Maximum Twin Sum of a Linked List Description

In this problem, we are given a linked list of even length, where each node has a twin. The twin of the ith node is the (n-1-i)th node, where n is the total number of nodes in the list. The twin sum is defined as the sum of a node and its twin.

Solution

To find the maximum twin sum of the linked list, we iterate through half of the linked list and calculate the sum of each node and its twin. By keeping track of the maximum sum encountered, we can find the desired result.

C++
 
class ListNode(var `val`: Int) {

    var next: ListNode? = null

}



fun maxTwinSum(head: ListNode?): Int {

    var current = head

    var maxSum = 0



    while (current != null && current.next != null) {

        maxSum = maxOf(maxSum, current.`val` + current.next!!.`val`)

        current = current.next!!.next

    }



    return maxSum

}


Similarities With Other Problems

The Maximum Twin Sum problem involves linked list manipulation and understanding node relationships. By solving this problem, we enhance our understanding of linked list traversal and arithmetic operations on linked list nodes.

Problem 3: Swap Nodes in Pairs Description

Given a linked list, the task is to swap every two adjacent nodes and return the head of the modified list. Only the nodes themselves can be changed, and the values within the nodes must remain unaltered.

Solution

To solve this problem, we employ a recursive approach. We swap the first two adjacent nodes and recursively call the function on the remaining linked list. By appropriately adjusting the pointers, we can swap the nodes in pairs throughout the list.

C++
 
class ListNode(var `val`: Int) {

    var next: ListNode? = null

}



fun swapPairs(head: ListNode?): ListNode? {

    if (head?.next == null) {

        return head

    }



    val newHead = head.next

    head.next = swapPairs(newHead?.next)

    newHead?.next = head



    return newHead

}


Similarities With Other Problems

The Swap Nodes in Pairs problem involves linked list manipulation and recursive algorithms. By solving this problem, we develop a deeper understanding of linked list traversal, pointer manipulation, and recursive problem-solving techniques.

Conclusion 

In this article, we explored three medium-level coding problems: Minimum Number of Vertices to Reach All Nodes, Maximum Twin Sum of a Linked List, and Swap Nodes in Pairs. Despite their apparent differences, these problems share common characteristics and help us strengthen our understanding of graph theory, linked list manipulation, and algorithmic problem-solving techniques. Furthermore, by examining their solutions, we acquire valuable insights into various programming concepts. Whether you are interested in graph algorithms, linked list manipulation, or recursive approaches, this article provides a useful resource for enhancing your problem-solving skills.

Data structure Directed acyclic graph Algorithm Coding (social sciences) Graph (Unix) Data Types

Opinions expressed by DZone contributors are their own.

Related

  • Universal Implementation of BFS, DFS, Dijkstra, and A-Star Algorithms
  • Doubly Linked List in Data Structures and Algorithms
  • Linked List in Data Structures and Algorithms
  • Queue in Data Structures and Algorithms

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!