Background
This is the most interesting puzzle I've seen till date and It was asked in campus interview of NIT Kurukshetra by Microsoft India Development Center. Luckily my friend could solve it and get into Microsoft.
Problem Definition
There are 5 Racing Tracks in a Ranch and you are given 25 horses. You have to find 3 fastest horses (considering there is no tie between any two horses) by conducting minimum number of races.
Solution:
This problem has interesting solution because to reach to the conclusion of this problem you only have to solve it to few steps and then analyzing the data from those steps you can easily come to conclusion. Let us discuss how to do so.
Divide 25 horses in five groups (A, B, C, D, E) with 5 Horses each. Now conduct the races of 5 Groups.
Number of Races Till Now: 5
After this you can arrange the top three horses from all the groups in following order
A - A1 A2 A3
B - B1 B2 B3
C - C1 C2 C3
D - D1 D2 D3
E - E1 E2 E3
Let us conduct a race among all the winners of a group i.e. A1, B1, C1, D1, E1
Number of Races Till Now: 6
Now sort the groups (A-E) from second table such that winner's group is placed first. For explanation let us assume that C1 is winner of 6th race with E1 as second winner and B1 as third, A1 fourth and D1 fifth.
Arrange the horses like this
C - C1 C2 C3
E - E1 E2 E3
B - B1 B2 B3
A - A1 A2 A3
D - D1 D2 D3
Now let us analyze these results to find three fastest horses.
1. Without doubt C1 is the fastest (Right? It has won from C2, C3 as well as A1, B1, D1, E1)
2. Second Fastest is Either E1 or C2 (Because all other are slower than these two. Agreed?)
3. Third Fastest will be among C2, C3, E1, E2, B1 (Why not E3?? It has two winners from it- E1, E2 so it can be at the max fourth.)
So we need to conduct a final race amond - C2, C3, E1, E2, B1 to determine second and third winner.
Number of Races Till Now (And Finally): 7 is the answer!!
For more such problems simply visit http://CodeBoat.blogspot.com
If you have any query/question or feedback. Feel free to send them over to codeboat@gmail.com
Background
One of my junior who is working with ST Microelectronics, Noida was asked this question in her interview. I am describing my approach to solve this question.
Fundamentals First
"Computer architecture supports two different memory storage techniques based on order of bytes in which data is stored in memory". e.g. In a two byte number 0xC06E
'C0' is Most Significant Byte (MSB) of this number.
'6E' is Least Significant Byte (LSB) of this number.
It is either saved with LSB first or MSB first.
Machines that store LSB first are Little Endian machines (6E C0)
And, Machines that store MSB first are Big Endian machines (C0 6E)
Tip: Intel Machines are Little Endian and PowerMac (Apple) are Big Endian.
Problem Definition
Write a piece of code that when compiled and executed on a machine tells whether machine is Little Endian or Big Endian.
Solution:
There are two ways we can achieve this by writing code. One, using Pointers and Second, using Unions (generally one of the less used feature of C).
Basic idea behind both these approaches is to assign a value of 1 to a multi-byte data type say int. And then check the first byte of memory address where multi-byte number is saved.
Approach 1: Using Pointers. #include<stdio.h>
#include<stdlib.h>
int isLittleEndian()
{
int intVal = 1;
int *ptrToInt = &intVal;
char *ptrToChar =(char *) ptrToInt;
if(*ptrToChar == 0)
return 0;
return 1;
}
int main()
{
if(isLittleEndian())
printf("Machine is Little Endian\n");
else
printf("Machine is Big Endian\n");
system("pause");
}
Approach 2: Using UNION #include<stdio.h>
#include<stdio.h>
#include<stdlib.h>
union
{
int a;
char b;
}testUnion;
int isLittleEndian()
{
testUnion.a = 1;
if(testUnion.b == 0)
return 0;
return 1;
}
int main()
{
if(isLittleEndian())
printf("Machine is Little Endian\n");
else
printf("Machine is Big Endian\n");
system("pause");
}
If you have any query/question or feedback. Feel free to send them over to codeboat@gmail.com
Background
This question is a frequently asked question in written tests conducted by Adobe. This question was sent to me by two of my close friends, one of them could easily make it to Adobe and is working with Adobe Noida now.
Problem Definition
In a Plane, If you are given co-ordinates of upper left corner and lower right corner of two rectangles, you need to write a #define macro which returns true/false based on whether triangles intersect/overlap.
Solution:
First let us set up data structure we will use for representation of rectangle so that we can then easily write an algorithm for the given problem. We can declare a structure representing rectangle and it can have x1, y1 and x2, y2 as two points. From a written test perspective it is sufficient to do so. But, It is always better to show your skills in a face to face interview here and be more modular.
First define a structure named Point and then use this structure when you are defining Rectangle. See the definitions below
struct Point
{
int x;
int y;
};
struct Rectangle
{
Point upperLeft;
Point lowerRight;
};
In this figure, consider 5 is the area of rectangle1 we are considering. We need to find conditions in which rectangle2 will not overlap with this. Conclusions:
- Any rectangle with it's lower right in areas 1, 2, 3, 4, 7 will not overlap with this rectangle.
- A rectangle with it's upper left in 3, 6, 7, 8, 9 will not overlap with it.
Conclusion2 can be coded as:
(rectangle2.lowerRight.x < rectangle1.upperLeft.x)
(rectangle2.lowerRight.y > rectangle1.upperLeft.y)
(rectangle2.upperLeft.x > rectangle1.lowerRight.x)
(rectangle2.upperLeft.y < rectangle1.lowerRight.y)Hence our final answer is
#define intersect(rectangle1, rectangle2) !(conclusion1 conclusion2)
Background
Gone are the days when Software companies used to ask questions like - write a function to reverse a given string. With increasing number of websites like this, providing solution to every other question asked in interviews, Companies are always going on step ahead in phrasing their questions to the candidate facing the interview. This one is a nice example of the same and was asked by Google from one of my friend.
Problem Definition
Based on given problem, Think of an example first to understand question better.
If You are given an input string:
"Code Boat provides best programming interview material."
Your program should generate and output like
"material. interview programming best provides Boat Code"
Solution 1:
Hmmm... Honestly, I believe in code reusablility. I just started thinking about strrev() function that used to asked in interviews previously, Yes!! you guessed it right it reverses whole string. But Didn't I say in the beginning that Companies have upgraded this question?? Yes, but keep in mind that this is a little bit different than what they used to ask previously. How?
- If I reverse whole string in Step 1.
- Then If I keep reversing all the words in it, one by one. I get an answer?
- Reverse Whole String it - "si it"
- Now Reverse words one by one first "si" to "is" and then "ti" to "it" and you get "is it"
void reverseString(char* string, int startIndex, int endIndex);
And then invoking it twice
- first with startIndex - 0 and endIndex- index of last char in whole string.
- Then by calling this function by passing start index and end index of individual words.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void reverseString(char str[], int startIndex, int endIndex)
{
char temp;
int i, j;
while(endIndex > startIndex)
{
temp = str[startIndex];
str[startIndex] = str[endIndex];
str[endIndex] = temp;
startIndex++;
endIndex--;
}
}
int main()
{
char str[] = "Code Boat provides best programming interview material.";
int length, index = 0, start=0, end;
length = strlen(str)-1;
//Reverse whole string first
reverseString(str,0,length);
printf("%-15s: %s\n","First Reversal",str);
//Reverse every word now
do
{
if(str[index] == ' ' || str[index]=='\0')
{
end = index-1;
reverseString(str,start,end);
start = index+1;
}
}while(index++ <= length);
printf("%-15s: %s\n","Final Reversal",str);
system("pause");
}
OUTPUT:
First Reversal : .lairetam weivretni gnimmargorp tseb sedivorp taoB edoC
Final Reversal : material. interview programming best provides Boat Code
Solution 2:
In case you are not asked to do an in-place reversal. Meaning, you can use extra space as well then you can use STACK data structure to PUSH all the words in given string and then POP them out to get reverse of string. Because STACK has a property Last In First Out. So output string contains the last word first. This solution is easy to code if you are using C# or JAVA like languages.
Algorithm For Solution 2
Input: "Code Boat provides best programming interview material."
//Pushing data onto stack
1. Read first word "Code" from string and PUSH on stack.
2. Read next word "Boat" and PUSH onto stack.
3. Repeat above steps until all words are exhausted.
//Solution Array
4. Declare index = 0 as start point.
5. POP first word i.e. material from stack and insert in str[index]
upto its str[index+lengthOfWord].
6. POP second word i.e. interview and insert in array
Background
This seems to be a very popular question for any web development interview to judge the basic knowledge of the candidate. To my surprise, when I was having my face to face interviews with D E Shaw, Hyderabad, I faced three different interviewers that day and this question was asked by all three of them. I was not very comfortable in answering this question and when I came back, Google search around the same did not help me get one convincing answer. So here I am to write it for you!!
Answer
GET and POST are simply two ways of communication between our web browser and a web server. Whenever we launch a browser and type in some url, browser sends and HTTP GET request to the server to get the page contents. So, GET is pretty much clear, right?
Now, An HTML page may have some form where we need to enter some information and press a submit button. Like for a google search we type in what we need in a text box and just hit an enter. Here developer needs to decide which method to use - GET (which is default if developer doesn't sepecify anything) or POST.
GET - It means that form data to be submitted will be encoded in the URL by browser and sent to the server. e.g. Google search for CodeBoat will submit data as
< form method="GET/POST" action="somescript.asp" >
You can just view source of Google.com home page you will find that form tag doesn't have a method specified which means it is using default method GET.
http://www.google.co.in/search?hl=en&q=codeboat&btnG=Search&meta=
POST - It means that form data needs to be submitted by browser as message body and not in URL.
<form action="/search" name=f >
So, Thumb Rule is - GET is meant for retrieving the data and POST is meant for sending data that updates database on server.
Important Points to Remember
- GET method has a limitation because URLs in may old browsers can not be more than 255 characters.
- GET can not be used when secure data needs to be sent to server. In case where a username and password are being sent to server for user validation.
- POST can handle as much data and is meant for sending data securely to the server.
