匿名网友
Q: All-time Most-Popular-Question: How to reverse a single link list? (Most companies ask!)
A: At least 2 popular/elegant ways to do this without using additional memory:
Non-Recursive & Recursive.
Tell me what’s the disadvantage of recursion? It’s damn expensive, be aware of stack overflow if the list is long.
// Non-Recursively (Most interviewers expect this sort of answer!)
Node *p = head; // h points to head of the linklist.
If( p == NULL)
return NULL;
link *h; //C++ style C programming
h = p;
if(p->next)
p = p->next;
h->next = NULL; // h is now an isolated node which will be the tail node eventually
while( p != NULL) {
link *t = p->next; //tmp node.
p->next = h;
h = p;
p = t;
}
return h; //h points to the new Head.
//-END-
// Recursively, In case you forgot.
reverse_ll(struct node ** hashref) {
struct node * first, last;
if(*hashref == NULL) return -1;
first = *hashref;
rest = first->next;
if(rest == NULL) return;
reverse_ll(&rest);
first->next->next = first; //reversion happens.
first->next = NULL;
} //-END-
Collateral Questions: Why recursion is evil?
A: Potential of Stack overflow for extensively nested recursions.
Q: How to print a link list reversely? (NetScreen, Netli, Yahoo!)
A: If Recursively:
rev_ll (Node *h) {
If(!h) return(-1) ;
else { rev_ll(h->next); print(h->data);}
}
If Non-Recursively:
Same as last Q/A: reverse the link-list then print out from the new head. Complexity: O(2*N)
//Similar question: How to reverse a string? Complexity O(N/2); exchange firstlast, 2nd2nd-to-the-last, etc…
Q: How to reverse doubly-linked list? (Akamai onsite San Mateo, CA)
A: // Basically, double linklist is easier to reverse, the only 2 things need to do are:
// tail head exchange; prev next exchange;
Node *PCurrent = pHead, *pTemp;
While(pCurrent) {
pTemp = pCurrent->next;
pCurrent->next = pCurrent->prev;
pCurrent->prev = pTemp;
pHead = pCurrent;
pCurrent = pTemp;
}
// pHead will point to the newly reversed head of the double link-list
// -END-
Q: How to insert a node into an ASCENDly sorted double link list? (Infoblox onsite)
A: // Note: the following code concerns all boundary conditions!!!
Assume we have a struct:
Struct Node {
Int data;
Node * prev;
Node *next;
};
//pHead, pCur, nn (new node), ppCur (pre-pCur)
if(pHead == NULL) return(0);
pCur = pHead;
while(pCur) {
if(pCur != pHead) {
ppCur = pCur->prev; //keep track of prev node.
}
if(pCur->data >= nn->data) {
if(pCur == pHead) { // insert at the head
pHead = nn;
nn->prev = NULL;
nn->next = pCur;
pCur->prev = nn;
} else { // insert at non head.
If(pCur->next == NULL) { // insert at the tail.
nn->next = NULL;
pCur->next = nn;
nn->prev = pCur;
} else { // insert somewhere in the middle.
nn->next = pCur;
pCur->prev = nn;
ppCur->next = nn;
nn->prev = ppCur;
}
return(pHead); // return head of double-linklist.
}
} else { // keep going!
pCur = pCur->next;
}
} // end of while()
Q: How to find a loop in a linked list (single link-list)/ Yahoo! Favorite onsite question.
A:
Node *p1, *p2, *head;
p1 = p2 = head;
do {
p1 = p1->next;
p2 = p2->next->next;
} while ( p1 != p2 && p1->next != NULL && p2->next != NULL && p2->next->next != NULL )
if ( p1->next == NULL || p2->next == NULL || p2->next->next == NULL) {
printf(“None loop found!n”;
} else if ( p1 == p2 && p1 != NULL ) {
printf(“Loop found!n”;
} // -END-
//Story Telling: A Yahoo! Director ever asked this question and he challenged me with this scenario: What if p1 and p2 fall into an endlessly looping hole? This imagined scenario/dilemma will NEVER happen as a simple reply! Don’t be afraid to stand off. This also propelled me to think what made one a Technical/Engineering Director? Stupidness, Arrogance or Ignorance? Maybe all.
Q: Print UNIQUE Array Element (PayPal onsite interview question) ？？？？
A: // Assume it’s a char * array
char * unique_array(char *s, int size)
{
int i = 1, c = 1;
for(c=1; c<=size; ++c) {
if (s[c] != s[i-1]) { s[i] = s[c]; i++; }
}
s[i] = ‘ ’; //NULL terminate the string!
return(s);
} //-END-
Q: Filter out matching char in a char * array
A: //
char * filter_array(char *s, int size, char tgt) {
int i = 0, c;
for(c = 0; c<size; c++) {
if(s[c] != tgt) { s[i] = s[c]; i++; }
}
s[i] = ‘ ’;
return(s);
} –END-
Q: Implement your atoi()
A: // char *a int i;
Int len = strlen(a);
Int i = 0, j = 0, sign = 2; // 2 stands for ‘+’
If (a[0] == ‘-‘) {
sign = 1;
++j;
} else if(a[0] == ‘+’ ) {
sign = 2;
++j;
}
++j;
while(j < len) {
i = 10 * i + (a[j] – 48); // 48 = 0x30 which is ASCII ‘0’
++j;
}
//-END-
//NOTE: a-z: 0x41-5a(65-90); A-Z: 0x61-7a(97-122)
Q: Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value.
A:
int str2int(const char *str)
{
int value = 0;
int sign = (str[0] == ‘-‘)?-1:1; // decide sign
int i = (str[0] == ‘-‘)?1:0; // decide starting index
char ch;
while(ch = str[i++])
{
if ((ch >= ‘0’)&&(ch <= ‘9’))
value = value*10 + (ch – ‘0’);
else
return 0; // non-integer
}
return value*sign;
} /* end of str2int()
Q: Implement your itoa() ?
A:
Solution 1: sprintf(s, “%d”, i);
Solution 2: Convert every digit to ASCII naturally and dump to char * array. Or just putchar() recursively.
Q:Print an integer using only putchar. Try doing it without using extra storage.
A: // recusion is one way. (since integer is only 16 or 32 or 64 bits long)
void putlong(long ln)
{
if (ln == 0) return;
if (ln < 0) {
putchar(‘-‘); // print – sign first
putlong(abs(ln)); // print as positive number
return;
}
putlong(ln/10); // print higher digits,
putchar(‘0’ + ln%10); // print last digit(mod), ‘0’ + will convert to ASCII printable char.
} // end of putlong()
