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.
Background
One of my subordinates applied for a job at Amazon, Hyderabad and he got a call for telephonic interview. According to him, Telephonic interview of Amazon is quiet easy where they do not look for depth in a particular technology. They rather cover Operating Systems, Databases, Web Technologies, OOPs and see the breadth of knowledge a candidate has. He requested me to allow him to give my name as one of the references in his resume and I agreed on one condition; If he can share his interview experience with me. I got two questions from him, One of them is this one.
Problem Statement
You are given a singly linked list, You have to write a function which takes as an input parameter pointer to the head node of the linked list and returns boolean result based on If list has a cycle (means end node doesn't have null in it and rather points to a node in the list itself) in it or not.
Solution
First of all whenever you are asked to write a function, what you should initially do is write the function prototype and ask your interviewer if that is what he wants!! Once you get the buy-in from him, proceed further to device an algorithm.
bool HasCycle(Node *head);
Proceeding further with this function definition, let use write code for the function.
Algorithm - Let us assume we are two people and there are set of connected rooms. We need to find whether these rooms are connected in a fashion that forms cycle or not? Here assumption is we are considering rooms to be arranged like linked list.
Now when we are two persons there to find that out, Let us assume it is you and me. Now you ask me to walk faster and see if there is any room that has no exit. And you keep coming slower. If I find a dead end I will come back and report to you otherwise, there will be time, where I will be chasing you inspite of leading you, If there is a cycle it will happen for sure. Thus If I catch you while following you, We conclude that there is a cycle.
With this algorithm in place, we are ready to go and write the code. Of course, using two pointers - You and ME!!
You can easily trace this function. And Yeah!! Good Luck for your upcoming Interview!!
typedef struct _Node
{
int data;
struct _Node* next;
}Node;
bool HasCycle(Node *head)
{
Node* fast, slow;
fast = slow = head;
while(true)
{
if(fast == NULL fast->next == NULL)
return false;
else if(fast==slow fast->next == slow)
return true;
else
{
fast = fast->next->next;
slow = slow->next;
}
}
}
Background
I attended an interview at D E Shaw last year and during face-to-face interview they usually have a puzzles round where they give you a puzzle and ask you to device an algorithm for solving it. I could not solve this particular problem during my interview but later on i kept thinking about it and now, I feel I've got a solution to this problem.
Problem Definition
There are two groups of wrestlers say Group A and Group B. Each group has 10 wrestlers. Given are two conditions:
- For a wrestler with given strength in group A there is a wrestler in group B of equal strength.
- No two wrestlers in a group have equal strength.
You have to find one-to-one mapping by arranging fights between wrestlers. Discuss the strategy/algorithm for the same.
Solution
Convention Let us name wrestlers in each group as:
Group A - WrestlerA1, WrestlerA2, .... WrestlerA10.
Group B- WrestlerB1, WrestlerB2, .... WrestlerB10.
Basic approach
Arrange a fight between WrestlerA1 and all the Wrestlers of Group B to find the matching wrestlers. Same way arrange a fight between WrestlerA2 and other remaining wrestlers of group B and keep following this strategy.
In a worst,
First wrestler has to fight with 9 wrestlers
Second has to fight 8 Wrestlers
Third has to fight 7 Wrestlers
And so on....
So this approach is not that efficient.
Quick Sort
If we correlate this to the quick sort algorithm, let us see what conclusion we can draw from it. Let us sort members of one group by arranging fights between themselves. In Group A - ramdomly select a member say wrestlerA5 and arrange fights between wrestlerA5 and all others and divide them among two groups - WinA5, LoseA5. where, WinA5 contain all the wrestlers who won from wrestlerA5 and LoseA5 contains all the member who lost to wrestlerA5.
Now among each sub-group use same kind of strategyand we get a group sorted like this. Avg Case Complexity in this case is O(NlogN).
Same way we can sort member in Group B and we get one-to-one correspondence based on given conditions.
Please leave a comment in case you have got a better solution than this one!!
Recently, I attended telephonic interview with LimeSpot Technology India Pvt. Ltd. (Noida). This was an hour long interview and below is the list of questions asked.
There was no introduction round.
Straight away I was asked following questions in given order:
[Interviewer]: Briefly explain the projects you have mentioned in your resume!!
[ME]: I was not having my resume with me so just honestly told him about the same. Then he selected one of my projects and asked about it.
[Interviewer]: When a "process" is started on a system what is the sequence of steps taken by OS at that time?
[ME]: As I work on Windows Operating Systems, I explained that any executable on Windows has a specific file format called Windows PE(Portable Executable) File Format. A PE file basically contains information about the executable in multiple, nicely organized, sections - data section, code section and file header, type of binary (32-bit or 64-bit), windows subsystem required by executable etc.
When OS loader starts a process it first validates the file format and determines Windows subsystem that this kind of exe requires to execute. Then OS allocates some address space and default to the process .
[Interviewer]: What are the various sections in address space of the process or how does the process's virtual memory look like?
[ME]: Process has a call stack for local variables, heap for runtime memory allocation and global data section, code.
[Interviewer]: What for does a process has this Stack?
[ME]: Local variables for a function are stored on Call Stack of the process. Whenever a function calls another function, context of calling function is stored on a new stack frame. Whenever callee returns then context of caller is obtained from stack and execution starts from instruction just after the function call.
[Interviewer]: What is process heap?
[ME]: Heap is area of memory that a process is allocated by operating system for any runtime memory requirements a process may have. Whenever we allocate memory using 'new' or 'malloc' kind of functions, it gets allocated from Heap only.
[Interviewer]: What is a thread, How does thread differ from a process?
[ME]: Thread is an actual executing instance of a process, a process can have one or more threads and all threads inside a process share same address space. Every thread has its' own call stack.
[Interviewer]: In a multi-threaded application how can you synchronize threads?
[ME]: Usually synchronization is achieved by using mutex, locks. In cases there are only two threads to be synchronized we can declare a boolean variable which if true then only thread1 starts execution and after thread1 is completed it can set the variable to false. Similarly, thread2 can check if the flag is false, then it executes and sets it to true.
[Interviewer]: Comment on inter-process communication!
[ME]: I read about IPC in my college days only and wrote programs for Linux so I just mentioned about Named Pipe, Shared Memory and Queues are used for Inter Process Communication. I was asked whether named pipe communication is possible on Windows systems as well. Yes, was the answer but I did not remember the Win32 APIs for creating Named-Pipes thus stopped my discussion over there and moved to the next question.
[Interviewer]: A website is reportedly having very bad performance and it uses databases to store it's information. What will be your strategy to fix this performance issue?
[ME]: My answer revolved around following three points:
- Avoid multiple round trips to the database.
- Cache data because new database servers provide this features (SQL Does)
- Use external CSS files inspite of inline CSS style code for individual html elements
- Minimize ViewState of a page
- See database design
- Use Indexes on Database Server
[ME]: I am not at all a database guy hence could answer only theoretically about it that a database supports indexing as we have book indexes to quickly search for any particular information we are searching for in a book.
[Interviewer]: Your resume mentions about a Chat Application project. Can you give a high level overview of how you created this application?
[ME]: I explained about my project and it's implementation.
[Interviewer]: In OOPs, Can you explain about polymorphism?
[ME]: I explained about overloading, as well as, runtime polymorphism.
[Interviewer]: Does C# support multiple inheritance? How can you achieve multiple inheritance in C#?
[ME]: No. A class can although implement as many interface thus we can create interfaces and implement them in a class, in case we want multiple inheritance.
[Interviewer]: Any idea about design patterns?
[ME]: As I have just started reading about design patterns, I told that this is current item on my TODO list and I am just reading about it. No experience about this so no further questions were asked about it!!
This was the end of it and I was given chance to ask questions. Here are the list of questions I asked:
What is the project I will be working on?
What is the source of revenue for Lime Spot as of now?
What are the travel opportunities at Lime Spot to US?
We exchanged "Have a Nice Time" kind of wishes with each other and interview was concluded. I've yet to listen from them!! (:)
Background
This is a question which usually gets asked in many programming interviews. One of my friends was asked this question in his Microsoft Interview and he answered it. Here is his experience in my words.
Tip!! When you face such question in interview, never hesitate to mention the solution that seems obvious to you.
Obvious Solution
Starting with first character of string, keep comparing this with all other characters in the string unless you find a non-repetitive one. But tell your interviewer that it is most trivial and Although you can optimize this solution by either comparing a character with the characters to the right of it, because this way you are removing redundant comparisons. But in both the cases, worst case complexity is going to be O(n^2). So tell your interviewer that you are looking for a better solution.
Maintaining a Count Array
A good solution may be if we can have an array which maintains count for number of times a character appears in the string and this array can be filled in O(n) by going once through the string. And once we are done with it, we can again parse whole string and find the first character that has count 1. Wow!!! This one requires two passes through whole string so it will take 2n time. Which is obviously O(n). If your interviewer is impressed with this approach then proceed further with the implementation of the algorithm.
int charCount[128];
char firstNonRepeatingChar(const char* string)
{
int i=0;
//Keep count
while(string[i]!='\0')
{
charCount[string[i]] += 1;
i++;
}
i=0;
//Find Character
while(string[i]!='\0')
{
if(charCount[string[i]] == 1)
return string[i];
i++;
}
return '-';
}
Special Note: Ask interviewer what does he want if all characters are repeated? In my case, interviewer told me, your function should return '-' in that case as they don't expect '-' to be one of the characters in the string.
But this is not where a tough interviewer will stop. Why??
Extra Space: Because you are using an array to store count of characters which will be of size 128 as there are 128 ASCII characters but if you are dealing with Unicode then this length will be 65536.
Optimize: Interviewer may ask you if you can make it n from 2n?
