Deleting the entire linked list

This is another common interview question. The interviewer wants to see how you tackle the problem and maintain pointers to correctly de allocate all the memory reserved by the linked list.

Suppose you start with the head element and traverse the list and delete elements as you move along…but wait a minute! Do you advance the pointer first or delete the pointer first? Suppose you advance the pointer than how would you delete the previous node? And if you delete the node than you can’t advance as your node contains the address of the next element.  So to perform this function we would need to maintain two pointers one which would hold the current node and one which would hold the next node in the linked list. Here is a sample code in C++

Void Delete (Node ** head)
{

Node* temp = *head;
while (temp) {

Node * temp1 = temp->next;
delete temp;
temp = temp1;
}

*head = NULL;

}

Updated courtesy supergokhan

 

Comments (2)

Detecting a cycle in a linked List (Floyd’s Cycle Detection)

OK here is another very interesting interview problem which I wanted to discuss today. The problem at hand is that you are given a singly linked list and (unfortunately) it contains a cycle i.e. some node points back to an earlier node in the linked list. Your task being a software engineer is to detect if  the linked list contains a cycle.

My initial brainstorming gave me an idea that I should traverse the list and mark nodes on my way so if I reach a node that has already been marked Hurrah !! Got ya !

Lets see how this approach works. So now I need to maintain a status for every node so I updated my Node Structure as follows

Struct Node {
int data;
Node * link;
bool status;
}

Firstly I would have to initialize all nodes with status value equal to “false”

Node * temp = head;
while (temp) {
temp->status = false;
temp = temp->link;

}

Having done that now my job is very simple. I can detect the cycle as follows:

Node * current = head;
bool isCycle = false;

while (current){

if(current->status ==true){
isCycle = true;

}

current->status = true;
current=current->next;

}

The approach seems to be fine but it required us to change our original Node data structure. Supposing the interviewer wants you to come up with a solution that doesn’t change the underlying data structure than you need to figure out some other way. Let’s look at a different algorithm that achieves this.

Most of us would remember the rabbit and turtle story from our childhood where the rabbit was very quick and turtle was very slow during the race. Consider they were racing on a straight track and for sometime assume the rabbit didn’t become complacent and instead kept on running he would have reached the finish line much quicker than the turtle, however consider they were racing in a circular field and there was no finish line the rabbit would have moved ahead quickly and eventually would have crossed the turtle again after some time. Can we use this story for our help? Yes we surely can ! this algorithm is a classical example of Floyd’s Cycle Detection Algorithm or also known as Tortoise and Hare Algorithm. So if we have a cycle in our linked list than some where along the traversal the faster pointer (Hare) would meet the slower pointer (turtle) indicating we have a cycle , else the hare would reach the end of the linked list if there is no cycle. Let’s see how we can code this.

//Hare moves twice the speed of the Turtle so if we have a cycle eventually Hare would meet the turtle again.

bool isCycle(Node *head) {

Node * turtle, * Hare;

turtle=Hare=head;

while (Hare){

if(Hare>link ==turtle->link){

return true;

}

turtle = turtle->link;
Hare= Hare->link->link;

}

return false;

}

Comments (1)

mth from the last element of a singly linked list

Write a program to find the mth from the last element of a singly linked list

Singly Linked List

So for the linked list shown m= 0 would return the node with information field 1203 (tail element) and m = 1 would return node with information field 1202.

Solution:

This is a very common interview question. Let’s look at a very simple solution.

  1. Traverse the list and count the number of nodes.
  2. Calculate the offset of the mth from last element from the start using  offset = (length – m)
  3. Traverse the linked list again (for int i=1 ; i <=offset; i++) and return the current node.

However there must be a better way of approaching this instead of using loops to traverse the list twice.

Another solution can be as follows:

  1. Initialize two pointers p and q both pointing to the head of the linked list.
  2. Now let’s make the distance between p and q equals to m by incrementing the q pointed m times.
  3. Now check if q-> next == NULL (means we have reached the end of the linked list and p is at m positions from the last element so we return node pointed by p) else increment both points p = p-> next and q = q-> next and repeat step 3 again.

Rough implementation in C++ would be as follows:

Node * mthfromLast(Node * head, int m){

if(head==NULL|| m < 0)
{   return NULL;
}

Node * p, *q = head;

for (int i = 0 ; i < m; i++){
if(q->next == NULL)

{ return NULL;
}

q = q-> next;
}
while(q->next!= NULL) {

p = p-> next;

q = q-> next;

}
return p;
}

