Showing posts with label interview. Show all posts
Showing posts with label interview. Show all posts

Thursday, May 31, 2012

Some C Interview Questions


Some recent set of questions I found from web, found them unique and interesting. 

The sizeof( ) function doesn’t return the size of the block of memory pointed to by a pointer. Why?
Answer:The sizeof( ) operator does not know that malloc( ) has been used to allocate a pointer. sizeof( ) gives us the size of pointer itself. There is no handy way to find out the size of a block allocated by malloc( ).

How do I write a program to convert a string containing number in a hexadecimal form to its equivalent decimal?
Answer: The following program demonstrates this:
main( )
{
char str[] = "0AB" ;
int h, hex, i, n ;
n = 0 ; h = 1 ;
for ( i = 0 ; h == 1 ; i++ )
{
if ( str[i] >= '0' && str[i] <= '9' )
hex = str[i] - '0' ;
else
{
if ( str[i] >= 'a' && str[i] <= 'f' )
hex = str[i] - 'a' + 10 ;
else
if ( str[i] >= 'A' && str[i] <= 'F' )
hex = str[i] - 'A' + 10 ;
else
h = 0 ;
}
if ( h == 1 )
n = 16 * n + hex ;
}
printf ( "\nThe decimal equivalent of %s is %d",
str, n ) ;
}
The output of this program would be the decimal equivalent of 0AB is 171.

