Stack Queue Algorithm Questions

Algorithm Questions - Series 2

Stack/Queue Algorithm Questions

Balanced--symbol checker
1. Read the symbol until EOF.
2a. If the symbol is an opening symbol, put it into the stack.
2b. If it is a closing symbol:
    i. If the stack is empty, report error.
    ii. Otherwise, pop the stack, if it's not the corresponding closing symbol, report an error.
3. At the end, if there is still element in the stack, report an error.
Postfix notation
In a postfix expression, an operator always follows its operands. Brackets and parentheses are unnecessary; we can simply traverse it and compute the result.
The algorithm for evaluating any postfix expression:
* While there are input tokens left
  o Read the next token from input.
  o If the token is a value
        + Push it onto the stack.
  o Otherwise, the token is an operator (operator here includes both operators, and functions).
        + It is known a priori that the operator takes n arguments.
        + If there are fewer than n values on the stack
              # (Error) The user has not input sufficient values in the expression.
        + Else, Pop the top n values from the stack.
        + Evaluate the operator, with the values as arguments.
        + Push the returned results, if any, back onto the stack.
* If there is only one value in the stack
  o That value is the result of the calculation.
* If there are more values in the stack
  o (Error) The user input has too many values.
Infix to postfix conversion
Read the token of infix expression
If it is operand, immediately output it.
If it is open parenthesis, put it to stack.
If close parenthesis, pop back symbols until an open parenthesis appears.
If operator, pop all symbols until a symbol of lower precedence or a right-associative symbol of equal precedence appears, then push the operator.
At the end, pop all remaining stack symbols.
Q. How to use array or list to implement a stack/queue.
Q. Use a single array to implement three stacks
1. Divide the array in three equal parts and allow the individual stack to grow in that limited space.
Q. Design a stack which, in addition to push and pop, also has a function min which returns the minimum element?
Use an additional stack which keeps track of the mins.
 public void push(int value){  
  if (value <= min()) { s2.push(value); }  
  super.push(value);  
 }  
 public Integer pop() {  
  int value = super.pop();  
  if (value == min()) { s2.pop(); }  
  return value;  
 }  
Q. Implement a data structure SetOfStacks, which should be composed of several stacks, and should create a new stack once the previous one exceeds capacity.
Implement a function popAt(int index) which performs a pop operation on a specifc sub-stack
class SetOfStacks
{ ArrayList stacks = new ArrayList();}
Push operates on the last stack, if the last stack is at capacity, we need to create a new stack.
Pop also operate on the last stack, If the last stack is empty (after popping), then we should remove it from the list of stacks.
Q. Implement a queue using two stacks
S1 will be ordered with the newest elements on the top, while s2 will have the oldest elements on the top.
We push the new elements onto s1, and peek and pop from s2. When s2 is empty, we’ll transfer all the elements from s1 onto s2, in reverse order
Q. sorts a stack in ascending order.
Method signature: Stack sort(Stack s).
 public static Stack<Integer> sort(Stack<Integer> s) {  
  Stack<Integer> r = new Stack<Integer>();  
  while(!s.isEmpty()) {  
   int tmp = s.pop();  
   while(!r.isEmpty() && r.peek() > tmp) {  
    s.push(r.pop());  
   }  
   r.push(tmp);  
  }  
  return r;  
 }  

Resources
Post a Comment

Labels

Java (159) Lucene-Solr (110) All (60) Interview (59) J2SE (53) Algorithm (37) Eclipse (35) Soft Skills (35) Code Example (31) Linux (26) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (15) Defects (14) Text Mining (14) J2EE (13) Network (13) PowerShell (11) Chrome (9) Continuous Integration (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Design (8) Dynamic Languages (8) Http Client (8) Maven (8) Security (8) Trouble Shooting (8) bat (8) blogger (8) Big Data (7) Google (7) Guava (7) JSON (7) Problem Solving (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) IDE (5) Lesson Learned (5) Miscs (5) Programmer Skills (5) System Design (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) OpenNLP (4) Project Managment (4) Python (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Firefox (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Google Drive (2) Gson (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Bit Operation (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Troubleshooting (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts