Kaidul Islam
BAN USER
Comments (8)
Reputation 100
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 3 vote
The wildcard positions have to be filled with all possible combination of 0 and 1. This can be done by backtracking but the best way is to check all numbers from 0 to 2^(total wildcard)  1 and set 0 or 1 by checking its bit pattern.
Complexity is O(2^n) in worst case.
vector<string> wildcardFillUp(string bitStream) {
vector<string> result;
vector<int> positions;
int cnt = 0;
int len = bitStream.length();
for(int i = 0; i < len; ++i) {
if(bitStream[i] == '?') {
positions.push_back(i);
++cnt;
}
}
int n = (1 << cnt)  1;
for(int i = 0; i <= n; ++i) {
for(int idx = 0, k = cnt  1; k >= 0; k) {
bool isSet = (bool) (i & (1 << k));
bitStream[positions[idx++]] = isSet ? '1' : '0';
}
result.push_back(bitStream);
}
return result;
}

Kaidul Islam
May 08, 2015 Comment hidden because of low score. Click to expand.
0
of 0 vote
Hi Felipe,
Thanks for your trial. your inserted tree is not a BST. if 10 is a root, 9 can't be its right child. Right child has to be greater than root.
Comment hidden because of low score. Click to expand.
0
of 0 vote
simple and nice solution!
 Kaidul Islam May 05, 2015Comment hidden because of low score. Click to expand.
2
of 2 vote
Use Morris Traversal. The idea is 
1. Initialize root as current
2. while current is not NULL
a) if current has no left child
 print current and set current = current.right
b) else
 set current as rightmost node of left child
Source Code:
void inorderWithConstantSpace(TreeNode *root) {
if(!root) return root;
TreeNode *current = root;
while(current) {
if(current>left) {
TreeNode *leftChild = current>left;
TreeNode *tmp = leftChild;
TreeNode *rightMost;
while(leftChild) {
rightMost = leftChild;
leftChild = leftChild>right;
}
rightMost>right = current;
current>left = nullptr;
current = tmp;
} else {
printf("%d ", current>value);
current = current>right;
}
}
}

Kaidul Islam
May 05, 2015 Comment hidden because of low score. Click to expand.
0
of 0 vote
double findKth(int A[], int m, int B[], int n, int k) {
if (m > n) return findKth(B, n, A, m, k);
if (m == 0) return B[k  1];
if (k == 1) return min(A[0], B[0]);
int aMid = min(k / 2, m);
int bMid = k  aMid;
if (A[aMid  1] <= B[bMid  1]) {
return findKth(A + aMid, m  aMid, B, n, k  aMid);
}
return findKth(A, m, B + bMid, n  bMid, k  bMid);
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m + n;
if(total & 1) return findKth(A, m, B, n, total / 2 + 1);
return (findKth(A, m, B, n, total / 2);
}
The overall time complexity is
O(log(n + n))
which is
O(logn)
.
 Kaidul Islam October 14, 2014Comment hidden because of low score. Click to expand.
0
of 0 vote
string encodedString(string input) {
int n = input.length();
if(n < 2) return input;
char prev = input[0];
int count = 1;
string result = "";
for(int i = 1; i < n; ++i) {
if(input[i] == prev) {
++count;
} else {
result = result + prev;
if(count > 1) result = result + (char)(count + 48);
prev = input[i];
count = 1;
}
}
result = result + prev;
if(count > 1) result = result + (char)(count + 48);
return result;
}

Kaidul Islam
October 14, 2014 Comment hidden because of low score. Click to expand.
6
of 8 vote
bool isPlaindrome(string str) {
int n = str.length();
for(int i = 0, j = n  1; i < j; ++i, j) {
if(str[i] != str[j]) return false;
}
return true;
}

Kaidul Islam
October 14, 2014 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
 Kaidul Islam October 07, 2017