What will be the output of the following code?
void main ()
{ int i = 0 , a[3] ;
a[i] = i++;
printf (“%d",a[i]) ;
}
Answer: The output for the above code would be a garbage value. In the statement a[i] = i++; the value of the variable i would get assigned first to a[i] i.e. a[0] and then the value of i would get incremented by 1. Since a[i] i.e. a[1] has not been initialized, a[i] will have a garbage value.

How do I know how many elements an array can hold?
Answer: The amount of memory an array can consume depends on the data type of an array. In DOS environment, the amount of memory an array can consume depends on the current memory model (i.e. Tiny, Small, Large, Huge, etc.). In general an array cannot consume more than 64 kb. Consider following program, which shows the maximum number of elements an array of type int, float and char can have in case of Small memory model.
main( )
{
int i[32767] ;
float f[16383] ;
char s[65535] ;
}

Are the following two statements identical?
char str[6] = "Kicit" ;
char *str = "Kicit" ;
Answer: No! Arrays are not pointers. An array is a single, pre-allocated chunk of contiguous elements (all of the same type), fixed in size and location. A pointer on the other hand, is a reference to any data element (of a particular type) located anywhere. A pointer must be assigned to point to space allocated elsewhere, but it can be reassigned any time. The array declaration char str[6] ; requests that space for 6 characters be set aside, to be known by name str. In other words there is a location named str at which six characters are stored. The pointer declaration char *str ; on the other hand, requests a place that holds a pointer, to be known by the name str. This pointer can point almost anywhere to any char, to any contiguous array of chars, or nowhere.

Is the following code fragment correct?
const int x = 10 ;
int arr[x] ;
Answer: No! Here, the variable x is first declared as an int so memory is reserved for it. Then it is qualified by a const qualifier. Hence, const qualified object is not a constant fully. It is an object with read only attribute, and in C, an object associated with memory cannot be used in array dimensions.

How does free( ) know how many bytes to free?
Answer: The malloc( ) / free( ) implementation remembers the size of each block allocated and returned, so it is not necessary to remind it of the size when freeing.

What is a stack ?
Answer: The stack is a region of memory within which our programs temporarily store data as they execute. For example, when a program passes parameters to functions, C places the parameters on the stack. When the function completes, C removes the items from the stack. Similarly, when a function declares local variables, C stores the variable's values on the stack during the function's execution. Depending on the program's use of functions and parameters, the amount of stack space that a program requires will differ.

What's the difference between these two declarations?
struct str1 { ... } ;
typedef struct { ... } str2 ;
A : The first form declares a structure tag whereas the second declares a typedef. The main difference is that the second declaration is of a slightly more abstract type -- its users don't necessarily know that it is a structure, and the keyword struct is not used when declaring instances of it.

How does a C program come to know about command line arguments?
A: When we execute our C program, operating system loads the program into memory. In case of DOS, it first loads 256 bytes into memory, called program segment prefix. This contains file tables,environment segment, and command line information. When we compile the C program the compiler inserts additional code that parses the command, assigning it to the argv array, making the arguments easily accessible within our C program.

When we open a file, how does functions like fread( )/fwrite( ), etc. get to know from where to read or to write the data?
A: When we open a file for read/write operation using function like fopen( ), it returns a pointer to the structure of type FILE. This structure stores the file pointer called position pointer, which keeps track of current location within the file. On opening file for read/write operation, the file pointer is set to the start of the file. Each time we read/write a character, the position pointer advances one character. If we read one line of text at a step from the file, then file pointer advances to the start of the next line. If the file is opened in append mode, the file pointer is placed at the very end of the file. Using fseek( ) function we can set the file pointer to some other place within the file

Why doesn't the following code give the desired result? 
int x = 3000, y = 2000 ;
long int z = x * y ;
Answer: Here the multiplication is carried out between two ints x and y, and the result that would overflow would be truncated before being assigned to the variable z of type long int. However, to get the correct output, we should use an explicit cast to force long arithmetic as shown below: 
long int z = ( long int ) x * y ;
Note that ( long int )( x * y ) would not give the desired effect.

Why doesn't the following statement work?
char str[ ] = "Hello" ; 
strcat ( str, '!' ) ;
Answer: The string function strcat( ) concatenates strings and not a character. The basic difference between a string and a character is that a string is a collection of characters, represented by an array of characters whereas a character is a single character. To make the above statement work writes the statement as shown below:
strcat ( str, "!" ) ;

What is the difference between "calloc(...)" and "malloc(...)"?
Answer:
1. calloc(...) allocates a block of memory for an array of elements of a certain size. By default the block is initialized to 0. The total number of memory allocated will be (number_of_elements * size). 
malloc(...) takes in only a single argument which is the memory required in bytes. malloc(...) allocated bytes of memory and not blocks of memory like calloc(...).

2.malloc(...) allocates memory blocks and returns a void pointer to the allocated space, or NULL if there is insufficient memory available.
calloc(...) allocates an array in memory with elements initialized to 0 and returns a pointer to the allocated space. calloc(...) calls malloc(...) in order to use the C++ _set_new_mode function to set the new handler mode.

Difference between const char* p and char const* p?
Answer:In const char* p, the character pointed by ‘p’ is constant, so u cant change the value of character pointed by p but u can make ‘p’ refer to some other location. in char const* p, the ptr ‘p’ is constant not the character referenced by it, so u cant make ‘p’ to reference to any other location but u can change the value of the char pointed by ‘p’.

How can you determine the size of an allocated portion of memory?
Answer:You can’t, really. free() can , but there’s no way for your program to know the trick free() uses. Even if you disassemble the library and discover the trick, there’s no guarantee the trick won’t change with the next release of the compiler.

Can static variables be declared within a header file? 
A:you can not declare a static variable without defining it as well (this is really because the actual storage class modifiers static and also extern are mutually exclusive). A static variable could be defined in a header file, but this would cause each source file that included the header file to get its very own private copy from the variable, which is most likely not what was meant

Can a variable become both constant and volatile?
A:Yes. The const modifier implies that this particular program code cannot change the value of the actual variable, but that will not imply that the value can not be changed by means outside this code. For instance, within the example in frequently asked questions, the timer structure was accessed through a volatile const pointer.The function by itself did not change the value of the timer, so it had been declared const. However, the value had been changed by hardware on the computer, so it was declared volatile. If a variable is both equally const and volatile, the two modifiers can come in either order.

Sunday, July 17, 2011

Google and Family Planning!– Interesting answer

The following question is reputedly one of many that Google may ask prospective job candidates:

Imagine a country in which every family continues to have children until they have a boy. If they have a girl, they have another child, and continue until they have a boy, then they stop. What is the proportion of boys to girls in the country? You should assume that there is an equal probability of having a boy or a girl.

The question has been discussed at length on the Internet and this site is one of many that provide an answer. The answer is correct (approximately the same number of boys and girls) but I doubt whether the way it is derived would help to get you a job with Google. There are numerous other similar posts, most of which give the correct answer, but all but a few miss what I believe is the point of the question. It is an example of misdirection; the question describes a strategy for ensuring that all families have exactly one boy and zero or more girls, but what it asks for is the overall distribution of boys and girls in the country as a whole. The way the question is stated leads you to believe that the strategy will affect the overall distribution - but does it? Anyone with some knowledge of probability should then realise that no strategy that involves stopping after a certain number of children can affect the overall proportion, because all births are independent events. In the population as a whole the probability that the next child, born anywhere in the country, will be a boy is 0.5, regardless of how many boys or girls have already been born, so the proportion will be 50:50. Of course the proportion will rarely be exactly equal because the gender of the children are random events, in fact they form a binomial distribution, but for large populations it will be very close to 50:50.

To many people this is counter intuitive - probably because the strategy clearly does affect the make up of every individual family. Consider another country where they adopt the strategy of stopping after having exactly two girls. The only family distribution you would find on both countries would be two girls and one boy (but in a different order); the overall distribution however would still be 50:50.

Tuesday, June 28, 2011

Finding Stack Direction for a Machine

How would you find out if a machine’s stack grows up or down in memory?

You need to call a function with one parameter, and create one more local variable, the parameters would be pushed on stack and also the local variables would be created on stack, hence, if your parameters address and locals address would give you the result.

Here is the code of subroutine for your reference.

void sub_routine(int a) { 
int b;
b = a;
if(&b < &a)
printf("Stack Grows Downward!");
else
printf("Stack Grows Upward!");
}

int main() {
sub_routine(10);
return 0;
}

If Richard Feynman applied for a job at Microsoft

Interviewer: Now comes the part of the interview where we ask a question to test your creative thinking ability. Don't think too hard about it, just apply everyday common sense, and describe your reasoning process.

Here's the question: Why are manhole covers round?

Feynman: They're not. Some manhole covers are square. It's true that there are SOME round ones, but I've seen square ones, and rectangular ones.

Interviewer: But just considering the round ones, why are they round?

Feynman: If we are just considering the round ones, then they are round by definition. That statement is a tautology.

Interviewer: I mean, why are there round ones at all? Is there some particular value to having round ones?

Feynman: Yes. Round covers are used when the hole they are covering up is also round. It's simplest to cover a round hole with a round cover.

Interviewer: Can you think of a property of round covers that gives them an advantage over square ones?

Feynman: We have to look at what is under the cover to answer that question. The hole below the cover is round because a cylinder is the strongest shape against the compression of the earth around it. Also, the term "manhole" implies a passage big enough for a man, and a human being climbing down a ladder is roughly circular in cross-section. So a cylindrical pipe is the natural shape for manholes. The covers are simply the shape needed to cover up a cylinder.

Interviewer: Do you believe there is a safety issue? I mean, couldn't square covers fall into the hole and hurt someone?

Feynman: Not likely. Square covers are sometimes used on prefabricated vaults where the access passage is also square. The cover is larger than the passage, and sits on a ledge that supports it along the entire perimeter. The covers are usually made of solid metal and are very heavy. Let's assume a two-foot square opening and a ledge width of 1-1/2 inches. In order to get it to fall in, you would have to lift one side of the cover, then rotate it 30 degrees so that the cover would clear the ledge, and then tilt the cover up nearly 45 degrees from horizontal before the center of gravity would shift enough for it to fall in. Yes, it's possible, but very unlikely. The people authorized to open manhole covers could easily be trained to do it safely. Applying common engineering sense, the shape of a manhole cover is entirely determined by the shape of the opening it is intended to cover.

Interviewer (troubled): Excuse me a moment; I have to discuss something with my management team. (Leaves room.)

(Interviewer returns after 10 minutes)

Interviewer: We are going to recommend you for immediate hiring into the marketing department

Source: http://www.sellsbrothers.com/interview?content=question.htm

Some ILLEGAL Questions !

  • What political party are you affiliated with?
  • Are you a member of the local country club?
  • Do you go to church regularly?
  • Are you currently married? Are you divorced? What is your sexual orientation?
  • What are your outstanding debts?
  • What charities are you involved with?
  • Do you drink?
  • Do you have a boyfriend?
  • Your last name is _______. What kind of name is that?
  • Do you have a girlfriend / boyfriend / Are you planning to have children
  • Do you have a physical disability?
  • Do you have any health problems?
  • Have you ever been convicted of a felony?
  • How many children do you have?
  • How old are you?
  • This is a Christian company. Do you think that you can be happy working here?
  • What does you father/mother do for a living?
  • What is your first language?
  • What is your IQ?
  • How much do you weigh?
  • What's your religion?

Few Google Puzzles

How do you get a fair result with an unfair coin? i.e it is expected to come more heads than tails.

Answer: Take HT as Heads, and TH as Tails, and Other times re flip the coin, now the probabilities are same.

You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)

