Ashes To Glory

Rotating a 2D array of integers (matrix) by a given angle (+90, -90, +180, -180)

2011-12-02T01:31:00.000+05:30

So, I came across this problem on a forum and before looking up, I tried to solve it. After 15 minutes of trying, I figured out that the solution is pretty easy and elegant which was messy otherwise if you are going to do it in an insane way. So, here we go:

Problem definition: You are given a 2D square matrix, or 2D array of integers of size n (n rows and n columns), your output should be n by n 2D matrix rotated by a given angle, which could be +90, -90, +180, -180.

Example:

Input Output

1 2 3 7 4 1

4 5 6 Rotate by +90 8 5 2

7 8 9 9 6 3

If you go by solving it something like manually, swapping elements, its going to be messy, tedious, and error prone in that there will be much more edge cases, test cases to handle. So, after trying on paper, I figured out following elegant solution to solve this in an easy manner.

Rotate by +90 (clockwise once):

Input: n by n matrix M, where n >= 2

Algorithm:

Step 1: Transpose M

Step 2: Reverse each row

Dry run:

Step 1: Transpose

M M'

1 2 3 1 4 7

4 5 6 -- 2 5 8

7 8 9 3 6 9

Step 2: Reverse each row

M' M''

1 4 7 7 4 1
2 5 8 -- 8 5 2
3 6 9 9 6 3

M'' is rotated form of M by +90 degree.

Pseudocode: is here which is self explanatory and easily convertible to source code in a language of your choice.

Transpose

for i in [0, n)

for j in [0, n)

if ( i < j )

swap( M[i][j], M[j][i] )

Reverse a row (rowidx)

start = 0

end = cols - 1

while ( start < end ) {

swap( M[rowidx][start], M[rowidx][end] )

++start

--end

}

Rotate

Transpose

for i in [0, rows)

Reverse( i )

