• @abhishekgwal This problem told you that each number followed by '[', so you will repeat the container inside this '[' number times so for example
if you have "b2[c1[d]] => b2[cd] => bcdbcd. I hope help you in this problem.

• @LavenderViking how is it lg(n)
can you explain in words how your algo is discarding half of the array?

• @abhishekgwal
expand with inner most [ ]

``````a3[b2[c1[d]]]e

expand innermost --> a3[b2[cd]]]e (only 1 number of d )

a3[bcdcd]]]e ( 2 number of cd )

a[bcdcdbcdcdbcdcd]e --> abcdcdbcdcdbcdcde

``````

• I have a solution for the first question, it seems easy but I am not sure my code is a clean code. I would be glad, if any feedback from you to my code. Thanks !

``````    public int missingNumber(int arr[]) {
int i = 1, count = 1;
while (i < arr.length) {
if (arr[i] == arr[i - 1]) count++;
else {
if (count != 3) return arr[i - 1];
else {
count = 1;
}
}
i++;
}
return count != 3 ? arr[arr.length - 1] : -1;
}
``````

• This post is deleted!

• @varun44 for the first problem, can we do two xor passes? The first is to get all of the non doubles. After the first pass, we would get 12346. Then, we do a second pass xor to find the missing number (an existing leetcode question).

• Fundamentally, to get a divide and conquer solution, we need to build some expectation of what the string is at some position. If we haven't removed a number on the left half, then when we check the middle, it will match our expectation, and if we have removed a number, it won't. This allows us to divide and conquer.

Sorting is more obvious divide and concur solution.

• Why aren't these questions on leetcode? I'm searching for the decompress string one.

• @mccloud35 Probably too many questions on leetcode have been used for interview and it's reasonable to have some new questions.

• question one the sample code:
#include <iostream>
#include <sstream>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<char, int> PAIR;
int cmp(const PAIR& x, const PAIR& y)
{
return x.second < y.second;
}
int main(){
string a = "11122333444";
map<char, int> m;
int count = 1;
int len = a.size();
m.insert({a[0],count});
for(int i =1; i<len; i++){
if(a[i]==a[i-1]){
++m[a[i]];
}else{
m.insert({a[i],count});
}
}
vector<PAIR> aa;
map<char, int>::iterator iter_map;
for (iter_map= m.begin(); iter_map != m.end(); ++iter_map)
{
aa.push_back(make_pair(iter_map->first, iter_map->second));
}
sort(aa.begin(),aa.end(),cmp);
cout<<"missed number is: "<< aa[0].first<<endl;
return 0;

}

• @varun44 how many years experience do you have? What level at Google were your interviews targeting? I believe for L3 they don't do system design but not sure about L4+.

int missingNumber(int arr[])
{
int i=0;
while(i!=arr.length)
{
if((i+2)<arr.length && arr[i]==arr[i+2])
i=i+3;
else
break;
}
return (i>=arr.length?-1:arr[i]);
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.