Leif E Glacer
BAN USERI'm a software architect with 27 years of R&D at companies like Microsoft, Intel, and IBM, as well as several smaller companies including my own startup.
Although it isn't stated, I feel fairly certain that the interviewer would want the nonspace sequence to be preserved. Otherwise the question is stupideasy.
It's akin to the remove algorithm in many libraries, which are required to be stable (i.e. preserve ordering of items not selected for removal).
Did you test this?
 Leif E Glacer August 09, 2013Granted, it does technically satisfy the "inplace" requirement, but the problem with this solution is that it will require up to O(n) memory for the recursive call stack .. I'm not sure this would satisfy the interviewer
 Leif E Glacer August 09, 2013Do you think the interviewer is looking for an O(n²) solution?
 Leif E Glacer August 09, 2013I think the question implies "inplace", but it would be good to clarify with the interviewer before proceeding
Also, using stock library functionality during an interview is often not allowed
I think this must be used as a screening question
A straightforward solution in C is
char* removeSpaces(char* str)
{
if (str)
{
char* pWrite = str;
for (char* p=str; *p; p++)
if (*p!=' ')
*(pWrite++) = *p;
*pWrite = 0;
}
return str;
}
Note that this can be made a little faster by partially unrolling the loop, skipping over characters before the first space since they don't need to be copied.
Now, if you know a language which has advanced metaprogramming, you can followup the simple solution above by showing a "lazy evaluation" solution, such as the following code in D. This is O(m) instead of O(n), where m is the number of spaces at the start of the string.
auto removeSpaces(E)(E[] input)
{
struct Result
{
private E[] source = input;
private void skipSpaces()
{
while(!source.empty && source.front==' ')
source.popFront();
}
this() { skipSpaces(); }
@property E front() { return source.front; }
@property bool empty () { return source.empty; }
void popFront()
{
source.popFront();
skipSpaces();
}
};
Result r;
return r;
}

Leif E Glacer
August 08, 2013 That's probably not what the interviewer is asking for
 Leif E Glacer August 08, 2013This solution will work
There is an O(n²) solution that uses shifting. I suspect the "without shifting" was a hint given by the interviewer to get the O(n) solution instead.
Glad to help Satyam.
To answer your question: the original question asks to output the number without any dashes  there's no need to perform a conversion. But, if you wanted to convert to a number, you'd need a 64 bit long since 18,002,662,278 is too large to be held in a 32 bit int.
Really? It works just fine. Here's code you can copy and paste to test for yourself.
template <typename E, size_t M, size_t N>
auto rotate(const E (&source)[M][N], E (&target)[N][M])
> decltype(target)
{
for (size_t i=0; i<N; ++i)
for (size_t j=0; j<M; ++j)
target[i][j] = source[Mj1][i];
return target;
}
template <typename E, size_t M, size_t N>
bool isEqual(const E (&a)[M][N], const E (&b)[M][N])
{
for (size_t i=0; i<M; ++i)
for (size_t j=0; j<N; ++j)
if (a[i][j] != b[i][j])
return false;
return true;
}
template <size_t M, size_t N>
void print(const char (&a)[M][N])
{
for (size_t i=0; i<M; ++i)
{
for (size_t j=0; j<N; ++j)
{
printf("%c ", a[i][j]);
}
printf("\n");
}
printf("\n");
}
int wmain(int argc, wchar_t* argv[])
{
char source[5][3] =
{
{ 'a', 'b', 'c' },
{ 'd', 'e', 'f' },
{ 'g', 'h', 'i' },
{ 'j', 'k', 'l' },
{ 'm', 'n', 'o' }
};
char actual[3][5];
char expected[3][5] =
{
{ 'm', 'j', 'g', 'd', 'a' },
{ 'n', 'k', 'h', 'e', 'b' },
{ 'o', 'l', 'i', 'f', 'c' }
};
rotate(source, actual);
print(actual);
if (isEqual(actual, expected))
printf("The test passed\n");
else
printf("The test failed\n");
return 0;
}
Outputs:
m j g d a
n k h e b
o l i f c
The test passed

