An Challenging Interview question with a difference

The following program is provided:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>

using namespace std;

//This class can be designed as you wish
class SR
{
public:
SR(int i) {}
};

int main()
{
int sum = 0;
for (int i = 1; i < 100; i++)
{
  SR ii(i);
  while (i--)
    sum += i;
}
cout<<"Expected value of sum = 161700" << endl;
cout<<"Returned value of sum = " << sum << endl;

return 0;
}

As already mentioned above, the expected output of 161700 is provided. The class 'SR' could be written as one wishes. How to do write the class 'SR' to get the desired output?

.

.

.

.

Give it a try before looking at the solution.

.

.

.

.

.

The modified program with the correct 'SR' class as follows:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>

using namespace std;

//This class can be designed as you wish
class SR
{
public:
 SR(int& i):ref(i)
 {
   var = i;
 }
 ~SR()
 {
   ref = var;
 }
private:
 int var;
 int &ref;
};

int main()
{
 int sum = 0;
 for (int i = 1; i < 100; i++)
 {
   SR ii(i);
   while (i--)
     sum += i;
 }
 cout<<"Expected value of sum = 161700" << endl;
 cout<<"Returned value of sum = " << sum << endl;

 return 0;
}

Source: Modified from here. Another similar question is available here.

Swap two variables without using third and in one line

Couple of weeks back I was interviewing a fresh graduate. Even though they are taught programming, I am not sure if they take it seriously and learn or practice it well. One of the questions I asked was to swap 2 numbers without using a temp variable.

Looking back now, I think it may be a bigger challenge to ask to swap numbers without using a temp variable and in one line. Below are my three different approaches but I would advise you to try it yourself before looking at the answer.

//Program to swap 2 numbers without using 3rd variable and in one line
//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>

using namespace std;

void approach1(int& a, int& b)
{
  cout<<"\nApproach 1"<<endl;
  a^=b^=a^=b;
}

void approach2(int& a, int& b)
{
  cout<<"\nApproach 2"<<endl;
  //b=(a+b)-(a=b); - This should work but doesnt, why?
  a =((a = a + b) - (b = a - b)); 
}

void approach3(int& a, int& b)
{
  cout<<"\nApproach 3"<<endl;
  a = ((a = a * b) / (b = a / b));
}



int main()
{
  int a = 13, b = 29;
  cout<<"\nOriginal"<<endl;
  cout<<"a = "<<a<<", b = "<<b<<endl;

  approach1(a, b);
  cout<<"a = "<<a<<", b = "<<b<<endl;

  a = 13, b = 29;
  approach2(a, b);
  cout<<"a = "<<a<<", b = "<<b<<endl;

  a = 13, b = 29;
  approach3(a, b);
  cout<<"a = "<<a<<", b = "<<b<<endl;

  return 0;
}

The output is as follows:

Agreed that the above would be applicable only for integers.

String Shift and Print

After my last blog post, someone pointed out a similar problem here. The problem goes:

Write a program that generates from the string "abcdefghijklmnopqrstuvwxyz{" the following:

a

bcb

cdedc

defgfed

efghihgfe

fghijkjihgf

ghijklmlkjihg

hijklmnonmlkjih

ijklmnopqponmlkji

jklmnopqrsrqponmlkj

klmnopqrstutsrqponmlk

lmnopqrstuvwvutsrqponml

mnopqrstuvwxyxwvutsrqponm

