Wednesday, August 28, 2013

WaTER JuGgggggg ProBlem

After a long time i am writing post in my blog. Hereafter i am planning to  post one algorithm on each day. It will be useful to me and peoples who are reading my blog also. I will try guys. I am not sure. Today i am discussing abt most famous puzzle (water jug problem.)
Question:

Given two vessels, one of which can accommodate a liters of water and the other which can accommodate b liters of water, determine the number of steps required to obtain exactly c liters of water in one of the vessels. You have infinite supply of water.
At the beginning both vessels are empty. The following operations are counted as ‘steps’:
  • emptying a vessel,
  • filling a vessel,
  • pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.
For example , you have 3 litres of water jug and 5 litres capacity of water jug, users wants 4 litres in any of jugs means , how you will get it. Here the following processes will help u to get 4 litres.

assume A-5, B-3
                          A              B
fill ()                  5               0
transfer()            2               3
empty()              2               0
transfer()            0               2
fill()                   5               2
transfer()            4               1
 
wow. finally u got 4 litres in one jug. I hope u understand the above processes. Next we will discuss how to write programs for getting no. of steps to reach final output.

Assume A-5, B-3, C-4

if(A>C)  we can get  C litres of water in A
if(B>C) we can get C litres of water in B
if both (A and B > C) we can get C litres of water in A or B

Algorithm is ,

if A>C & B<C)  transfer A->B until you get C litres of water in A
and viceversa.
in last case. if both are bigger than C means, transfer from A->B or B->A.

in first case (A>C), first fill 5 to A, and transfer to B upto it reaches the capacity and

return the transferred to A and reduces the current amount in A .

Now I hope you understand the logic.

Now we will write program for this.

Program:

#include<iostream>
#include"Jug.h"
using namespace std;
int main()
{
 Jug j1(3,0),j2(5,0);

 int no=4;
 int count;
 count=j2.make(no,j1); // do comparisons which objects passes , other object as argument. i am very lazy doing like these things.

 if(!count)
  cout<<"failed to make"<<endl;
 else
  cout << "no. of steps : " << count << endl;

}

program2: jug.cpp

#include "Jug.h"
#include<iostream>
using namespace std;
int count=0;
Jug::Jug(int c,int curr)
{
 this->Capacity=c;
 this->Current=curr;
}

Jug::~Jug(void)
{
}
int Jug::make(int no,Jug &V2)
{

 if(CheckGCD(Capacity,V2.Capacity)!=1 || Capacity< no)  // we have to check if gcd is exist or not.
 {
  cout<< "Solution not exist" << endl;
 
  return 0;
 }
 while(Current!=no)  // until u get the 4
 {
  ++count;
 
  if(!Current)
  {
   Current=Capacity;   // if empty means fill the jug with full capacity
 
   cout<<"fill() of high quantity vessel"<<endl;
  }
 
  cout<<"current: "<<Current<<endl;
    
  cout<<"transfer()"<<endl;
  Current=Current-V2.transfer(Current);// transfer the amount of water in Jug 1
 
  if(!Current)
 
   cout<<"empty() of high quantity vessel"<<endl;
  if(V2.Current==V2.Capacity)
    {
     V2.empty();
    
     cout<< "empty() of less quantity vessel" <<endl;
    }
 }
 cout<<"current"<<Current<<endl;
 return count;
}

int Jug::transfer(int amount)
{
 int transferred=0;
 if(Current+ amount > Capacity )
 {
  transferred=Capacity-Current;
 
  Current=Capacity;
  cout<<"fill() of less quantity vessel" << endl;
 
  return transferred;
 }
 else

 {
  Current=Current+ amount;

  cout<<"fill() of less quantity vessel" << endl;
  return amount;
 }

}
void Jug::empty()
{
 Current=0;
}
int CheckGCD(int a,int b)
{
 return b? CheckGCD(b, a % b) : a;
}

Jug.h contains declarations for all the functions.

