Google App Engine

Google announced yesterday about their ambitious project "Google App Engine",

The idea for Google is why we should spend so much effort developing applications? Lets make developers outside Google develop applicatons for us. This is the same idea like "YouTube" the users upload the videos for Google.

Each user gets free 500MB of persistent storage and bandwidth for about 5 million page views a month.

Don't hurry to register since the project is limited to the first 10,000 developers, And there are more than 10,000 developers which already registered.

When I tried to check the App Gallery all the applications returned the following error after trying to login: "The requested page is expiered".


Google App Engine

GWT vs. Flex

This article would compare Google GWT (Google Web Toolkit) and Adobe Flex 2 and would describe the advantages and disadvantages of each of these technologies.
This two technologies are both Rich Internet Application (RIA) frameworks.

GWT Advantages:

• Doesn't require plug in installation on the client side
• GWT doesn't require the user to know JavaScript since the code is written in Java
• GWT doesn't cost money since it is Open Source.
• Changes in the Client side are immediately shown on the browser by using refresh, no need to restart the server.
• GWT can be easily debugged in hosted mode.
• There is compatible between different web browsers.

GWT Disadvantages:

• The html and JavaScript code which GWT generates is pretty heavy and not necessary fully optimized.
• GWT doesn't come out of the box with all the possible widgets, there is a need to use extra components

Flex Advantages:

• The UI looks nicer then plain HTML/JavaScript code, It contains huge amount of animations, widgets etc'
• Compatible between different web browsers
• Flex 2 SDK and Flex Builder 2 for Education are both free
• Google can index SWF files

Flex Disadvantages:

• It requires plug in installation on the client side , however this may not be disadvantage since Adobe claims that Flash is installed on more then 99% percent of users.
• Flex Builder 2 costs some money

Google Interview Question - Part 7

Here is another question:

Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.

And here is the answer:

A:

private static String match(String a, String b)

{

String result = "";

Set lettersSet = new HashSet(26);

for (int i=0; i

lettersSet.add(new Character(b.charAt(i)));

}

for (int i=0; i

if (lettersSet.contains(new Character(a.charAt(i)))) {

result=result+a.charAt(i);

}

}

return result;

}

Google Interview Question - Part 6

Continue with the question in the previous post:
http://j2ee-now.blogspot.com/2007/12/google-interview-questions-part-5.html

Here is the answer to the question,
If two threads would run in parallel and call this method with values 10 and 7,
The first thread would create the array with size 10 and then thread 2 would re-initialize the same static array with size 7, then the fist thread would run on the array from 0 to 9 and would put values inside however the array size is now 7 so on list[7] it would throw the exception.

Google Interview Questions Part 5

Here is a snippest of code, how it is possible that the code would throw ArrayIndexOutOfBoundsException ?

private static String[] list = null;

public static String[] getArray(size) {
list= new String[size];
for (int i = 0; i < size; i++) {
list[i] = "a" + i
}
return list;
}

This question is a bit tricky

Google Interview Questions Part 4

Here are some other questions and solutions

Q: N threads .. n resources .. what protocol do you use to ensure no deadlocks occur?
A1: Avoiding Deadlocks with Lock Leveling, each thread would have different level, thread with high level would be able to lock thread with lower level but not contrary.
A2: Avoid acquiring more then one lock at a time.
A3: Acquire the lock always in the same order. A4: Shrink synchronized blocks.

Q: You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?
A1: It might be using time, or perhaps random numbers. Or it does nasty things with memory. Or it could be running under windows.
A2: There might be multiple recursions in the code which are causing a stack overflow, cause "Out Of Memory" exception
A3: A probable cause would be an uninitialized pointer/variable being used

Google Interview Questions Part 3

Q: Here are some more questions and answers:
Which bits are on in the three packets of the handshake?

A: it’s SYN, SYN+ACK, ACK, The source want to send data to he destination, In first step it sends SYN to ask the desination if he is ready to receive data, then the destination wants to answer that he is ready for receiving bits
so he sends SYN+ACK, then the source need to confirm to the destination that he got is request so he send back ACK.

TCP is connection oriented while UDP is not.
TCP: connection establishment -> data transfer -> connection termination

1. The initiating host (client) sends a synchronization (SYN flag set) packet to initiate a connection. Any SYN packet holds a Sequence Number. The Sequence Number is a 32-bit field in TCP segment header. For example let the Sequence Number value for this session be x.
2. The other host receives the packet, records the Sequence Number of x from the client, and replies with an acknowledgment and synchronization (SYN-ACK). The Acknowledgment Number is a 32-bit field in TCP segment header. It contains the next sequence number that this host is expecting to receive (x + 1). The host also initiates a return session. This includes a TCP segment with its own initial Sequence Number value of y.
3. The initiating host responds with a next Sequence Number (x+1) and a simple Acknowledgment Number value of y + 1, which is the Sequence Number value of the other host + 1.



Q: What is Karatsuba algorithm?
A: It's algorithm to do mulipilacation of two large positive numbers with n digits in the complexity of O(n^2)


Q: Tell me what happens when you type www.google.com into a web browser
A1: Explaining that DNS operates via UDP, port 53, and so forth …, the ip address is returned from the DNS
(Sometimes the ISP cache this URL->IP mapping and this save the time of accessing the DNS).
and HTTP GET request is send to google.com server, which return the HTML of the google.com homepage.
A2: Google's DNS servers perform load balancing to allow the user to access Google's content most rapidly. This is done by sending the user the IP address of a cluster that is not under heavy load, and is geographically proximate to them. Each cluster has a few thousand servers, and upon connection to a cluster further load balancing is performed by hardware in the cluster, in order to send the queries to the least loaded Web Server

Google Interview Questions Part 2

Well here is the solution for the question from

http://j2ee-now.blogspot.com/2007/12/google-interview-questions-part-1.html

First you should pass on the list and create a new list with the summary of the numbers till now, for example if the list is:

-7 12 -5 13 -2

Then the new list would be:

-7 5 0 13 11

The subset with holds the largest sequential sum is the subset from the lowest number in the new list plus index 1 (In our case -7 (index 0) is the lowest so we start from 5 (index 1)) till the highest number in the list which is 13 (index 3) so the result is (12, -5, 13) which it's sum is 20.

Why does it work? because if we went from he lowest sum till now to the highest sum till now this is the biggest different of the numbers in the summary therefore this numbers sum would be the largest in the list.



You can find more Google Interview Questions here:

Google Interview Questions Part 3
Google Interview Questions Part 4
Google Interview Questions Part 5
Google Interview Questions Part 6
Google Interview Questions Part 7

Google Interview Questions Part 1

A friend of mine was interview for a position in Google, he got this hard question asked:

"You have a list of numbers which some of them are negative and some of them are positive, find out the largest sum of sequential subset of numbers from this list."

For example:

-5, 20, -4, 10, -18

The solution is the subset [20, -4, 10] which its sum is 26

The solution for this question is not summary the positive numbers or sort the list because the subset needs to be sequential.

A possible not efficient answer would be to to calculate the summary of all the possible subsets in the list but the complexity of this solution is O(N^2)

However the interviewer wanted a solution of O(N) !!!

Let see you solve this problem in few minutes...

In the next post I would publish the solution