Posts Tagged ‘interview’

Posted on November 28, 2011 - by Sarath

Preparing for your first-job interviews

It has been a long time since i wrote a blog entry. Here is some interesting piece for final year computer science students.

Getting a job is one of the happiest things in the life of a final year guy. I also had such wonderful moments during my final year. I would like to share some bytes of info that can help you out.

University/College studies and your first job

In the long four years of engineering course, you study a lot of things. Lot of junk and little good. In reality very few subjects really help and are useful for a computer science job. For getting a job, you will need even fewer set of subjects among them. Hence, finding a job is easy. But you have to master the subjects that you love. I will list out the few subjects that will help you find a job.

Data structures, Algorithms and Analysis, Operating Systems, Computer Networks, C Programming, Object Oriented Programming, Database Management systems, Compilers (Optional), Distributed Computing (Optional), Microprocessors (Optional)

The perspective of current education system and the industry goals diverge very much. In colleges, we study for obtaining some marks. The teachers also have the goal to help their students to obtain marks rather than learning something that may help gain the ability to solve computer science programs using their skillsets. In industry, the ultimate goal is to produce good quality software within short span of time. That means, the skill requirements are good coding skills, ability to understand and solve problems algorithmically with analysis to validate and come up with optimal and practical solution. To grow up as a software engineer that meets the industry requirements, the education system at college fails.

You have to put good self effort to gain the skillsets and the passion for learning. You should have good coding skills with proficiency in one or more programming languages, understanding of standard algorithm techniques at basic level. Let us have a run through objectives during preparation for a job.

Preparing your CV

Curriculum Vitae is important while applying for a job. Your CV is a blueprint of your personality. It is the first phase during a recruitment that gives the recruiters an overall view of your skillset and your background. Hence, it is worth to spend few days in preparing your CV. Note the following things while preparing your CV.

Use a different layout from other candidates who are applying for job along with you. Make yourself different from others. Write a career objective that states your interest. If you are applying for a specific role, Write a highlights section as the first section in your CV. Highlights should list out important achievements and your skillsets in bullets. This section is indented for HR who screens your resume. The next section can be ‘Skills’, which lists out your skill sets and programming languages. Write in an order separated by commas such that less proficient technologies should come last. You should also mention the operating systems you are familiar with. The next section can be Achievements. But you can move this section to the end of the resume if you think that you do not have considerable good technical achievements for highlighting. The next section should be Projects. This is the most important section in your resume. You should spend some time in writing this section. You should specify the title of the project, duration (optional), the technologies used, a summary of the project describing the project in few words, and project highlights section. The project highlight section should list key features about your project listed as bullets. Write them in an impressive manner stating the facts properly.

Eg.

1. Implemented a H.263 video streaming library for android 2.3

2. Implemented video frames collector and device mapper that converts video stream to v4l linux device

3. Tested on Android 2.3 and found that 25 % performance improvement than the bundled video library

If you have lot of numbers to showcase the benchmarking or awesomeness of your project. that is great. If your project bagged some awards or deployed for some good numbers of users, mention that figures and achievements in the highlights.

I would prefer to order the project in the order of significance rather than chronological order. After the project section, have an achievements section which lists all technical and non-technical achievements. You can split your achievements section into subsections like publications, events, etc. Write the educational background section as the last section of your resume. Because it is the most insignificant portion of a resume if you are looking for a good computer science job. It states few figures that indicate your marks which is not an indicator of your knowledge.

Tips for interview preparation

You should acquire sound knowledge about few of the subjects listed in the earlier section of this article. Usually recruitment process consists of a written test paper followed by a couple of interviews. Focus of your preparation should be based on the job position you are applying for. If you are preparing for a developer interview, you should be sound with Data Structures and Algorithms. You might be bored with the subject since you attended some boring series of lectures from colleges to grab marks. Try again approaching the subject in a different manner. You will definitely enjoy it. Start reading the book ‘Programming Pearls’ before you start preparing. It will give you a wonderful insight you never had before. I will focus on developer interviews.

