Stack - DS Algo related questions

-

The Stack data structure is widely used in various programming scenarios, and interview questions often explore different applications of stacks. Here are some common programs where Stack is used, along with related interview questions:

1. Balanced Parentheses

  • Problem: Check if the given string of parentheses is balanced.
  • Question: Write a function to determine if the input string has balanced parentheses (e.g., {[()()]}).
  • Usage: Push opening brackets onto the stack and pop them when a closing bracket is encountered. At the end, if the stack is empty, the parentheses are balanced.

2. Reverse a String

  • Problem: Reverse a string using a stack.
  • Question: Given a string, reverse it using a stack data structure.
  • Usage: Push all characters of the string onto the stack and then pop them to get the reversed string.

3. Evaluate Postfix Expression

  • Problem: Evaluate an arithmetic expression written in postfix notation.
  • Question: Write a program to evaluate a postfix expression (e.g., 231*+9-).
  • Usage: Traverse the expression, push operands onto the stack, and pop for operations.

4. Infix to Postfix Conversion

  • Problem: Convert an infix expression to a postfix expression.
  • Question: Convert an infix expression (e.g., A+B*C) to postfix using a stack.
  • Usage: Operators are pushed onto the stack and output when appropriate precedence is met.

5. Next Greater Element

  • Problem: Find the next greater element for each element in an array.
  • Question: Given an array, find the next greater element for every element.
  • Usage: Traverse the array, use the stack to keep track of elements for which the next greater element hasn’t been found.

6. Stock Span Problem

  • Problem: Calculate the stock span values for each day.
  • Question: Given the price of stocks for N days, calculate the span of stocks.
  • Usage: Use the stack to keep track of previous days’ prices to compute the span.

7. Celebrity Problem

  • Problem: Find the celebrity in a party of N people.
  • Question: In a group of N people, a celebrity is known by everyone but knows no one. Find the celebrity using O(N) comparisons.
  • Usage: Utilize a stack to eliminate non-celebrities and identify the potential celebrity.

8. Design a Min Stack

  • Problem: Design a stack that supports push, pop, and retrieving the minimum element in constant time.
  • Question: Implement a stack that has a getMin() method returning the minimum element.
  • Usage: Use an auxiliary stack to keep track of the minimum values.

9. Check for Palindrome Using Stack

  • Problem: Check if a string is a palindrome.
  • Question: Determine whether a string is a palindrome by using a stack.
  • Usage: Push the first half of the string onto a stack and then compare with the second half.

10. Sort a Stack

  • Problem: Sort a stack in ascending order using another stack.
  • Question: Write a function to sort a stack using only push and pop operations.
  • Usage: Use a secondary stack to sort elements as they are popped from the original stack.

These are just some of the common scenarios where stacks are frequently used.

Comments

Post a Comment

Popular posts from this blog

Full Stack Java Developer - FAQ

-
PROJECT Explain project architecture & technologies stack used in current project?   Your current project deployment process, If its Microservices then explain its CI/CD process?   How do you scale up and down your application if its support microservice architecture?   If you worked on Jenkins then explain it job/pipeline?   What all approach you will take to track slow running application from end to end, Explain step by step?   How do you deal the difficult customer with adhoc requirement?   How will you handle pressure situation within team?   All achievements in IT career?   Anything you have learned during COVID situation last year? CORE JAVA Static method can be overloaded? Static method can be override...
Read more

DSA Interview Coding Questions

-
1] Arrays 1] Find first and second best score Example Given an array, write a function to get first, second best scores from the array and return it in new array. Array may contain duplicates. Example myArray = { 84 , 85 , 86 , 87 , 85 , 90 , 85 , 83 , 23 , 45 , 84 , 1 , 2 , 0 } firstSecond ( myArray ) // {90, 87} Solution: import java . util . Arrays ; import java . util . Collections ; public class Exercise { public static int [] findTopTwoScores ( int [] array ) { int firstHighest = Integer . MIN_VALUE ; int secondHighest = Integer . MIN_VALUE ;   for ( int score : array ) { if ( score > firstHighest ) { secondHighest = firstHighest ; firstHighest = score ; } else if ( score > secondHighest && score < firstHighest ) { secondHighest = score ; } }   return new int []{ firstHighest , secondHighest }...
Read more

Java Interview Question - New FAQs

-
1. Performance Testing & Setting up benchmarks Performance testing evaluate how a system performs under load & to setup benchmarks below steps to be noted down. Steps are: Define KPIs: Response time, throughput, CPU/memory usage etc. Identify Critical Scenarios: like login, search, submit form Use Tools: Gatling, Apache Bench, JMeter (Use to simulate 1000 concurrent users hitting a Rest API and measure the response time Baseline Measurement: Run tests under normal load to establish a baseline Load Testing: Gradually increase users to find system limits Stress Testing: Push beyond limits to see how the system fails Bench marking: Compare results against industry standards or previous releases 2. ACID properties in database It ensure the reliable transaction Atomicity : All operations in a transaction succeed or none do Consistency : DB remains in a valid state before and after the transaction Isolation : Concurrent transactions don't interfere Durability : Once commited...
Read more