Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 vote

I've considered this problem more today and I think it's even more simple than what I had originally explained.

We will keep one stack, call it s. We first begin by pushing a "1" onto s.

Now, we will start reading the string from the end to the beginning. If we encounter a number, we will multiply this number with the number currently on top of the stack and then push this product onto the stack. When we encounter a close parenthesis ")", we will copy whats on the stack and push on top of the stack. When we encounter an open parenthesis "(", we will pop whatever is on the stack. Finally, when we encounter an element, the number that is currently on top of the stack will be the number of atoms of that element is described by that specific portion of the string.

- Skor March 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution is not clear, can you elaborate with an example.

- anon March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

Hey anon, let's consider the following:

A2((AB3)2(C2D)4)5

First, we know that this is equivalent to:

A2((A1B3)2(C2D1)4)5, so let's work from this one for ease of the algorithm.

Stack: 1

We start out with this.

Now, we begin from the right. We will push a (1 * 5) onto the stack. We do this because we know that whatever is to the left of the 5, there will be 5 of it. We encounter a ")" which means that this multiple will affect everything within some parenthesis, so we won't pop it just yet.

Stack : 1/5

Next, we encounter a 4. We know that whatever is left of the 4 will be multiplied by 4, but also , since we have a 5 on top of the stack, multiplied by 5 because of the outside multiple.

Stack: 1/5/20

We encounter a ")" which means to continue since this multiple will apply to whatever is in the parenthesis.

Encounter a 1, so push (20 * 1) on the stack.

Stack: 1/5/20/20

Now, we encounter our first Element (D), and we know that there will be 20 Ds so far. So in our list of Elements, add 20 to D. Since we encountered an element, we can pop off the stack

Stack : 1/5/20


Encounter a 2, so push (2*20) on the stack.

Stack: 1/5/20/40

Now, we see we have Element C, so add 40 to C in the list and pop off the stack:

Stack : 1/5/20

Since we encounter an open parenthesis "(", we pop off the stack signaling that we are done with an encounter of some in parenthesis expression:

Stack : 1/5

Now, we begin on a new parenthesis set, which is succeeded by a "2":

Stack : 1/5/10

Push (3*10),

Stack : 1/5/10/30

Add 30 to B

Pop 30

Stack : 1/5/10

Push(1 * 10)

Stack : 1/5/10/10

Add 10 to A

Pop 10

Stack : 1/5/10

Encounter a "(", pop 10

Stack : 1/5

Encounter another "(", pop 5

Stack : 1

We see a 2, so push (2*1)

Stack : 1/2

Add 2 to A, pop off 2

Stack : 1

We are done.

- SK March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Final List should look like:

A: 12
B: 30
C: 40
D: 20

Then you can organize however it needs to be empirically

- Skor March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include <cstdio>
#include <iostream>
#include <stack>
#include <cctype>
#include <cstdlib>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
#include <cassert>
#define INF INT_MAX
#define NIL -1
#define PR(A) cout<<endl<<#A<<" = "<<A<<endl;
#define INF INT_MAX
using namespace std;
typedef vector<vector<int>> matrix;
typedef vector<int> arr;
typedef unsigned int ui;
vector<vector<int>> & make_matrix(int m,int n,int r=0){
    vector<vector<int>>&q=*(new vector<vector<int>>);
    q.resize(m);
    for(auto &i:q){
        i.resize(n);
        fill(i.begin(),i.end(),r);
    }//edn fr
    return q;
}//end vector
void printarr(arr &a,int low=0,int high=INT_MAX){
    if(high==INT_MAX){
        high=a.size()-1;
    }//END IF
    cout<<endl;
    for(int i=low;i<=high;i++){
        cout<<a[i]<<' ';
    }//end for
}//end [rint
void printmatrix(matrix &a){
    for(auto i:a){
        cout<<endl;
        for(auto j:i){
            cout<<j<<" ";
        }//end for
    }//end for
}//end [rint
void func(string &s){
    stack<int>q;
    q.push(1);
    int i=s.length()-1;
    vector<int>count(256,0);
    while(i>=0){
        if(s[i]=='('){
            q.pop();
            i--;
        }//end if
        else if(s[i]==' ')
                i--;
        else if(isdigit(s[i])){
                int k=1;
                int num=0;
                while(i>=0 && isdigit(s[i])){

                        num=num+(k*(s[i]-'0'));
                        i--;
                }//end while
                while(i>=0 && s[i]==' ')
                    i--;
                if(isalpha(s[i])){
                        count[s[i]]+=num*q.top();
                        i--;
                }//end if
                else{
                    q.push(num*q.top());
                    i--;
                }//end else
        }//end else if
        else if(isalpha(s[i])){
                count[s[i]]+=q.top();
                i--;
        }//end else if
    }//end while
    for(int i=0;i<count.size();i++){
            if(count[i]){
                    cout<<char(i)<<count[i];
            }//end for
    }//end for
}//end func
int main(){
string s="A2((AB3)2(C2D)4)5";
func(s);
   return 0;
}

- Klaus July 19, 2015 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More