That was fair enough until only asked to rotate by +90 degree. If problem is further extended to be solved for any given angle, of course the rotation should make sense, for example, 47 degree is not a choice ;-). So, here are some elegant techniques (I'll be brief now for other angles, because for +90 degree I have elaborated the solution):

Rotation by -90 degree (anticlockwise once):

Step 1: Transpose

Step 2: Reverse each column

Rotation by +180 degree (clockwise twice): Two methods follows

First:

Rotate input matrix +90 degree twice, if routine for which is available to you

Second: (You'll be amazed!)

Step 1: Reverse each row

Step 2: Reverse each column

Rotation by -180 degree (anticlockwise twice): Three(!!!) methods follows

First:

Rotate input matrix -90 degree twice, if routine for which is available to you

Second: (You'll be amazed again!)

Step 1: Reverse each column

Step 2: Reverse each row

Third: (Aha!)

Because rotating a matrix +180 degree or -180 should produce same result. So you can rotate it by +180 degree using one of above methods.

Concluding note: Above techniques are elegant and very simple and straightforward to implement. Try them for some input of your choice and rotate it in all angles. These techniques are tested with a working C program.

Cheers!

Rajendra

Use of Data Structures in Operating Systems

2011-11-04T10:30:00.001+05:30

Computer science students generally study data structures, both those on the main topic of a full course and as portions of many upper level courses, such as compilers, databases, networking and operating systems. Data structures are used abundantly in operating systems.

Queues - are used wherever entities need to wait, e.g., processes waiting for a processor, I/O requests are waiting for devices to become available, processes waiting for access to their critical sections and so on.

Stacks - are used for supporting the function call return mechanism.

Trees - are used to represent file system directory structures, to keep track of the allocation of disk space to files, to build hierarchical page directory structures in support of virtual address translation and so on.

Graphs - are used when studying networking.

Hash Tables - are used when implementing Process tables to access a process's control block (PCB) quickly, using PID (process identification number) as the key.

Cheers!

Rajendra

Strategies For A Great Interview

2011-10-30T13:56:00.000+05:30

A typical one hour interview with a single interviewer consists of five minutes of introductions and questions about the candidate's resume. This is followed by five to fifteen minutes of questioning on basic programming concepts.

The core of the interview is one or two detailed algorithm design questions where the candidate is expected to present a detailed solution on a whiteboard or paper. Depending on the interviewer and the question, the solution may be required to include syntactically correct code in a language that the candidate is comfortable with. The reason for asking such question's is that algorithms and associated data-structures underlie all software. They are often hidden in library calls. They can be a small part of a code base dominated by I/O and format conversion. But they are the crucial component in terms of performance and intricacy.

The most important part of interview preparation is to know the material and practice solving problems. However the non-technical aspects of interviewing cannot be underplayed either. There are a number of things that could go wrong in an interview and it is important to have a strategy to deal with them.

1. Before the Interview

One of the best ways of preparing for an interview is mock interviews. Get a friend to ask you question's and have you solve the problems on a whiteboard or paper. Ask your friend to take notes and give you detailed feedback, both positive and negative. Also ask your friend to provide hints from the solution if you are stuck. This will help you overcome any fear or problem areas well in advance.

2. Approaching the Problem

No matter how well prepared you are, there is a good chance that the solution to an interview problem will not occur to you immediately. When this happens, there are several things you can do.

Clarify the question: This may seem obvious but it's amazing how many interviews go badly because the candidate spends most of the time trying to solve the wrong problem. If a question seems exceptionally hard, there is a good chance you have misunderstood the question. The best way to clarifying the question is to state a concrete instance of the problem. For example: if the question is "find the first occurrence of a number greater than k in a sorted array", you could ask the following: the input array is [2,20,30] and k is 3, then are you supposed to return 1 (index of 20)?"

Work on small examples: This may not be true for all the problems. However there is a large class of problems where after working out the solution for a few small examples! you may see a pattern emerge.

Spell out the brute-force solution: Problems that are put to you in an interview tend to have an obvious brute-force solution that has a large runtime compared to more sophisticated solutions. For example! instead

of trying to work out a dynamic programming solution for a problem, try all the possible configurations. There are several advantages to this: (1.) it helps you explore opportunities for optimization and hence reach a better solution! (2.) it gives you an opportunity to demonstrate some problem solving and coding skills! and (3.) it establishes that both you and the interviewer are thinking about the same problem. Be warned that this strategy can sometimes be detrimental if it takes too long to describe even the brute-force approach and leaves you with less time to work on the optimal solution.

Think out loud: One of the worst things you can do in an interview is to freeze up while solving the problem. It is always a good idea to think out loud while searching for a solution. On one hand! this increases the chances of you finding the right solution because it forces you to put your thoughts in a coherent manner. On the other hand, it helps the interviewer guide your thought process in the right direction. In the very least, even if you are not able to reach the solution, this leaves the interviewer with the impression that you have the intellectual ability to attack an unknown problem.

Search for isomorphic problems: Even if you may not have seen the exact problem, you may have seen another problem with similar mathematical structure. See if this seems like a good fit for general algorithmic

techniques, such as, divide-and-conquer, dynamic programming, greedy, etc.. Can you map the problem to a graph? Can you map it to an objective function and a set of constraints, such as an integer linear program?

3. Presenting the Solution

Once you have a solution, it is important to present it well and do a comprehensive job at it. A lot of these things become simpler if you use a higher level language such as Java. However you should use the language

with which you are most familiar. In most scenarios, it is perfectly fine to write a pseudo-code as well. Here are some thoughts that could help:

Test for corner cases: For a number of problems, your general idea may work for the majority of the cases but there may be a few obscure inputs where your algorithm (or code) would fail. For example, you

could write a binary search code that crashes if the input is an empty array or you may do arithmetic without considering the possibility of integer overflow. It is important to check for these things carefully. One way of doing this is to construct a few test cases and work out the output of your algorithm for them. In many cases, the code to handle some obscure corner cases may be too complicated. In such cases, you should at least mention to the interviewer that you are aware of the problem and you could try to address it if they are interested.

Function signature: Several candidates tend to get this wrong and getting your function signature wrong reflects badly on you. For example, it would be bad if you are writing the code in C language and your function returns an array but you fail to return the size of the array along with the pointer. Another place where function signatures could be important is knowing when to pass parameters by value versus by reference.

Memory management: If you allocate memory in your function, you must ensure that in every execution path, this memory is de-allocated. In general, it is best to avoid memory management operations all together. If you must do this, consider use of scoped pointers.

Syntax: In almost all cases, the interviewers are not evaluating you on the correctness of the syntax of your code. The editors and compilers do a great job at helping you get the syntax right. However you cannot underplay the possibility of an interviewer leaving with the impression that you got most of the syntax wrong since you do not have much experience writing code. Hence once you are done writing your code, you should make a pass over it to avoid any obvious syntax errors before claiming you are done.

4. Know your Interviewers

If the organization can share some information about the background of your interviewers, it can help you a great deal. For fresh graduates, it is also important to think .from the perspective of the interviewers. It is also important to note that once you ace the interview, you will have an offer and you would have an important decision to make: is this the organization where you want to work? Interviews are the best time to collect this information. Based on your interaction with the interviewers, you can get a pretty good idea of their intellect as well as how pleasant the organization could be. Most interviews end with the interviewers letting the candidates ask questions. You should make the best use of this time by (1.) getting the information you would need and (2.) communicating to the interviewer that you are interested in the job. Prepare a list of questions in advance that both gets you helpful information as well as shows your knowledge and interest in the organization.

5. General Conversation

Often interviewers will spend some time asking questions about your past projects, dissertation, etc.. The point of this conversation is:

- Can the candidate clearly communicate a complex idea: This is one of the most important skills for working in an engineering team. If you have a grand idea to redesign a big system, can you communicate it to

your colleagues and bring them on board? It is best to practice how you want to present some of your best work in advance. Being precise, clear, and having concrete examples can go a long way here. For candidates who have to communicate in a language that is not their first language, it may be important to speak slowly and perhaps use the whiteboard to augment their words. Is the candidate passionate about his work: We always want our colleagues to be passionate, full of energy, and inspiring to work with. If you are so passionate about your work that your eyes light up while describing your work, it can go a long way in terms of establishing you as a great colleague. Hence when you are asked to describe a project from the past, it is best to pick something that you are passionate about rather than a project that was complex but did not interest you.

- Is there a potential interest match with some project: During a general conversation, the interviewer may gauge areas of strengths for a potential project match. If you know the requirements of the job, you may want to steer the conversation in that direction. However in the computing industry, things change so fast that most teams prefer a strong generalist. Also, it is a good idea to maintain a homepage with links to your projects and articles; things that can help interviewers learn more about you.

Cheers!

Rajendra

Multi-tasking vs Multi-threading vs Multi-processing

2011-10-29T10:58:00.000+05:30

Multi-tasking - Illusion of being able to do more than one thing at a time.
Multi-threading - Illusion of being able to do more than one thing at a time within a thing.
Multi-processing - Really being able to do more than one thing at a time.

Cheers!
Rajendra

Number To Words Algorithm

2011-01-11T12:12:00.003+05:30

Number To Words Algorithm

Problem: Given any number of maximum 15 digits number convert it to a string which represents this number in words.
e.g., Input: 231 Output: Two Hundred And Thirty One.

1. Input example: 34541009234120

Find length of input string of digits, if it's a multiple of 3 then do nothing else pad with leading zero's to make it's length an exact multiple of 3 and divide the input number into 5 groups of 3 digits each, so our example input becomes

034 541 009 234 120
   Group No.   5 4 3 2 1

2. Find group of most siginificant digit, e.g., here MSD is 0 and it's group is:

groupNum = length%3 ? (length/3+1) : (length/3);

3. One loop for number of groups of 3 digits each;

4. One loop for each of the 3 digits inside a given group, so the time complexity boils down to linear;

5. Inside inner loop, for any given 3 digits generate a string like for e.g., 541 becomes "Five Hundred And Forty One";

6. Now decide which string would come after this according to the group number e.g., here group of 541 is 4 so "Billion" (from D array given above) would be appended to the string generated in step 5;

7. When outer loop finishes, return the string generated for the whole number.
   e.g., "Thirty Four Trillion Five Hundred And Forty One Billion Nine Million Two Hundred And Thirty Four Thousand One Hundred And Twenty"

Limitations:
   1. This algorithm generates words according to US number to words system.
   2. It generates words from numbers till 999 trillion 999 billion 999 million
   999 thousand and 999

Source code (C++):  Available on request.
   Post a comment to mention your email ID. You would receive the source code as
   soon as I get the request.

Cheers!
Rajendra

A lightweight Image Processing Library in C++

2011-01-11T10:57:00.002+05:30

Ever wondered how to work with/on images with little or no development overhead on your own? Here is the answer, the CImg image processing library. CImg stands for Cool Image; it is an open source, written entirely in C++, image processing toolkit which is very easy to use, handy for image processing tasks.

I first encountered this library when I was working on the dissertation, I had to extract frames from a video which I did easily using mpeg2encode and mpeg2decode, after that I had to read these frames (images) into 2D arrays and process them. I started looking for a way to achieve this and ended up with CImg library.

CImg is designed with following properties in mind:

Usefulness: CImg defines classes and methods to manage images in your own C++ code. You can use it to load/save various file formats, access pixel values, display/transform/filter images, draw primitives (text, faces, curves, 3d objects, ...), compute statistics, manage user interactions on images, and so on...

Genericity: CImg defines a single image class which can represent datasets having up to 4-dimensions (from 1d scalar signals to 3d hyperspectral volumetric images), with template pixel types (bool,char,int,float,...). It also handles image collections and sequences.

Portability: CImg is self-contained and thus highly portable. It fully works on different operating systems (UNIX, Windows, MacOS X, BSD, …) and is compatible with various C++ compilers (VC++, g++, …).

Simplicity: CImg is lightweight. It is made of a single header file “CImg.h” that must be included in your C++ source. It defines only four different classes, encapsulated in a namespace. It can be compiled using a minimal set of standard C++ and system libraries.

Just include a single header file in your application or library and you done and fully equipped with amazing capability of this library.

How to use CImg in your C++ program?

You just need to add these two lines in your C++ source code, in order to be able to work with CImg images:

#include “CImg.h”

using namespace cimg_library;

I guess this is enough introduction, believe me; you have to use it to realize its power and usefulness.

Reference: http://cimg.sourceforge.net

Cheers!
Rajendra

External linkage vs. internal linkage in C++

2010-02-27T09:31:00.003+05:30

A global variable has external linkage by default. Its scope can be extended to files other than containing it by giving a matching extern declaration in the other file.
The scope of a global variable can be restricted to the file containing its declaration by prefixing the declaration with the keyword static. Such variables are said to have internal linkage.
Consider following example:

1.cpp


void f(int i);
extern const int max = 10;
int n = 0;
int main()
{
    int a;
    //...
    f(a);
    //...
    f(a);
    //...
}

The signature of function f declares f as a function with external linkage(default). Its definition must be provided later in this file or in other translation unit (given below).
max is defined as an integer constant. The default linkage for constants is internal. So that max can be accessed in other files. Its linkage is made external with the keyword extern.
n is defined as an integer variable. The default linkage for variables defined outside function bodies is external.

2.cpp


#include "iostream" // make it angle brackets!
using namespace std;

extern const int max;
extern int n;
static float z = 0.0;

void f(int i)
{
    static int nCall = 0;
    int a;
    //...
    nCall++;
    n++;
    //...
    a = max * z;
    //...
    cout << "f() called " << nCall << " times." << endl;
}

max is declared to have external linkage. A matching definition for max(with external linkage) must appear in some file. (As in 1.cpp)
n is declared to have external linkage.
z is defined as a global variable with internal linkage.
The definition of nCall specifies nCall to be a variable that retains its value across calls to function f(). Unlike local variables with the default auto storage class, nCall will be initialized only once at the start of the program and not once for each invocation of f(). The storage class specifier static affects the lifetime of the local variable and not its scope.

NB: The keyword static plays a double role. When used in the definitions of global variables, it specifies internal linkage. When used in the definitions of the local variables, it specifies that the lifetime of the variable is going to be the duration of the program instead of being the duration of the function.

What a date!? 1.1.2010

2010-01-01T21:55:00.006+05:30

Hi, yesterday night, 31 Dec. 2009, 01:00am, I was thinking that let's see if there is something special about the new year date 1.1.2010, and after figuring out some very common observations, I found out at 09:14pm, on 1.1.2010 that the number 112010 (hundred and twelve thousand ten) is a sum of two primes which are 111997 and 13!!. What's big deal! Clearly not. But it is.

I came to this conclusion after running my code for 30 minutes(total time). Yesterday, at the same time, I was working out a problem on arrays, the problem was "Given a sorted array of integers and a target value t, find if there exists a pair (x, y) such that x + y = t and if yes, report these numbers." I solved this problem using 2 counters, first at start i = 0 and second at end, j = n-1, where n is the length of the array, if sum of a[i] and a[j] is greater than target value t, then I would decrement j, else increment i, so by following this greedy approach, I would eventually reach to the pair which sum to t (if at all), otherwise I would report that there is no such pair. I implemented this algorithm in C and run my code first for 10 numbers which worked fine and then I ran the code on 1 million numbers which also worked fine.

So, how does it relates with primes? It does so in that if I can find primes up to a certain number n in sorted order (non decreasing) then if I now run my above code then I will be able to find if a given number (even) hopefully is a sum of two primes or not, this is a powerful result in finding out if any given even number is a sum of two primes or not, and has a very good practical application (Goldbach's conjecture).

Now, what I did is that I found out primes up to 112010 and ran my code over this sorted array of primes up to 112010 and I found out that this number is indeed a sum of two primes (111997 and 13)!

Code available on request! Any queries, suggestions or comments are welcome!

Cheers!
Rajendra

Geany - Nice IDE for C/C++ development

2009-12-31T22:08:00.012+05:30

Geany is a fast and lightweight IDE for C/C++ programming in Ubuntu environment. It is open source (free) and anyone who has access to internet connection and Ubuntu installed on their system, can install it using following command on terminal:

sudo apt-get install geany

Alternatively, if you know and like to work with Synaptic package manager, then it is more intuitive to install Geany IDE using the SPM.

After installation, you can run Geany from Applications --> Programming --> Geany, click on Geany to run it you would see something like following screens on your desktop/laptop: (Click on any image given in this post to view it full size)

Key features of this nice and fast IDE are following:

1. It is very fast in compilation, buiding executables, and running code;
2. You can run terminal inside this IDE to switch to your current working directory and run your executable, to debug your code through gdb;
3. It does not have irritating GUI, where many unnecessary things are bombarded;
4. You can insert file headers, like date, time, General public license, source headers(stdio.h etc...) very quickly;
5. It supports many prominent languages like, C, C++, Java, Fortran, Caml, D, FreeBasic, Haskell, Haxe, Pascal, Assembler source files.

I would go through a bare basic example of C language to compile, build exe, running the exe.

Creating your first C source code, there are two ways you can do this:

(1.) create any folder anywhere in your system, name it whatever you wish, say “sample”, now make an empty file name it whatever you want to give to your C source file, for instance, say “sample.c”, give the extension .c this is necessary, double click on “sample.c”, it should open directly in Geany workspace, if you don't have any other IDE installed, but if you have, then it may not open in Geany by default, in this case, you would have to explicitly open it with Geany (right click on “sample.c” and open with Geany!). Now, you have your file opened in Geany workspace.

(2.) just open Geany IDE from Applications --> Programming --> Geany and click down arrow near New in the menu bar of Geany, you would see options like, C source file, C++ source file etc... click on C source file and you are done.

Now, from one of the above two steps, you have created your first C source file. You would like to see some action now, ok, if you are at any stage in C language (student, beginner, geek, professional, expert), you should be able to write any small piece of C code to see how Geany compiles, builds exe, and runs. I assume that you have or you will write any snippet within few minutes, now let's test it.
1. Compile: click F8 to compile(builds object file sample.o) and see how fast it compiles;
2. Build: click F9 to build executable(buids exe sample) and see how fast it does so.
3. Run: you can either run from terminal inside Geany or you can simply press F5 to run the executable you just build.
That's it!
Following are some screenshots giving you how nice it looks like programming with Geany and also demonstrates some of the points described above.

Any comments, suggestions and queries are most welcome.

Cheers!
Rajendra

Given n-th prime, find (n+1)-th prime!

2009-12-28T08:22:00.003+05:30

Problem: Given n-th prime, how do you find (n+1)-th prime? Write a function
int GetNextPrime(int n);
Example:
Input: 7 Output: 11
Input: 13 Output: 17
Hint: Search for Bertrand's Postulate!

C source code to check IsFibonacci()

2009-11-25T08:22:00.007+05:30

As promised, here is code to check for any given number belongs to Fibonacci series or not?

/*
Theorem:
A positive integer n is Fibonacci if, and only if, (5*n*n+4) OR (5*n*n+4) is a perfect square.
*/

bool IsFibonacci(int n)
{
    // Calculate criteria expressions
    int criteria[2];
    criteria[0] = 5 * n * n + 4;
    criteria[1] = 5 * n * n - 4;

    // Determine whether one of them is a perfect square
    int sqr[2];
    sqr[0] = sqrt(criteria[0]);
    sqr[1] = sqrt(criteria[1]);

    // Return result
    return ((pow(sqr[0], 2) == criteria[0]) || (pow(sqr[1], 2) == criteria[1]));
}

Comments and suggestions are always welcome!

Cheers!
Rajendra

How to know that a given number is Fibonacci or not?

2009-11-20T01:53:00.009+05:30

Hi,

I am back after a long time! I am assuming the reader is well acquainted with Fibonacci numbers. Still here goes the definition:

The sequence of numbers beginning
0, 1, 1, 2, 3, 5, 8, 13...
where each successive number in the sequence is the sum of the two preceding numbers. More precisely the sequence can be defined through the recurrence relation:

F(n) = 0, if n = 0
= 1, if n = 1
= F(n-1)+F(n-2), if n > 1

Following C source code returns the n-th Fibonacci number:

int Fibonacci(int n)
{
if (n == 0 || n == 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Now, here comes my primary objective of writing this post:

How to know whether a given number belongs to Fibonacci series or not?
OR
How to know that a given number is Fibonacci or not?

Algorithm 1. (Naive approach)
Input: n
Output: true or false

// Calculate Fibonacci numbers till we reach equal to or exceed n

// Return true if we found any of the calculated numbers equal to n
// and return false otherwise

This algorithm is inefficient.

Now, here we are at the point where crux of the whole story is.


Theorem: A number n is Fibonacci if, and only if, (5*n*n + 4) OR (5*n*n - 4) is a perfect square.[Ira Gessel 1972]

Check out my next post for the proof of this theorem or google it!

Checking for perfect square is easy as follows:
1. take the square root of the number;
2a. Just check if fractional part is zero (suggested by Equinox) OR

2b. discard its fractional part;
3. take square of the integral part;
4. if this square is equal to given number then number is a perfect square or it is not.

NEXT POST: C code for above theorem and proof of the theorem.

Cheers!
Rajendra

Implementation of my division algorithm in C++

2008-10-12T15:45:00.008+05:30

Hello guys, I have written a new approach (in C++) towards dividing two large numbers, input is dividend and divisor, and output shall be quotient and remainder. The algorithm and source code in C++ is presented here "as-is", anyone can use it, without any warranty to the damage(s) that may happen. The source code in text format is well documented and is self-explanatory.

ALGORITHM:
INPUT : Dividend, Divisor
OUTPUT: Quotient, Remainder

static int cnt;
if (dividend = divisor)
   return quotient = 0, remainder = 0
else if (dividend < divisor)   
return quotient = 0, remainder = dividend 
else  
{
   static int residue = dividend;  
   while(residue >= divisor)
{
residue = residue - divisor;
cnt++;
}
}
return quotient = cnt; remainder = residue;

The source code in C++ can be downloaded from HERE

My 5 Golden Rules about Interviews!

2008-10-06T02:02:00.005+05:30

Hello friends! Let me talk something about my previous post first! My previous post addressed the interview issues regarding the language questions. However, we all know that there are less language questions than that of ((Data Structures, Problem Solving, Algorithms, OS, Networks, etc.))(From now onwards, called 'BUNCH') These are the most important among all of the topics and is the topic of my discussion in this post too.

RULE 1. "Know Your Enemy( The host)":

You need to understand that the techie on the other side of the table who is going to interview you, is a technical person in the company, has sound knowledge of the Bunch(even if you doubt the 'soundness', there is no harm in assuming it!!), He knows answers to all the questions which he is going to ask you very well(obviously, but answering the problems you know answers already isn't a big deal, so this shouldn't give you the impression of his knowledge on the subject!).

RULE 2. "Host isn't The Champ":

I hope you have understood the rule 1, now you know that what your host is, so make it very very clear in your mind that "Nobody learned from birth, it is this world which have given you all the knowledge or whatsoever" and the host is no exception at all, so rule 2 is that host isn't the champ, he was like you once, you will be like him some day, please don't misunderstand me, I don't mean that you underestimate him, I just want to make sure that you feel confident, feel standing on your feet, have poise, and don't shake."

RULE 3. "If you know the answer beforehand, pretend as if you solved it right now"

That should be fairly simple idea for you guys, you have done it many times before with your friends, family etc., you remember/noticed it or not, but ya true, sometime we pretend in giving some answer so well that the other person can't catch. This happens often in puzzles, we solve so many puzzles that we remember the data in the question as well as the answer, or atleast the way to solve it, and we pretend too! Fair enough, go ahead, keep doing it, the only thing that changes here in the interview is that you have to do the same thing in a very formal and sophisticated manner.

RULE 4. "Understand why the problem has been given to you"

That sounds stupid, isn't it? Really not, as will be clear soon. The problem has been given to me because
No. 1. I am being interviewed.
No. 2. Host want me to solve the problem, or atleast I try it hard.
No. 3. Host want to see how easy/tough/fast/late I give up, means I fought.
OK, fine, bottom line is that the host has given you the problem to check the following:
1. How fast you solve, even if you solve it!
2. How efficient is your solution(in terms of complexity).
3. If you haven't solved it, did you quit early?
4. If you haven't solved it, how long you fought with the problem to find the solution?

RULE 5. "NEVER EVER GIVE UP"

My interview experience advocates this principle of never-ever-giving-up.

I found this principle applicable everywhere, let me make it more clear to you guys, many times, such situations happened before me (including interviews, friends etc.) that this golden rule helped me. Never giving up gives you a sense of fighter, that reflects on your face, you don't really have to pretend it though, but remember one thing actions and feelings go together, by regulating the actions, we can indirectly regulate the feelings which are not in our direct control. So guys, be wise, and never give up.

BOTTOM LINE:

"No matter how hard the given problem is, no matter you have heard about it before or not, no matter nothing, fight with a problem to solve it like a tiger goes for its hunt, and never ever give up. The host want to see how hard you tried!"

Cheers!
Rajendra

A bit from my Interview Mantra!!

2008-10-02T12:38:00.004+05:30

Surprisingly, a sudden turn from my pot! I am going to talk about my interview experience and want to share a bit!
In my little yet good experience, interviews want to know that you know the language (a little bit) and that you understand data structures and/or algorithms (ie programming techniques not necessarily language specific) and more importantly can see how you combine both. They also like to see that you can think.

While I doubt there are "standard" questions, I would suggest studying some data structures and thinking about what you can do with them (I think lists, queues/stacks and binary trees would be the most likely).

To show you can think, they will usually ask you to manipulate/work with the structure to do something slightly out of the ordinary (that is, they will assume you can create/traverse the structure but will have you solve a problem with it).

For Example: One that I have experienced before (more than once) relates to finding the midpoint of a linked list.

It is also good to understand how different data structures vary (eg difference between doubly & singly linked list, queue and stack) as well as differences in simple algorithms (eg post-order/pre-order/inorder traversal of trees, different search and sort methods).

A lot depeneds on the type of position. If you are going for a graduate/entry level position, they often want to gauge what you know. This means they will talk to you before asking questions and ask you your strengths. Try to sell the ideas listed above that you understand, to prompt for a question in that area (to confirm your story). For example:

Q: What areas did you study at School?
A: I completed courses in Software Engineering, Artificial Intelligence and Data Structures and Algorithms. During the Data Structures and Algorithms course my major project required me to design a simple program to store University Enrolments. Focusing on optimizing search times rather than Add/Delete times, I decided to organize my data in a Binary tree....etc

In this way, you claim "I know about BT's" and you should get a question on one. As with School, ultimately the prospective employer wants to know what you know not what you don't know.

Of course, different companies, different countries possibly different story, but in my experience: Always sell your knowledge, and try (not always possible) to steer interviews toward areas you know. Most important though, be confident but not cocky and don't just make things up if you don't know (even if the interviewer is only a human resource manager).
Cheers!
Rajendra

How I got introduced to Qt and some basics?

2008-09-11T06:58:00.017+05:30

Hello friends,
Today, I am going to talk about something very off-the-line and new, it's Qt. What is this? we will come to this later.

How I came to this? Actually, ... there is indirect link to, me reaching at Qt. I had XP on my laptop, and just 1 month before, I removed XP completely, and installed UBUNTU 8.04 in my suddenly awaken sense of open source sharing, pirated software crime etc. !!!

Things went very well, as I was doing my routine work, But I realized that, MS VC++, VB, is so strong for my application development, and I didn't know whether I can develop or learn my GUI, event based applications in Eclipse? (I still don't know!).
So, I was chatting once to my colleague Deepak on tea, we were chatting about why I wanted to switch to XP again? He suggested, use Qt yar, it is for C++ GUI development.
So, this way, I reached to Qt.

What is Qt anyway?
Developed by: Norwegian Company Trolltech
Qt is a multiplatform C++ GUI toolkit. It provides application developers with all the functionality needed to build applications with state-of-the-art graphical user interfaces. Qt is fully object-oriented, easily extensible, and allows true component programming.
Most suitable link for resources, about Qt FAQ's, help, forums, technical FAQ's, is :
TROLLTECH - http://www.trolltech.com/

Installation:
Option 1.
Use Synaptic;
Option 2.

apt-get install libqt4-core libqt4-dev libqt4-gui qt4-dev-tools qt4-designer

After, downloading packages and installation is done, go to
Applications --> Programming --> you will see...
Qt4 Assistant
Qt4 Designer
Qt4 Linguist
Click on designer to view your beautiful, GUI to create C++ GUI applications.
You will see:
P.S.: credits for information available here is to : TROLLTECH
Following is the fundamental sequence of implementation events that happens in any GUI, or event-based application:
Step 1. Design your GUI according to your application's requirements;
Step 2. Add properties and variable names to the controls in your GUI;
Step 3. Add code to controls.
More to come ...

Cheers!
Rajendra