Sunday, 10 March 2013

Pocket Gems Coding Test

Following coding questions were asked by Pocket Gems, a social gaming company based in San Francisco. Total duration was 1 hour.


1) Given an array of positive numbers. We can make any element of the array negative. We have to find the minimum positive sum after modifying numbers of array, by making some numbers negative.


2) Given an array of pairs of the form <a, b>. We have to find a sub-array such that the 1st element in the pairs are in increasing order and the sum of 2nd element of the pairs in the sub-array is maximum possible.


Source: Arun Chaudhary, DCE
Posted by at
Labels: ,

9 comments:

  1. satya8 April 2013 at 18:08

    Hi Thanks a lot posting.
    Is it a pen paper test or in interviewstreet based?

    ReplyDelete
  2. Chinmay22 April 2013 at 05:45

    It was a live coding test. You had to write executable code.

    ReplyDelete
  3. Aakash12 September 2013 at 04:45

    What are the limits on the size of the array, and the values of its elements in Q1?

    ReplyDelete
  4. Chinmay13 September 2013 at 00:10

    I think you can assume the numbers to be in a finite range. Are you using DP?

    ReplyDelete
  5. Unknown27 September 2013 at 14:21

    @chinmay, i think the first problem is a simple case of DP where you partition the array in two parts such that the difference between their sum is the least...then you negate all the elements of the array which fall fall in the category of lesser total sum.

    ReplyDelete
  6. Unknown31 October 2013 at 16:28

    The 2nd problem could also be solved using dynamic programming.
    Starting from index 0 of the pair array, we would add the 2nd element of the pair to max_sum variable as long as the first element of the pair is increasing as compared to the previous value.
    if it doesn't increase at a given index we check if the the current second element of the pair is greater than the max_sum so far and thus update accordingly.

    ReplyDelete
  7. Unknown3 December 2013 at 16:55

    can other department students take the test?

    ReplyDelete
  8. gene apolinares31 March 2014 at 02:57

    Good post!

    Do you want to work home-based? With internet access, Unemployed pinoys (UEP) can provide you a job where you can work at home and earn money while being able to spend time with your family or loved ones at home.

    Join us now at http://www.unemployedpinoys.com

    ReplyDelete
  9. Hina Mohiuddin25 October 2021 at 12:45

    Your work is truly appreciated round the clock and the globe. It is incredibly a comprehensive and helpful blog. Topaz

    ReplyDelete

Subscribe to: Post Comments (Atom)