Friday, December 14, 2012

Google Fresher Interview


There is a linked list of numbers of length N. N is very large and you don’t know N. 
You have to write a function that will return k random numbers from the list. 
Numbers should be completely random.


One approach is to use random and modulo with N. But if we don't know N, it becomes interesting. The approach that we discuss is called "reservoir sampling". In this approach, we read the first K numbers and store it in the list. For our example lets say K is 10. So we will have the first 10 elements in the list. Next read the 11th element, compute a random function which returns a random number between 0 to 11. If the random number (r) is less than 10, then set the r'th number to 11th number, else continue.


Question: 2

Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN. 
Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn


We can use a divide-and-conquer approach. Lets say the list contains {1, 2, 3, 4, 5, 6, 7, 8, a, b, c, d, e, f, g, h}. Using binary-search kind of approach, convert it into {1, 2, 3, 4, a, b, c, d, 5, 6, 7, 8, e, f, g, h}. Break the list into 2 parts and apply the same algorithm on the 2 parts - {1, 2, 3, 4, a, b, c, d} and {5, 6, 7, 8, e, f, g, h}. 


Question: 3

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).


We can do it in 2 pass, O(n). If the list is a: {4, 2, 5, 1}, we create a product list b: {0, 0, 0, 0}. Set b[0] to 1. Set pf (product forward) to 1 and pb(product backward) to 1. Start pass forward. Set pf  = pf * a[i-1]. So at i=1, pf will be 4. Set value of pf to b[i]. So the list will become {1, 4, 0, 0}. Next at i2, pf will become 4*2=8, so the list will be {1, 4, 8, 0} and next it will be {1, 4, 8, 40}.
Start pass backward from last but one item that is i=2. Set pb = pb*a[i+1]. Set value of b[i]*pb to b[i]. So pb=1. The list will be finally {10, 20, 8, 40}


Question: 4

You are given an array with integers (both positive and negative) in any random order. 
Find the sub-array with the largest sum


1 comment:

  1. Please implement a graph database (a kind of NoSQL). This graph database
    should consist of nodes (with have properties) for entities and edges (which
    have single or multiple properties and can be directional or bidirectional) for
    relationships, and support node indexing and query. The query language has
    following keywords: START, MATCH, WHERE, RETURN, ORDER BY,

    Example Input:
    Node martin = graphDB.createNode();
    martin.setProperty(“name”, “Martin”);
    Node pramod = graphDB.createNode();
    pramod.setProperty(“name”, “Pramod”);
    Node barbara = graphDB.createNode();
    pramod.setProperty(“name”, “Barbara”);
    martin.createRelationshipTo(pramod, FRIEND, since = 1998);
    pramod.createRelationshipTo(martin, FRIEND, since = 1998);
    martin.createRelationshipTo(barbara, FRIEND);
    barbara.createRelationshipTo(martin, FRIEND);
    START node = Node:nodeIndex(name = “Barbara”)
    MATCH path = node-[relation*1..3]->related_node
    WHERE type(relation) = ‘FRIEND’
    RETURN, length(path), relation.since;