Additional Note:

  • There are 5 rational pirates, A, B, C, D and E. They find 100 gold coins. They must decide how to distribute them.
  • The pirates have a strict order of seniority: A is superior to B, who is superior to C, who is superior to D, who is superior to E.
  • The pirate world's rules of distribution are thus: that the most senior pirate should propose a distribution of coins. The pirates, including the proposer, then vote on whether to accept this distribution. If the proposed allocation is approved by a majority or a tie vote, it happens. If not, the proposer is thrown overboard from the pirate ship and dies, and the next most senior pirate makes a new proposal to begin the system again.
  • Pirates base their decisions on three factors. First of all, each pirate wants to survive. Second, each pirate wants to maximize the number of gold coins he receives. Third, each pirate would prefer to throw another overboard, if all other results would otherwise be equal

Answer: It might be expected intuitively that Pirate A will have to allocate little if any to himself for fear of being voted off so that there are fewer pirates to share between. However, this is as far from the theoretical result as is possible.

This is apparent if we work backwards: if all except D and E have been thrown overboard, D proposes 100 for himself and 0 for E. He has the casting vote, and so this is the allocation.

If there are three left (C, D and E) C knows that D will offer E 0 in the next round; therefore, C has to offer E 1 coin in this round to make E vote with him, and get his allocation through. Therefore, when only three are left the allocation is C:99, D:0, E:1.

If B, C, D and E remain, B knows this when he makes his decision. To avoid being thrown overboard, he can simply offer 1 to D. Because he has the casting vote, the support only by D is sufficient. Thus he proposes B:99, C:0, D:1, E:0. One might consider proposing B:99, C:0, D:0, E:1, as E knows he won't get more, if any, if he throws B overboard. But, as each pirate is eager to throw each other overboard, E would prefer to kill B, to get the same amount of gold from C.

Assuming A knows all these things, he can count on C and E's support for the following allocation, which is the final solution:
A: 98 coins
B: 0 coins
C: 1 coin
D: 0 coins
E: 1 coin

Also, A:98, B:0, C:0, D:1, E:1 or other variants are not good enough, as D would rather throw A overboard to get the same amount of gold from B.

