Example of Permutations in C++

Example of how you can let the Algorithm class generate permutations of String

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

using namespace std;

int main()
{
  string someString="ABC";
  vector<string> someVector;

  someVector.push_back(someString);

  string::iterator itBegin = someString.begin();
  string::iterator itEnd = someString.end();

  while(next_permutation(itBegin, itEnd)) //std::next_permutation defined in algorithm
  {
    someVector.push_back(string(itBegin, itEnd));
  }
  copy(someVector.begin(), someVector.end(), ostream_iterator<string>(cout, "\n"));

  return 0;
}

The output is as follows:

Via: Learning C++: Permutations in C++

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

Forwarding functions

Sometimes it is required to seperate the interface from implementation and 'forwarding functions' can be useful. The interface class can forward the work to the implementation keeping the interface clean and minimal.

The following is a simple example where function f() forwards its work to function g():

//g.h
#pragma once

bool g(int x)
{
  if (x%2 == 0)
    return true;
  else
    return false;
}


//f.h
#pragma once

bool f(int x);


//f.cpp
#include<iostream>

#include "f.h"
#include "g.h"

bool f(int x)
{
  return g(x);
}


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

#include "f.h"

using namespace std;

int main()
{
  if(f(20))
    cout<<"TRUE"<<endl;
  else
    cout<<"FALSE"<<endl;

  return 0;
}

There are couple of things to keep in mind when writing them. See here.

You can read more about seperating Interface and Implementation here.

Strategy for software engineering position interview

From my experience in hiring and attending job interviews, employers are generally looking at 5 areas when hiring a software engineer ...

1. Technical knowledge of specific technology product
2. Experience of the business problem domain
3. General technical and architecture sense
4. Personality and working style
5. IQ, problem solving skills
   

While 1 to 4 are very straightforward to answer, the most interesting and challenging part is the item (5) because there are effectively no time to prepare. Depends on how good you can manage pressure, you brain can be totally blank at the interview session.

I personally believe that a short interview doesn't necessary reflects a person's ability in doing the actual work. I personally have worked with many people who is a high performer in work but a poor interviewee. So don't lose confidence because you fail an interview, there is a factor of luck involved in this process.

Nevertheless, most employers are willing to accept a higher false negative, but the chance of false positive must be very low. Because the pass rate of these IQ and algorithm questions are generally pretty low, it is a very effective means of filtering the candidates. Therefore, be able to tackle this kinds of question well is a critical success factor of interviewing.

Notice that there is no substitution of "good knowledge", "high IQ" and "the ability to speak/think under a pressured environment", but I've found there are some very useful technique and strategies.

1. Rephrase the question slowly in your own words

This can help you to make sure you fully understand the question and clarify if there is any hidden assumptions you have made. Repeat the question "slowly" also gives you more time to think.

From the interview perspective, he/she can see clearly the candidate's ability to digest a problem.

2. Construct a Visual model of the problem

Use a whiteboard, or paper (if this is a phone interview) to diagram the problem that you perceive. Our brain is good in understanding picture than words so having a diagram will be very useful to come up with solution ideas.

From an interview's perspective, he/she can see a clear picture how you analyze the problem.

3. Use a special, simple case to guide you

Never try to tackle the general problem at first, start with a super-simple, special case, and think how you would solve this simple case first. This is very helpful to reduce the amount of things that you need to consider and let you focus in the core part of the problem.

4. Start with a very naive solution as a baseline

Tell the interviewer that you want to start with a very naive solution to establish a baseline. The naive solution can usually be constructed using a brute-force approach (try all combination until you find a matched solution). After that analyze the complexity of this naive solution as a baseline for future comparison.

5. Improve your solution

At this stage, you need to evolve and improve your solution. Here are some general techniques.

• Divide and conquer: Decompose the problem into smaller ones and solve each sub-problem separately, then combine the solutions for the overall problem.
• Reduce to well-known algorithm models: Try to model your problem in terms of well-studied computer science data structure model (e.g. Tree, Graph, Search, Sort) and then apply well known algorithm to solve them
  
• Recursive structure: Try to structure your problem in a recursive form. Finding the solution for the base case and then expand the solution in a recursive manner.
  
• Greedy method: Try to modify attributes of your current best solution to see if you can get a better one. Watch out of being trapped in a local optimal solution.
  
• Approximation: Instead of finding an exact solution, try to see if it is acceptable to find an approximate solution. Probabilistic approach (try 100 random combination and pick the best outcome)

6. Keep talking while you think

Don't wait until you fully figure out the answer. Keep talking while you are thinking about the solution so the interviewer understand how you analyzing things, and you are also showing how well you can express your thoughts. It is also easier for the interviewer to guide you or give you hints. And finally you may impressed the interviewer even you cannot get to the exact answer.


7. Generalize your solution for the final answer

After you find a working solution for the simple case, extend the simple case to see how you would solve it. See if you can find a general pattern how the solution would look like. Once you find it, generalize your solution for the general problem

From the interview's perspective, he/she can assess if the candidate can think in different levels of abstraction, and the ability to apply a solution in a broader scope of problem.


8. Remember the interview hasn't ended at the office building

You always have the chance to think through the question that you haven't given satisfactory answer after you walk out from the office. Submit a solution via email once you get back home (do it ASAP though), along with a thank you note to the interviewer.

Simulating 'break all' in C++

