Category: Java Coding Test

Problem Description

With the recent advancements in DNA analysis technology, a password system based on genetic information has been proposed. In this system, a DNA sequence of a certain length is used as a password. DNA consists of 4 nucleotides: A, T, C, and G. You need to find subsequences from a given DNA sequence that can be valid passwords. Each password must pass a validity check based on certain rules, which require a minimum and maximum occurrence of specific nucleotides.

Problem

Write a program that counts the number of valid passwords based on a given DNA string and the minimum and maximum occurrences of each nucleotide (A, T, C, G).

Input Format

• The first line contains the DNA string. (1 ≤ DNA.length ≤ 1000)
• The second line contains the minimum and maximum occurrence counts of each nucleotide (A, T, C, G) separated by spaces.

Output Format

Print the number of valid passwords.

Example

Problem-Solving Process

To solve this problem, we will follow the steps outlined below.

1. Problem Analysis

Since the password must satisfy validity conditions, we need a way to count the occurrences of each nucleotide in the subsequence. After generating all the substrings of the given DNA string, we need to check the occurrences in each substring.

2. Sliding Window Technique

Checking all substrings is inefficient due to the maximum string length of 1000. We will use a technique called sliding window. This technique maintains a combination of indices that represent a portion of the array or string, expanding or contracting as necessary to the left or right.

3. Exploring Implementation Methods

Using the sliding window, we will adjust the length of the subsequence while checking the counts of each nucleotide. During this process, we will verify if the counts meet the conditions and count valid passwords.

4. Code Writing

public class DNAPassword {
        public static void main(String[] args) {
            String dna = "AGCTTAGCTG";
            int[] minCounts = {1, 2, 1, 2}; // Minimum occurrence counts for A, T, C, G
            int[] maxCounts = {2, 3, 2, 3}; // Maximum occurrence counts for A, T, C, G
            
            System.out.println(validPasswordCount(dna, minCounts, maxCounts));
        }

        public static int validPasswordCount(String dna, int[] minCounts, int[] maxCounts) {
            int[] counts = new int[4]; // Counts for each nucleotide
            int validCount = 0;
            int left = 0;

            for (int right = 0; right < dna.length(); right++) {
                counts[getIndex(dna.charAt(right))]++;
                
                while (isValid(counts, minCounts, maxCounts)) {
                    validCount++;
                    counts[getIndex(dna.charAt(left))]--;
                    left++;
                }
            }
            return validCount;
        }

        private static int getIndex(char c) {
            switch (c) {
                case 'A': return 0;
                case 'T': return 1;
                case 'C': return 2;
                case 'G': return 3;
                default: return -1;
            }
        }

        private static boolean isValid(int[] counts, int[] minCounts, int[] maxCounts) {
            for (int i = 0; i < 4; i++) {
                if (counts[i] < minCounts[i] || counts[i] > maxCounts[i]) {
                    return false;
                }
            }
            return true;
        }
    }

5. Testing and Verification

After writing the code, experiment with the input values as shown in the example to verify that the number of valid passwords is correctly printed. Test various DNA strings and count values that meet the given conditions to check the reliability of the program.

Result Analysis

The number of valid passwords outputted as a result must actually match the answer provided in the problem. Additionally, set various test cases to confirm that the results are as expected.

Conclusion

In this course, we have covered the DNA password problem as an example of a Java coding test. I hope you have gained an understanding of how useful the sliding window technique can be in solving algorithmic problems. In the next course, we will cover more useful algorithms!

Developing algorithm problem-solving skills is very important for software developers. Especially when preparing for employment, it is necessary to understand and utilize various algorithms and data structures. In this course, we will understand the concepts of Depth First Search (DFS) and Breadth First Search (BFS), and we will solve actual algorithm problems. In this process, we will examine problem definition, approaches, Java code implementation, and time complexity together.

Problem Definition

The given problem is as follows:

Problem: Given an undirected graph consisting of vertices from 0 to N, write a program to check if it is possible to reach all vertices starting from a specific starting vertex. Let’s solve this problem using two methods: DFS and BFS.

Problem Approach

Graph search algorithms have two main methods: Depth First Search and Breadth First Search. These two methods have different characteristics and applications. Therefore, we will prepare implementations of both methods to solve the problem.

1. DFS (Depth First Search)

DFS explores by going deep first and returns when there are no more vertices to visit. This method can easily be implemented using a stack or through recursion.

DFS Implementation

Here is the Java code that explores the graph using DFS:

import java.util.*;

public class Graph {
    private int vertices;
    private LinkedList[] adjacencyList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
        adjacencyList[destination].add(source); // Undirected graph
    }

    public void dfs(int start) {
        boolean[] visited = new boolean[vertices];
        dfsUtil(start, visited);
    }

    private void dfsUtil(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (Integer neighbor : adjacencyList[vertex]) {
            if (!visited[neighbor]) {
                dfsUtil(neighbor, visited);
            }
        }
    }
}

2. BFS (Breadth First Search)