Note: The game can easily be extended to up to 200 pirates (or further even if you don't increase the amount of gold).

You have to get from point A to point B. You don’t know if you can get there. What would you do?

Best Answer: Well, point A is where you are now. You know how you go into a mall, and they have the "mall map" inside a case and you look for the "you are here" spot? That's your reference point, and if you have even the slightest sense of direction, you can find the store you want on the map and start walking to it.

Next...point B. In the same scenario above point B would be the store you looked for and started walking toward. So, in other words, point B is where you want to go. In the mall example you could locate the store and go in the exact opposite direction following only the outer walls and still get there. Not very effective, but the end result would be successful...albeit very delayed.

Or, you could locate the store, point yourself in that direction, and walk straight to it and get there much faster and much more efficiently. Successful end result and with a lot of extra time to spare when compared to the walking the other way. Right?

Something else that can come up even in your "direct" walk to point B is distraction. After all; you're in a mall. You're bound to see some shoes you just "got to have". Or you'll stop and drool over that awesome surround sound digital megaDef home theater system. Maybe you'll decide to stop and sample that divine cinnamon roll that's been wafting up your nose for the past 15 minutes. You get the idea. Distractions can keep you from arriving at your desired location. If not for good, at least for a significantly postponed time.

In your ongoing marketing efforts you need to get from point A (where you are now) to point B (your desired end result, location, or outcome) in an efficient, timely manner to be as effective and successful as possible. So you'll need to keep some key points in mind:

  • Know (not think you know) where you are
  • Know (not think you know) where you want to go
  • See clearly where "point B" is or clearly, vividly visualize yourself there
  • Be aware of what your distractions are or could be and build up barriers against them

And don't stop until you get there...then you'll begin to prepare for a new "point B"
This isn't mystical. It isn't magical. It isn't mind control or mind over matter. It's the good ol' work ethic. You keep working at it until you achieve it. I don't buy into the "work smarter not harder" cliche' either. No way. You work smarter AND harder.

Increase your skills consistently so you can achieve more in less time. Learn more software programs to streamline your efficiency. But then you gotta (as we used to say in high school choir) practice, practice, practice! You don't get better simply by "being smarter". I like to say: Education without Application leads to a Continuation of Frustration. So apply that wonderful brain of yours to the task at hand and do it until you do it better than anybody.

Once you've developed this approach to your efforts...your sphere of influence will be made up of bold, straight lines you can walk with confidence.

Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?

I would argue that the COLOR of the shirt is less important than the OCCASION you wear the shirt for.The best top level hash to make on the shirts would be when the shirt is appropriate to wear. Divide the shirts into Work Shirts, Leisure Shirts, and Gym Shirts (insert other categories as you see fit). Then when it’s time to select a shirt for work in the morning, you don’t have to think about what COLOR you want to wear. Maybe then organize the work shirts by color.

Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

Day1: nothing happens. As every woman would be expecting that one of the men, she knows for adultery should die. No one would kill her own husband.
Day2: When no one dies, each woman would instantly come to know that her husband has cheated, and each woman would kill their husband. So everyone dies.

If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?

Let p be the probability of seeing a car in a given 10 minutes. Then (1-p) is the probability of not seeing a car in 10 minutes, and (1-p)3 is the probability of not seeing a car in 30 minutes. But:
     (1-p)3 = 0.05
--> p = 0.63159...

If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands?

Assume for now the angle is 0 degrees, but hour hand moves about 0.5 degrees in one min, and in 15 minutes he moves by 7.5 degrees, so the angle is 7.5 degrees.

Monday, June 27, 2011

Google Interview Questions that makes you feel stupid

Why are manhole-covers round in shape?

The question of why manhole covers are typically round, at least in the U.S., was made famous by Microsoft when they began asking it as a job-interview question. Originally meant as a psychological assessment of how one approaches a question with more than one correct answer, the problem has produced a number of alternate explanations

Reasons for the shape include:

  • A round manhole cover cannot fall through its circular opening, whereas a square manhole cover may fall in if it were inserted diagonally in the hole. (A Reuleaux triangle or other curve of constant width would also serve this purpose, but round covers are much easier to manufacture. The existence of a "lip" holding up the lid means that the underlying hole is smaller than the cover, so that other shapes might suffice.)
  • Round tubes are the strongest and most material-efficient shape against the compression of the earth around them, and so it is natural that the cover of a round tube assumes a circular shape.
  • Similarly, it is easier to dig a circular hole and thus the cover is also circular.
  • The bearing surfaces of manhole frames and covers are machined to assure flatness and prevent them from becoming dislodged by traffic. Round castings are much easier to machine using a lathe.
  • Circular covers do not need to be rotated to align them when covering a circular manhole.
  • Human beings have a roughly circular cross-section.
  • A round manhole cover can be more easily moved by being rolled.
  • A round manhole cover is cheapest to manufacture related to other shapes because requires the least amount of metal to cover an opening wide enough for a person to get through.
  • Most manhole covers are made by a few large companies. A different shape would have to be custom made.
  • The round manhole cover can more easily accommodate a Ninja Turtles shell

How many golf balls can fit in a school bus?

This is one of those questions Google asks just to see if the applicant can explain the key challenge to solving the problem.

I figure a standard school bus is about 8ft wide by 6ft high by 20 feet long - this is just a guess based on the thousands of hours I have been trapped behind school buses while traffic in all directions is stopped.

That means 960 cubic feet and since there are 1728 cubic inches in a cubit foot, that means about 1.6 million cubic inches. 

I calculate the volume of a golf ball to be about 2.5 cubic inches (4/3 * pi * .85) as .85 inches is the radius of a golf ball. 

Divide that 2.5 cubic inches into 1.6 million and you come up with 660,000 golf balls. However, since there are seats and crap in there taking up space and also since the spherical shape of a golf ball means there will be considerable empty space between them when stacked, I'll round down to 500,000 golf balls. 

Which sounds ludicrous. I would have spitballed no more than 100k. But I stand by my math. 

How much should you charge to wash all the windows in Seattle?

This is one of those questions where the trick is to come up with an easier answer than the one that's seemingly being called for. We'd say. "$10 per window."

In a country in which people only want boys every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

This one caused quite the debate, but we figured it out following these steps:

  • Imagine you have 10 couples who have 10 babies. 5 will be girls. 5 will be boys. (Total babies made: 10, with 5 boys and 5 girls)
  • The 5 couples who had girls will have 5 babies. Half (2.5) will be girls. Half (2.5) will be boys. Add 2.5 boys to the 5 already born and 2.5 girls to the 5 already born. (Total babies made: 15, with 7.5 boys and 7.5 girls.)
  • The 2.5 couples that had girls will have 2.5 babies. Half (1.25) will be boys and half (1.25) will be girls. Add 1.25 boys to the 7.5 boys already born and 1.25 girls to the 7.5 already born. (Total babies: 17.5 with 8.75 boys and 8.75 girls).

And so on, maintianing a 50/50 population.

How many piano tuners are there in the entire world?

We'd answer "However many the market dictates. If pianos need tuning once a week, and it takes an hour to tune a piano and a piano tuner works 8 hours a day for 5 days a week 40 pianos need tuning each week. We'd answer one for every 40 pianos."

On Wikipedia, they call this a Fermi problem.

The classic Fermi problem, generally attributed to Fermi, is "How many piano tuners are there in Chicago?" A typical solution to this problem would involve multiplying together a series of estimates that would yield the correct answer if the estimates were correct. For example, we might make the following assumptions:

  • There are approximately 5,000,000 people living in Chicago.
  • On average, there are two persons in each household in Chicago.
  • Roughly one household in twenty has a piano that is tuned regularly.
  • Pianos that are tuned regularly are tuned on average about once per year.
  • It takes a piano tuner about two hours to tune a piano, including travel time.
  • Each piano tuner works eight hours in a day, five days in a week, and 50 weeks in a year.

From these assumptions we can compute that the number of piano tunings in a single year in Chicago is

(5,000,000 persons in Chicago) / (2 persons/household) × (1 piano/20 households) × (1 piano tuning per piano per year) = 125,000 piano tunings per year in Chicago.

And we can similarly calculate that the average piano tuner performs

(50 weeks/year)×(5 days/week)×(8 hours/day)×(1 piano tuning per 2 hours per piano tuner) = 1000 piano tunings per year per piano tuner.

Dividing gives

(125,000 piano tuning per year in Chicago) / (1000 piano tunings per year per piano tuner) = 125 piano tuners in Chicago.

A famous example of a Fermi-problem-like estimate is the Drake equation, which seeks to estimate the number of intelligent civilizations in the galaxy. The basic question of why, if there are a significant number of such civilizations, ours has never encountered any others is called the Fermi paradox.

Design an evacuation plan for San Francisco

Again, this one is all about the interviewer seeing how the interviewee would attack the problem. We'd start our answer by asking, "What kind of disaster are we planning for?"

How many times a day does a clock’s hands overlap?

22 times, AM, 12, 1.05, 2.06 … 10.55, (11 times) and PM same number, so total 22 times.

Explain the significance of "dead beef"

DEADBEEF is a hexadecimal value that has was used in debugging back in the mainframe/assembly days because it was easy to see when marking and finding specific memory in pages of hex dumps. Most computer science graduates have seen this at least in their assembly language classes in college and that's why they expect software engineers to know it.

A man pushed his car to a hotel and lost his fortune. What happened?

He landed on Boardwalk. (Painful, right?)

You need to check that your friend, Bob, has your correct phone number but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

Since you are just "checking," you ask him to call you at a certain time. If he doesn't, he doesn't have your number.

Too simple? A reader suggest: "In that case you need a check-sum. Have Bob add all the digits of your phone number together, write down the total, and pass that back to you."

You're the captain of a pirate ship, and your crew gets to vote on how the gold is divided up. If fewer than half of the pirates agree with you, you die. How do you recommend apportioning the gold in such a way that you get a good share of the booty, but still survive?

You divide the booty evenly between the top 51% of the crew.

You have eight balls all of the same size, 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighing?

Take 6 of the 8 balls and put 3 on each side of the scale. If the heavy ball isn't in the group of 6, you know it's one of the remaining 2 and so you put those two in the scale and determine which one. If the heavy ball is in the 6, you have narrowed it down to 3. Of those 3, pick any 2 and put them on the scale. If the heavy ball is in that group of 2, you know which one it is. If both balls are of equal weight, then the heavy ball is the one you sat to the side

You are given 2 eggs, You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process

The maximum egg drops for this method is 14 times. Instead of partitioning the floors by 10, Start at the 14th floor, and then go up 13 floors, then 12, then 11, then 10, 9, 8, 7, 6, 5, 4 until you get to the 99th floor, then here.  If the egg were to break at the 100th floor, it would take 12 drops (or 11 if you assume that it would break at the 100th floor).  Say, for example, that the 49th floor was the highest floor, the number of drops would be the 14th, 27th, 39th, 50th (the egg would break on the 50th floor) plus the 40, 41,42,43,44,45,46,47,48, and 49th floor for a total of 14 drops.

Explain a database in three sentences to your eight-year-old nephew

The point here is to test the applicant's ability to communicate complex ideas in simple language. Here's our attempt, "A database is a machine that remembers lots of information about lots of things. People use them to help remember that information. Go play outside."

You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?

This one is all about the judging interviewee's creativity. We'd try to break the electric motor.

Monday, June 20, 2011

Big Endian and Little Endian


  • What is the difference between big endian and little endin machines

The data ordering at the memory is different for them, in little endian higher address have the most significant byte and lower have the least signifincant byte. and otherway round in case of big endian machines.

  • How do u determine a processor to be little endian or big endian, write a small program for it.

int a = 1;
if( *((char *)&a) == 1) 
    printf("Little endian");
else
    printf("Big Endian");


This can also be done using an eum as shown below


enum
{ 
  int a;
  char c[4];
}

a = 1;
if(char[1] == 1) 
    printf("Little Endian");
else
    printf("Big Endian");

Thursday, June 9, 2011

Traverse a tree without recursion

The basic problem of traversing a tree requires recursion. If you dont have recursion then you should have a mechanism to save either side of the tree on to a temporary location, this can be done with a stack.
So the algorithm should be

1) traverse the node, if there is right push on to stack, and go to left node
2) if there is no left then pop from the stack and go to that node.
3) do this til all the nodes are exhausted. i.e. till your node pointer is null