int CheckGCD(int, int);
class Jug
{
 int Capacity,amount,Current;
public:
 Jug(int , int);
 ~Jug(void);
 void empty();
 int transfer(int );
 int make(int , Jug &);

};

reply if any test cases are wrong in this program.


References:

                  http://amrendra.in/2012/09/13/water-jug-problem/







 

Tuesday, January 22, 2013

Recover Ubuntu/Linux mint After Installing Win 7/xp/vista.

Hi guys,
           Many of the users, using dual boot system (windows 7 + linux mint/ubuntu). Win 7 created a lot of problem due to viruses. So many of the times, win 7 crashes. So when u are installing win 7 again , old ubuntu got disappeared. This post will help u a lot to recover old ubuntu. there is no need to reinstall ubuntu/linux mint again.
           By default, Windows 7 takes over your boot-up process and wants to be your only OS, and Linux treats Windows like a weekend hobby you keep in a shed somewhere on your hard drive. Follow through this guide, and I'll explain how to rebuild a system from the ground up with Windows 7 and Ubuntu, with either a backed-up and cleaned-out hard drive (recommended) or Windows 7 already installed. When we're done, you can work and play in either operating system, quickly and conveniently access your documents, music, pictures, and other files without worry or inconvenience, and boot into either system without having to worry about whether Windows is going to get mad at you.

For this , u need win7 installation disc, ubuntu/mint live cd, internet connection for downloading boot-repair.

Boot-Repair  is an Ubuntu tool which can easily resolve such issues. As this is a GUI based application, therefore, you will require being logged into your operating system for it to work. Therefore, despite the boot issues, you should be able to get access to your desktop for this app to resolve the boot issues. Having said that, the issues which it resolves mainly do not cause the inability of a system to loose boot functionality. For example, the GRUB boot problems may be causing inconsistency in allowing you to boot from your OS. Similarly, if you have installed another operating system, you might not be able to login from Ubuntu by default.

So, by reinstalling grub we can recover old ubuntu/mint.

steps:

1. after installing win7, insert live cd of ubuntu/linux mint.

2. connect to internet in ubuntu/mint.(many of struck with connecting to internet using wireless card , for this, use wvdial.exe or create a network profile and connect via mobile broadband)

3. after connection, open terminal, and

type the following commands:

-> sudo add-apt-repository ppa:yannubuntu/boot-repair
-> sudo apt-get update
-> sudo  apt-get install boot-repair


first cmd link to boot-repair website.

and 2nd cmd update all packages.because when u r using apt-get install cmd without update, it shows,
 error: command not found.

3rd cmd to download boot-repair.

after downloading boot-repair,open this app.

4. click recommended repair. after repair, it shows url. note it for future reference.

5. If the repair did not succeed, indicate the URL to people who help you by email or forum.

 see the url: https://help.ubuntu.com/community/Boot-Repair .


Monday, October 29, 2012

Memory Representation of storage classes in c


A typical memory representation of C program consists of following sections.
1. Text segment
2. Initialized data segment
3. Uninitialized data segment
4. Stack
5. Heap


1. Text Segment:
A text segment , also known as a code segment or simply as text, is one of the sections of a program in an object file or in memory, which contains executable instructions.
As a memory region, a text segment may be placed below the heap or stack in order to prevent heaps and stack overflows from overwriting it.
Usually, the text segment is sharable so that only a single copy needs to be in memory for frequently executed programs, such as text editors, the C compiler, the shells, and so on. Also, the text segment is often read-only, to prevent a program from accidentally modifying its instructions.

2. Initialized Data Segment:
Initialized data segment, usually called simply the Data Segment. A data segment is a portion of virtual address space of a program, which contains the global variables and static variables that are initialized by the programmer.
Note that, data segment is not read-only, since the values of the variables can be altered at run time.
This segment can be further classified into initialized read-only area and initialized read-write area.
For instance the global string defined by char s[] = “hello world” in C and a C statement like int debug=1 outside the main (i.e. global) would be stored in initialized read-write area. And a global C statement like const char* string = “hello world” makes the string literal “hello world” to be stored in initialized read-only area and the character pointer variable string in initialized read-write area.
Ex: static int i = 10 will be stored in data segment and global int i = 10 will also be stored in data segment

