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 68th bit, we know that 68th 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 4th bit in the array[2]. This can be performed without division and modulus operators by using bit shift operators.
i=68
array[i>>5] |= 1 << (i & 0x1F)
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.
int count=0
while (n){
n=n&(n-1)
count++
}
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:
for (n in numbers)
{
hash[n] = 0
}
for (n in numbers)
{
hash[n] = hash[n] + 1
}
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.
void reverse
(struct linked_list
*list
)
{
if (list
->next
!=NULL
)
reverse
(list
->next
);
printf("%s\n", list
->element
);
} - 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/
Over a couple of weeks I was reading and practicing the book "
sing database from 
I started reading about 
We are living in the era of Information Revolution. Everyday wast amount of information is being created and disseminated over World Wide Web(WWW). Even though each piece of information published in the web is useful in some way; we may require to identify and extract relevant/useful information.Such kind of information extraction includes identifying Person Names, Organization Names etc.. ,finding category of a text, identifying sentiment of a tweet etc ... Processing large amount text data from web is a challenging task, because there is an information overflow. As more information appears there is a demand for smart and intelligent processing and text data. The very field of text analytics has been attracted attention of developers around the glob. Many practical as well as theoretical books has been published on the topic. 
Chandan had interviewed 
On 20th Oct. 2004