nopqrstuvwxyz{zyxwvutsrqpon

Well there is no time limit this time and we dont even need to use google. I think this is slightly trickier than the last one.

Here is my solution:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy

#include<iostream>
#include<string>

using namespace std;

int main()
{
  string str = "abcdefghijklmnopqrstuvwxyz{";
  unsigned strlen = str.length();
  string tempStr;
  int loop = 0;
  while(tempStr.length() < strlen)
  {
    int start1 = loop;
    int count1 = loop + 1;
    tempStr = str.substr(start1,count1);

    count1--;
    for(; count1 > 0; count1--)
      tempStr.append(str.substr(start1+count1-1, 1));

    cout<<tempStr;
    cout<<endl;
    loop++;
  }
  return 0;
}

ASCII Print

Few weeks back, someone I know got asked the following question in an interview:

Write a C++ program in 15 minutes to print the following in the output:

a

bcb

cdedc

defgfed

efghihgfe

fghijkjihgf

ghijklmlkjihg

hijklmnonmlkjih

ijklmnopqponmlkji

jklmnopqrsrqponmlkj

klmnopqrstutsrqponmlk

lmnopqrstuvwvutsrqponml

mnopqrstuvwxyxwvutsrqponm

nopqrstuvwxyz{zyxwvutsrqpon

You can do search on the web for any information but all your searches would be logged and used to assess your answer.

Well my obvious guess would be to take help of ASCII table. My only search was for Ascii table in google. I did try and make it in less than 15 mins. My solution is below but do try it on your own before looking at my solution.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>
#include<string>

using namespace std;

int main()
{
  char c=(char)97; //'a' in ASCII
  char loop = 0;
  while(c <= 'n')
  {
    char x = 0;
    for(; x <=loop; x++)
    {
      cout<<char(c+x);
    }
    for(char y = 1; y < x; y++)
    {
      cout<<char(c+x-y-1);
    }
    cout<<endl;
    c++;
    loop++;
  }

  return 0;
}

Challenging problem to test your 'for loop' basics

While scouting through the web I came across this fun puzzle:

In the following code:

#include<iostream>

using namespace std;

int main()
{
 int i, n = 20;
 for (i=0; i<n; i--)
 {
   cout << "x" << endl;
 }

 return 0;
}

by changing only ONE character in the above code, meaning you cannot change 20 to 31, because you will have changed two characters, you can change 20 to 21, because you only changed the 0, do the following:

find 3 ways to make the above code print x 20 times (by changing only one character).

Give it a try, if you can do it then look at the answer below.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

The first one should be simple:

i-- becomes n--

.

.

.

.

.

.

.

I guess this is the second one you got

i<n becomes i+n

.

.

.

.

.

.

.

.

.

.

The third one which is tricky, In fact there are two similar solutions is:

i<n becomes, -i<n,
i<n becomes, ~i<n

remember BODMAS

Interesting Challenging problem on Code Complexity

Picked up this interesting problem from the following book:



How many execution paths can this simple three line code take:

String EvaluateSalaryAndReturnName( Employee e )
{
  if( e.Title() == "CEO" || e.Salary() > 100000 )
  {
    cout << e.First() << " " << e.Last() << " is overpaid" << endl;
  }
  return e.First() + " " + e.Last();
}

The answer may surprise you. I have embedded the actual pages from Google books. Luckily the whole problem and solution is given. See Item 18.

The challenging 'Infinite loop' problem

Picked this one up from The C++ blog.

Consider the following program:

#include <iostream>

int main()
{
    int i;
    int array[4];
    for(i=0; i<=8; i++)
    {
        array[i]=0;
    }

  return 0;
}

Most people including myself expect this program to crash. This is not the case. The reason being the way everything is stored on stack. In simple representation, the storage is something like this:



So when i = 6, value of i is reset to 0 and the loop continues forever.

After digging some information on stack, heap, etc. I found some useful info in C++ in 24 hours:

Programmers generally deal with five areas of memory:

• Global name space
• The free store (a.k.a. Heap)
• Registers
• Code space
• The stack

Local variables are on the stack, along with function parameters. Code is in code space, of course, and global variables are in global name space. The registers are used for internal housekeeping functions, such as keeping track of the top of the stack and the instruction pointer. Just about all remaining memory is given over to the free store, which is sometimes referred to as the heap.

The problem with local variables is that they don't persist. When the function returns, the local variables are thrown away. Global variables solve that problem at the cost of unrestricted access throughout the program, which leads to the creation of code that is difficult to understand and maintain. Putting data in the free store solves both of these problems.

You can think of the free store as a massive section of memory in which thousands of sequentially numbered cubbyholes lie waiting for your data. You can't label these cubbyholes, though, as you can with the stack. You must ask for the address of the cubbyhole that you reserve and then stash that address away in a pointer.

The stack is cleaned automatically when a function returns. All the local variables go out of scope, and they are removed from the stack. The free store is not cleaned until your program ends, and it is your responsibility to free any memory that you've reserved when you are done with it.

The advantage to the free store is that the memory you reserve remains available until you explicitly free it. If you reserve memory on the free store while in a function, the memory is still available when the function returns.

The advantage of accessing memory in this way, rather than using global variables, is that only functions with access to the pointer have access to the data. This provides a tightly controlled interface to that data, and it eliminates the problem of one function changing that data in unexpected and unanticipated ways.

For this to work, you must be able to create a pointer to an area on the free store and to pass that pointer among functions. The pointer is created using new and once you are done with it you can free the memory using delete.

The problem with Maps in C++

The following discussion is from More Exceptional C++ By Herb Sutter:

Question 1:
a: What's wrong with the following code? How would you correct it?

map::iterator i = m.find( 13 );
if( i != m.end() )
{
const_cast( i->first ) = 9999999;
}

b: To what extent are the problems fixed by writing the following instead?

map::iterator i = m.find( 13 );
if( i != m.end() )
{
string s = i->second;
m.erase( i );
m.insert( make_pair( 9999999, s ) );
}

Consider a map named m that has the contents shown in Figure; each node within m is shown as a pair. I'm showing the internal structure as a binary tree because this is what all current standard library implementations actually use.

As the keys are inserted, the tree's structure is maintained and balanced such that a normal inorder traversal visits the keys in the usual less ordering. So far, so good.

But now say that, through an iterator, we could arbitrarily change the second entry's key, using code that looks something like the following:

1. a) What's wrong with the following code? How would you correct it?

// Example: Wrong way to change a

// key in a map m.

//

map::iterator i = m.find( 13 );

if( i != m.end() )

{

const_cast( i->first ) = 9999999; // oops!

}

Note that we have to cast away const to get this code to compile. The problem here is that the code interferes with the map's internal representation by changing the map's internals in a way that the map isn't expecting and can't deal with.

Example above corrupts the map's internal structure (see Figure). Now, for example, an iterator traversal will not return the contents of the map in key order, as it should. For example, a search for key 144 will probably fail, even though the key exists in the map. In general, the container is no longer in a consistent or usable state. Note that it is not feasible to require the map to automatically defend itself against such illicit usage, because it can't even detect this kind of change when it occurs. In Example above, the change was made through a reference into the container, without calling any map member functions.

A better, but still insufficient, solution is to follow this discipline: To change a key, remove it and reinsert it. For example:

b) To what extent are the problems fixed by writing the following instead?