3. Uninitialized Data Segment:
Uninitialized data segment, often called the “bss” segment, named after an ancient assembler operator that stood for “block started by symbol.” Data in this segment is initialized by the kernel to arithmetic 0 before the program starts executing
uninitialized data starts at the end of the data segment and contains all global variables and static variables that are initialized to zero or do not have explicit initialization in source code.
For instance a variable declared static int i; would be contained in the BSS segment.
For instance a global variable declared int j; would be contained in the BSS segment.

4. Stack:
The stack area traditionally adjoined the heap area and grew the opposite direction; when the stack pointer met the heap pointer, free memory was exhausted. (With modern large address spaces and virtual memory techniques they may be placed almost anywhere, but they still typically grow opposite directions.)
The stack area contains the program stack, a LIFO structure, typically located in the higher parts of memory. On the standard PC x86 computer architecture it grows toward address zero; on some other architectures it grows the opposite direction. A “stack pointer” register tracks the top of the stack; it is adjusted each time a value is “pushed” onto the stack. The set of values pushed for one function call is termed a “stack frame”; A stack frame consists at minimum of a return address.
Stack, where automatic variables are stored, along with information that is saved each time a function is called. Each time a function is called, the address of where to return to and certain information about the caller’s environment, such as some of the machine registers, are saved on the stack. The newly called function then allocates room on the stack for its automatic and temporary variables. This is how recursive functions in C can work. Each time a recursive function calls itself, a new stack frame is used, so one set of variables doesn’t interfere with the variables from another instance of the function.

5. Heap:
Heap is the segment where dynamic memory allocation usually takes place.
The heap area begins at the end of the BSS segment and grows to larger addresses from there.The Heap area is managed by malloc, realloc, and free, which may use the brk and sbrk system calls to adjust its size (note that the use of brk/sbrk and a single “heap area” is not required to fulfill the contract of malloc/realloc/free; they may also be implemented using mmap to reserve potentially non-contiguous regions of virtual memory into the process’ virtual address space). The Heap area is shared by all shared libraries and dynamically loaded modules in a process.

Examples.

The size(1) command reports the sizes (in bytes) of the text, data, and bss segments. ( for more details please refer man page of size(1) )

1. Check the following simple C program
#include <stdio.h>

