Google Interviews Part I- Questions and more

This is a summary of my own experience on interviewing in Google. The process went quite well and lasted for about 40 days. I had 4 phone interviews and then they flew me to the Google Site I had applied to. I had 5 on-site interviews, quite stressful and lengthy to finally reach the bitter end 3 days later, when I was informed that I had the potentials but not matched to the exact expectations of the position.

Either you are into computers, or you are having your own interviews with Google or other major software company or you are just curious, you might find this topic to be at least interesting. Later I will reveal many of the questions they asked me but for what follows I will give my own summary view of this process.

I am sure you have heard for 'weird puzzles' or 'crazy questions' during the interviews (for example how many golf balls fit into a school bus? or how many piano tuners are there in the world?). Well, all these are total nonsense. Google is all about algorithms (Well at least the searhing-Google). If you are planning of preparing for interviews some textbooks on the subject might be a good start. Another good advice would be to check out the data structures and algorithms library available in the programming language of your choice (for example Java Collections Framework or .NET Collections package)

But don't be scared. Googlers are not creatures with extra-terrestrial intelligence. You will talk to people that are great scientists but also to people that are not. You will talk to engineers that honor their title but also to others that are merely mediocre programmers. Google is now a big company and this is inevitable. You will understand what I mean if you keep on reading the next blog posts.

So, a few quick tips would be:
1. Have a strong understanding of algorithms
2. Have a mastery on programming and especially the libraries available (collections)
3. Be calm and inspire confidence
4. Goto 1

These 4 advices are fairly general. You can customize it further for the Google case. For example since Google is a search company you should consider fair questions regarding Regular Expressions.

