Posts Tagged ‘code’

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 March 28, 2011 - by Sarath

How to apply for Google Summer of Code – A byte of note

Google Summer of Code organizations list has been published. Soon, within april 8th you will be able to submit your applications. Google summer of code is a premier Open Source programs managed by Google. The certificate of Google Summer of code adds higher market value to your resume. You will be receiving certificate stating 3 months Student Developer for Google and also you will be receiving a good paycheck of $5000.

I participated thrice (2008,2009,2010) with different organizations. I would like to give you few advices regarding how to apply and participate.

There are 171 open source organizations got accepted by Google for GSOC 2011. You can see the list from:
http://socghop.appspot.com/program/accepted_orgs/google/gsoc2011

Each of the organizations will accept few projects (No of projects as per decided by google). No of projects for each organization varies according to the market value of organizations. You can submit one or more (I prefer 3 applications) to same or different organizations.

Each of the organizations will have there project ideas page. You can select an idea that interests you or propose a new idea to them. (But already listed idea has more changes to get accepted – I feel so).

Each student who get accepted will be assigned with a mentor from the corresponding organization. Mentor will be a very experienced guy who is already contributing to the projects. In my case during my first summer of code, surprisingly my mentor John Palmeri is the author DBus-IPC, Gnome Executive and Author of GNOME network manager. You can get such kind of exposure during the project.

How to apply for a project ?

Go through the accepted organization list, Click on the organization, Go to the ideas page. You can find many ideas listed with details (Prerequisite, Difficulty level, Expected mentor, Contact person, Related information URL, URL of mailing list, etc). If you find some idea interesting, invest some time researching about the background, and related technologies related to the idea. Once you gain basic information about what you exactly need to do with project and what technologies you should use, contact the mentor or person listed.

To collect necessary details about the project and get the background of technology, look into mailing list associated with the project/organization. You can also subscribe to the mailing list.

Contacting organization or associated person:

e-mail :
Write properly what idea you want to work on, your background and how you wanted to work on the project. Include as much as details on how you will implement the project and ask necessary questions.
IRC Chat:
If you are not familiar with IRC, IRC is a type of group chat system widely used in Open Source development environment. Each organization will have a channel (Eg. #pardus-devel – pardus linux developers channel), where you can login and chat with a registered nickname. For open source project, the chat server will be irc.freenode.net.
To use IRC, you can install XChat client using: sudo apt-get install xchat
or use the webchat interface http://webchat.freenode.net/
For basics of IRC chat, read http://www.irchelp.org/irchelp/irctutorial.html
You can use the assigned contact person’s nickname to contact him over IRC.
IRC is a public chat where many are interacting each other. Please do not spam or ask stupid questions like (I am newbie. I want to participate in GSOC. Plzzz help.)
Write proper words rather than using chat language like ( u thr. plz. i gt ths idea frm). Do not flood the channel. Be very decent and formal over the chat channel.
Before you ask questions, I strictly recommend read this article to following the hacking culture:

http://www.catb.org/~esr/faqs/smart-questions.html

How do each organization select Project proposals ?

From my experience, there will be a group of people from the GSOC organization who review the project proposals. They will have an internal voting system. They vote induvidually and rank the list of proposals. According to the number of project slots assigned for the organization, they select the higher ranked proposals. The most higher preference is always to get successful completion of projects. So they look heavily at the strength of your project proposal. The project proposals that consist of as much strong details to support the fact that you are going to complete the project get accepted.

How to write a project proposal ?

Usually you will find a specified format for the project proposal for each of the organization. Once the application period opens, you will come to know about the format.
To have strong proposal I recommend to include the following things:

1. Your background. Showcase your abilities (Even if you haven’t done much. Market what you have)
2. Do enough research on project ideas and arrive at list of technologies you want to use (Include libraries required, dependencies, challenges, diificulties). This should show much of research and effort you have invested in the project.
3. List out the features of the idea you are going to implement and how it benefits. (You can discuss with the mentor and arrive with features and benefits)
4. If you had contacted the mentor before and had positive conversations about the project and discussions. He might also talk about you to other individuals in the organization. You can talk the public organization IRC channel, it gives lot of attention to you from the members who are going to vote for your proposal. If you have discussed technical details and give confidence in your ability, that will be positive to you while they vote.
5. Prototype (Optional)
   Prototypes are bonus points for a proposal. You can create GUI prototype designs, code prototype designs, etc if necessary. (Last time, I coded a command Pardus Linux Live installer in 500 LOC, served as prototype)
6. Timeline
   Timeline is a must for a project proposal. You should indicate how you are going to spend three months time to completion and development of project.
   A good format will be :
   Week 1 (May X – May Y) – Development of M module. Customization of C using T tool and commit changes…etc
7. Version control
   You should be familiar with some version control systems like SVN, GIT, BAAZAR, etc
   Here is a basic How to on SVN:?http://betterexplained.com/articles/a-visual-guide-to-version-control/
   You should let then know that you are comfortable with the organization specific version control.
   Before writing the proposal you should check out code from the corresponding branches related to your project idea.

For example, if you are contributing to Webcam app – Cheese, you should check out code of cheese using Git version control and build the application from source code and try out things.

All the best with your project proposals.

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.