Find the code here, for your reference. Push and Pop can be implemented as a simple stack methods.

/* Traverse a tree without recursion */
/* The basic idea is to use a stack for storing the other side of the tree when going in one direction */

void traverse_without_recursion(node *head) {
    node *next = head;
    while(next != NULL) {
        printf("%d", next->data);
        if(next->right)
            PUSH((int)(next->right));
        if(next->left)
            next = next->left;
        else next = (node *) POP();
    }
}

Write a program to find the max and second max


This is little tricky, but not difficult. easiest way to do this is to sort the array and then find the answer. But that not expected out of you.

The algorithm here is take thefirst element as the max and second max. Then loop through all elements

  1. If the number is larger than max then make it max, and make old max to second max.
  2. Else if it is more than second max then make it the second max.
  3. In all other cases drop that number
Here goes the code for your reference.

/*
** Write a program for finding the max and second max 
** of an array of given size */

#define SIZE 10

int main(void)
{
    int array[SIZE] = {10, 5, 16, 2, 1, 2, 3, 18, 21, 4};
    int i, max, sec_max;

    max  = sec_max = array[0];

    for(i=0; i< SIZE; i++)
    {
        if(array[i] > max) {
            sec_max = max;
            max = array[i];
        }
        else if(array[i] > sec_max)
            sec_max = array[i];
    }

    printf("max =  %d, sec max = %d", max, sec_max);
}