Singly Linked List Image was taken from : http://www.tech-faq.com/images/singly-linked-list_clip_image002.jpg

Leave a Comment

Raymond Davis

Dawn Newspaper 3/17/2011

ISLAMABAD: Federal Minister for Information and Broadcasting Dr Firdous Ashiq Awan said on Wednesday that Raymond Davis was released after the payment of blood money (diyat) in accordance with the Shariat Law of Pakistan.”

While skimming through today’s news paper the above headline caught my attention and like many Pakistanis a series of questions came up in my mind. Yes that’s true that Islam has laid down a proper code for accepting money against bloodshed to forgive the culprit. However on what grounds Raymond has been released from other cases such as carrying illegal arms and doing actions such as spying and putting the whole integrity of a nation on line? Which Shariat law or Country law allows foreigner to invade country secrets carry illegal arms and than just go away??? Any Pakistani involved in a similar action in US would have been let go this easily?.  Raymond should have been put under trial and test for all offenses before allowing to fly off away from the country. It’s a shame that Government officials preplanned everything to allow him a safe exit.

Honorable minister although your statement reflects your loyalties to your party and to your seat and NOT to Pakistani nation, but would you have accepted bloodshed money decision if God forbids something of similar sort had happened to your loved ones?

Let’s for a change draw a line at some point in degrading ourselves in front of  US.

 

Leave a Comment

Struggling Freelancer? Follow the 10 Commandments!

Struggling Freelancer? Follow the 10 Commandments!

The Ten Commandments which according to the Hebrew Bible is a list of religious and moral imperatives that were given by God to the people of Israel to give them a clear direction as to how to achieve religious success by avoiding some cardinal sins! Without a doubt success in any domain can only come if we avoid “sins” related to that domain and freelancing is no exception. To make the best out of our freelancing job we have to avoid these sins and follow what I call the 10 Commandments of Freelancing.

1. Thou shall not Work without a contract: Pinch yourself hard! Does it pains? Yes it must have, sadly this is real world! We are not living in a world only to be heard of in fantasy stories where everyone is loyal and you can trust every potential client and can’t believe that they can stab us in the back. The biggest mistake many freelancers do is that they just trust the client too much! Protect all your bases before starting the work with a fully documented contract including things such as payment terms and scope of work to be delivered.

 

2. Thou shall not undercharge: Are you working 18+ hours a day on your freelance projects and still managing a diet which includes beans and bread most of the time? Surely is one of many signs that you might be charging too little! Most freelancers don’t even know what they are worth! Or are happy with an amount with which they can meet there minimum expenses. Always keep yourself up to date with the latest hourly or fixed time rates for the domain you work in.

 

3. Thou shall not overcharge: Having said that you should know what’s your worth is and not undercharge you should always understand that clients are always looking for a quality yet cost effective solution. Keep up to date with market prices of similar services and always bid around it to gain attention. Anything way above or way down and alarm bells start ringing in the customers mind.

 

4. Thou shall not overload your plates: you should know your limits. I agree that the feel of earning more and more dollars is simply irresistible but “reputation” that’s something on which your business would grow in the future. Avoid working like the greedy algorithms searching for a local optimum and in turn spoiling the global optimum! Don’t overload yourself with work, be within your limits and build a reputation with quality work.

 

5. Thou shall not miss deadlines: I can’t insist on this more! This may be one of the worst forms of sins in freelancing. Clients hate deviations in commitments and this would ruin all your reputation until and unless you have a very genuine excuse.

 

6. Thou shall not work with simply every client: Remember it’s a real world! There are all types of clients in the world, some clients want the whole word but simply don’t want to spend anything. Some clients are just simply too hard to please! No matter what you do. Excuse such clients in a polite manner so you can focus more on clients who are happy to pay you up to par and bring you more success.

 

7. Thou shall NOT rely on just a single client: That’s a major mistake many freelancers do when they initiate a startup. You might find an angelic client who would suffice your need for the time being for success you need to diversify yourself work with different people which not only improves your confidence but also you establish growing relationships and business links.

 

8. Thou shall not become static: Technology never stays the same! If you want to achieve success in the freelancing domain and keep up with the pace of changing technology.

 

9. Thou shall not stop marketing your services: Have a lot of work? Well let’s be honest it’s not going to last forever. Keep advertising or marketing your services socialize with people go on business events or conferences that’s where you make relationships and out of any such relationship you get a solid lead or a reference.

 

