Interview Question

Latest Interview question by Brocade communication

1. Why do we need to send MSS to other side?
2. What is value of syn in finla ack of 2-way handshake?
3. if r1 and r2 router r connected to hub and some host on hub sends packet to some network then it reaches to both router then how do router decide that one on these 2 router have to f/w this packet to other router?
4. HTML call flow, content length.
5. DNS call flow
6. if we write yahoo.com and what will happen?
7. Black widow archecture.

1. what is reentrant code ?2. what is spin lock , bottom half , semaphore , mutex , tasklet (difference between them )?3. what is virtual memory and why we need it?4. find the mid node of singly link list in one pass ?5. reverse singly and doubly link list ?6. delete a node from lik list if u know only the address of node to be deleted ?7. 8, ,5,3 and measure 4 liters water problem ?8. if u have 10 number from 1 to 10 and array of 9 then how to find missing element in one pass ? (n(n+1)/2) 9. MSS how to get value of mss ? default 536 ? could be different for sender and reciver for same connection ?10. psedo header of TCP and UDP ?11. count the number of bits set in number (n = n & n-1);12. check if number is power of 2 or not ?13. change xth bit from integer ?14. what is mobile ip?15. what is priority inversion and priority inheritance and priority celling ?16. segmentation and fragmentation ?17. why tcp is three way handshak why not two way ? (as in ace of two way its diffciult to know if its a new SYN or retransmited SYN )18. Routing protocols ? 19. slow start and congestion avoidence ?20. mirror image of binarry tree ?21. create binarry tree form normal tree ?22. serching and sorting algo ?23. how to find loop in a singly link list ?24. IPC machenism ?25. fork and exec ?26. static , volatile , static function , union , register , address of registar variable (compile defined in gnu c if u try to get address of register variable then it will ignore register request)28. What is DMZ ?29. difference b/w switch and router ?30. IGMPv1 and IGMPv2 ?31. Tcp timers , keepalive , prove management etc.32. TCP connection setup ?33. function pointer ?34. what is finate state machine ? 35. how to check if character used in some string and other string is not same and that too in a single PASS ? ex "neeraj" & "jenar" should be same ? (and assign prime number to each character and add if sume is same then character are same)36. difference betwen normal os and RTOS (in rtos we can preempt kernel and know worst time of execution )37, how rtt is calculated in tcp ?38. trce route and path mtu discovery ?39. os scheduling algo ?

40. Write Addition of two numbers using Bitwise operators.

---------------------------------------------------------------------------
Lnode *reverse_list( Lnode *head )/********************************/{ Lnode *rhead = NULL, *head1;
while ( head != NULL ) { head1 = head->next; head->next = rhead; rhead = head; head = head1; }
return rhead;}

