G a y le L a a k

Solutions to Chapter 17 |  Networking
254
CareerCup com
17 4  What is a network / subnet mask?  Explain how host A sends a message / packet to 
host B when:
 (
a) both are on same network and (b) both are on different networks   
Explain which layer makes the routing decision and how 
 
 
pg 84
SOLUTION
A mask is a bit pattern used to identify the network/subnet address   The IP address consists 
of two components: the network address and the host address 
The IP addresses are categorized into different classes which are used to identify the network 
address 
Example: Consider IP address 152 210 011 002  This address belongs to Class B, so:
Network Mask: 11111111.11111111.00000000.00000000
Given Address: 10011000.11010101.00001011.00000010
By ANDing Network Mask and IP Address, we get the following network address:
10011000.11010101.00000000.00000000 (152.210.0.0)
Host address: 00001011.00000010
Similarly, a network administrator can divide any network into sub-networks by using subnet 
mask   To do this, we further divide the host address into two or more subnets 
For example, if the above network is divided into 18 subnets (requiring a minimum of 5 bits 
to represent 18 subnets), the first 5 bits will be used to identify the subnet address 
Subnet Mask: 11111111 11111111 11111000 00000000 (255 255 248 0)
Given Address: 10011000 11010101 00001011 00000010
So, by ANDing the subnet mask and the given address, we get the following subnet address: 
10011000 11010101 00001000 00000000 (152 210 1 0)
How Host A sends a message/packet to Host B:
When both are on same network: the host address bits are used to identify the host within 
the network 
Both are on different networks: the router uses the network mask to identify the network and 
route the packet   The host can be identified using the network host address 
The network layer is responsible for making routing decisions   A routing table is used to 
store the path information and the cost involved with that path, while a routing algorithm 
uses the routing table to decide the path on which to route the packets 
Routing is broadly classified into Static and Dynamic Routing based on whether the table is 
fixed or it changes based on the current network condition 

Solutions to Chapter 17 |  Networking
Cracking the Coding Interview | Knowledge Based
255
17 5  What are the differences between TCP and UDP?  Explain how TCP handles reliable 
delivery (explain ACK mechanism), flow control (explain TCP sender’s / receiver’s win-
dow) and congestion control  
 
pg 84
SOLUTION
TCP (Transmission Control Protocol): TCP is a connection-oriented protocol   A connection can 
be made from client to server, and from then on any data can be sent along that connection 
 
»
Reliable - when you send a message along a TCP socket, you know it will get there unless 
the connection fails completely   If it gets lost along the way, the server will re-request 
the lost part   This means complete integrity; data will not get corrupted 
 
»
Ordered - if you send two messages along a connection, one after the other, you know 
the first message will get there first   You don’t have to worry about data arriving in the 
wrong order 
 
»
Heavyweight - when the low level parts of the TCP “stream” arrive in the wrong order, re-
send requests have to be sent   All the out of sequence parts must be put back together, 
which requires a bit of work 
UDP(User Datagram Protocol): UDP is connectionless protocol  With UDP you send messages 
(packets) across the network in chunks 
 
»
Unreliable - When you send a message, you don’t know if it’ll get there; it could get lost 
on the way 
 
»
Not ordered - If you send two messages out, you don’t know what order they’ll arrive in 
 
»
Lightweight - No ordering of messages, no tracking connections, etc   It’s just fire and 
forget!  This means it’s a lot quicker, and the network card / OS have to do very little work 
to translate the data back from the packets 
Explain how TCP handles reliable delivery (explain ACK mechanism), flow control (explain TCP 
sender’s/receiver’s window).
For each TCP packet, the receiver of a packet must acknowledge that the packet is received  
If there is no acknowledgement, the packet is sent again  These guarantee that every single 
packet is delivered   ACK is a packet used in TCP to acknowledge receipt of a packet   A TCP 
window is the amount of outstanding (unacknowledged by the recipient) data a sender can 
send on a particular connection before it gets an acknowledgment back from the receiver 
that it has gotten some of it 
For example, if a pair of hosts are talking over a TCP connection that has a TCP window with 
a size of 64 KB, the sender can only send 64 KB of data and then it must wait for an acknowl-
edgment from the receiver that some or all of the data has been received   If the receiver 