Monday, September 20, 2010

Single Linked List Example - Add/Delete

Here is the sample program, I have written to explain the singly linked list. This has three functions, one to insert to the list at the head, which is pretty easy by making the new item as the head, and other one to remove from the list when the data is found, 3rd one to insert to the tail of the list, in this case you need to traverse till the end of the list and then insert the item there.

#include <stdio.h>
#include <malloc.h>

typedef struct node_type {
    int data;
    struct node_type *next;
} node;

node *list_head = NULL;

void insert_list(node **plist_head, int data)
{
    node *item = (node *)malloc(sizeof(node));
    item->data = data;
    item->next = *plist_head;
    *plist_head = item;
}

void insert_list_tail(node **plist_head, int data)
{
    node **list_ptr = plist_head;
    node *item = (node *)malloc(sizeof(node));
    item->data = data;
    item->next = NULL;

    while(*list_ptr) 
        list_ptr = &(*list_ptr)->next;

    *list_ptr = item;
}

void show_list(node **list_head)
{
    node **list_ptr = list_head;
    while(*list_ptr)
    {    
        printf("%d\t", (*list_ptr)->data);
        list_ptr = &(*list_ptr)->next;
    } 
    printf("\n");
}

void remove_list(node **plist_head, int data)
{
    node **list_ptr = plist_head;
    while(*list_ptr)
    {
        if((*list_ptr)->data == data)
        {
            node *tmp = *list_ptr;
            *list_ptr = (*list_ptr)->next;
            free(tmp);
            break;
        }
        list_ptr = &(*list_ptr)->next;
    }
}

main()
{
    show_list(&list_head);
    insert_list(&list_head, 2);
    show_list(&list_head);
    insert_list(&list_head, 5);
    show_list(&list_head);
    insert_list(&list_head, 9);
    show_list(&list_head);
    insert_list(&list_head, 1);
    show_list(&list_head);
    remove_list(&list_head, 9);
    show_list(&list_head);
    remove_list(&list_head, 2);
    show_list(&list_head);
    insert_list_tail(&list_head, 8);
    insert_list_tail(&list_head, 12);
    show_list(&list_head);
}

Hope this will help someone who just has just started learning Linked list in C, let me know if something is not clear.

Thursday, September 16, 2010

Where is ZERO size array is used?

If you normally try to declare a zero size array, you would end of getting array, but if the same is used as the last element of a structure then it does not give any error. Infact its method or trick to use variable size array for the last element, this can be achived as shown in the below program.

#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef struct 
{
    int d;
    char name[0];
}s;

int main(void)
{
    char str[] = "prasad";
    int len;
    s *s1;
    len = strlen(str);
    s1 = (s *)malloc(sizeof(*s1) + len + 1);
    strcpy(s1->name, str);
    s1->d = 12345678;
    printf("d : %d  name : %s", s1->d, s1->name);
}

This kind of trick is normally not required, and you can program most of the things in this world with out using this, but still some people want to show that they can do something special than everybody, so they can do this trick, but when you do this you must be extra careful as you need to allocate right amount of memory for the variable size array, else you would end of corrupting others memory.

Monday, September 13, 2010

How to use Pointers for 2D Arrays

This is when, you want to have a two dimentional array and whos column size of fixed, but how many number of rows you need, you want to decide run time, in that case you may want to allocate memory for the whole 2D array dynamically. But the access to that array should be as simple as accessing it normally when declared using the standard syntax, i.e by using row and column numbers.

Remember that you cannot use, int **p for this purpose, or even int *p[4] for this purpose.

#include <stdio.h>
#include <malloc.h>

main()
{
    int i, j;
    int a[3][4];
    int (*p)[4];

    int size = 3;
    p = (int (*)[4])malloc(12*4);
    for(i=0; i<3; i++)
        for(j=0; j<4; j++)
        {
            p[i][j] = i+j;
            a[i][j] = p[i][j];
        }

    for(i=0; i<3; i++)
    {
        for(j=0; j<4; j++)
            printf("%d ", a[i][j]);
        printf("\n");
    }
}

Have a nice time, and enjoy programming.!

Saturday, August 28, 2010

An Overview of C++

1) What is a structured language?

The languages such as C and PASCAL are structure languages, which are characterized by their support for stand-alone subroutines, local variables, rich control constructs and their lack of reliance upon the GOTO statements.

2) What is the basic difference between the object oriented programming language and the structured pro-gramming language?

In structured programming language, the program is organized around the code, means, program is struc-tures into subroutines or functions which act on data, on the other hand the object oriented programming you define the data type, which will define how can access that data, in the sense the program is organized around data.

3) What are the characteristics of C++ or object oriented programming language?

The three main characteristics of an object oriented programming language is Encapsulation, Polymorphism and Inheritance. The class definitions explains encapsulation, the function and operator overloading explains polymorphism and the

4) What is Encapsulation in Object oriented programming language?