An alternative version:-----------------------
Function `reverse_list_r()' is a recursive version of `reverse_list()'.
This alternative uses `accumulator recursion', a form of recursion much used in functional language programming.Again, two lists are involved in the processing -- the original list, and the accumulating reverse-list. (The actual work of reversingthe list, and the recursion, takes place in the subsidiary function, `reverser()'.)
Lnode *reverse_list_r( Lnode *head )/**********************************/{ return reverser( head, NULL );}
Lnode *reverser( Lnode *head, Lnode *rhead )/******************************************/{ Lnode *head1;
if ( head == NULL ) return rhead; else { head1 = head->next; head->next = rhead; return reverser( head1, head ); }}
/***Discourse for Ex. K.3.2 (142--1998)===================================


----------------------------------------------
25. Reverse a linked list.
Ans: Possible answers -
iterative loop curr->next = prev; prev = curr; curr = next; next = curr->next endloop
recursive reverse(ptr) if (ptr->next == NULL) return ptr; temp = reverse(ptr->next); temp->next = ptr; return ptr; end
----------------------------------------
56. Write a program to remove duplicates from a sorted array.
ANS. int remove_duplicates(int * p, int size) { int current, insert = 1; for (current=1; current < size; current++) if (p[current] != p[insert-1]) { p[insert] = p[current]; current++; insert++; } else current++;
return insert;
} -------------------------------------------
reverse with single parameter
4. node * reverse (node * n) { node * m ;
if (! (n && n -> next)) return n ;
m = reverse (n -> next) ; n -> next -> next = n ; n -> next = NULL ; return m ; }-------------------------------
Bit-manipulation* 1. Reverse the bits of an unsigned integer.
* 2. Compute the number of ones in an unsigned integer.
3. Compute the discrete log of an unsigned integer.
* 4. How do we test most simply if an unsigned integer is a power of two?
5. Set the highest significant bit of an unsigned integer to zero.
6. Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).
Hints and Answers
1. #define reverse(x) \ (x=x>>16(0x0000ffff&x)<<16, x="(0xff00ff00&x)">>8(0x00ff00ff&x)<<8, x="(0xf0f0f0f0&x)">>4(0x0f0f0f0f&x)<<4, x="(0xcccccccc&x)">>2(0x33333333&x)<<2, x="(0xaaaaaaaa&x)">>1(0x55555555&x)<<1)
2. #define count_ones(x) \ (x=(0xaaaaaaaa&x)>>1+(0x55555555&x), \ x=(0xcccccccc&x)>>2+(0x33333333&x), \ x=(0xf0f0f0f0&x)>>4+(0x0f0f0f0f&x), \ x=(0xff00ff00&x)>>8+(0x00ff00ff&x), \ x=x>>16+(0x0000ffff&x))
3. #define discrete_log(h) \ (h=(h>>1)(h>>2), \ h=(h>>2), \ h=(h>>4), \ h=(h>>8), \ h=(h>>16), \ h=(0xaaaaaaaa&h)>>1+(0x55555555&h), \ h=(0xcccccccc&h)>>2+(0x33333333&h), \ h=(0xf0f0f0f0&h)>>4+(0x0f0f0f0f&h), \ h=(0xff00ff00&h)>>8+(0x00ff00ff&h), \ h=(h>>16)+(0x0000ffff&h)) If I understand it right, log2(2) =1, log2(3)=1, log2(4)=2….. But this macro does not work out log2(0) which does not exist! How do you think it should be handled?
4. #define power_of_two(x) \ ((x)&&(~(x&(x-1))))
5. (from Denis Zabavchik) Set the highest significant bit of an unsigned integer to zero #define zero_most_significant(h) \ (h&=(h>>1)(h>>2), \ h=(h>>2), \ h=(h>>4), \ h=(h>>8), \ h=(h>>16))
Graphics---------------------------------------
25. Reverse a linked list.
Ans: Possible answers -
iterative loop curr->next = prev; prev = curr; curr = next; next = curr->next endloop
recursive reverse(ptr) if (ptr->next == NULL) return ptr; temp = reverse(ptr->next); temp->next = ptr; return ptr; end ----------------------------------Kruskal's Algorithm (spanning tree)The steps are: The forest is constructed - with each node in a separate tree. The edges are placed in a priority queue. Until we've added n-1 edges, Extract the cheapest edge from the queue, If it forms a cycle, reject it, Else add it to the forest. Adding it to the forest will join two trees together. Every step will have joined two trees in the forest together, so that at the end, there will only be one tree in T. We can use a heap for the priority queue. The trick here is to detect cycles. For this, we need a union-find structure. --------------------------------------------------------------

Basic Slow-StartThe algorithm begins in the exponential growth phase initially with a congestion window size (cwnd) of 1 or 2 segments and increases it by 1 Segment Size (SS) for each ACK received. This behavior effectively doubles the window size each round trip of the network. This behavior continues until the congestion window size (cwnd) reaches the size of the receiver's advertised window or until a loss occurs.When a loss occurs half of the current cwnd is saved as a Slow Start Threshold (SSThresh) and slow start begins again from its initial cwnd. Once the cwnd reaches the SSThresh TCP goes into congestion avoidance mode where each ACK increases the cwnd by SS*SS/cwnd. This results in a linear increase of the cwnd.-----------------------------------------------------------
Hi,
carti wrote:> Can anyone who knows well explain with example> of what is spinlock?> ...
> Something like the following it says.> > spinlock like a semaphore but has no process list. And when> a process finds a lock closed by another process, its "spins"> around repeatedly, executing a tight instruction loop until the lock> becomes open.> > I dont especially understand what is spinning and executing a> right instruction loop.
Spinlock (aka busy lock) is when a thread repeatedly tests for acondition. Eg. Look at the following C code -
1. while (lock == 1) continue; /* tight loop */ 2. lock = 1; 3. /* critical section goes here */ 4. lock = 0;
When executing this code the thread waits for some other thread toset lock to zero. When lock is zero, the thread enters the criticalsection.
A tight loop is a loop with a very small body. Spinning is the slangfor repeatedly executing a tight loop that effectively does nothing(like line 1 above).
Note: a race condition exists between lines 1,2. There exists thepossibility that more than one thread can enter the critical section atthe same time. This is because, the "test" to check "lock == 0" and the"set" "lock = 1" operations are not atomic. Atomic test-and-set supportfrom the hardware helps in preventing this. See the 'membar' (memorybarrier) instruction on Alpha architectures for how atomic test-and-setis implemented in hardware.
Spinlocks have the following features - 1. eats CPU - you are constantly checking lock status 2. you cannot hold this lock for long without degrading performance the rule of thumb goes that spinlocks are fine upto 150 iterations of your (while) loop. 3. on a lot of CPU architectures (esp ones that implement atomic test-and-set instructions), spinlocks are cheap to create. 4. can be implemented without kernel support
Semaphores are different in that while waiting to obtain a lock, athread is 'put to sleep' and does not consume any CPU cycles. Thethread is woken up (by the kernel or the threading library) when thelock becomes available. Creating/using semaphores is expensive becausethe kernel/threading library has to setup/maintain some internal datastructures, so its best to use them in cases where you have to wait along time to obtain a lock.
HTH,
- Raja------------------------------------------------------------------
Mutex & semaphore
There synchronization semantics are very different:
mutexes allows serialization of access to a given resource i.e. multiple threads wait for a lock, one at a time and as previously said, the thread owns the lock until it is done, most importantly only this particular thread can unlocks it.a binary semaphore is a counter with value 0 and 1, a task blocking on it until any task does a sem_post. The semaphore advertise that a resource is available, and it provides the mechanism to wait until it is signaled as being available.As such one can see a mutex as a token passed from task to tasks and a semaphore as traffic red-light (it signals someone that it can proceed).
There is a lot of confusion around these two concepts. They permit the same kind of feature i.e. synchronization but as I explained with different semantics.
Semaphores are usually more expensive to use than mutex, but they provide you sometimes more reliability. For example, let’s say you have two threads, thread A and thread B trying to serialize access to resource R.
The mutex way would be;
step 00 – create a lock objectstep 01 – A request the lockstep 02 – B request the lockstep 03 – A grab the lockstep 04 – A uses Rstep 05 – A release the lockstep 06 – B grab the lockstep 07 – B uses Rstep 08 – A request the lockstep 09 – B release the lockstep 10 – A grab the lock
Q: What happens if thread B returns between step 7 and step 9 ?A: step 10 may never occurs …
In this scenario there is no way to recover, the mutex is an opaque object and you are stuck in a deadlock situation. If you are using C++, you may get over it using RAII, but if you use plain C, well that’s harder.
With semaphores things are a little bit different, you can make step 10 happen even if your thread leaves early. You need an external actor of course (a monitoring thread for example) that upon thread completion may resume the work flow.
Since people are confused by semaphores or misuse them more frequently, here are a few examples on how to use them.
Serializing access using a semaphore
Note that when using a binary semaphore to serialize access to a resource, you need to initialize it with the value 1, meaning resource available.
Requesting the lock is done by calling sem_wait() on it, and releasing the lock is done by calling sem_post():
// thirst get a semaphore and initialize it with the value 1sem_init( … )…
// lock the resourcesem_wait( …)
… do some stuff …
// release the resourcesem_post( … )
The consumer / producer model
if you initialize the semaphore withe the value 0 and call sem_wait on it, the semantic is different, you are waiting for some one to signal you that there is some job to do.In this scenario, the semaphore is not used to serialize access to a particular resource, it is used as signaling mechanism.A consumer is waiting for a consumer to signal him that some data is available or that there is work to do.
very simple and effective, that’s why semaphore are used so frequently for producer/consumer work flows.
// thirst get a semaphore and initialize it with the value 0sem_init( … )…
while( true ){// wait for some job to dosem_wait( …)
… work hard on it …}
// yep there is no sem_post here: the producer, that gives this task// work to do is supposed to be the one calling sem_post()
check your platform semaphore implementation, sem_post(), sem_wait() and sem_init() are the API to use POSIX semaphores.
Your platform API may be different, but the concepts are the same.
Enjoy and share.-------------------------------------------------------
Priority inversion
http://www.netrino.com/Embedded-Systems/How-To/RTOS-Priority-Inversion
--------------------------------------------------------
good interview questions
http://www.techinterviews.com/programming-puzzles-riddles-and-interview-problems-------------------------------------------------------
puzzels
http://gurmeetsingh.wordpress.com/puzzles/---------------------------------------------------------