Question

Backtracking is a computing algorithm using stack to “remember” user-generated events when using a program. A user event may be “pressing the Enter key on keyboard” or “clicking a mouse button”. Stack is a data structure with the Last-In-First-Out property (LIFO). If we push the aforesaid user events into a stack, a computer program using that data structure can “rewind” user events by popping them out of stack one at a time. This backtracking feature is available as Edit -> Undo in most editorial processing programs such as Microsoft Word. Similarly, most programs have Edit -> Redo allowing you to undo your Undo's. To record backtracking in both directions (undo, redo), a software program uses two separate stacks, one for tracking all of the push operations for Undo and another for tracking all of the pop operations for Redo. To illustrate this, say we label each user event with a unique, sequentially increasing, non-negative number:

Event Type	Event Number
Clicking a Mouse button	1
Pressing the Enter key	2
Pressing the “A” key	3
Pressing the “b” key	4

All push operations are sequentially tracked in an events_pushed stack, whereas pop operations are tracked in an events_popped stack.

If the user goes through the above events 1 -> 2 -> 3 -> 4 without undoing them, we have

Event Sequence: push(1) -> push(2) -> push(3) -> push(4):
events_pushed: [1,2,3,4]
events_popped: []

If the user goes through the sequential events 1 -> 2 -> 3 -> 4 and undo the last one:

Event Sequence: push(1) -> push(2) -> push(3) -> push(4) -> pop(4)
events_pushed: [1,2,3,4]
events_popped: [4]

Both events_pushed and events_popped keep track of all of the pushes and pops, respectively and sequentially, recording the user journey from beginning to end. Your will write a solution method to check if two input stacks, events_pushed and events_popped, represent the result of an actual sequence of events happened on an initially empty stack. If so, the solution methods turns true, false otherwise.

import java.util.Stack;
public class HomeworkAssignment2_1 {    
    public static void main(String[] args) {
    // just like any problems, whatever you need here, etc.

}
// YOUR STYLING AND DOCUMENTATION GOES HERE
class Solution {
   // OR, YOUR STYLING AND DOCUMENTATION CAN GO HERE TOO
   public boolean isSameEventSequence(int[] events_pushed, int[] events_popped) { 
      // YOUR CODE HERE 
   }
}

For example, the sequence of events 1 -> 2 -> 3 -> undo 3 -> 4 -> undo 4 -> undo 2 -> undo 1 is captured as follows:

Event Sequence: push(1) -> push(2) -> push(3) -> pop(3) -> push(4) -> pop(4) -> pop(2) -> pop(1)
events_pushed: [1,2,3,4]
events_popped: [3,4,2,1]

Both events_pushed and events_popped listed above represent the actual sequence of events; your solution method returns true in this case.

EXAMPLES

Input: events_pushed = [2,1,3], events_popped = [3,2,1]

Output: false

Explanation: this is not possible, given that 2 happens before 1 so the events_popped is not the result of the actual event sequence represented in events_pushed: push(2) -> push(1) -> push(3)

Input: events_pushed = [1,2,3], events_popped = [1,2,3]

Output: true

Explanation: this is the result this sequence:

push(1) -> pop(1) -> push(2) -> pop(2) -> push(3) -> pop(3)

Input: events_pushed = [1], events_popped = [1]

Output: true

Explanation: this is the result of this sequence: push(1) -> pop(1)

CONSTRAINTS AND ASSUMPTIONS

• events_pushed.length = events_popped.length; this means that both input stacks have the same number of events.
• events_pushed is a permutation of events_popped in values; this means that both input stacks have the same event numbers but in different order.
• Both stacks’ length > 0 but less than 100.
• No repeated values in either stacks.
• 1 <= events_pushed[i], events_popped[i] < 100

HINTS

• There is no need to modify your input stacks; they can be read-only.
• You may consider using a local stack to keep track of your accounting. Another stack means additional O(n) memory. However if you think you can solve this problem without extra space, I'd love to see it!

Answer 1

import java.util.Stack;
import java.util.Scanner;
public class HomeworkAssignment2_1
{
   public static void main(String[] args) {
   Scanner S=new Scanner(System.in);
      
       System.out.println("Enter the number do you want to push and pop");
       int n=S.nextInt();
      
       int[] events_pushed=new int[n];
       int[] events_popped=new int[n];
      
       System.out.println("Enter the push values");
       for(int i=0;i<n;i++)
       events_pushed[i]=S.nextInt();
          
       System.out.println("Enter the pop values");
       for(int i=0;i<n;i++)
       events_popped[i]=S.nextInt();
  
       Solution s=new Solution();
       boolean flag=s.isSameEventSequence(events_pushed, events_popped);
       System.out.print(flag);
   }
}

class Solution {

public boolean isSameEventSequence(int[] events_pushed, int[] events_popped) {
Stack<Integer> s=new Stack<Integer>();
int j=0;
for(int i=0;i<events_pushed.length;i++)
{
s.push(events_pushed[i]);
if(events_pushed[i]==events_popped[j])
{s.pop();
j++;
}
}

int i=s.size()-1;
while(i>=0&&j<events_popped.length)
{
if(s.get(i)==events_popped[j])
s.pop();
else
break;
i--;
j++;
}
if(s.isEmpty())
return true;
  
return false;
}
}