Solutions to Chapter 17 |  Networking
256
CareerCup com
acknowledges that all the data has been received, then the sender is free to send another 64 
KB   If the sender gets back an acknowledgment from the receiver that it received the first 
32 KB (which could happen if the second 32 KB was still in transit or it could happen if the 
second 32 KB got lost), then the sender can only send another additional 32 KB since it can’t 
have more than 64 KB of unacknowledged data outstanding (the second 32 KB of data plus 
the third) 
Congestion Control
The TCP uses a network congestion avoidance algorithm that includes various aspects of an 
additive-increase-multiplicative-decrease scheme, with other schemes such as slow-start in 
order to achieve congestion avoidance 
There  are  different  algorithms  to  solve  the  problem;  Tahoe  and  Reno  are  the  most  well 
known   To avoid congestion collapse, TCP uses a multi-faceted congestion control strategy  
For each connection, TCP maintains a congestion window, limiting the total number of unac-
knowledged packets that may be in transit end-to-end   This is somewhat analogous to TCP’s 
sliding window used for flow control   TCP uses a mechanism called slow start to increase the 
congestion window after a connection is initialized and after a timeout   It starts with a win-
dow of two times the maximum segment size (MSS)   Although the initial rate is low, the rate 
of increase is very rapid: for every packet acknowledged, the congestion window increases 
by 1 MSS so that for every round trip time (RTT), the congestion window has doubled   When 
the congestion window exceeds a threshold ssthresh the algorithm enters a new state, called 
congestion avoidance   In some implementations (i e , Linux), the initial ssthresh is large, and 
so the first slow start usually ends after a loss   However, ssthresh is updated at the end of 
each slow start, and will often affect subsequent slow starts triggered by timeouts 

Solutions to Chapter 18 |  Threads and Locks
Cracking the Coding Interview | Knowledge Based
257
18 1  What’s the difference between a thread and a process?
 
pg 86
SOLUTION
Processes and threads are related to each other but are fundamentally different  
A process can be thought of as an instance of a program in execution   Each process is an in-
dependent entity to which system resources (CPU time, memory, etc ) are allocated and each 
process is executed in a separate address space   One process cannot access the variables 
and data structures of another process   If you wish to access another process’ resources, 
inter-process communications have to be used such as pipes, files, sockets etc  
A thread uses the same stack space of a process   A process can have multiple threads   A key 
difference between processes and threads is that multiple threads share parts of their state  
Typically, one allows multiple threads to read and write the same memory (no processes can 
directly access the memory of another process)  However, each thread still has its own regis-
ters and its own stack, but other threads can read and write the stack memory  
A thread is a particular execution path of a process; when one thread modifies a process 
resource, the change is immediately visible to sibling threads 

Solutions to Chapter 18 |  Threads and Locks
258
CareerCup com
18 2  How can you measure the time spent in a context switch?
 
pg 86
SOLUTION
This is a tricky question, but let’s start with a possible solution 
A context switch is the time spent switching between two processes (e g , bringing a wait-
ing process into execution and sending an executing process into waiting/terminated state)  
This  happens  in  multitasking    The  operating  system  must  bring  the  state  information  of 
waiting processes into memory and save the state information of the running process 
In order to solve this problem, we would like to record timestamps of the last and first in-
struction of the swapping processes  The context switching time would be the difference in 
the timestamps between the two processes 
Let’s take an easy example: Assume there are only two processes, P1 and P2 
P1 is executing and P2 is waiting for execution   At some point, the OS must swap P1 and 
P2—let’s assume it happens at the Nth instruction of P1   So, the context switch time for this 
would be Time_Stamp(P2_1) – Time_Stamp(P2_N)
Easy enough   The tricky part is this: how do we know when this swapping occurs?  Swap-
ping is governed by the scheduling algorithm of the OS   We can not, of course, record the 
timestamp of every instruction in the process  
Another issue: there are many kernel level threads which are also doing context switches, 
and the user does not have any control over them 
Overall, we can say that this is mostly an approximate calculation which depends on the 
underlying OS   One approximation could be to record the end instruction timestamp of a 
process and start timestamp of a process and waiting time in queue 
If the total timeof execution of all the processes was T, then the context switch time = T – 
(SUM for all processes (waiting time + execution time)) 

Solutions to Chapter 18 |  Threads and Locks
Cracking the Coding Interview | Knowledge Based
259
18 3  Implement a singleton design pattern as a template such that, for any given class 
Foo, you can call Singleton::instance() and get a pointer to an instance of a singleton 
of type Foo   Assume the existence of a class Lock which has acquire() and release() 
methods   How could you make your implementation thread safe and exception safe?
 
pg 86
SOLUTION
1 
using namespace std;
2 
/* Place holder for thread synchronization lock */
3 
class Lock {
4 
public:
5 
 
Lock() { /* placeholder code to create the lock */ }
6 
 
~Lock() { /* placeholder code to deallocate the lock */ }
7 
 
void AcquireLock() { /* placeholder to acquire the lock */ }
8 
 
void ReleaseLock() { /* placeholder to release the lock */ }
9 
};
10 
11 
/* Singleton class with a method that creates a new instance of the 
12 
 * class of the type of the passed in template if it does not 
13 
 * already exist. */