Companies usually ask some technical aptitude questions, puzzles and questions from the subjects along with the test paper. Most of the questions will be repeated. Search for programmer interview aptitude questions and brain teasers for programmers on Google. You will find a good list. Try to solve them. Learning algorithms are not hard. But understanding the use cases and ability to apply them to solve problems require some effort and practice. Whenever you learn an algorithm, try to implement it using a programming language. For practicing algorithms to coding, you should use some highly object oriented and simple languages. The best language you can learn is python. You can practice coding algorithms with Python without any implementation complexity and it will look like a pseudo code. Learn python today. Seriously it won’t take more than a day to learn things that you will require to implement algorithms. C is a great language. Implementing certain Data structures or algorithms in C gives you a good experience to code well in C. I will write some notes on few algorithms that you should try implement in C. Algorithm analysis for important algorithms should be understood. You should know the worst case complexity (Find out the worst cases in the case of a particular algorithm), Best Case complexity (Also the best case) and the average case complexity (Also the average case example). Space complexity of the algorithm should be known in order to select the best algorithm according to problem environment.

Data Structures and Algorithms

Binary Search

This is a very important algorithm you can apply at many different problem environments you never expect.

Understand the runtime complexity for the Binary Search and understand how to derive the complexity from algorithm. Note that it can be applied for only sorted lists. Learn how to apply Binary Search in a Rotated Sorted List by using recursion and how the algorithm complexity varies. Implement Binary Search using C for a list of strings. You should familiarize the terms in place sorting, stable sorting and also should understand which sorts come into these categories.

Insertion Sort

Understand the algorithm and derivation of algorithm analysis. Compare it with Card game in which we move the cards to the suitable position. Keep the example in mind and apply to similar problems. In Insertion sort, we sort the element set by consequently moving the current element to the appropriate position in an already sorted set.

QuickSort
QuickSort is a very important sorting technique. It uses divide and conquer technique. Divide the given set of elements into smaller sets recursively and apply comparison and swap. When comparison and swap is performed to formulated smaller sets, it results in the larger sorted set. Learn algorithm analysis. Learn how to find kth smallest element by modifying the Quicksort algorithm in O(nk) complexity. Find out mean of a set of elements in O(n) by modifying the above problem.

MergeSort
Mergesort is also a divide and conquer sorting technique. The concept is to merge two sorted list to obtain larger sorted set. By dividing the given array into smaller subset by recursion, smaller subsets are formed. Merging the subsets from lower level to higher level, we obtain sorted array. Learn algorithm analysis. Note that merge sort takes an extra array. Hence this is not an in place sorting. It has O(n) space complexity. You should practice problems related to merge sort. Eg. You are given two sorted arrays with size n and 2n. The second array contain n elements in the positions 0 to n-1. Now without using extra space, formulate the elements in 1st and 2nd array into 2nd array and return a sorted array of size 2n.

HeapSort
Heapsort is an interesting sorting technique. Heap is a tree in which parent node is always >= child nodes (called as max-heap) or parent node is always <= child nodes (called as min-heap). This is the basic property for a heap. Let us have an overview of how to create a heap and manage it. When we need to add an element into an existing heap, we add the element as root or to the rightmost bottom element in the heap. Then apply heapify operation. Heapify operation can be of two types: shiftup and shift down. When we add a new element to an existing heap as root element, we perform shift down operation. Shift down operation performs a traversal from root level to bottom level, at each level of traversal, it compares whether heap property is violated, if so it will perform swap between parent node and child node to obey the heap property. Hence the element we added as root will move to the accurate position when the traversal reaches the bottom level. If we add a new element to the bottom right element, we need to perform a shift up to position the element to the right position. We traverse from parent in the bottom level to the root, by checking the heap property at each level and swapping elements to meet the heap property, we get a balanced heap when traversal reaches the top element.

Heapsort makes use of these operations to obtain a sorted set. Let us assume we have a heap (1,n). the root element will be the highest value (max-heap). Hence it will be the last element in the sorted list. We swap the root and the last element. Now the heap property is lost. But the nth position of array has the correct element in the sorted list. So we exclude nth element and heapify the heap(1,n-1) by using shift down operation. Because the root element is the one breaking the heap balance. After doing heapify 2nd time, we get 2nd highest element as root element. Now swap root element with n-1 element. Hence n-1, nth elements are 2nd largest and largest elements. Now exclude the n-1 and nth element, heapify heap(1,n-2). Follow the procedure until the newly formed heap size become one. You will get a sorted list. Read the chapter Heaps from Programming Pearls (It will give you a wonderful insight). Practice the problems: Find kth largest element from a given unsorted array. Implement priority queues.

External Sorting

