DS & Alogorithms

This is the subject which plays a crucial role in your placement process. If one is good at this he can crack the interview easily

REFERENCES


Following are the books to follow for this subject

 1. Introduction to Algorithms
                           By     Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein
2. Data Structures and Algorithms Made Easy 2nd Edition 
                           By    Narasimha Karumanchi

For interview questions you can go for
3. Crack the coding interview
                           By    Gayle Laakmann

you can download the PDF of the above references in the following links

 1. Introduction to Algorithms
                           By     Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein
2. Crack the coding interview
                           By    Gayle Laakmann

Websites that you can follow

1. www.careercup.com
2. www.geeksforgeeks.org
3. www.topcoder.com
4. www.codechef.com


Practice Questions


Arrays & Strings

  1.  Implement an algorithm to determine if a string has all unique chracters. What if you cannot use additional data structure?
  2. Implement a function void reverse (char* str) in C or C++ which reverses a null terminated string.
  3. Given two strings. Write a method to decide if one is a permutation of other.
  4.  Write a method to replace all spaces in a string with ‘%20’. You may assume that string has sufficient space at the end of the string to hold the additional characters, and that you are given the “true” length of the string.
  5.  Implement a method to perform basic string compression using the counts of repeated characters.                Example: aabcccccaaa  -> a2bc5a3
  6. Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate image by 90 degrees. Can you do this in place?
  7. Write an algorithm such that if an element in an MXN matrix is 0, its entire row and column are set to 0.
  8. Assume you have a method issubstring. which checks if one word is a substring of other. Given two strings s1 and s2, write code to check if S2 is a rotation of s1 using only one call to isSubstring.
  9. .       How do you reverse the words in a string?
    "My name is Aravind vijaya kumar"         to           "kumar vijaya Aravind is name My" 
     A O(n) and 'in space' solution is appreciable.
  10.   Given an array of 2n elements of which n elements are same and the remaining n elements are all different. Write a C program to find out the value which is present n times in the array. There is no restriction on the elements in the array. They are random (In particular they not sequential.)
  11. Write an efficient function in C that deletes characters from a string.    Use the prototype:  void RemoveChars(char str[], char remove[]);                                  where any character existing in remove must be deleted from str. For example, given a str of "Battle of the Vowels:Hawaii" and remove of"aeiou",  the function should transform str to "Bttl f th Vwls:Hw vs. Brzny".                                                        Justify any design decisions you make and discuss the efficiency of your solution
  12. Say we have a data structure as follows:

    enum {RED,BLUE,GREEN};
    struct Ball
    {
    /*...*/
    int color;
    };
    int ColorOfBall(Ball b)
    {
    return b.color;
    }
    Ball arr[SIZE];

    The array arr consists of balls of with one of the three colours (Red,Green,Blue). Now we need to sort the array in such a way that all the Red coloured balls come first, followed by blue and then green. The restriction is that call to function ColorOfBall is a very costly operation. You have to use it as less as possible. (In other words we would be looking for the solution with least number of calls to the function ColorOfBall.)

