7 MAY
GENERATING PARENTHESES
Given an integer N representing the number of pairs of parentheses, the task is to generate all combinations of well-formed(balanced) parentheses.
void addParenthesis(vector<string>& v, string str, int left, int right){
if(left == 0 && right == 0){
v.push_back(str);
return;
}
if(right > 0)
addParenthesis(v, str+")", left, right-1);
if(left > 0)
addParenthesis(v, str+"(", left-1, right+1);
}
vector<string> AllParenthesis(int n)
{
vector<string>res;
if(n > 0){
addParenthesis(res,"", n, 0);
}
return res;
}
8 MAY
FLATTENING A LINKED LIST
Given a Linked List of size N, where every node represents a sub-linked-list and contains two pointers:
(i) a next pointer to the next node,
(ii) a bottom pointer to a linked list where this node is head.
Each of the sub-linked-list is in sorted order.
Flatten the Link List such that all the nodes appear in a single level while maintaining the sorted order.
Node* merge(Node *a, Node *b){
if(a == NULL)
return b;
if(b == NULL)
return a;
Node *res;
if(a->data < b->data){
res = a;
res->bottom = merge(a->bottom, b);
}
else{
res = b;
res->bottom = merge(a, b->bottom);
}
res->next = NULL;
return res;
}
Node *flatten(Node *root)
{
if(root == NULL || root->next == NULL)
return root;
return merge(root, flatten(root->next));
}
9 MAY
REMOVE K DIGITS
Given a non-negative integer S represented as a string, remove K digits from the number so that the new number is the smallest possible.
void buildLowestRec(string S, int K, string& res){
if(K == 0){
res.append(S);
return;
}
int len = S.length();
if(len <= K){
return;
}
int minIndex = 0;
for(int i = 1; i <= K; i++){
if(S[i] < S[minIndex])
minIndex = i;
}
res.push_back(S[minIndex]);
string new_str = S.substr(minIndex+1, len-minIndex);
buildLowestRec(new_str, K-minIndex, res);
}
string removeKdigits(string S, int K) {
string res = "";
buildLowestRec(S, K, res);
string ans = "";
int flag = 0;
for(int i = 0; i < res.length(); i++){
if(res[i] != '0' || flag == 1){
flag = 1;
ans += res[i];
}
}
if(ans.length() == 0)
return "0";
else
return ans;
}