14 
template  class Singleton {
15 
 private:
16 
 
static Lock lock;
17 
 
static T* object;
18 
 protected:
19 
 
Singleton() { };
20 
 public:
21 
 
static T * instance();
22 
}; 
23 
Lock Singleton::lock;
24 
25 
T * Singleton::Instance() {
26 
 
/* if object is not initialized, acquire lock */
27 
 
if (object == 0) {
28 
 
 
lock.AcquireLock();
29 
 
 
/* If two threads simultaneously check and pass the first “if” 
30 
 
 
 * condition, then only the one who acquired the lock first
31 
 
 
 * should create the instance */
32 
 
 
if (object == 0) {
33 
 
 
 
object = new T;
34 
 
 
}
35 
 
 
lock.ReleaseLock();
36 
 
}
37 
 
return object;
38 
}

Solutions to Chapter 18 |  Threads and Locks
260
CareerCup com
39 
40 
int main() {
41 
 
/* foo is any class defined for which we want singleton access */
42 
 
Foo* singleton_foo = Singleton::Instance(); 
43 
 
return 0;
44 
}
The general method to make a program thread safe is to lock shared resources whenever 
write permission is given   This way, if one thread is modifying the resource, other threads 
can not modify it 

Solutions to Chapter 18 |  Threads and Locks
Cracking the Coding Interview | Knowledge Based
261
18 4  Design a class which provides a lock only if there are no possible deadlocks 
 
 
pg 86
SOLUTION
For our solution, we implement a wait / die deadlock prevention scheme 
1 
class MyThread extends Thread {
2 
 
long time;
3 
 
ArrayList res = new ArrayList(); 
4 
 
public ArrayList getRes() { return res; }
5 
6 
 
public void run() {
7 
 
 
/* Run infinitely */
8 
 
 
time = System.currentTimeMillis();
9 
 
 
int count = 0;
10 
 
 
while (true) {
11 
 
 
 
if (count < 4) {
12 
 
 
 
 
if (Question.canAcquireResource(this, 
13 
 
 
 
 
 
 
 
 
 
 
 
 
 Question.r[count])) {
14 
 
 
 
 
 
res.add(Question.r[count]);
15 
 
 
 
 
 
count++;
16 
 
 
 
 
 
System.out.println(“Resource: [“ + 
17 
 
 
 
 
 
 
Question.r[count - 1].getId() + “] acquired by 
18 
 
 
 
 
 
 
thread: [“ + this.getName() + “]”);
19 
 
 
 
 
 
try {
20 
 
 
 
 
 
 
sleep(1000);
21 
 
 
 
 
 
} catch (InterruptedException e) {
22 
 
 
 
 
 
 
e.printStackTrace();
23 
 
 
 
 
 
}
24 
 
 
 
 
}
25 
 
 
 
}
26 
 
 
 
else {
27 
 
 
 
 
this.stop();
28 
 
 
 
}
29 
 
 
}
30 
 
}
31 
32 
 
public long getTime() { return time; }
33 
 
public void setRes(ArrayList res) { this.res = res; }
34 
 
MyThread(String name) {
35 
 
 
super(name);
36 
 
}
37 
}

Solutions to Chapter 18 |  Threads and Locks
262
CareerCup com
18 5  Suppose we have the following code:
 
class Foo {
 
public:
 
 
A(.....); /* If A is called, a new thread will be created and 
 
 
 
 
   * the corresponding function will be executed. */
     
B(.....); /* same as above */
     
C(.....); /* same as above */
 
} 
 
Foo f;
 
f.A(.....);
 
f.B(.....);
 
f.C(.....);
i)  Can you design a mechanism to make sure that B is executed after A, and C is ex-
ecuted after B?
iii) Suppose we have the following code to use class Foo  We do not know how the 
threads will be scheduled in the OS 
 
Foo f;
    f.A(.....); f.B(.....); f.C(.....); 
 
f.A(.....); f.B(.....); f.C(.....);
Can you design a mechanism to make sure that all the methods will be executed in 
sequence?
 
pg 86
SOLUTION
i) Can you design a mechanism to make sure that B is executed after A, and C is executed after B?
1 
Semaphore s_a(0);
2 
Semaphore s_b(0);
3 
A {
4 
 
/***/
5 
 
s_a.release(1);
6 
}
7 
B {
8 
 
s_a.acquire(1);
9 
 
/****/
10 
 
s_b.release(1);
11 
}
12 
C {
13 
 
s_b.acquire(1);
14 
 
/******/
15 
}
ii) Can you design a mechanism to make sure that all the methods will be executed in sequence?
1 
Semaphore s_a(0);

