Tags: c++ questions, algorithm, |
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: algorithm, questions, answers, c++ questions |
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: tech leader, c++ questions |
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