In summary, it has been a really unique experience. Google is really a great company and probably the best place for software engineers (too bad I couldn't see it my self). During the on-site interviews I had the chance to launch at the in-Google restaurant, which was really amazing, providing dishes literally for any kind of diet. You will also talk to interesting people and if lucky you will meet some of them and talk about subjects you are keen on. It is a challenge worth taking and be prepared to deal with all possible outcomes.

In later blog posts I will give out the entire set of questions they asked me during the interviews. You can find the 1st Google Interview here.I have recorded more than 20 questions but unfortunately I am not free to disclose the questions I was asked on site (I am bound to an NDA-Non Disclosure Agreement) Till then, enjoy your holidays!

Hacking Java I

Well Java is said to be safe since JVM commonly takes care of everything (loading, resolution and so on). Actually it is. However this does not mean that Java is safe from careless usage.When JVM loads a class file, it does not take for granted that it was produced by some kind of Java compiler. It actually is interested in checking its file format.This process is known as bytecode verification and it is supposed to prevent from invoking code that seems to be messed up.

Whatever class fails the verification it is really a bad Java class. But this does not mean that classes that pass it are ok.

To demonstrate this I am going to develop a useful but harmless example to test a case where we compile Java source code and subsequently we deform the class file to alter its functionality.

Here is the code...

public class JavaHack {

public static void main(String[] args){

int a=6;
int b = DivideBy2(a);
int c = DivideBy3(a);
System.out.println(""+a+"/2 = "+b);
System.out.println(""+a+"/3 = "+c);
}

public static int DivideBy2(int i) {return i/2;}
public static int DivideBy3(int j) {return j/3;}

}

If compiled and run successfully we will finally get the output:
6/2=3
6/3=2

Now use a Hex editor, like HxD Editor.
Open the JavaHack class with the editor and search for the sequence: 0xB8 0x00 0x02 0x3D 0x1B ... and alter 0x02 byte to 0x03.
Then immediately(no more compilation) run the JavaHack class. The output will be:
6/2=2 (!)
6/3=2

The function DivideBy2 seems to be returning wrong results. What is actually going on is that we do not call this method any more. To explain, every method has an index into the method table in the class file. The DivideBy2 has id 2 and DivideBy3 has id 3. The sequence 0xB8 0x00 0x02 is actually invokestatic #2 in JVM code, meaning that it invokes the static method with id 2. Changing the value 0x02 to 0x03 actually calls the function DivideBy3, which eventually is called twice!! This explains the strange result of the modified class file.

The example can be easily extended and generalized to create more complex hacks (e.g. find out values of un-initialized variables and so on)

"The Perfect Logicians" Puzzle

Puzzles of any kind (mathematical, logic etc) is certainly a way to kill some time. It also can be a very efficient and clear way to test your abilities in dealing with complex situations and developing the proper solutions.

Personally I have often found myself derailing from my everyday routine, struggling to solve such problems. My favorites are the kind where the problem is easily stated (some lines), resists hard to usual thinking but surrenders easily to a different but also ingenious approach.
Enjoy!

The problem can be stated as follows.

We have two integers, say α and β, for which it is known that

β>α>1 and α+β<100

There are two perfect logicians, say P and S.
P is given the product of the numbers and S is given the sum of them.
P calls S on the phone and a short conversation follows:

P: I cannot find the numbers...
S: I knew that.
P: Hmm..Now I can!
S: Well, now I can find them too!

Can you find the numbers?
(Use of computer programming is advised!)


You can find a solution to the perfect logicians puzzle here.

The Man In Our Machines

And his name is Mark Zbikowski.

And to be honest, not all machines, but only Windows based.
(Sorry for the eye catch!)
In every application you start, in every dll file that is loaded on your RAM (whether on your desktop, laptop or PDA device), as long as it is Windows based, there are two magic bytes in head of all the others that have a very specific meaning. These are the initials of one of the first Microsoft employees that was involved on all crucial Windows development phases. As said his name is Mark Zbikowski.

Take any windows executable file, dll file, either for PC or Windows CE and you will notice that the first two bytes are 0x4D 0x5A or in ASCII code MZ. Every file conforming to the Windows PE(Portable Executable) format (exe, dll, ocx etc) has an introducing DOS Header.

DOS was Microsoft's first Operating System delivered with all IBM PCs and was entirely command line based. Executable files (technically files that the system loader could map into memory and hand over the CPU control) were also identified by the .exe .com or .bat extension. With the domination of the Win32 and GUI environments, every new program that required Win32 functionality (e.g. drawing) was not able to be hosted under "pure" DOS. The least they should do was to print an error message like "This program cannot be run in DOS mode". This is a commonly found string also in every PE file (although it can be altered on compilation time)

So every windows application or library has a DOS part (basically a DOS dump program that prints out your desired message). In the beginning of this part that is actually the beginning of the file, the two bytes of the key DOS developer, Mark Zbikowski, are found much like a legacy for us to keep in mind that computers have been much less capable.

In the beginning of the PC era, there were not many things that you could do with a computer. Just programs for simple mathematical operations and one-color command line text editors seemed more like a programmer's joke or an attempt to prove that nothing special could be done with these machines. The process address space was limited just to 64K. Programs used to be the same both in the disk and on memory. With a 16-bit memory pointer you could only reach out for 65536 bytes.

Things changed when Mark decided to put a header before the executable file (much following the Unix style) that would describe the entire file and basically its sections so that it would be possible to create a process image much richer than its disk one. This led to a better memory management and of course good news for developers. So, this header replacing machine specific assembly code, should simply mean...nothing. Zbikowski decided to place his initials and since then every windows 'component' carries this legacy.

Further Reading:
Mark Zbikowski Wikipedia Entry
Mark Zbikowski interview

In next posts I will try to give a brief overview of the PE format used in current Windows systems and the exciting amount of information you could retrieve by processing its raw bytes. (Did you know for example that Skype application was technically built in 1992 ? -to help you I was not there! )

Hello World!

The title is very familiar to most developers.

In case you are not familiar with the story, creating a program that displays a 'Hello World', is the first thing that the majority of developers does when learning a new platform or language. (just like 'mom' or 'dad' are a baby's first words)

That said, I would like to welcome you all, to a brand new development blog site, where I hope you will find what you are looking for. Which brings me to the next topic.

'Looking for' is the next thing after creating the 'Hello World' program..! It is somewhat frustrating but it is true, that developers have to make a lot of search (documentation, sample code etc) when trying to figure out HOW-TO get things done. It is times when documentation is not enough, you are fed up hitting on the wall and your last resort is requesting help from the community. I personally have been greatly benefited by developer blogs, forums and support. So, I decided to make a small contribution to this...

So, again a juicy welcome to you all and enjoy your visit!!