External sorting is an important sorting technique used when the amount of data we need to process is greater than the available memory. For eg, we have 1GB of integers and 256MB of RAM. Hence it is clear that we cannot load entire list of numbers into ram and perform in memory sorting. External sorting techniques are to be used to solve this problem. K-Way merging is one of the simplest methods to solve the problem of RAM < data size. We can split the data into K parts. The part split is performed such that each split is less than the size of RAM. Then we can sort each part individually using any sorting algorithm. Then we can perform a special type of merging to obtain sorted output. Let us see how to perform the merge.

For eg, we split the data into 4 parts and we individually sorted them. Then take the first element from each 4 sorted lists and sort them and find out the lowest element. It will be the first element in the sorted output. Add it to the new list called full sorted array.

Now, from the array from which we obtained the lowest element, take the next element, sort the list again and find out the second lowest element. From the array we obtained 2nd lowest element pop out the next element and sort again to find out the third lowest element. Proceed the process until all arrays becomes empty or one array remains few elements. If an array remains unempty add those elements in the order to the full sorted array. Have a look at implementation code (http://code.google.com/p/kway/)

Bit array technique for solving RAM < Data problem for sorting counting numbers

In a 32 bit system an integer takes 32bits to store an integer and a 64 bit system takes 64bits to store a number. But for storing counting numbers, we can use bit vectors which are formulated by using 64 or 32 bits in an integer. If we set 0th bit in 32 bit we can represent it as 1. If we set 2nd position, we can represent it as 2. If we define an integer array of size N, we can actually represent 32*N numbers using that integer array. In order to sort large number of unique counting numbers we can use, bitsorting by setting and clearing bit positions. If we need to represent 1 to 68 numbers we need only 68 bits. We can represent it using an integer array of size 3. Ie, 32*3 = 96 bits. To set 68^th bit, we know that 68^th bit is situated in the array offset 2. To obtain the array offset, divide the number by 32. (68/32 = 2). Now we need to know which bit position needs to be set in the 32 bits available in array[2]. For that, findout modulus by 32. 68%32 = 4. Hence set the 4^th bit in the array[2]. This can be performed without division and modulus operators by using bit shift operators.

Here we find out i/32 using right shift operator (Each right shift causes division by two. Five times rightshift = division by 2^5 (32) ). By using AND operation with 0x1F, we get 5 Least significant bits, the value of 5 LSB returns in the position in 32 bits. Hence we shift 1 towards that much positions to left and is ORed to do the bit set operation.

Have a look at the implementation code. http://cm.bell-labs.com/cm/cs/pearls/bitsort.c

Bit manipulation problems

By using bit manupulation, we can do lot of tricks over numbers. See http://graphics.stanford.edu/~seander/bithacks.html for lot of interesting bit twiddling hacks.

One of the very common problems, is counting the number of set bits in a number.

n&(n-1) will return a number obtained by setting rightmost set bit in number n to zero.

Another problem is to check whether a number is power of 2. For a number which is power of 2, there will be only one set bit in the number. Hence if we do n=n&(n-1), we will obtain zero. Using a single line operation we can identify power of 2 or not.

Hashing

Hash is an important data structure that can be used to solve different problems. When you are asked to find the number of occurrence of numbers in a given list of numbers, you can simply use hash for solving the problem. Iterate through the list of numbers, like:

We can solve many problems in O(n) using hash.
Implementing a hashtable in C is not easy at a first attempt. Try to code yourself a hashtable in C using pointer to pointer.

Binary Tree and Traversals

Binary trees are common interview questions. There are lot of BT based questions. Have understanding of common questions like the following.

* Difference between full binary tree and complete binary tree

* Find out Maximum/Minimum height of a tree (Recursive and Non-Recursive)

* What is the maximum number of elements in a tree with height H.

* Nth smallest/largest element in a binary tree

* Algorithm to find out Least Common Ancestor (LCA)

For your information, Least Common Ancestor is the common node in a binary tree which is obtained by traversing from two selected leaf nodes to the root element.

Linked list problems

- Reversing linked list

Linked lists are also very common interviewer question. First practice to be done for linked list problem is to write a linked list structure in C yourself and implement linked list traversal. Then add functions to reverse the linked list in place as well as by creating new linked list. If you do not want a new linked list, but you only need to print the elements of linked list in reverse order, use a recursive function that can do recursive calls till the end of linked list and print the elements.
Eg.

- Cycle in a linked list

Test for cycle/loop in a linked list is a commonly asked problem. You can initialize two variables as start node for linked list and traverse in a while loop such that while loop ends when one of them becomes null or both variables becomes equal. In the while loop, we traverse two variables with different speed.
(varA=varA->next, varB=varB->next->next)

Have a look at well explained tutorial, ?http://ostermiller.org/find_loop_singly_linked_list.html

Tree traversals

It is very important to understand all the tree traversals and implementation.

1. Preorder traversal

2. Post order traversal

3. Inorder traversal

Traversals can be easily implemented using recursion. But interviewers might ask about non-recursive algorithm. In that case, use stack based algorithm to explain inorder traversal. You can easily implement inorder traversal using stack.

Graph Traversals

Graph traversals are commonly asked in interviews. Have the understanding of Shortest path algorithms.

Depth First Search

In depth first search initially traversal goes deep into deepest node and traversal proceeds. You can use a stack to implement depth first search or else ?you can use recursion to implement this.

Breadth First Search

In breadthwise traversal, you can use it to print the tree in the sorted order. You can use the same algorithm used for depth first search by changing stack into queue to obtain the algorithm for BFS.

Dynamic programming
Dynamic programming is an important algorithm technique to solve a large problem by splitting into smaller overlapping problems. When overlapping small problems are solved, the larger problem solution is obtained. Problems like finding shortest path can be solved using dynamic programming. It usually involves using a storage of subsolutions so that they are used in solving bigger problems which overaps the subsolutions. The dynamic programming is difficult to identify as well as apply to solve problem scenarios. It requires considerable spending of time to learn and master it. When you look into some problems and look at its solutions, you may feel it is not that hard. But when you are given a different problem you may not be even able to identify it can be solved using dynamic programming. Even if you identify, you will find hard to code the problem solution. Hence, give considerable time to work on this one.

Try to learn the problem to find subsets of a set using dynamic programming

Trie data structure
Trie is an interesting data structure that can be used to implement autocomplete feature. You can read more about trie from my older blog post. (Implementing autocomplete with trie data structure)

Conceptual Questions

Lot of conceptual questions are being asked during interviews. It will test your basic knowledge and understanding. Find some of the commonly asked topics

* CPU Scheduling algorithms

* Layers of TCP and OSI network stack

* Understand how Virtual Memory/Paging works

* Understand what happens when you enter a URL on web browser and how website is loaded

* Understand how a computer boots and explain the story

* What is the difference between 32 bit and 64 bit machine and OS

* Understanding TCP/UDP protocol

* Understanding ARP/RARP

* Understand DHCP

* Understand DNS (Recursive, Iterative resolution)

* Understand how email works (POP, SMTP)

* Understand Web 2.0, REST, Thrift, RPC

* Understand IPV4 vs IPV6

Books/References

1. Programming Pearls
Programming pearls is a great book you should read as a computer enthusiast. You will be inspired to learn about data structures and algorithms.

2. Cracking the Code interview
It is a nice book consisting of lots of interesting questions

3. Glassdoor.com
Glassdoor is a great website consisting of lots of questions being asked for different companies. As a first programming exercise, write a perl/python/bash script to parse questions into a text file. I had a python script that I had written long time ago. (Lost that somewhere)

Choosing your first job

Every job interview is a great experience. In my life, i had attended three job inteviews and ended up in receiving 3 offers. Each of the interviews were different experiences. Once you face interviews build positive approach in finding feedback yourself. When you receive multiple offers, put enough effort to understand about what you are going to do with each of the job offers your receive. Choose the job you love to do, so that you never have to work a day in life. Thanks and all the wishes.

You can find few posts about interviews from this blog here, http://www.sarathlakshman.com/category/interview/
I dedicate this blog post to all my juniors in Computer Science Dept, Model Engineering College, Cochin

Image credit: http://www.flickr.com/photos/stevefrog8/

Posted on April 30, 2011 - by Sarath

Writing a Tic Tac Toe program using AI (Minimax)

Most of us know the Tic-Tac-Toe game. If not, you might know this game in another name. I belonged to the second category. I had played this game many times in my childhood but with another localised name. This game said to be a simplest example of programming with a game tree. Tic-Tac-Toe also seems to be a common interview coding question for Software Engineer – Developer positions.

Let me give a brief idea of what is this game about. It consits of a board containing 9 cells with 3×3 (rowxcolumn). It is a two player game with each player assigned with a marker symbol (X or O). During the first turn the player mark the symbol X (Marker symbol corresponding to the player) to a cell among the available cells, and the second player will mark O (Second player’s symbol) to a cell among the available cells. The game continues until it reaches either one of the conditions:
When one column, row or diagonal has X, The player assigned with X wins else if this state arrived for O, the player O wins. If the board contains no free cell left and none of the above conditions arrived, the Game ends with Draw. (more…)

Posted on April 20, 2011 - by Sarath

Zynga India interview experience

Zynga is well known for the social gaming platform which has emerged through Facebook. Zynga has played a great role in bringing about a good number of user base through the gaming platform. Last year, Zynga started their first international office outside US in India. Recently, I appeared for Zynga interview and landed with a job offer.

It happened all of a sudden. My book (Linux Shell Scripting Cookbook) news spread through different mailing lists. One of the XMECian who works as Engineering Manager at Zynga, India refered me hearing this
news. He came online and asked for my Resume. Within a minute after I send my resume, I got a phone call from Zynga HR. He told me that they want to consider me for Studio Engineering team (The team which is responsible for development and maintenance of Zynga games) and asked whether I am available for the following week. We decided to conduct the interview on March 10th. He told that he will book the flight tickets and get back through mail. The call was less than 1 minute. I was stuck. Hooh. I asked the man who referred me what was happening in a minute. He answered simply with a smilie, “Zynga Speed!”.

Two days before the interview date, HR contacted me and confirmed the date again. He sent me round trip flight tickets (Cochin – Bangalore). I had no clue what kind of interview will it be and what kind of role they are looking for. I did not prepare anything since they are conducting me direct interview without conducting the test process.

I was eagerly waiting for February 10th. Finally the day came. The flight was scheduled for 7.45 AM. I was so excited. My first flight journey. I reached the airport in time. Thanks to my friend Harish for dropping me at the airport ruining his sleep. It was Kingfisher red small flight. I got the seat 1F, which was the first row window seat. It was a great experience – flight taking off and landing. The flight reached bangalore on time. There were buses to the city in front of the airport. I took some BIAS – 6 bus and told bus conductor to remind me when reach M.G road. I stepped down near M.G road. When I asked some one standing near the bus stop he directed me to a road. I walked for sometime and I understood that I am not going to reach anywhere. So I hired an autorikshaw reached the Zynga Game Network which is in the 5th floor of Esquire building.

The HR welcomed me and I followed him to a conference cabin. In 10 minutes, an interviewer came. He introduced himself that he is working as Principal Engineer in the studio and has been working in Microsoft-US for many years and after that Google-In for last two years. He asked about myself and scanned through my resume. He asked what I would like to do and what I have been doing. I gave a brief intro about myself and gave an overview of work I have done in the past. He was very curious to know about my projects and asked many interesting questions. I could use the whiteboard to illustrate my explanations. When I told that my interests are with Operating Systems, he asked few questions to check my understanding about Scheduling, Paging, Virtual memory, etc. He asked me three coding questions and 1 puzzle (for designing an approach to solve a game). While going through my projects, he was very much curious about my Pardusman project. We had a very friendly conversation. At the end of my interview, he asked about my interest on which stream I would like to choose. Studio Engineering, Network operations and something else. He explained me about what studio engineering team does. Basically studio team takes
the ownership of games and also develop, release and maintain them. Studio team work on technologies like PHP, Adobe Flash, JS, etc (More specifically Windows platform). I was more specifically interested in a group called Systems Engineering Group (SEG). They write systems tools for servers as well as bugfix, patch, improve already existing opensource systems tools, servers for Zynga’s own purpose of deploying in the servers. But sadly, they don’t recruit freshers to SEG. After the first interview I met one of the XMECian, who works as Senior Software Engineer at Zynga. He gave a good picture of Zynga, how they work, the different teams, etc. I went to the cafeteria for lunch. Zynga offers free food to all employees . I met my Senior at Cafeteria and was having lunch along with him. Suddenly somebody called my name and told that we will have lunck together. He started asking about me and why I am at Zynga today, etc. Asked about my interests, college life and we talked a lot. In the mid, he introduced himself. He was a technical architect at studio team. He told that it is also an interview. We talked lot of technical things. After the food, we moved to a conference cabin. He asked which are the programming languages I am comfortable with. Then he gave me two coding questions. One on Javascript and another on C. He told that he will be back after few minutes. He returned after few minutes and looked at my papers and said few comments and thanks. The interview is over. I got few insights during his interview. The HR came to me and told that I will be next interviewed by Director of Engineering, Studio. In the next interview, he introduced himself and told that he worked in US as Vice president for Myspace. It was great talking to him. We had a very friendly conversation rather than interview question answer sessions. He shared his experience of building great scalable products. I showed him my book. He was really curious to know about me. Very pleasant piece of conversation. By the end of the interview the time was up.

The HR came to me in a hurry and told that Cab is ready and I can move to the airport. He brought me immediately to the Cafeteria and got some cold drinks. HR was really nice, he was taking care of everything. I was accompanied by another person who introduced himself as CEO of some dot com company. I reached airport in time. I came to Cochin on Jetairways Boeing flight. Thanks to my roommate Navin for picking me from airport to hostel. The next day I had a phone HR interview for zynga. It was usual HR questions like expected pay, why zynga, kind of work I look for, etc. I requested her about my interest in Systems Engineering Group. But she told that they don’t recruit freshers in SEG and told they will get back to me in a week.

After a week I got a call from the Zynga HR, whom I had correspondence from the beginning. He told that they need me to be interviewed once more. I agreed and I received the flight tickets again by mail. On Febraury 23rd again I flew to Bangalore. At Zynga, the interviewer came little late due to some meeting. He introduced himself that he is an architect at SEG. I got the clue that they are considering me for SEG. He asked about my interests. Then we had a long interview comprehensively on Operating System internals, application debugging, etc. Finally he asked me about preferred programming language and whether am I comfortable with C. Then we had lunch together at the Cafeteria. After lunch, he wanted me to write a program in python. Once I completed, he told me to write the same in C. Once the interview is over, I had another interview with an engineering manager. He introduced himself by saying that previously he worked as engineering manager at Google and currently work in SEG. Asked about my book and interests. He spoke about the work they do in SRE, etc. Next he wanted me to solve a puzzle on white board. I came up with a correct solution. Then he was open for answering my questions. The HR came and asked to leave as soon as possible not to miss the flight. I returned second time in Jet Airways Boeing. Due to Airshow at Bangalore, the flight was little delayed. It was raining also. I could see the clouds through the windows of flight. Awesome. Thanks to Adarsh for picking me from airport to hostel.

In Zynga, you will find a lot of self driven engineers and is a great place to learn and grow.

On 9th of March, I received a call from HR saying ‘Welcome to the Zynga family’. You are hired as Associate Software Engineer in Systems Engineering Group

Posted on April 1, 2011 - by Sarath

The story of my job interviews with Taggle.com and Yahoo!

It has been a while since I thought of writing my previous job interview experiences with different companies.

Taggle.com came to our campus in month of July 2010. It was CTO, Tej Arora who came to the campus for the recruitment. First of all there was a Presentation about Taggle Internet ventures and how it works.

Taggle.com is a group buying website where you get goods for reduced prices, with greater than 50 % off when there are a group of people to buy it. We had a objective multiple choice test of around 40 questions. It consisted of few aptitude questions, data structure questions, etc. It was a good question paper. By evening 5 pm, the result of the technical test came out. There were around eleven guys shortlisted for the next programming test. The eleven selected candidates were send for the programming round. We were allowed to write code on our own laptop and use any programming language we liked. He gave us two set of questions. Set 1 consisted of 1 difficult question and other set consisted of 2 easy questions. We were able to choose one set for coding. I chose the question to implement text auto completion functionality (set 1) and wrote the code in Python. He verified my program and told me to wait and come back once the programming round is completed by others. My friend Fayaz also had written autocomplete functionality. There were other two girls Nishita Suresh and Legena P.K who had worked on the other set of problems. Four of us had personal interviews. He didn’t ask me any technical interview questions but we had a very friendly conversation about the work and benefits at Taggle Internet ventures.

Once interviews were completed, the results were announced. Fayaz and Me got placed in Taggle.com.

Yahoo! came to our campus on October 30th, 2010. It was a day before seventh semester university exams started. Yahoo was considered as the superstar company that comes to MEC campus with highest pay and perks. The day when placement cell announced ‘Yahoo’ is visiting campus, everyone looked with wow. Placement cell members gave us the info that Yahoo! is going to recruit for Service Engineering team where they look for guys who live and feed in UNIX environment. In the following days placement cell posted specifications and info on what they are looking for and their requirements. There were a lot of XMECians working in Yahoo and they send us some materials they studied during their time. Everyone started seriously preparing for Yahoo with lot of effort. I also wanted to get into Yahoo. It was the time I was working on my book and I had hectic schedules. Some of my seniors who got into Yahoo were famous for Shell Scripting and sed. So I had thought of seriously looking into SED. I spend few days on SED and AWK. It was really nice writing sed scripts, which looks very awkward but performs incredible text processing operations in single line of code. To brush up my shell scripting skills, I went through the first draft of my incomplete book. But, that helped me a lot to fix bugs in my book. I also brushed up few conceptual things like How E-mail works, Networking basics, etc. The day of Yahoo interview came. The cut-off percentage was 70%. There was a presentation on Yahoo! and what they are looking for? Benefits and perks at yahoo. Then we attended the screening test. The test consisted of few aptitude questions, lot of Perl questions, networking questions, questions from OS scheduling, SQL and few other things. But it was not that difficult. After the test, in about an hour the results were out. 15 guys were in. The next was programming round.

They gave two questions, To write an intruder detection system script by parsing the auth.log log file and program for generating random sequence of n numbers from single random seed. I wrote the script for intrusion detection and basic implementation of random sequence generator (I had uncertainty about the question and what I had done was slightly different from what they had meant). After the programming round, they shortlisted four candidates. Joju John Joseph, Subeen N, Neha Mahadevan and me. They announced that there will be three rounds of interviews (two technical and 1 HR round).

My turn for the interview came. They scanned through my Resume and were impressed with my work and Book. Interviewers asked about my interests. I told them that I live in GNU/Linux. One of the interviewer asked me to narrate the story of a computer from the time we press power button until it boots up. I had a long narration of the story of computer boot ups including in-depth explanation of Ramdisk and all (Actually Linux boot was one of my favorite things which I had worked on). Then he asked few questions like What happens when a user browse a Web page, DNS query, DNS records, and few other questions. The interview went through topics like GDB, Core file, Debugging, Killing processes, Init, Signals, Orphaned processes, SSH, SSH Auto-login, and many other questions. I don’t recall most of them. At the end of the interview, they told that they were pretty impressed and satisfied. The next round of interview was HR interview. It was very friendly in nature asking me usual HR questions. He was busy noting down my details on a form during the interview. After the HR interview I went for the second technical interview. They told that there is nothing to ask and we were having friendly conversation about college and environment. The interviewer told me about his college, Yahoo recruitment experience and few things about work environment. When my interviews were over, I had to wait outside with Placement cell volunteers until the three rounds of interview gets finished for other three guys. It took lot of hours. Finally they announced the result. Joju John Joseph and I got the placement offers for Service Engineering team. Neha and Subeen got internship offers.

I will write about my Zynga interview experience soon. Stay tuned!

Posted on March 5, 2011 - by Sarath

Implementing a spell checker

Following my previous post on autocomplete, here comes a spell checker program. First of all I would like to warn you that this is the worst and inefficient spell checker you have ever seen. The most slowest and CPU expensive . I wrote this program long ago for fun. I thought of sharing the code I wrote.

The purpose of this post is to show how to write a spell checker in few lines by using the Levenshtein distance algorithm. This is not a context sensitive spell checker. The following spell checker program checks each word, and if it has spell errors it will list out some word suggestions.

Levenshtein algorithm is used to calculate distance between two words Levenshtein distance. It is defined as minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character. See wikipedia for more details on the algorithm.

This spell checker program uses a dictionary file. Every Unix like OS comes with a default dictionary file (in the directory /usr/share/dict/). Make use of that. To spell check a word, following program calculate Levenshtein distance by comparing all words in the dictionary. If the Levenshtein distance equal to one, those words will be listed as word suggestions. If the distance is zero, that means the word is a valid dictionary word. Checking across all the words in the dictionary is very expensive. Hence in order to reduce the number of comparisons needed, we use a subset of words in the dictionary having word length equal to, plus one and minus one with respect to the word we are checking for spell error. For implementing that, we have built a hash called wordsmap (python dictionary). The key used for the hash is the word length and the value assigned is a list of words of words having the word length as the key.

Let us do a test run with the program:

Write your comments here.