Solutions to Chapter 18 |  Threads and Locks
Cracking the Coding Interview | Knowledge Based
263
2 
Semaphore s_b(0);
3 
Semaphore s_c(1);
4 
A {
5 
 
s_c.acquire(1);
6 
 
/***/
7 
 
s_a.release(1);
8 
}
9 
B {
10 
 
s_a.acquire(1);
11 
 
/****/
12 
 
s_b.release(1);
13 
}
14 
C {
15 
 
s_b.acquire(1);
16 
 
/******/
17 
 
s_c.release(1);
18 
}

Solutions to Chapter 18 |  Threads and Locks
264
CareerCup com
18 6  You are given a class with synchronized method A, and a normal method C  If you 
have two threads in one instance of a program, can they call A at the same time? Can 
they call A and C at the same time?
 
pg 86
SOLUTION
Java provides two ways to achieve synchronization: synchronized method and synchronized 
statement 
Synchronized method: Methods of a class which need to be synchronized are declared with 
“synchronized” keyword   If one thread is executing a synchronized method, all other threads 
which want to execute any of the synchronized methods on the same objects get blocked 
Syntax: method1 and method2 need to be synchronized
1 
public class SynchronizedMethod {
2 
 
// Variables declaration
3 
 
public synchronized returntype Method1() {
4 
 
 
// Statements
5 
 
}
6 
 
public synchronized returntype method2() {
7 
 
 
// Statements
8 
 
}
9 
 
// Other methods
10 
}
Synchronized statement: It provides the synchronization for a group of statements rather 
than a method as a whole   It needs to provide the object on which these synchronized state-
ments will be applied, unlike in a synchronized method 
Syntax: synchronized statements on “this” object
1 
synchronized(this) {
2 
 
/* statement 1
3 
 
 * ...
4 
 
 * statement N */
5 
} 
i) If you have two threads in one instance of a program, can they call A at the same time?
Not possible; read the above paragraph 
ii) Can they call A and C at the same time?
Yes  Only methods of the same object which are declared with the keyword synchronized 
can’t be interleaved 

Solutions to Chapter 19 |  Moderate
Cracking the Coding Interview | Additional Review Problems
265
19 1  Write a function to swap a number in place without temporary variables 
 
 
 
pg 89
SOLUTION
This is a classic interview problem   If you haven’t heard this problem before, you can ap-
proach it by taking the difference between a and b:
1 
public static void swap(int a, int b) {
2 
 
a = b - a; // 9 - 5 = 4
3 
 
b = b - a; // 9 - 4 = 5
4 
 
a = a + b; // 4 + 5 = 9
5 
 
 
6 
 
System.out.println(“a: “ + a);
7 
 
System.out.println(“b: “ + b);
8 
}
You can then optimize it as follows:
1 
public static void swap_opt(int a, int b) {
2 
 
a = a^b; 
3 
 
b = a^b; 
4 
 
a = a^b; 
5 
 
6 
 
System.out.println(“a: “ + a);
7 
 
System.out.println(“b: “ + b);
8 
}

Solutions to Chapter 19 |  Moderate
266
CareerCup com
19 2  Design an algorithm to figure out if someone has won in a game of tic-tac-toe 
 
pg 89
SOLUTION
The first thing to ask your interviewer is whether the hasWon function will be called just 
once, or multiple times   If it will be called multiple times, you can get a very fast algorithm 
by amortizing the cost (especially if you can design your own data storage system for the 
tic-tac-toe board) 
Approach #1: If hasWon is called many times
There are only 3^9, or about twenty thousand tic-tac-toe boards   We can thus represent our 
tic-tac-toe board as an int, with each digit representing a piece (0 means Empty, 1 means 
Red, 2 means Blue)   We set up a hashtable or array in advance with all possible boards as 
keys, and the values are 0, 1, and 2   Our function then is simply this:
int hasWon(int board) {
  return winnerHashtable[board];
}
Easy!
Approach #2: If hasWon is only called once
1 
enum Piece { Empty, Red, Blue };
2 
enum Check { Row, Column, Diagonal, ReverseDiagonal }
3 
 
4 
Piece getIthColor(Piece[][] board, int index, int var, Check check) {
5 
 
if (check == Check.Row) return board[index][var];
6 
 
else if (check == Check.Column) return board[var][index];
7 
 
else if (check == Check.Diagonal) return board[var][var];
8 
 
else if (check == Check.ReverseDiagonal) 
9 
 
 
return board[board.length - 1 - var][var];
10 
 
return Piece.Empty;
11 
}
12 
 
13 
 Piece getWinner(Piece[][] board, int fixed_index, Check check) {
14 
 
Piece color = getIthColor(board, fixed_index, 0, check);
15 
 
if (color == Piece.Empty) return Piece.Empty;
16 
 
for (int var = 1; var < board.length; var++) { 
17 
 
 
if (color != getIthColor(board, fixed_index, var, check)) {
18 
 
 
 
return Piece.Empty;
19 
 
 
}  
20 
 
}
21 
 
return color;
22 
}
23