CareerCup

You are given a directed cyclic graph represented by an adjacency matrix. The graph has at least one terminal node (i.e. the node with no outgoing edges).

Each edge of the graph is assigned a positive integer representing a probability of taking this edge. E.g. if you have 3 outgoing edges with numbers 3, 2, and 4, this means that the prob. of taking these edges are: 3/9, 2/9 and 4/9, respectively.

You need to find the probability of reaching each terminal node from the starting node 0.

Example:
adjacency matrix 5x5:

m = {{0 1 0 0 1},
        {0 0 3 2 0},
        {4 0 0 1 0},
        {0 0 0 0 0},
        {0 0 0 0 0}}

so we have two terminal nodes here: 3 and 4
we can take the following paths:
0 -> 1 -> 3 = probability: 1/2*2/5 = 1/5
0 -> 1 -> 2 -> 3 = probability: 1/2*3/5*1/5 = 3/50
0 -> 1 -> 2 -> 0 -> 1 -> 3 ... and so on

or to the node 4:
0 -> 4: probability: 1/2
0 -> 1 -> 2 -> 0 -> 4: probability 1/2*3/5*4/5*1/2 = 3/25

and so on, summing up probabilities of all possible paths we get:
total probability to reach node 3: 13/38
total probability to reach node 4: 25/38

Given a stream of integers where probability of a smaller number being first in stream is more than probability of larger number in stream.

Implement a method that returns true if you have already seen that element in stream otherwise return false.

eg. stream could look like 1,2,3,5,6,11,7,3......
more examples - 3,4,1,2,5,9,22,12

---
I explained using a hashset but that solution was not viable because of the space requirement.
I don't think I handled this question well. So would love people's opinion on it.

Given a array of integers find the index which partitions the array to two with high numbers and low numbers. For example [5, -1, 3, 8,6] the index 3 will partition the array to [5,-1,3] and [8,6] all the numbers in the second partition are greater than first. The solution has to work in O(n).

Design database schema with entity and relations to store the family tree of a person.

Given array of ball size we need to return the sum of shadow balls

For example

7 3 2 8 1

shadow ball of 7 ---> 3, 2, 1
shadow ball of 3 ---> 2, 1
shadow ball of 2 ---> 1
shadow ball of 8 ---> 1

Output ---> 3+2+1+1 --> 7

Complexity should be better than 0(n^2)

Design a low level design and db schema for railway reservation system for supporting following 2 features -

1) User would give source city, destination city and date as input and would get the list of trains matching the criteria.

2) On selection of a train from the list user should be able to see the schedule of the train including the arrival time, departure time and station name.

Given two very large files – first contains Id and name, another one contains Id and address – you need to create 3rd file which will contain id, name, and address. -First, ask the clarifying questions and then tell the approach.

Two tables employee (contains name and Id) and employee details having work experience history (contains Id, fromYear, toYear) – find out all the employees who worked w/o career break.
Java implementation for the same.
From the same table list the name, fromYear, toYear for all employee.
Dependency Injection.
Design patterns which can be used.

I was asked to sort extra large file 10GB which contains single word in each line, within 4GB RAM. I told External sort and optimised it with min-heap but interviewer was asking to optimise disk I/O. As last he told that use CS fundamentals. Don't know what was he expecting. Please help.

How can you read last 10 lines of a big file and a follow up question was how would you extend this process optimally to read last 10 lines of 1000s of files?

Use synchronized, wait() and notify() to write a program such that below mentioned conditions are fulfilled while reading and writing data to a shared resource.

When a write is happening, no read or other write should be allowed(read and write threads should wait)

When a read is happening, no write should be allowed (write threads should wait) but. other read threads should be able to read.

Donot use any API classes e.g. ReadWriteLock, AtomicInteger etc..

I was asked to integrate linkedIn and dropbox. So linkedIn is not into file storage system, hence they want to use the services of dropbox. The goal is to create, update, delete the documents of a profile in linkedIn. But these documents will not be stored in linkedIn. They will be stored in dropbox.
Moreover, to get this integration, linkedIn does not want to scale up they system. This means, if they have 400 servers, they do not want to add any more servers to achieve the integration.
How can I design this?