Leif E Glacer
August 08, 2013 This question is a classic entrylevel question at many tech companies, which is why it's included in Gayle's book.
It was one of my favorites when interviewing candidates in the 1990s, but became so popular that I got too many candidates providing a memorized answer, unable to explain the details of what they wrote. This rendered the question almost useless for interview purposes.
It's not very tricky, but many interviewers like to ask it because it requires familiarity with C/C++ rectangulararray syntax and has enough details to enable an interviewer to observe a candidate's attention to detail. The java solutions are less interesting to the interviewer. I've observed that many midlevel and seniorlevel candidates have trouble tracking all the details of this question, so it's not entirely inappropriate for nonentrylevel positions.
An example m x n case:
┌ ┐
│ a b c │
│ d e f │
A = │ g h i │
│ j k l │
│ m n o │
└ ┘
┌ ┐
│ m j g d a │
R(A) = │ n k h e b │
│ i l i f c │
└ ┘
By simple inspection we can see that R[i][j] = A[m  j  1][i], so the code to rotate the matrix 90° is fairly trivial.
As an interviewer, I'm always ecstatic when a candidate demonstrates a solution like the following, and is able to explain every aspect of it.
template <typename E, size_t M, size_t N>
auto rotate(const E (&source)[M][N], E (&target)[N][M])
> decltype(target)
{
for (size_t i=0; i<N; ++i)
for (size_t j=0; j<M; ++j)
target[i][j] = source[Mj1][i];
return target;
}
This implementation demonstrates a number of things besides a correct answer. It works for any size matrix, provided the size is known at compile time. It shows the interviewer a little "advanced" knowledge of C++, e.g. passing arrays by reference, metaprogramming with C++ templates, and familiarity with recent additions to the language like "decltype" and "auto".
There is a followup question that many interviewers like; some even skip right to it. I'm not fond of it because it requires a nonobvious trick which can be difficult for even excellent, experienced programmers to see without hints. This is a little unfair considering the emotional stress the interview imposes; worse, you simply can't know if a candidate knew the trick to begin with or figured it out on their own. The objective of these kinds of questions is not to stump a candidate (or for an interviewer to show off!), but rather to see how a candidate dissects problems and codes a solution.
The followup question is to rotate an N x N matrix "in place", that is, where source and target are the same matrix. The implication is that the algorithm should NOT use an intermediate matrix.
A 5 x 5 matrix and it's 90° rotation.
┌ ┐
│ a b c d e │
│ f g h i j │
B = │ k l m n o │
│ p q r s t │
│ u v w x y │
└ ┘
┌ ┐
│ u p k f a │
│ v q l g b │
R(B) = │ w r m h c │
│ x s n i d │
│ y t o j e │
└ ┘
Our first algorithm cannot be used when source and target are the same since new values will overwrite old ones before they're read (same problem as with overlapping array copies). The nonobvious "trick" is to observe first that the entries in the corners {a, e, y and u} exchange, or rather rotate, positions. This fouratatime rotation of values is best placed in an auxiliary function and is trivial. In C++ it's:
template <typename E>
void rotate(E& a, E& b, E& c, E& d)
{
auto tmp = d;
d = c;
c = b;
b = a;
a = tmp;
};
Accordingly, the rotation of the matrix can then be performed through a series of these fouratatime rotations, first on the outer rows and columns, then working towards the center. There are N/2 "shells", and when N is odd, the central element does not rotate. We'll need to perform N1 fouratatime rotations for the outermost entries, N3 fouratatime rotations for one level in, and so on until the center is reached.
Following the metaprogramming methodology from our first rotate function, our inplace algorithm in C++ looks like this:
template <typename E, size_t N>
auto rotateInPlace(E (&m)[N][N])
> decltype(m)
{
// There are N/2 "shells"
for (size_t i=0; i<N/2; i++)
{
// temporary variables for clarity
const size_t top=i, bottom=Ni1, left=i, right=Ni1;
// i.e. n = { N1, N3, N5 ... } for each i
const size_t n = Ni*21;
// rotate the current "shell"
for (size_t j=0; j<n; ++j)
rotate( m[top][left+j], m[top+j][right],
m[bottom][rightj], m[bottomj][left] );
}
return m;
}
Please note that (contrary to some other comments on this question) the time complexity of this algorithm is still O(N²) since every element must be visited. Doing them fouratatime doesn't change the bigO time complexity.
Some of my colleagues aren't happy with the above C++ solutions because they only work on fixedsize matrices stored in rectangular arrays. Instead, they insist on an implementation with dynamically sized matrices because they think it somehow adds complexity to the problem. In such situations, I prefer to see candidates provide a basic Matrix class and then provide the same algorithms as above. I do NOT like candidates to write a very complicated function with pointers and extra parameters; nor do I like to see them use Cstyle jagged arrays, i.e. an array of array pointers, instead of a rectangulararray (can you guess why I hate such solutions?).
Something like the following Matrix class declaration is usually sufficient for the interviewer (i.e. no implementation needed):
// Simple interface for a Matrix class
template <typename E>
class Matrix
{
public:
Matrix(size_t heightAndWidth); // for an N x N
Matrix(size_t height, size_t width); // for an M x N
size_t Height() const;
size_t Width() const;
E& operator() (size_t row, size_t column);
const E& operator() (size_t row, size_t column) const;
};
The underlying rotation algorithm is exactly the same for all contiguously stored, rowmajor matrices.
template <typename E>
Matrix<E>& rotate(const Matrix<E>& source, Matrix<E>& target)
{
// implementation is basically the same as above
}
One could be tempted to suggest that the Matrix class *might* implement special matrices, e.g. sparse, triangular, or symmetric; or that the matrix class could employ a novel storage strategy, e.g. column major contiguous arrays, or jagged arrays. As a candidate, I usually withhold such comments until near the end of the interview session since implementation of these Matrix classes and concomitant algorithms is nontrivial and not appropriate for an interviewquestion. If you do make such comments, be prepared to discuss the implications of the matrix design on the rotation algorithm. For example, some matrix classes store the data in a special format to enable very fast transpose and rowreversal operations; these operations could be used to rotate the matrix faster than using the algorithm described above. (We're also talking about VERY LARGE matrices here)
There is a performance consideration that I sometimes mention if I'm given this question as a candidate. The elements of rectangular Carrays are stored contiguously, in rowmajor order. The rotate algorithm above WRITES the target matrix entries "inorder" with respect to their placement in memory; the source matrix entries are READ outoforder. When given the choice of inorder WRITES or inorder READS, it's generally advisable to defer to the former since it may enable better compiler optimizations. However, some processors may perform better on orderedreads instead of writes (see why?). In this case, the ONLY CORRECT ANSWER is to write it both ways and run a performance analysis experiment.
I think this is a good entrylevel *screening* question.
Firstly, its solutions don't require foreknowledge of any "trick", just a basic understanding of ASCII layout and how to use it to do character translations.
Secondly, an efficient implementation is very elementary, and, as we see from earlier posted solutions, there are a variety of ways to solve the problem. It's easy to code in <1015 minutes, perhaps longer for a candidate with minimal experience or for someone who feels a lot of stress or nervousness when interviewing for a job.
I personally only use this question for screening out the bottom 1:50 candidates, or those candidates who can't program at all under the stress of an interview. It will NOT tell me anything about the quality of the candidate when she/he writes an adequate solution.
Here's a straight forward solution in D that uses only an array table to translate the letters to numbers. It's more efficient than the hashmap solutions and simply leverages the positional adjacency of successive characters 'A'...'Z' in UTF8 or ASCII encoding.
// This code is in D
string mapPhoneDigits(string s)
{
static string tbl = "22233344455566677778889999";
assert(tbl.length==26);
// An Appender is somewhat similar to StringBuilder in java.
// Alternatively the programmer could simply write each char to stdout
auto result = appender!string();
foreach (c; s)
{
if (c>='0' && c<='9')
result.put(c);
else if (c>='A' && c<='Z')
result.put(tbl[c'A']);
}
return result.data;
}
int main(string[] argv)
{
string phoneNumber = "1800COMCAST";
writeln(phoneNumber, " => ", mapPhoneDigits(phoneNumber) );
return 0;
}
Note to interviewers: Please do NOT waste your time with this question when interviewing senior candidates. Sadly, I recently experienced a company asking this question when I interviewed with them  it's terribly easy and shows the candidate that the interviewer needs more training. On the other hand, if I accept their offer I can immediately help the team to improve their interview process :)
 Leif E Glacer July 09, 2013
I'm not sure why other solutions here are so ... complicated.
A simple solution in C
A solution in D
If the interviewer generalizes the question, more generic solutions might be helpful.
Here again in D
Then, removeSpaces can be implemented simply as
But I think that might be beyond the scope of the question ;)
 Leif E Glacer August 09, 2013