Platform Independent Solution

Please see Syllabus for more information.

Your solution has to be platform-independent; it must run on any platforms including any online IDEs:

You solution should be free of any use of packages. Example, absolutely no

/* Java Program Example - Java Import Packages */ package YOUR_CUSTOM_PACKAGE HERE;

Your solution, regardless of how many classes it has, should be in one .java file.

Your solution has to run on any online IDEs.

If your solution fails the platform-independence criteria, you will have to resubmit work subject to the late penalty.

Your solution should be reusable, meaning it will be invoked and validated against a series of input sequentially to produce consistent outcomes like so:

Solution sol = new Solution(); sol.your_function(test_input_1...); sol.your_function(test_input_2 ...);

Backtracking (https://en.wikipedia.org/wiki/Backtracking Links to an external site.) 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 Sequence

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 integer arrays, 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.

Starter Code

import java.util.Stack; public class HW2_1 { public static void main(String[] args) { // just like any problems, whatever you need here, etc. } } // FILL OUT THE FOLLOWING API TEMPLATE, WHICH FOLLOWS THE // PURPOSE/PARAMETERS/RETURN VALUES STYLE PER THE SYLLABUS. /** * PURPOSE: * PARAMETERS: * RETURN VALUES: */ class Solution { 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.

No repeated values in either stacks.

Both stacks length > 0 but less than 100, namely, 1 <= events_pushed[i], events_popped[i] < 100.

For this problem, pop() will not be called on an empty Stack which means you won't have to handle EmptyStackException. Error handling is not required for this course.

Hints

You may import java.util.Stack; or build your own Stack from scratch; the choice is yours.

You may also import other data structures (as long as they are a part of the standard java.util libraries) of your choice if you wish to solve your problem that way.

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!