10. Thou shall always follow up with your clients: Have a bunch of happy clients? Always follow up with them introduce new services and keep in touch. They can be your biggest source of new work both by giving you work themselves or referring other potential clients.

 

The list is exhaustive however if you follow these 10 golden rules you are guaranteed to have success in freelancing domain.

Leave a Comment

How to Apply for a Freelance Project

I started freelancing back in 2006 when I was going through the final phases of my Bachelors degree in Computer science and like any other graduate student I wanted to make some extra cash apart from my pocket money to meet my every growing list of expensesJ.

The toughest part of being a freelancer is hunting for leads and then stands out amongst a huge pool of potential candidates to catch the employers/clients attention. While popular job boards such as vworker.com, odesk.com, guru.com, freelancer.com and elance.com have made the job of searching for suitable projects/jobs easier, the later is still a difficult job on hand.

Over the years I have grown a complete company out of my initial one man freelance startup with some simple methodologies that make you have employer’s attention instantly. Once you have his attention. Well done! Now you simply have to build on this to secure the lead.  In this blog post I wanted to share some of those insights that I learnt over the years.

  • Read the Entire Job Description: I know sometimes project postings can become really lengthy and boring and you just want to skim over the description and simply apply/bid on the position. I can’t stress that enough! Employers spend hours and hours nailing down the requirements and they expect the same from all the potential candidates as well! It’s their first criteria of filtering out a good candidate from a rejected candidate. For them it’s simple if you are not focused enough to even go through the entire description once than in the long run you won’t be staying focused on the actual job on hand.

 

  • Avoid Generic Bids: If I am the employer I would hate this the most! if you don’t even have the courtesy to go over my project requirements and reply back with project specific questions/relevant experiences or portfolios/suggestions etc. than it would be better off that I ignore your bid altogether. So as a rule of thumb attract the client always by asking him questions about the project and try to involve him in a conversation. This gives the employer an impression that you are serious about the project and give some thought about his requirements. Give him a feeling that you gave special personalized attention to his project!

 

  • Remain within your limits: Since this won’t be the last post on which you would be bidding or commenting neither it would be the last project the employer would be posting its always a great idea to leave a good impression. So assuming the client project requirements state “I am looking for a C# programmer with over 10 years of professional experience” ask yourself am I entitled for this position/project? Considering the requirement would I be putting on stake client’s time and resources as well as mine? And of course in the long run would it spoil my freelance image in front of a client who has potentially a lot more of work coming up? Be honest with your self! It will really pay off in the long run. I have numerous clients who come over sometimes offering thousands of dollars for doing a development in language/domain I am totally alien in, at first it’s tempting but remember one failure means your whole image goes down.

 

  • Portfolio: Once you are done with everything in a structured manner and client is interested in talking further with you, he would be asking for your relevant experience. Always keep you portfolio up to date. Categorize your portfolio and make it very easy for the client to locate relevant experience. Remember the client is not interested in how fancy your portfolio page looks rather what’s the quality of work you have done until now.

 

  • Communication: I can’t insist it more but constant communication is the key to build a long lasting relationship. Clients are investing time and money in the project and most of the time they are under time pressures too. So if you can’t keep in touch at all times or give timely project status reports its more than likely that after an initial project the client won’t ever approach you again. Make your clients feel that their projects are in safe hands!

 

Comments (1)

Microsoft Interview Experience

Last month I applied to Microsoft through their college recruiting website for SDE/SDET positions and to my amazement the very next day I was contacted by a recruiter who was interested in setting up a telephonic interview with me and had sent me a few initial questionnaires to fill back and return to her. We decided a date and time and I started waiting anxiously for the big day.

Phone Interview

Nicole (recruiter) was sharp on time on the interview day and started off the conversation in a very friendly manner which really helped easing my nerves out. There were no technical questions asked (although I was anticipating a lot of them) and most of the conversation revolved around my resume on questions such as what was your most challenging project? What would you have done different if allowed to go back in time? Do you like to work standalone or do you prefer team projects? Why do you want to work for Microsoft? And finally before we hung up the phone she said “Ok if I want you to test a calculator with simple mathematical functions and made for small children. How would you test it? “. I then asked here a large number of different questions on Microsoft’s work culture, salary and benefits and career paths before we ended the interview. I was pretty satisfied with my performance and was expecting a call up for further rounds.

After two weeks I was again contacted by another recruiter who wanted to set me up for a face to face interview in Dubai on 3rd March 2011.  I was asked to provide all my travelling details which I did so and Microsoft arranged a fully paid trip to Dubai for me.