int main(void)
{
    return 0;
}
[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
960        248          8       1216        4c0    memory-layout

2. Let us add one global variable in program, now check the size of bss (highlighted in red color).
#include <stdio.h>

int global; /* Uninitialized variable stored in bss*/

int main(void)
{
    return 0;
}
[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
 960        248         12       1220        4c4    memory-layout

3. Let us add one static variable which is also stored in bss.
#include <stdio.h>

int global; /* Uninitialized variable stored in bss*/

int main(void)
{
    static int i; /* Uninitialized static variable stored in bss */
    return 0;
}
[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
 960        248         16       1224        4c8    memory-layout

4. Let us initialize the static variable which will then be stored in Data Segment (DS)
#include <stdio.h>

int global; /* Uninitialized variable stored in bss*/

int main(void)
{
    static int i = 100; /* Initialized static variable stored in DS*/
    return 0;
}
[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
960         252         12       1224        4c8     
memory-layout

5. Let us initialize the global variable which will then be stored in Data Segment (DS)
#include <stdio.h>

int global = 10; /* initialized global variable stored in DS*/

int main(void)
{
    static int i = 100; /* Initialized static variable stored in DS*/
    return 0;
}
[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
960         256          8       1224        4c8    memory-layout



 

Thursday, October 18, 2012

TCP windowing

TCP Windowing(Referred from http://packetlife.net/blog/)

As we know, TCP is a connection-oriented protocol; both ends of a connection keep strict track of all data transmitted, so that any lost or jumbled segments can be retransmitted or reordered as necessary to maintain reliable transport. To compensate for limited buffer space (where received data is temporarily stored until the appropriate application can process it), TCP hosts agree to limit the amount of unacknowledged data that can be in transit at any given time. This is referred to as the window size, and is communicated via a 16-bit field in the TCP header.
Suppose we have two hosts, A and B, that form a TCP connection. At the start of the connection, both hosts allocate 32 KB of buffer space for incoming data, so the initial window size for each is 32,768.
TCP_windowing1.png
Host A needs to send data to host B. It can tell from host B's advertised window size that it can transmit up to 32,768 bytes of data (in intervals of the maximum segment size, or MSS) before it must pause and wait for an acknowledgment. Assuming an MSS of 1460 bytes, host A can transmit 22 segments before exhausting host B's receive window.
When acknowledging receipt of the data sent by host A, host B can adjust its window size. For example, if the upper-layer application has only processed half of the buffer, host B would lower its window size to 16 KB. If the buffer was still entirely full, host B would set its window size to zero, indicating that it cannot yet accept more data.
TCP_windowing2.png
On a LAN with high bandwidth and extremely low delay, windows are rarely stressed as there are typically very few segments in transit between two endpoints at any given time. On a high-bandwidth, high-delay network, however, an interesting phenomenon occurs: it is possible to max out the receive window of the destination host before receiving an acknowledgment.
As an example, let's assume a TCP connection is established between two hosts connected by a dedicated 10 Mbps path with a one-way delay of 80ms. Both hosts advertise the maximum window size of 65,535 bytes (the maximum value of a 16-bit unsigned integer). We can calculate the potential amount of data in transit in one direction at one point in time as bandwidth * delay: 10,000,000 bps divided by 8 bits per byte, multiplied by 0.08 seconds equals 100,000 bytes. In other words, if host A begins transmitting to host B continuously, it will have sent 100,000 bytes before host B receives the first byte transmitted. However, because our maximum receive window is only 65,535 bytes, host A must stop transmitting once this number has been reached and wait for an acknowledgment from host B. (For the sake of simplicity, our example calculations do not factor in overhead from TCP and lower-layer headers.) This delay wastes potential throughput, unnecessarily inflating the time it takes to reliably transfer data across the network. TCP window scaling was created to address this problem.

Window Scaling

Window scaling was introduced in RFC 1072 and refined in RFC 1323. Essentially, window scaling simply extends the 16-bit window field to 32 bits in length. Of course, the engineers could not simply insert an extra 16 bits into the TCP header, which would have rendered it completely incompatible with existing implementations. The solution was to define a TCP option to specify a count by which the TCP header field should be bitwise shifted to produce a larger value.
window_scale_option.png
A count of one shifts the binary value of the field to left by one bit, doubling it. A count of two shifts the value two places to the left, quadrupling it. A count of seven (as shown in the example above) multiplies the value by 128. In this manner, we can multiply the 16-bit header field along an exponential scale to achieve more than sufficiently high values. Of course, this causes us to lose granularity as we scale (we can only increase or decrease the window size in intervals of 2n where _n_ is our scale), but that isn't much of a concern when dealing with such large windows.
bitwise_shift.png
The window scaling option may be sent only once during a connection by each host, in its SYN packet. The window size can be dynamically adjusted by modifying the value of the window field in the TCP header, but the scale multiplier remains static for the duration of the TCP connection. Scaling is only in effect if both ends include the option; if only one end of the connection supports window scaling, it will not be enabled in either direction. The maximum valid scale value is 14 (section 2.3 of RFC 1323 provides some background on this caveat for those interested).
Revisiting our earlier example, we can observe how window scaling allows us to make much more efficient use of long fat networks. To calculate our ideal window, we double the end-to-end delay to find the round trip time, and multiple it by the available bandwidth: 2 * 0.08 seconds * 10,000,000 bps / 8 = 200,000 bytes. To support a window of this size, host B could set its window size to 3,125 with a scale value of 6 (3,125 left shifted by 6 equals 200,000). Fortunately, these calculations are all handled automatically by modern TCP/IP stack implementations.

Websites for Placements Preparations

i listed below, some of the good websites for placement preparation:

networks:

http://tutorpiggy.blogspot.in.
http://networking.blogspot.in/p/cisco-ios-commands.html
http://newadmins.blogspot.com
http://www.rrbbbs.gov.in/post_qualifications.php
http://ciscodays.blogspot.in/2009/06/interview-questions.html
http://www.tcpipguide.com/free/t_ARPCaching.htm
http://aptipedia.blogspot.in/2010/12/computer-network-questions-and-answers.html
http://www.brainbell.com/tutorials/Networking/The_Unknown_Host_Message.html
http://tcpipguru.com/switching-interview-questions-and-answers/
http://www.i-1.nl/blog/?p=186
http://studentsmela.blogspot.in/2010/08/important-c-networks-interview.html
http://tcpipguru.com/how-many-dhcp-servers-can-reside-on-one-subnet/
http://210.43.128.116/jsjwl/net/kurose/ethernet/transparent_bridges.htm

http://www.9tut.com/ccna-tcpip-model-operation


algorithms and coding:

www.geeksforgeeks.org -collection of all algorithms..

google groups-algogeeks

http://algorithmguru.com/content/

http://www.programmingsimplified.com/c/source-code/c-anagram-program

for memory allocation in c:

http://www.itechtalk.com/thread103.html

http://www.tenouk.com/ModuleZ.html

http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory

http://www.careercup.com/page?pid=netapp-interview-questions
http://arvind-mohan.blogspot.in/2011/08/blog-27-some-important-data-structure.html
http://classic-puzzles.blogspot.in/2006/12/13-balls-problem-one-of-hardest.html
http://www.ceglug.org/index.php?option=com_content&view=article&id=53:doubly-linked-list&catid=6:lab&Itemid=11
http://www.cprogramming.com/tutorial/function-pointers.html
http://leadventures.blogspot.in/
http://rahulraj1990.wordpress.com/2011/07/26/hello-world/
http://www.mbauniverse.com/mba-exam-preparation/basicarithmaticpart1.php
http://www.totalgadha.com/mod/forum/discuss.php?d=5484
http://www.totalgadha.com/mod/forum/discuss.php?d=4207
http://sameerbsws.blogspot.in/2011/08/thought-works-placement-papers-2011.html



operating systems:

http://www.geeksforgeeks.org/archives/20116
http://www.careercup.com/page?pid=operating-system-interview-questions&n=2
http://cs.nyu.edu/~gottlieb/courses/2008-09-fall/os2250/lectures/lecture-05.html
http://www.ccplusplus.com/search/label/IPC
http://os-concepts.blogspot.in/
http://www.steve.org.uk/Reference/Unix/faq_2.html
http://www.personal.kent.edu/~rmuhamma/OpSystems/Myos/threads.htm

Wednesday, October 17, 2012

interview questions_networks



    1. What Is a MAC Address?   

    2. Define SMTP?   

   3.  Define Telnet?   

    4. Describe Application layer.   

   5.  Explain the core naming mechanism, Domain Name System (DNS).   

    6. Explain the functionality of PING.   

   7.  What is multicasting?   

    8. What is a network? What are the different kinds of network? Explain them.   

    9. Explain the 7 Layers of OSI.   

   10. How would you identify if a recursive code is correct/ not?

  11.  Implement a doubly linked list?

  12. Find the number of bits set in a random number?

  13. Find the position of set bit in a number?

  14. Difference between Binary Semaphore and a Mutex?

  15. .Explain how RIP & OSPF differ, which is better?

  16.Explain NAT & NATP?

  17.Write a programme to find number of bits set in an integer?

 18.Write a program for binary tree height calculation?

 19.Explain the OSI model and protocols used in each layer?

 20.Explain TCP vs UDP?

 21.What is XMPP Protocol do u have idea? Please explian ?



22. what happens in all layers when we type www.google.com in browser. (most famous question

      asked in any interview )

ans:  explain socket() from application , dns , dns mapping, dns cache, arp , tcp , http, logo
         identification.