Tags: , , | Posted by Admin on 5/16/2010 11:19 PM | Comments (0)
Question Come out with an algorithm for getting the column number provided the column name in a excel sheet and vice versa. Excel has a naming convention of A,B..Z,AA,AB,AC..ZZ,AAA… This had to be converted to the column numbers. A will be 1 and AA will 27.. Also the algorithm to find the name provided column number.   Answer #include <string> #include <iostream> using namespace std; int ExcelColNum (char *name) {     int s = 0;     for (int i=strlen(name)-1, e=1; i>=0; –i, e*=26) {         s += e*(name[i]-’A'+1);     }     return s; } string ExcelColName (int num) {     string name;     for ( ; num; num/=26) {         name.insert (name.begin(), ‘A’+(num-1)%26);     }     return name; } int main(void) {     cout << "AAA ==> " << ExcelColNum ("AAA") << endl;     cout << "703 ==> " << ExcelColName (703) << endl;     return 0; }   Results are, AAA ==> 703 703 ==> AAA
Tags: , , , | Posted by Admin on 7/29/2008 12:59 AM | Comments (0)
1. Reverse a singly linked list // // iterative version // Node* ReverseList( Node ** List ) { Node *temp1 = *List; Node * temp2 = NULL; Node * temp3 = NULL; while ( temp1 ) { *List = temp1; //set the head to last node temp2= temp1->pNext; // save the next ptr in temp2 temp1->pNext = temp3; // change next to privous temp3 = temp1; temp1 = temp2; } return *List; } 2. Delete a node in double linked list void deleteNode(node *n) { node *np = n->prev; node *nn = n->next; np->next = n->next; nn->prev = n->prev; delete n; } 3. Sort a linked list //sorting in descending order struct node { int value; node* NEXT; } //Assume HEAD pointer denotes the first element in the //linked list // only change the values…don’t have to change the //pointers Sort( Node *Head) { node* first,second,temp; first= Head; while(first!=null) { second=first->NEXT; while(second!=null) { if(first->value < second->value) { temp = new node(); temp->value=first->value; first->value=second->value; second->value=temp->value; delete temp; } second=second->NEXT; } first=first->NEXT; } } 4. Reverse a string void ReverseString (char *String) { char *Begin = String; char *End = String + strlen(String) - 1; char TempChar = '\0'; while (Begin < End) { TempChar = *Begin; *Begin = *End; *End = TempChar; Begin++; End--; } } 5. Insert a node a sorted linked list void sortedInsert(Node * head, Node* newNode) { Node *current = head; // traverse the list until you find item bigger the // new node value // while (current!= NULL && current->data < newNode->data) { current = current->next); } // // insert the new node before the big item // newNode->next = current->next; current = newNode; } 6. Covert a string to upper case void ToUpper(char * S) { while (*S!=0) { *S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S; S++; } } 7. Multiple a number by 7 without using * and + operator. NewNum = Num << 3; // mulitplied by 2 ^ 3 = 8 NewNum = NewNum - Num; // 8 – 1 = 7 8. 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. #include int strtoint(char *s) { int index = 0, flag = 0; while( *(s+index) != '\0') { if( (*(s + index) >= '0') && *(s + index) <= '9') { flag = 1; index++; } else { flag = 0; break; } } if( flag == 1 ) return atoi(s); else return 0; } main() { printf("%d",strtoint("0123")); printf("\n%d",strtoint("0123ii")); } 9. Print a data from a binary tree – In-order(ascending) // // recursive version // Void PrintTree ( struct * node node ) { if ( node == NULL ) return; PrintTree(node->left ); Printf(“%d”, node->data); PrintTree(node->right ); } 10. print integer using only putchar // // recursive version // void PrintNum ( int Num ) { if ( Num == 0 ) return; PrintNum ( Num / 10 ); Puthcar ( ‘0’+ Num % 10 ); } 11. Find the factorial of number // // recursive version // int Factorial( int Num ) { If ( num > 0 ) return Num * Factorial ( Num –1 ); else return 1; } // // iterative version // int Factorial( int Num ) { int I int result = 1; for ( I= Num; I > 0; I-- ) { result = result * I; } return result; } 12. Generate Fib numbers: int fib( n ) // recursive version { if ( n < 2 ) return 1; else return fib ( n –1 ) + fib ( n –2 ); } int fib( n ) //iterative version { int f1 =1, f2 = 1; if ( n < 2 ) return 1; for ( i = 1; i < N; i++) { f = f1 + f2; f1= f2; f = f1; } return f; } 13. Write a function that finds the last instance of a character in a string char *lastchar(char *String, char ch) { char *pStr = NULL; // traverse the entire string while( * String ++ != NULL ) { if( *String == ch ) pStr = String; } return pStr; } 14. Return Nth the node from the end of the linked list in one pass. Node * GetNthNode ( Node* Head , int NthNode ) { Node * pNthNode = NULL; Node * pTempNode = NULL; int nCurrentElement = 0; for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->pNext ) { nCurrentElement++; if ( nCurrentElement - NthNode == 0 ) { pNthNode = Head; } else if ( nCurrentElement - NthNode > 0) { pNthNode = pNthNode ->pNext; } } if (pNthNode ) { return pNthNode; } else return NULL; } 15. Counting set bits in a number. First version: int CoutSetBits(int Num) { for(int count=0; Num; Num >>= 1) { if (Num & 1) count++; } return count; } Optimized version: int CoutSetBits(int Num) { for(int count =0; Num; count++) { Num &= Num -1; } }
Tags: , | Posted by Admin on 1/10/2005 12:18 PM | Comments (64)
A web-friend of mine just interviewed for a tech lead position at Google. Here’s a (slightly tidied up and anonymized) version of their experiences: Most of my work, at least at the start, should be in “production software”–googlese for the software that helps keep Google’s amazingly huge distributed system running smoothly and seamlessly, and is mostly Python though with ample helpings of C++ here and there and a little bit of Java where integration is needed with some Java-centric application server (e.g. to serve google-ads on sites using such servers). Plenty of “sideshows” doing such things as statistical analysis and data mining on the huge wealth of data Google collects, maybe giving [name deleted]’s team a hand in data-quality assurance, etc, etc. Plus, every Google techie is supposed to use 20% of his time working on his or her own pet projects which might become Google’s Next Big Thing—that’s how gmail was born. The selection process is grueling—multiple rounds of phone interviews where they ask you (depending on the fields of expertise you claim) everything from what’s 210, to how you would tweak bits in C to find out if a machine’s stack grows up or down in memory, all the way to having you “program on the phone”… then all of a sudden they rush you to Silicon Valley and you get a long full day of nonstop interviewing. I didn’t quite ace mine because I hadn’t thought of cramming on TCP/IP fundamentals, so I didn’t remember which bits are on in the three packets of the handshake (it’s SYN, SYN+ACK, ACK—I could have worked it out, but not jetlagged and after about 6 hours’ interviews ;-). I made up for that when they had me program at the whiteboard a C++ implementation of unbounded precision multiplication; I did a test-driven implementation of the trivial routine with std::vector<digit> containers, then did some handwaving about the Karatsuba algorithm (far too hard to implement standing up at a whiteboard, of course and could sense I had struck lucky… The guy interviewing me at that time had never really done unbounded precision computation work (at least not implementation of high-quality libraries for it), so by just opening the door a crack to the huge and mathematics that underlies that field (in which I had the good fortune to dabble a bit — a byproduct of my interests in combinatorial arithmetic) I had apparently exceeded expectations. Lots of back-of-envelope computation and the like, too. A friend of mine thought he was doing well in his second Google phone interview when asked to sketch a way to compute bigram statistics for a corpus of a hundred million documents—he had started discussing std::map<std::string> and the like, and didn’t get why the interviewer seemed distinctly unimpressed, until I pointed out even if documents are only a couple thousand words each, where are you going to STORE those two hundred billion words—in memory?! That’s a job for an enterprise-scale database engine! So, at least as far as the interviewing process goes, it seems designed for people with a vast array of interests related to programming, computation, modeling, data processing, networking, and good problem-rough-sizing abilities—I guess Google routinely faces problems that may not be hugely complex but are made so by the sheer scale involved. I can just hope the actual day-to-day work is as interesting, fascinating and challenging as the interviews were—but from all I hear, it probably is. And they have bar-quality espresso machines in rest areas… Original story