Encapsulation is a mechanism that binds together the code and the data it manipulates, and keep both safe from outside interference and misuse, the private data or code is accessible only within that object or class and public data or code can be accessed from outside, which gives an interface to the outside world to access the inside code and data of object.

5) What is polymorphism and what kind of polymorphisms are supported in C++?

One interface, multiple methods, in simple terms it is an attribute that allows one interface to control access to a general class of actions, the specific action selected is determined by the exact nature of the situation. Compiler will select the method appropriate for a particular situation, and programmers don’t need do it manually.

C++ supports both run time and compile time polymorphism. Compile time using function overloading and operator overloading. Run time using virtual functions.

6) What is inheritance in object oriented programming languages?

This is a concept of classification, where an objects property can be derived from another object, and it only needs to define those qualities that make it unique within its class. Example the Apple belongs to the class fruits and fruits belongs to class food etc.
7) How does bool data type is defined in C++?

There is standard Boolean data type in C++, which takes value true or false, true being 1 and false being zero automatic conversion to integer is supported, all non-zero value is treated as true and zero as false.

8) What is a class in C++

Class is a means to define an objects outline using data and code and access permissions, this is the inheri-tance is achieved in C++.

9) What is function overloading?

When you have similar tasks to be performed then you can declare functions with same name, keeping the number of parameters and /or their type different. Then the compiler will select the right function depending on the situation. This process is called function overloading. It is not only enough to keep the return type different. This is a polymorphism feature of C++. The other polymorphism feature available in C++ is operator overloading. There is run time polymorphism also using virtual functions using inheritance and derived class.

10) What are constructor and destructors?

It is very often that we need to initialize the class before we can use them, so C++ provides a way to auto-matically do it using constructor and then de-allocate any resources in the destructor. The constructor has same name as that of the class and it does not have any return type, because constructor cannot return anything. It should also be public member function of the class, because objects of that class needs to be defined in public scope. The same rules apply to the destructors also, destructors names has additional ~ at the beginning. The constructors are called when the declaration statements are executed, and destructors are called when the objects are destroyed

Friday, August 6, 2010

Name Mangling in C++

When C++ compilers compile a C++ program, it encodes all function names and certain other identifiers to include type and scoping information. This encoding process is called name mangling. Linker uses these mangled names to ensure type-safe linkage. These mangled names appear in the object files and final executable file.

What's a symbol?

In every C++ program/library/object file, all non-static functions are represented in the binary file as symbols. These symbols are special text strings that uniquely identify a function in the program, library or object file

The Need for Name Mangling:

C language programs does not use name mangling, because in C no two non-static functions can have the same name. i.e., the symbol name is the same as the function name: the symbol of myfunc will be myfunc
Because C++ allows overloading (different functions with the same name but different number of arguments) and has many features C does not, like classes, member functions, exception specifications — it is not possible to simply use the function name as the symbol name. To solve that, C++ uses name mangling, which encodes the function name and all the necessary information (like the number and size of the arguments) into some special string which only the compiler knows about

eg.,
bpte4500s001:/sunbuild1/giri/testcases/% nm hide.o

hide.o:

[Index]   Value      Size    Type  Bind  Other Shndx   Name
[3]     |        16|      56|FUNC |GLOB |3    |2      |__1cKCRectangleKset_values6Mii_v_
[4]     |         0|       0|NOTY |GLOB |0    |ABS    |__fsr_init_value
[1]     |         0|       0|FILE |LOCL |0    |ABS    |hide.cpp
[2]     |        88|      32|FUNC |GLOB |2    |2      |main
"__1cKCRectangleKset_values6Mii_v_" is the mangled name

But this kind of scheme is undesirable for the developers because the names are difficult to read & debug

Two utilities are available with Sun Studio C/C++ compiler collection to convert the mangled names to their original source code names:
1) c++filt &
2) dem

C++filt is a filter that demangles (decodes) mangled names.
bpte4500s001% echo __1cKCRectangleKset_values6Mii_v_ | c++filt
void CRectangle::set_values(int,int)

"dem" is another utility to demangle C++ names
bpte4500s001% dem __1cKCRectangleKset_values6Mii_v_
__1cKCRectangleKset_values6Mii_v_ == void CRectangle::set_values(int,int)

Note:
C++ standard does not define how names have to be mangled; thus every compiler mangles names in its own way. Some compilers even change their name mangling algorithm between different versions. This could be a problem if the developers hack & rely on how compiler mangles the C++ symbols, as the same algorithm may not work with the next version of C++ compiler

Thursday, August 5, 2010

Interview qeustions on C/C++

1. What is the size of the structure, assume int to be 4 bytes and float to be 4 bytes.

struct {
    enum  {
        integer,
        floating
    } type;
    union {
        int a;
        float b;
    };
} t1;

Answer: The enum would take one integer (4) and other union together will take one more space of larget between two (4), so total 8 bytes.

suppose the structure delcaration is changes as below, then what would be the size?

struct {
    enum type {
        integer,
        floating
    } ;
    union {
        int a;
        float b;
    };
} t1;

Answer: This would result in compilation error, as there is no member of 'type'

2. What doe the following function do? can it be given a better name?

DT* func(DT* a, const DT* b)
{
    DT *c = a;
    while(*a++ = *b++);
    return c;
}

Answer: Assuming that DT is an integer or char, the function would copy data from b to a, untill a zero in b is obtained, zero is also copied, so it can be renamed as string copy function.

3. Is the out put of line one and two inside the loop same, or different?

int a[100][100];
for(int i = 0; i<100; i++) {
    for(int j = 0; j<100; j++) {
        printf("%d", a[i][j]);
        printf("%d", a[j][i]);
    }
}

Answer: The output would be different as they refer to different row and colum, but at the end they out put all the data in the two dimentional array.

If one needs to be prefered over the other, which one will you prefer? and why?