Sometimes your program is inside multiple loops when it meets a certain criteria and all you want to do is to break out from all the loops. Some programming languages allow 'break all' statements while most of them dont.

In Java there is a nice little feature of using a label on the outermost loop and then you can say inside 'break label' to break from the outermost loop. This is shown in the example below

String valueFromObj2 = null;
String valueFromObj4 = null;
OUTERMOST: for(Object1 object1: objects){
  for(Object2 object2: object1){
    //I get some value from object2
    valueFromObj2 = object2.getSomeValue();
    for(Object3 object3 : object2){
      for(Object4 object4: object3){
        //Finally I get some value from Object4.
        valueFromObj4 = object4.getSomeValue();
        //Compare with valueFromObj2 to decide either to break all the foreach loop
        if( compareTwoVariable(valueFromObj2, valueFromObj4 )) {
          break OUTERMOST;
        }
      }//fourth loop ends here
    }//third loop ends here
  }//second loop ends here
}//first loop ends here

The important thing to remember is this is not available in C++.

Another way of doing 'break all' is to have a 'flag' in each of the loop as well like:

while ( condition && !flag)

Then inside the nth loop set the flag to true and break. All the the loops will exit. This is a good approach and is widely used.

I prefer using another approach using the goto statement. A lot of C++ people hate goto and think its pure evil but I dont think its always that bad. Also see this. Example as follows:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Example of simulating break all in C++
#include<iostream>

using namespace std;

int main()
{

  cout << "Entering the nested loop" << endl;
  for(int loop1 = 0; loop1 < 4; loop1++)
  {
    cout<<"Loop1 : " << loop1 << endl;
    for(int loop2 = 0; loop2 < 4; loop2++)
    {
      cout<<"Loop2 : " << loop2 << endl;
      for(int loop3 = 0; loop3 < 4; loop3++)
      {
        cout<<"Loop3 : " << loop3 << endl;
        if(loop3 == 3 && loop2 == 2 && loop1 == 1)
        {
          goto SOMELABEL;
        }
      }
    }
  }
SOMELABEL:
  cout << "Exiting the nested loop" << endl;

  return 0;
}

The output is as follows:

Class initialisation and constructors

There is often lots of confusion with regards to class initialisation. People may forget to take care while using default constructors and copy constructors. Here is a simple example that tries to explain lots of concepts.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//This program gives an example of constructors and initialisations

#include<iostream>

using namespace std;

//Example of a class
class someClass1
{
public:
  //implicit default constructor
  int x;
  int *y;
};

//Example of a class with constructor
class someClass2
{
public:
  someClass2(const someClass2& xyz)
  {
    cout<<"** copy constructor called"<<endl;
    x = xyz.x;
    y = new int(*xyz.y);
  }
  //default constructor will have to be explicitly defined
  someClass2() {};
  //overloading operator '='
  const someClass2& operator = (const someClass2& xyz)
  {
    cout<<"** operator '=' called"<<endl;
    x = xyz.x;
    y = new int(*xyz.y);
    return *this;
  }
  int x;
  int *y;
};

int main()
{
  someClass1 a; //Default initialisation
  a.x = 1234;
  a.y = new int(6789);

  cout<<"someClass1: a.x = "<<a.x<<"       a.y( " <<a.y<< " ) = "<<*(a.y)<<endl;

  someClass1 b = a; //Copy Initialisation

  cout<<"someClass1: b.x = "<<b.x<<"       b.y( " <<b.y<< " ) = "<<*(b.y)<<endl;

  someClass1 c(a); //Direct Initialisation

  cout<<"someClass1: c.x = "<<c.x<<"       c.y( " <<c.y<< " ) = "<<*(c.y)<<endl;

  //Calling default constructor
  someClass2 aa;
  aa.x = 2468;
  aa.y = new int(3579);

  cout<<"someClass2: aa.x = "<<aa.x<<"      aa.y( " <<aa.y<< " ) = "<<*(aa.y)<<endl;

  //calling copy constructor
  someClass2 bb = aa; //Copy Initialisation - note copy constructor will be called

  cout<<"someClass2: bb.x = "<<bb.x<<"      bb.y( " <<bb.y<< " ) = "<<*(bb.y)<<endl;

  //calling copy constructor
  someClass2 cc(aa); //Direct Initialisation - note copy constructor called in this case as well

  cout<<"someClass2: cc.x = "<<cc.x<<"      cc.y( " <<cc.y<< " ) = "<<*(cc.y)<<endl;

  someClass2 dd;
  //calling operator =
  dd = aa;

  cout<<"someClass2: dd.x = "<<dd.x<<"      dd.y( " <<dd.y<< " ) = "<<*(dd.y)<<endl;

  return 0;
}

The output is as follows:

There are certain things worth noting in the above example:

• In case of someClass1, since only the default constructor is used, the same pointer is used for y in all the cases. This can cause serious problems in the code if one of the classes delete the memory pointed by y for class someClass1. This problem is not present in someClass2
• If any constructor is defined, it becomes necessary to define the default constructor. You can make sure that nobody uses default constructor in case of someClass2 by making it private (I havent done that because I wanted to show operator =)
• As you can see in case of variable cc, copy constructor would always be called instead of operator =.
• operator = would only be called in case of assignment. This is a common mistake.
• In the code above, cc(aa) is better than using bb = aa even though the results are the same. The main advantage being that it will avoid confusion with operator '=' if its overloaded for a novice and the constructor can be overloaded to take more than one input in future.