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!!

  
  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;
         }
     }
  }
  

You can easily trace this function. And Yeah!! Good Luck for your upcoming Interview!!

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

I should admit here that I should have mentioned about -

• Minimize ViewState of a page
• See database design
• Use Indexes on Database Server

[Interviewer]: What are indexes in a database?
[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?