BFS explores by prioritizing width, first exploring the neighbors of the current vertex and then the neighbors of those neighbors. It is primarily implemented using a queue.

BFS Implementation

Here is the Java code that explores the graph using BFS:

import java.util.*;

public class Graph {
    private int vertices;
    private LinkedList<Integer>[] adjacencyList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
        adjacencyList[destination].add(source); // Undirected graph
    }

    public void bfs(int start) {
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();

        visited[start] = true;
        queue.add(start);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");

            for (Integer neighbor : adjacencyList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

Code Execution Example

Now let’s run an example of exploring a graph using DFS and BFS. The code below creates a graph and performs a traversal using both methods:

public class GraphTraversalExample {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);

        System.out.println("DFS Traversal:");
        graph.dfs(0);

        System.out.println("\nBFS Traversal:");
        graph.bfs(0);
    }
}

Time Complexity Analysis

The time complexities of DFS and BFS are as follows:

• DFS: O(V + E) where V is the number of vertices and E is the number of edges.
• BFS: O(V + E) as it visits each vertex and edge in the graph once.

Conclusion

DFS and BFS are fundamental algorithms for graph traversal. By understanding and utilizing these algorithms, various problems can be solved. If you have learned the basic concepts and implementation methods of graphs through this course, you are ready to tackle more complex problems. Subsequently, it is advisable to connect theory with practice by solving various problems often encountered in actual coding tests.

In the future, I hope you will learn more diverse data structures and algorithms to elevate your programming skills to the next level.

Problem Description

You are standing at an ATM machine. To withdraw money from the ATM, you must go through several processes.
The time it takes for each user to complete the withdrawal varies, and this time is how long it takes the user to perform operations at the ATM.
There are `n` users, and when the withdrawal times for each user are given, you need to write a function that calculates the total time it takes for all users to complete their withdrawals.

Input

• First line: an integer `n` representing the number of users (1 ≤ n ≤ 1000)
• Second line: `n` integers representing each user’s withdrawal time (1 ≤ time ≤ 10000)

Output

Output the total time taken for all users to complete their withdrawals.

Example Input

    5
    3 1 4 3 2
    

Example Output

    32
    

Problem Analysis

The total time taken for all users to finish their withdrawals at the ATM includes the waiting times of other users until each user completes their withdrawal.
That is, the time it takes for a specific user to finish their withdrawal is the sum of their withdrawal time and the times of all previous users who have completed their withdrawals.
This allows us to calculate the withdrawal completion time for all users.

Solution Approach

1. Read the withdrawal times of users and store them in an array.
2. Sort the input withdrawal times in ascending order.
3. To calculate the total withdrawal time, compute the cumulative withdrawal completion time for each user.
4. Sum the withdrawal completion times of all users to find the final total time.

Java Code Implementation

        import java.util.Arrays;
        import java.util.Scanner;

        public class ATMWithdrawal {
            public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                
                // Input number of users
                int n = sc.nextInt();
                int[] times = new int[n];
                
                // Input withdrawal times
                for (int i = 0; i < n; i++) {
                    times[i] = sc.nextInt();
                }
                
                // Sort time array
                Arrays.sort(times);
                
                // Cumulative time variable
                int totalTime = 0;
                int accumulatedTime = 0;
                
                // Calculate cumulative time for each user
                for (int time : times) {
                    accumulatedTime += time; // Add current user's withdrawal time
                    totalTime += accumulatedTime; // Add accumulated time to total time
                }
                
                // Output result
                System.out.println(totalTime);
                
                sc.close();
            }
        }
    

Code Explanation

The above Java code is structured to solve the ATM withdrawal time calculation problem in the following way:

1. First, a Scanner object is created to receive input, and the number of users n is read.
2. Next, each user's withdrawal time is read and stored in the array times.
3. Arrays.sort(times) sorts the withdrawal times in ascending order. This is important for minimizing each user's waiting time.
4. Two variables are used to calculate the total withdrawal time: totalTime holds the total time taken for all users to complete their withdrawals, and accumulatedTime stores the current cumulative time.
5. As we iterate through the withdrawal times, the current user's withdrawal time is added to the accumulated time, which is then added to the total time.
6. Finally, the total withdrawal time is printed.

Time Complexity Analysis

The time complexity of this algorithm primarily depends on sorting the array of withdrawal times.
The average time complexity of the most common sorting algorithm, quicksort, is O(n log n), so the overall time complexity of the algorithm is O(n log n).
After that, the task of accumulating the withdrawal times is solved in a single iteration, resulting in O(n).
Therefore, the overall time complexity is O(n log n).

Summary

In this lecture, we practiced basic array sorting and cumulative summation through the ATM withdrawal time calculation problem.
Most algorithmic problems can be solved using basic data structures and algorithms.
When withdrawal times are optimized, waiting times reduce, and consequently, it will be more efficient for all users to use the ATM.
Problems like this can be used to practice various algorithms and data structures, which can help in job preparation.