CSE Company Interview Questions

PROBLEM : Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for binary tree  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class BSTIterator {     stack<TreeNode *> sta ; public:     BSTIterator(TreeNode *root) {         pushLeft(root) ;     }     /** @return whether we have a next smallest number */     bool hasNext() {         if(sta.empty())             return false ;         return true ;

PROBLEM : Given a postfix expression, the task is to evaluate the expression and print the final value. Input: The first line of input will contains an integer T denoting the no of test cases . Then T test cases follow. Each test case contains an postfix expression. Output: For each test case, evaluate the postfix expression and print the value. Constraints: 1 <= T <= 100 1 <= length of expression <= 100 Example: Input: 2 231*+9- 123+*8- Output: -4 -3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<math.h> #include<stack> #include <string.h> #include <ctype.h> #include <stdlib.h> int Postfix(string str){ int ans=0 ; stack<int> s ; for(int i=0;i<str.length();i++){ if(isdigit(str[i])) s.p

PROBLEM : Given an infix expression. Conver the infix expression to postfix expression. Infix expression:The expression of the form a op b. When an operator is in-between every pair of operands. Postfix expression:The expression of the form a b op. When an operator is followed for every pair of operands. Input: The input contains an infix expression.The expression should contain all characters and ^,*,/,+,-. Output: Output the infix expression to postfix expression. Constraints: 1<=T<=100 1<=length of expression<=30 Example: Input: 2 a+b*(c^d-e)^(f+g*h)-i A*(B+C)/D Output: abcd^e-fgh*+^*+i- ABC+*D/ -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<stack> bool isChar(char ch){ if((ch>='a'&&ch<='z')||(ch>=

PROBLEM : An string of words is given, the task is to reverse the string using stack. Input: The first line of input will contains an integer T denoting the no of test cases . Then T test cases follow. Each test case contains a string s of words without spaces. Output: For each test case ,print the reverse of the string in new line. Constraints: 1<=T<=100 1<=length of the string <=100 Example: Input: 2 GeeksQuiz GeeksforGeeks Output: ziuQskeeG skeeGrofskeeG -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- void reverse(char *str, int len) {     stack<char> sta ;     for(int i=0;i<len;i++)         sta.push(str[i]) ;         for(int i=0;i<len;i++){         str[i]=sta.top() ;         sta.pop() ;     } } --------------------------------------------------------------------------------