etaCarinae
BAN USER
Resume
Comments (4)
Reputation 15
If you want to think complex, think simple!
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2
of 2 vote
A Solution in Objective C:
PS:
Node/DLL Structure: ...Node < prev.(Node).next > Node...
 (Node *)copyDLL:(Node *)p {
if (!p) {
return nil;
}
Node *clone = new Node;
clone.val = p.val;
clone.next = [self copyDLLNext:p.next];
if (clone.next) {
clone.next.prev = clone;
}
clone.prev = [self copyDLLPrev:p.prev];
if (clone.prev) {
clone.prev.next = clone;
}
return clone;
}
 (Node *)copyDLLNext:(Node *)p {
if (!p) {
return nil;
}
Node *clone = new Node;
clone.val = p.val;
clone.next = [self copyDLLNext:p.next];
if (clone.next) {
clone.next.prev = clone;
}
return clone;
}
 (Node *)copyDLLPrev:(Node *)p {
if (!p) {
return nil;
}
Node *clone = new Node;
clone.val = p.val;
clone.prev = [self copyDLLPrev:p.prev];
if (clone.prev) {
clone.prev.next = clone;
}
return clone;
}

etaCarinae
September 02, 2014 Comment hidden because of low score. Click to expand.
0
of 2 vote
I think the solution is still possible by binary search
Step 1. Do a binary search type traversal to determine the array index where the rotation has happened (just a bit tricky).
Step 2. Compare the key with the value at the index of rotation. This indicates in which half we would find the key. Do a binary search in that half to find the index of that key.
Complexity: O(log n)
Comment hidden because of low score. Click to expand.
1
of 1 vote
This may not be a google question, nevertheless it was interesting to solve.
The following is a solution in O(1) space and O(N) time
and maintaining the order of entries :
int nextPos(int *list, int size) {
static int np = 1;
static int next = 1;
int retVal = 1;
if (np == 1) {
// initialize
np = 0;
while (np < size && list[np] < 0) {
np++;
}
if (np < size) {
next = list[np];
}
}
retVal = next;
np++;
while (np < size && list[np] < 0) {
np++;
}
next = (np < size) ? list[np] : 1;
return retVal;
}
int nextNeg(int *list, int size) {
static int nn = 1;
static int next = 1;
int retVal = 1;
if (nn == 1) {
// initialize
nn = 0;
while (nn < size && list[nn] >= 0) {
nn++;
}
if (nn < size) {
next = list[nn];
}
}
retVal = next;
nn++;
while (nn < size && list[nn] >= 0) {
nn++;
}
next = (nn < size) ? list[nn]: 1;
return retVal;
}
void makeAlternate(int *list, const NSUInteger size) {
// int list[] = {1, 2, 3, 4, 1, 4};
// int size = 6;
if (size < 1  !list) {
return;
}
int np = nextPos(list, size);
int nn = nextNeg(list, size);
int pos = 0;
bool fillPos = (list[pos] < 0);
if (!fillPos) {
np = nextPos(list, size);
} else {
nn = nextNeg(list, size);
}
pos++;
while (pos < size && np != 1 && nn != 1) {
if (fillPos) {
list[pos] = np;
np = nextPos(list, size);
} else {
list[pos] = nn;
nn = nextNeg(list, size);
}
pos++;
fillPos = !fillPos;
}
// either arr finished or all negative or all positive
if (pos < size) {
if (nn == 1) {
while (pos < size) {
list[pos++] = np;
np = nextPos(list, size);
}
} else {
while (pos < size) {
list[pos++] = nn;
nn = nextNeg(list, size);
}
}
}
// print the arr
for (int i = 0; i < size; i++) {
printf("%i, ", list[i]);
}
}

etaCarinae
September 02, 2014 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Assuming there aren't duplicate values or the two integers provided don't repeat,
 etaCarinae November 06, 2016Carry out a DFS over the tree, and
 when you find the one of the two values, store the stack.
 continue the DFS search
 when you find the next value, store the stack.
 terminate the search.
 Reverse the two stacks
 keep popping both the stacks until both of them have identical nodes.
 stop when the nodes in the stack differ.
The recent most popped node or nil is the answer.