Linked List

  1.  Write code to remove duplicates from an unsorted linked list.
    FOLLOW UP
    How you would solve the problem if a temporary buffer not allowed?
  2. Implement an algorithm to find kth element from last element of a singly linked list
  3. Implement an algorithm to delete a node in the middle of a singly linked list. given only access to that node.
  4. write code to partition a linked list around value x so that all nodes value less than x come before all nodes greater than or equal to x.
  5. You have two number represented by a linked list, where each node contains a single digit. The digits are stored in reverse order such that 1’s digit is at the head of the list. Write a function to add the two numbers and   returns the sum as a linked list.
     What if the number is in normal order i.e 1's digit at the tail
  6. Given a circular linked list, Implement an algorithm which returns the node at the beginning of the loop.
  7. Implement a function to check if a kinked list is a palindrome.
  8. Given a singly-linked, find out the mid point of a single linked list in a single parse of the list. Assume the program would be loaded in read-only memory so no manipulation of the list is allowed.
  9. You are given a singly link-list such that each node of this list is also a head of another link list of the same type. So, how does one flatten the linked-list
    struct node {
    void *data; /* could be anything */
    struct node *next;
    struct node *down;
    };
  10. Given two sorted linked lists, L1 and L2, write a C program to compute L1 /\ L2 (L1 intersection L2).


 Stacks & Queues

  1. Describe how you could use single array to implement three stacks.
  2. How you design a stack which, in addition to push and pop, also has function min which returns the minimum element? Push, pop and min all operate in O(1) time.
  3. Imagine stack of plates, If the stack gets too high, it might topple. Therefore , In real life we would like to implement new stack when the previous stack exceeds some threshold. Implement a data structure setofstacks that mimics this. Setofstacks should be composed of several stacks and should creates a new stack once the previous one exceeds capacity. Setofstacks.push() and setofstacks.pop() should behave identically to a single stack (that is pop() should return the same value as it would if the same values as it would if there were just a single stack.
  4. Classic problem of towers of Hanoi.
  5. Implement a MyQueue class which implements a queue using two stacks.
  6. Write a program to sort a stack in ascending order(with biggest item on top). You may use additional stacks to hold items. But you may not copy the elements into any other data structure( such as array). The stack supports the following operations push, pop, peek, isEmpty.

Bit manipulation & General

  1. Write an efficient C program to count the number of bits set in an unsigned integer.
    i/p o/p
    ==== ===
    0(00) 0
    1(01) 1
    2(10) 1
    3(11) 2
    ..... ...
  2. .       What's the "condition" so that the following code snippet prints both HelloWorld !
    if "condition"
    printf ("Hello");
    else
    printf("World");
  3. .       Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
    1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
    shows the first 11 ugly numbers. By convention, 1 is included. Write a program to find and print the 1500'th ugly number.
  4. int main()
    {
    int i, n = 20;
    for (i = 0; i < n; i--)
    printf("*");
    return 0;
    }
    Change/add only one character and print '*' exactly 20 times.
  5. .       You are given have a datatype, say X in C. The requirement is to get the size of the datatype, without declaring a variable or a pointer variable of that type, And, of course without using sizeof operator!
  6.        You are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5).
    * How can you find the repeating number?
    * What if i give you the constraint that you can't use a dynamic amount of memory (i.e. the amount of memory you use can't be related to n)?
    * What if there are two repeating numbers,instead of one (and the same memory constraint?)
  7.        Given an array of numbers, except for one number all the others, occur twice. Give an algorithm to find that number which occurs only once in the array.
  8.        There is a series of numbers in ascending order. All these numbers have the same number of binary 1s in them. Given the number of 1 bits set in the numbers, write an algorithm/C program to find the nth number in the series.
  9.        Given a numbers x and n, where n is a power of 2, write C code, which gives the multiple of n which is greater than or equal to x.
    ex :
    I/P: 13 8
    O/P: 16
    I/P: 17 16
    O/P: 32
    The challenge: Do not use division or modulo operator.
  10.  Given two arrays A and B. Array 'A' contains all the elements of 'B' but one more element extra..... Find out the extra element......
    Restrictions: Don’t use any relational ops ( > or > or == etc....), array elements are not in order ...,
  11. Write an algorithm to check whether a given unsigned number is a multiple of 3, without using division and modulo operators.
  12. Propose a data structure for the following:
    - The data structure would hold elements from 0 to N-1. There is no order on the elements (no ascending/descending order requirement)
    The complexity of the operations should be as follows:
    * Initialization - O(1)
    * Insertion of an element - O(1)
    * Deletion of an element - O(1)
    * Finding a element - O(1)
    * Deleting all elements - O(1)
  13. Write a "C" function,
    int AddOvf(int* result, int a, int b)
    If there is no overflow, the function places the resultant sum a+b in "result" and returns 0. Otherwise it returns -1.
    The solution of casting to long and adding to find detecting the overflow is not allowed 
  14. Write a C function that rotates to the right by 'n' bit positions the bits of an unsigned int x
    No assumptions to be made on the the values 'n' can take and the size of 'x'.
  15. How to find a number is power of two or not?
    Also design a data structure in the data path which will return no of bits set in an element
    of size either 32 bit or 64 bits in constant no of time
  16. Write your own macro for finding the offset of a structure member.
  17. Write a function which will take input as no of rows and columns and return a pointer to the
    2D array after allocating required memory
  18. write a function which will take an unsigned integer as input and return an unsigned integer as
    output in which the adjacent bits are swapped

No comments:

Post a Comment

Subscribe to: Posts (Atom)