Basic programming questions

  1. Design a data structure such that given a stream of numbers, you can find the maximum of the numbers at any point and also all the numbers.
  2. Given an array of 1s and 0s arrange the 1s together and 0s together in a single scan of the array. Optimize the boundary conditions.
  3. Find the common ancestor of two given nodes in a binary tree, how do you exploit the properties of a given BST for the same problem.
  4. You’re given a function getsort(data) that sorts the data given. The function sorts in place and does not use any extra memory. How do you validate the function with respect to 1) it sorts 2) it does not use extra memory
  5. Explain the Traveling Salesman problem? What is an NP-complete problem? What is the Hamiltonian cycle problem?
  6. Find out the least common ancestor in a binary tree.
This entry was posted in General. Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

3 Comments on Basic programming questions

  1. Ummar Farooq
    Posted 11/16/2008 at 3:04 pm | Permalink

    2nd Question Ans: add all the numbers in one pass. that will give you no of 1’s and place taht many 1’s in the array and then rest 0’s.
    O(n)
    and no need to use check condition operaton.
    Regards

  2. Alan
    Posted 1/5/2009 at 3:50 pm | Permalink

    That’s two passes through the array. One to read (and add) and one to write. My way would be to read a value, if it’s a ONE, move it to the front of the array (or just leave it in place) and if it’s a ZERO, swap it out to the end of the array. Inc/dec/leave alone counters as required, then continue. Stop when the 1s counter == 0s counter.

  3. sherry
    Posted 2/4/2009 at 5:18 am | Permalink

    1.i think link list must be used
    2.use a position var which keeps track of the position of 0 which gets swapped when nxt instance of 1 occurs and then mov pos to nxt instance of 0 and continue abv operation
    3.probably use a prefix and infix order of the tree and keep track of the ancestors of each node in a double dimension array

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*