My interview was in the evening session and to avoid any last moment delays I reached Microsoft Office 30 minutes before the scheduled time. I had to go over 4 technical interviews with Directors of Microsoft Business solutions, Windows Azure, Silverlight and Visual Studio groups respectively.

Interview-1

My first interview was with Director of Business Solutions group (Mr. Azfar). We started off with general discussion about my resume before I was handed a marker and was asked to solve problems on the white board.  The questions that I was asked here were as follows:

  • Write a function that takes a pointer to the head of a linked list and an index and deletes that node. Node consists of a void pointer data and link to the next node. Write test cases for this function.
  •  What’s the difference between master data and reference data?
  • Suppose you have to design the sales modules of an ERP system how you would structure the model for better reporting?
  • Suppose you are given a bit stream and you don’t know from where the bit stream starts. Write a function that returns true if the bit stream has an alternating pattern. For example 000000101010 would return true and 0000001010000 would return false.  Also I had to write test cases for the function.

I was very confident throughout and hardly faced any issue in nailing out the problems on the whiteboard.  I was walking through my algorithms keeping the interviewer in loop and also managed to come up with solid designs and test cases. The interview ended lasted for about 50 minutes after which I was given a 2 minute period to ask any questions if I had. Overall the first interview was a very satisfactory one and it geared me up for upcoming interviews.

We had a 15 minute break during which the recruiter on site Erick, a nice friendly chap made us fill some forms and asked me about my interests and possible teams I would like to work on.

Interview-2

My second interview was with Jason who is head of Testing in Microsoft Visual Studio team (if I am recalling correctly) he was one of the most nice fellows I have ever came across in my professional career he was very friendly and supporting throughout the interview.  Once again I was asked to code on the whiteboard. The coding problems were as follows:

  1. Write a function that takes two strings and returns true if one string is the substring of other.
  2. Suppose you have a  2D array whose elements are increasing both row wise and column wise and you have to find an element if it is present in the array or not. I had to come up with an efficient algorithm for doing this.
  3. Write test cases for both the above functions.
  4. Design a stack using two queues.

I got confused a bit during the interview and hence took longer than normal to solve these simple problems. However Jason was very comforting and supporting throughout.

Interview 3

Third interview was with Director of Windows Azure Development group. This interview focused totally on problem solving and writing test cases for the problems. The problems I was asked during the interview were

  1. Suppose you have a dictionary of words design an algorithm that would scan all words and determine all words that are anagrams. Your algorithm should be efficient and NOT O (n square).
  2. Write a function that would return the first non repeating character in a string. So “Total” would return 0.
  3. Write a function to print the mth from last element of a linked list. (m=0 is the last element). This had to be done using one loop only.
  4. Reverse a string in place ! (in place was the only catch here)

Once again I managed to come up with solutions of all the problems. There was a slight bug in my solution to problem 2 which the interviewer pointed out and I fixed it. Other than that the interviewer was pretty satisfied on how I approached the problems and covered all cases. I was pretty satisfied with this interview and was anxiously waiting for the next one.

 

Interview 4

This was my final interview for the day. I don’t exactly remember the name and designation of the recruiter but he was one friendly chap. Very energetic! And as soon as we entered the conference room he laid the rules straight away! “Write a fully working code! And write efficient code and nothing less!”  All I managed to do was to smile and reply back “ I will try my best”. This interview lasted for 50 minutes and I had just one problem to solve. The problem was as follows:

  1. Suppose you have Binary tree you want to store the binary tree somewhere on the disk or on the cloud once stored than write a routine that would retrieve and rebuild the tree. Cover all cases and come up with at least 10 solid cases.

After a few minutes of brainstorming I came up with an algorithm which I guess really took the interviewer with surprise and he was really impressed with the approach. We managed to walk through the algorithm and write proper code on the white board. The test case session was a very interactive one and I managed to come up with some strong test cases. Overall the interview ended up on a very satisfactory note and I walked out confident and hoping for success!

Post Interviews:

Microsoft gave all the candidates souvenirs and we left for our hotels. I had the flight same night so had little time to roam around Dubai.

Now after 3 days of my interview I was contacted back by Microsoft that they would like to make me an offer in their Dynamics team! It’s an amazing feeling and I have no words to explain this. I am looking forward to a life time experience at Microsoft in coming months!

If you have any questions related to my experience you can contact me by responding to the post.

Comments (28)

« Newer Posts · Older Posts »