Has anyone interviewed with Microsoft, Fargo North Dakota? Care to share the experience and some interview questions?

Hi,

could you please advise how to land a job in Microsoft. I have applied for many openings through LinkedIn but not getting contacted from Microsoft recruiters or have received any updates yet.

Thanks
Deepa

Given a list of sorted lists each of size maximum size M, implement an iterator (maintain the order of items as in the original list of lists).

I had a solution requiring extra space using minHeap; However, the interviewer was looking for a constant space solution.

Let's assume we have a queue named 'Demo' which receives messages from various users.

Create a Listener which will listen to the queue 'Demo' continuously and as soon as the message is send to the queue the Listener will print out the message.

The queue is running on port : 8161
Username : admin
Password : admin

Explain the difference between ORM and JDBC.
Provide some examples and when to use one over the other.

There are n number of stones. Each stone has a weight associated with it. 1st stone’s weight is 1, 2nd stone’s weight is 2.. and so on. You are given an integer x. You need to pick the maximum number of stones such that the total weight of stones picked is less than x.
You’re also given an array of stones which you can not pick.?

You are given a set of functions:

int open_port();
opens a serial port and returns 0 if everything ok (or -1 if error)

int read_port(char *buf, int buf_size)
which reads data from a serial port and stores it to 'buf' of size 'buf_size' or blocks until the data is available and returns the number of bytes read (or -1 if error occurred)

void close_port();
closes a serial port connection

Design a class:

class SerialConnection {
public:
     using ByteHook = std::function<void(char)>;

     SerialConnection(ByteHook callback);
....    
};

which should read data from the serial port asynchronously and send it to the callback function ByteHook byte by byte (e.g., for decoding).

Note that if you don't call 'read_port' often enough, the underlying system buffer might get full and some bytes will get lost..

Which data structures / sync primitives you are going to use ?

Question : Given a set of N numbers [1,N], partition them into 2 disjoint subsets based on a set of K queries.
Each query is of the type (n1, n2) where n1 and n2 are distinct numbers from the set and n1 and n2
belong to opposite subsets.

Example:

Input:

Input:
N = 4
K = [(1, 2), (1, 3), (2, 4)]

Output:
Set 1 : (1,4)
Set 2 : (2,3)

I don't remember perfectly the question, but it was like this


Given a list of 100 songs on your cell phone, find a way for each user to hear the songs without repeating songs, you need to use an algorithm that uses shuffle for songs.

Did any one took Microsoft Online Technical Screen ?? What questions I can expect in this test ??

Given a wall, which is made up of two types of bricks (Porus / opaque ). Porus bricks allow water pass through them. Opaque won't. Find whether water reaches to ground, if there is any rainfall.
Water can flow from top to bottom, diagonally, horizontally as well. Only flowing from bottom to top is not possible.

Give an positive integer n, find out the smallest integer m, such that all digits in m multiply equals to n. For example, n = 36, return 49. n = 72, return 89. You can assume there is no overflow.

Find Duplicate number from a huge amount of data which cannot fit in the memory.

Find kth-largest number from a huge amount of data which cannot fit in the memory.

We have an array if 0's and 1's like

00010000010001001

Assume that all 1's are a person and if a new person comes and if we want to add to the array in such a way that the gap between individuals are maximum as possible.

if we add a new person, then the new array should be

000100100010001001

Evaluate infix expression: 2 + 3 * 5

Interleave two singly linked lists into one.

LL1: 1 -> 2 -> 3 -> 4
LL2: 10 -> 20 -> 30 -> 40 ->50

Output LL1: 1-> 10 -> 2 -> 20 -> 3 -> 30 -> 4.
Note: Stop when we hit null for LL1.

You need to design a new YouTube feature where userA is uploading a video and userB (friend of userA) gets notified for the video and wants to watch the same video in real time (i.e. even the video is not completely uploaded but we want to enable the other user to watch it).
How would you tackle the situation when userB wants to view the content starting from a position which is not yet uploaded.

Draw block diagram for this problem identifying the different components.