Answer: The first one will be faster as it has less cache miss in case of a cache enabled system compared to the second one, so in a practical system the using first line would be faster, and so it should be prefered. Theoretically if memory access does not use cache, then both will be same in terms of time taken.

4. What is function overloading? how does compiler will know which function to call?

class{ 
    void func(int a);
    void func(int a, int b);
}

Answer: Having many function definitions for the same functions with different number of arguments is called function overloading, and the compiler will decide about the functions by seeing the type and number of params passed to the function call, and decide on which function to call at compile time.

Suppose if the function is defined below with a default argument and when calling if it is not passed then how would compiler decide about function?

class{ 
    void func(int a);
    void func(int a, int b = 0);
}

Answer: Then the compiler wont be able to decide, and it will throw a compile time error.

Wednesday, August 4, 2010

First bit set in an Integer

Write a C code which returns the position of the first bit set.fot eg. for number 104(1101000) output will be 4.

You need to right shift the number untill the number becomes zero and count the number of times right shifted, then you subtract it from the size of an interger (32 bit on a 32 bit machine), you will get the answer. Here is the code for your reference.

int fbs(unsigned int num)
{
    int pos = -1;
    while(num!=0)
    {
        num <<= 1;
        pos++;
    }
    return 32 - pos;
}

Mod 16 without using arithmatic

Write a function which takes an integer value as an argument and return its mod 16 value without using these (%,+,_,/) arithmetic operations

int mod16(int a)
{
    return a>>4;
}

The 4 bits left shift will give mod 16.

what is the difference between dynamic and static linking? which is better?

A dynamic-link library (DLL) is an executable file that acts as a shared library of functions. Dynamic linking provides a way for a process to call a function that is not part of its executable code. The executable code for the function is located in a DLL, which contains one or more functions that are compiled, linked, and stored separately from the processes that use them. DLLs also facilitate the sharing of data and resources. Multiple applications can simultaneously access the contents of a single copy of a DLL in memory.

Dynamic linking differs from static linking in that it allows an executable module (either a .dll or .exe file) to include only the information needed at run time to locate the executable code for a DLL function. In static linking, the linker gets all of the referenced functions from the static link library and places it with your code into your executable.

Using dynamic linking instead of static linking offers several advantages. DLLs save memory, reduce swapping, save disk space, upgrade easier, provide after-market support, provide a mechanism to extend the MFC library classes, support multilanguage programs, and ease the creation of international versions.

In case of free software licenses also, there are provisions with LGPL, using which you dont have to share the code which are linked dynamically.

Thursday, July 15, 2010

Wipro C/C++ Interview Questions

1. What is the main difference between the C++ class and the C structure?


Answer : Both in C++ class and C structure you can have member functions and member variables, but in C++ the member functions are inside the memory allocated for the object, but in C structures they will reside out the memory allocated for the structure.  C++ the member functions are passed with 'this' pointer which pointer to the objects and rest of the things are taken care by compiler with the help of 'this' pointer. This is done by compiler during compile time, and this remains the main difference and helps in achieving the object oriented nature of C++.

2. What is the difference between the two declarations below using volatile keyword.
volatile struct reg_map {
          int reg_r1;
          int reg_r2;
};

struct reg_map {
        volatile int reg_r1;
        volatile int reg_r2;
};

Answer : In the first case it is up to the compiler to make all the variables as volatile, but in second case the compiler will always make the members as volatile, so that the purpose is served. In first case we need to check if the compiler really makes all members volatile or not, and if it does not, then it does not serve the purpose.

3. I have a union declared as below    union  ex_union {
    int a;
    short int ar[2];
   }
 
if I assign the value 0x112233 to a, what would be the values of elements ar[0] and ar[1]

Answer: Considering it to be little endian machine, the value would be, 0x2233 and 0x0011 respectively, Because in Little endian end byte will be in little address and first byte will be in high address.

4. Assume you have a function with two params a and b, and you need to return an int after processing like below.

   int compare(int a, int b)
   {
       if a>b return 1
       if b>a return -1
       if a = b, return 0
   }
you need to write this function without using if else, switch and ternary operators, how do you do it?
Answer: The purpose of this question is, to reduce the pipe line flush during branch, since here there is 50% chance of branch, we need to avoid any branch instructions.
int compare(int a, int b)
{
    int x, m, s;
    x = a - b;             // find the difference
    m = x || 1;            // if magnitude not zero make it 1
    s = (x & (1 << 31));   // get the sign
    __asm sar s, 31        // extend the sign to make it -1
    return s | m;          // or sign and magnitude
}

This can also be written like below, but it will introduce branch in the generated x86 code, check it in visual studio.
int compare (int a, int b)
{
   int x  = 0;
   (a>b) && (x = 1) || (a<b) && (x = -1);
   return x;
}

Update:
In both the above cases, the compiler will generate the the branch instruction, which is same as the if, else and thus defeating the purpose, I have an solution for it, after the subtraction find the sign of the result using below function (code) and it wont generate the branch instruction.

int IntSign(int num)
{
    int sign = (num !=0) | -(int)((unsigned int)num >> (sizeof(int)*8 - 1));
    return sign;
}


The assembly code generate for the calculation is as below (visual studio for x86)

    int sign = (num !=0) | -(int)((unsigned int)num >> (sizeof(int)*8 - 1));
0041140E  xor         eax,eax 
00411410  cmp         dword ptr [num],0 
00411414  setne       al   
00411417  mov         ecx,dword ptr [num] 
0041141A  shr         ecx,1Fh 
0041141D  neg         ecx  
0041141F  or          eax,ecx 
00411421  mov         dword ptr [sign],eax 
    return sign;
00411424  mov         eax,dword ptr [sign]