Solution to Three Medium-Level Coding

Java Code GeeksJune 2nd, 2023Last Updated: June 2nd, 2023

0 207 5 minutes read

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

The problems are:

Problem 1: Reverse Words in a String
Problem 2: Find Missing Number in an Array
Problem 3: Check Balanced Parentheses

Problem 1: Reverse Words in a String

The problem is to reverse the order of words in a given string. To solve this, we can follow these steps:

Split the input string into an array of words using the split function and providing a space as the separator.
Reverse the array of words using the reverse function, which modifies the original array in place.
Join the reversed array of words back into a string using the join function, specifying a space as the separator.
Return the reversed string.

The solution takes advantage of the built-in array functions available in JavaScript to simplify the process. It handles cases where the words are separated by single spaces.

function reverseWords(str) {
  // Split the string into an array of words
  const words = str.split(' ');

  // Reverse the array of words
  const reversedWords = words.reverse();

  // Join the reversed words back into a string
  const reversedString = reversedWords.join(' ');

  return reversedString;
}

// Example usage
const input = 'Hello World';
console.log(reverseWords(input)); // Output: 'World Hello'

Problem 2: Find Missing Number in an Array

The problem is to find the missing number in an array of distinct integers from 1 to n, where n is the length of the array. Here’s how we can solve it:

Calculate the expected sum of integers from 1 to n using the formula (n * (n + 1)) / 2.
Iterate through the given array and calculate the sum of all the elements.
Subtract the actual sum from the expected sum to find the missing number.

The solution assumes that the input array is missing only one number and contains distinct integers. It uses the concept of the sum of an arithmetic series to calculate the expected sum and then finds the missing number by subtracting the actual sum.

function findMissingNumber(nums) {
  const n = nums.length + 1; // Expected length of array
  const sum = (n * (n + 1)) / 2; // Sum of integers from 1 to n

  let actualSum = 0;
  for (let i = 0; i < nums.length; i++) {
    actualSum += nums[i];
  }

  return sum - actualSum;
}

// Example usage
const numbers = [1, 2, 4, 6, 3, 7, 8];
console.log(findMissingNumber(numbers)); // Output: 5

Problem 3: Check Balanced Parentheses

The problem is to determine if a given string containing parentheses is balanced or not. A balanced string has an equal number of opening and closing parentheses, and they are properly nested. Here's the approach to solving it:

Create an empty stack to keep track of opening parentheses encountered.
Iterate through the string character by character.
If an opening parenthesis is encountered, push it onto the stack.
If a closing parenthesis is encountered:
- If the stack is empty, it means there is no matching opening parenthesis, so the parentheses are unbalanced. Return false.
- If the stack is not empty, pop an opening parenthesis from the stack to match the closing parenthesis.
After iterating through all the characters, check if the stack is empty. If it is, the parentheses are balanced; otherwise, they are unbalanced.

The solution utilizes a stack data structure to maintain the order of opening parentheses encountered. It checks for each closing parenthesis if there is a corresponding opening parenthesis on the stack. If the stack is empty at the end, it means all opening parentheses have been closed, indicating balanced parentheses.

These verbal explanations provide a more detailed understanding of the approach used to solve each coding problem. The code snippets provided earlier can be used as a reference for implementation.

function isBalancedParentheses(str) {
  const stack = [];

  for (let i = 0; i < str.length; i++) {
    const char = str[i];

    if (char === '(') {
      stack.push(char);
    } else if (char === ')') {
      if (stack.length === 0) {
        return false; // Unbalanced parentheses
      }
      stack.pop();
    }
  }

  return stack.length === 0; // Check if all opening parentheses are closed
}

// Example usage
const parentheses1 = '(()())';
console.log(isBalancedParentheses(parentheses1)); // Output: true

const parentheses2 = '())(';
console.log(isBalancedParentheses(parentheses2)); // Output: false

These solutions provide implementations for the given problems. However, it's always good to consider edge cases and further optimize the code as per specific requirements.

Similarities With Other Problems

Although the three coding problems provided above are distinct, they do share some similarities with other types of problems. Here are some similarities:

String Manipulation: Both the "Reverse Words in a String" problem and the "Check Balanced Parentheses" problem involve manipulating strings. In the first problem, we split and reverse a string, while in the second problem, we iterate over a string to check for balanced parentheses. These problems require string handling techniques and manipulation operations such as splitting, joining, iterating, and checking characters.
Array Manipulation: The "Find Missing Number in an Array" problem deals with manipulating an array. It requires iterating over the array and performing calculations to find the missing number. Similar array manipulation techniques, such as calculating sums, iterating over elements, and performing arithmetic operations, are commonly used in other array-related problems.
Data Structures: All three problems involve the use of data structures. The "Check Balanced Parentheses" problem uses a stack to keep track of opening parentheses. The "Find Missing Number in an Array" problem operates on an array. Understanding and working with different data structures is crucial in problem-solving and often applicable to various problem domains.
Iteration and Conditionals: Each problem involves iterations over elements or characters, combined with conditional statements to make decisions or perform certain actions. Iteration and conditionals are fundamental programming concepts used in problem-solving across various domains.

These similarities highlight the recurring patterns and techniques used in problem-solving. By recognizing and understanding these commonalities, you can develop a problem-solving mindset and apply similar strategies to solve new problems efficiently.

Conclusion

In conclusion, the three medium-level coding problems provided - reversing words in a string, finding a missing number in an array, and checking balanced parentheses - demonstrate various problem-solving techniques and concepts commonly encountered in programming.

These problems involve string manipulation, array manipulation, data structures like stacks, and the use of iterations and conditionals. By understanding the underlying concepts and patterns within these problems, you can develop a problem-solving approach that can be applied to similar problems in different contexts.

Mastering these fundamental problem-solving techniques, such as string and array manipulation, data structure utilization, and algorithmic thinking, will greatly enhance your ability to tackle a wide range of coding challenges. Practice and exposure to different problem-solving scenarios will further sharpen your skills and enable you to approach new problems with confidence.

Remember, problem-solving is an iterative process that improves with practice, patience, and a deep understanding of programming fundamentals. So, keep challenging yourself with diverse problems and continue expanding your problem-solving toolkit.