Monday, December 17, 2007

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 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 server, which return the HTML of the 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

1 comment:

Ray Cromwell said...

Karatsuba is not O(n^2), that's the naive algorithm. It's O(n^lg(3))


RSS Feeds Submission Directory