// Example: Better way to change a key

// in a map m.

//

map::iterator i = m.find( 13 );

if( i != m.end() )

{

string s = i->second;

m.erase( i );

m.insert( make_pair( 9999999, s ) ); // OK

}

This is better, because it avoids any change to keys, even keys with mutable members that are significant in the ordering. It even works with our specific example. So this must be the solution, right?

Unfortunately, it's still not enough in the general case, because keys can still be changed while they are in the container. "What?" one might ask. "How can keys be changed while they're in the container, if we adopt the discipline of never changing key objects directly?" Here are two counterexamples:

Let's say the Key type has some externally available state that other code can get at—for example, a pointer to a shared buffer that can be modified by other parts of the system without going through the Key object. Let's also say that that externally available state participates in the comparison performed by Compare. Then making a change in the externally available state, even without the knowledge of the Key object and without the knowledge of the code that uses the associative container, can still change the relative ordering of keys. So in this case, even if the code owning the container tries to follow an erase-then-reinsert discipline, a key ordering change can happen at any time somewhere else and therefore without an erase-then-reinsert operation.

Consider a Key type of string and a Compare type that interprets the key as a file name and compares the contents of the files. It's obvious that even if the keys are never changed, the relative ordering of keys can still change if the files are modified by another process, or (if the file is shared on a network) even by a user on a different machine on the other side of the world.

For details see Item 8 of the book More Exceptional C++ By Herb Sutter

A Word and Letter Counter program example

This is a very simple program but people can sometime get lost in writing them. I have not taken into account all the different error scenarios but this program is quite robust.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//In this program we will count the total number of words, letters
//and the frequency of each letter. For simplicity we will end the
//program when enter is pressed.
#include<iostream>

using namespace std;

void wordLetterCounter(int &numWords, int &numLetters, int letterCount[]);

int main()
{
  int numWords = 0, numLetters = 0;
  int letterCount[26]={0}; //each letter count init to 0

  cout<<"\n\nPlease enter some words and finish by pressing enter : ";

  wordLetterCounter(numWords, numLetters, letterCount);

  cout<<"\n\nNumber of Words = "<<numWords<<"     Number of Letters = "<<numLetters<<endl;
  cout<<"\nFrequency of letters as follows:"<<endl;
  for(int i = 0; i < 26; i++)
  {
    cout<<char('a'+i)<<" = "<<letterCount[i]<<endl;
  }

  return 0;
}

void wordLetterCounter(int &numWords, int &numLetters, int letterCount[])
{
  char c;
  char lastLetter=' ';

  //Remember 'A'=65, 'Z'=90 and 'a'=97, 'z'=122 in Ascii
  while(cin.get(c))
  {
    //Converting upper to lower case to make it case insensitive
    if(c >= 'A' && c <= 'Z')
      c+=char(32);

    //Increase Letter Count and number of letters
    if(c >= 'a' && c <= 'z')
    {
      letterCount[c - 'a']++;
      numLetters++;
    }

    //Increase number of words
    if(c == ' ' && lastLetter != ' ')
      numWords++;

    //If new line then break;
    if(c == '\n')
    {
      //Before you exit, the numWords should be increased if there was atleast 1 letter
      if(numLetters)
        numWords++;
      break;
    }
    lastLetter = c;
  }
}

The Output is as follows. Note that there is a '.' and many spaces between Dr. and Spock but the wordcount is correct.

Program to print itself

I came across this interesting program that can print itself. I have modified it from C to C++ and added few comments. Its worth exploring.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Challenge program to self print itself
//Original from http://www.cprogramming.com/challenges/solutions/self_print.html
#include<iostream>
char *program = "#include <iostream>%cchar *program = %c%s%c;%cint main()%c{%c  printf(program, 10, 34, program, 34, 10, 10, 10, 10, 10, 10);%c  return 0;%c}%c";
int main()
{
  printf(program, 10, 34, program, 34, 10, 10, 10, 10, 10, 10);
  return 0;
}
//Note the trick
//In ASCII, 10 = LF or new line feed
//In ASCII, 34 = double quotes or "
//%c is printing charachter. 10 for new line and 34 for double quotes
//%s is printing the string

The output is as follows. Note that the aim is for the program to print itself and not the comments. Also the output is wrapped around.