etaCarinae
BAN USERIf you want to think complex, think simple!
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;
}
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)
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]);
}
}
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.