CareerCup

Round 5
Question 5 : Now lets say you are given k number of input streams, each stream have two method implemented, one is ReadNextNumber() and another is WriteToStream(), lets say each of the streams are sorted. How will you return a single sorted stream which contains all the streams data.

Round 5
Question 4 : Now lets say you have 1 PB(1000 TB) of numbers, what kind of system you would prefer, not that you can't store this data in one box. How will you sort these many numbers, what is the time complexity in seconds ?. does increasing core per machine help here ?

Round 5
Question 3 : Now lets say you have 1 TB(1000 GB) of numbers, how do you sort it, tell me the complexity in seconds ?, any optimization you would like to do here, ?, lets say your machine is having two core, now ?

Round 5
Question 2 : You are given a 1 GB of numbers, you have to sort them. Tell me the time required in seconds ?

Round 5 (taken by PRINCIPAL GROUP ENG MANAGER)(hiring Manager)
Question 1 : Tell me about your achievements ?

Round 4
Question 5 : Question 5 : Do you know A/B testing ?, when we tell you some result of an experiment, how do you know the results are accurate ?, actually this question was about the statistics, he asked me many questions to check my statistics knowledge ?

Round 4
Question 4 : You are given following input
Input{userId, LoginTime}
You have ping output in following way
Output(UserId, LoginTime, SessionId).
Note that the session Id is an integer, and when a user login after 30 minutes of its previous login, you will give him/her next sessonid.
new user, will always get next sessionId.

Example
Input
1 9:00 AM
2 9:10 AM
1 9:25 AM
30 12:34PM
23 3:09 PM

Output
UserId LoginTime SessionId
1 9:00 AM 1
2 9:10 AM 2
1 9:25 AM 1
30 12:34PM 3
23 3:09 PM 4

You have to do it in either SQL/Scope. You also have to minimise the complexity.

Round 4
Question 3 : this question was similar to Round 2 Question No 3, which is basically convert row type of data to column type of data

Round 4
Question 2 : Why are you switching your job ?, why our team ?

Round 4 (taken by PRINCIPAL DATA SCIENTIST)
Question 1 : Tell me about your previous work at Microsoft ?. any work you are proud of ?

Round 3
Question 2 : You are given a array of integers, array may have duplicates, you have to find out the rank k number, and then print out the k highest numbers ?
Required complexity is O(N) + O(1) space, duplicates may be an issue, on which she wanted me to put more focus.

Round 3 (taken by SOFTWARE ENGINEER 2)
Question 1 : How are you ?, Tell me about your career achievements, Tell me about one of the project you are proud of ?.

Round 2
Question 3 : You have to implement an external iterator which iterate the binary tree InOrder. You have to figure out what kind of iterator one should use, and implement each of those function. required complexity is O(N) time + O(log(N)) space

Round 2
Question 3 : You are given following set of tables
Object{obj_id, obj_name,....<Other object related details>}
Attribute{att_id, att_name,....<Other attribute related details>}
ObjectAttributeMapping{objAtt_id, obj_id, att_id, att_value}

You have to provide the output in following format
Output table with column name {obj_id, obj_name, att_name1, att_name2, att_name3,...}
each object should only be represented in one row, and att_name1 column will have att_id1 values, from ObjectAttributeMapping table, similarly att_name2 column will have value of att_id2 from ObjectAttributeMapping etc...

Note that you have to do this in either SQL/Scope.

Example
Object
obj_id obj_name
1 cube
2 square
3 matrix

Attribute
Att_id Att_name
1 color
2 height
3 length
4 width

ObjectAttributeMapping
objAtt_id obj_id att_id att_value
1 1 1 'red'
2 1 2 10
3 1 3 12
4 1 4 5
5 2 1 'green'
6 2 2 6
7 3 3 5
8 3 4 9

Output should be
obj_id obj_name color height length width
1 cube 'red' 10 12 5
2 square 'green' 6 null null
3 matrix null null 5 9

Round 2
Question 2 : You are given following two tables,
Customer{cust_id, cust_name, ...<Other customer related details>}
Order{order_id, order_name, cust_id, ...<Other order related details>}

You have to provide the output in following format.
cust_id, cust_name, [Total amount of orders]

Please note that you have to do this in SQL/Scope, and print only those customer who have at least one order.

Round 2(taken by PARTNER SCIENTIST MANAGER)
Question 1 : How are you ?, What is your interest ?, why you want to change your job and move to our team ?

Round 1(taken by DATA SCIENTIST 2)
Question 1 : You are given a street map of a city, Every day you travel from your home to work. some day you take bus or someday your our car. Bus fare is also not constant, it may change in future, may increase or decrease ?
you have to find shortest path from your home to your work ?.
Note that : you have to expose this as library, so no custom assumptions. need to find out how you incorporate variable bus fare ?, also it is up-to the user to choose between bus and his car ?, in case of bus, you have to minimise the total money, and in case of care, you have to minimise the distance.

Given a linked list of strings find the sequence where last character should be equal to first character. Here the head string should always be the same. All the solutions possible should be printed Ex given following Here -> is-> ew-> long -> shut -> error -> roll Output should be 1. [Here, ew] 2. [Here, error, roll, long] All the possibilites should be printed.

An input device can read input of 8 bytes over 2 seconds. It needs control over an input buffer during this operation. A disk writer can write data of 16 bytes over 4 seconds to the disk. It too needs control over the data buffer for the duration of its operation.
Design a system that can capture input from input device and write it onto the disk. The interviewer explicitly asked for detailed code for the implementation.

---EDIT---
The input device thread cannot be blocked, if made to wait, data gets overwritten and we have to capture all data available to the input device

P.S.: I don't think we can use synchronized block from java since their locks cannot be interrupted, I have read up on trylock() mechanism but not entirely sure how the exact code would look like.

Write code in the language of your choice to determine how many numbers between 1 and 100,000 contain an even number of odd digits

What I understand that number of digit in a number should be odd
is..
2 4 6 8 are even number which having only 1 digit and 1 is odd number
10 12 14 18 ……are even number but number of digit in these number are 2. 2 is not odd number hence we gonna discard all these number

102 104 106 …. Are even number and number of digit in these number is 3 that is odd number hence we will count these number

1000 1002 1004….are even number and number of digit in these number is 4 that is even number hence we will not count these number…

Please let me know if you think differently.

Tech Screening
Question 1 : You will be given a stream of integers, and a integer k for window size, you will only receive the streams integers one by one. whenever you receive an integer, you have to return the maximum number among last k integers inclusive of current entry.

Interviewer was expecting O(N) solution for N asks.

Edits: Interviewer was expecting O(N) Time + O(1) avg case space complexity solution for N asks.
and integers are not given in a array, every time only one integer will be passed as input to your method.

Round 3
Question 1, you are given a puzzle, You can check the image here

https://drive.google.com/file/d/0B6-TjTC-KfTqQThBamxPa0NwNGM/view?usp=sharing

You have to write a program to provide a solution for this.

Round 2
Question 1: Design a traffic signalling system for a city.
1.a : think as you were asked this question in a high level meeting with leadership teams, what would you do at that time ?
1.b : what are the check-list/to-do you will do before start of your project.
1.c : how will you go over each and every check-list/to-do
1.d : Once you have done all this, what are the design principle you will follow.
1.e : what kind of system you would choose(I gave distributed/centralized)
1.f : Tell me the pros and cons of these type which you have listed
1.g : how do you go over your goal.
1.h : how will you make the cons go away from one system which out changing it to another type(like possible modification).
1.i : How will to achieve your goal which was given to you by LT team.
1.f : Now lets write the code for a road intersection, make it generic enough both in terms of colors, and ordering, so what it can be used anywhere.
Note that : a road intersection may have many traffic lights one for each side of the roads

Round 1
Question 1.a
You are given a stock market feed of a single stock.
It contains the change over the previous value. you have to find out the max gain one can get out of it.
Example : -1, 2, 6, -5, -3 7, -3
Days 0 1 2 3 4 5 6
Answer is buy before day 1 and sell it after day two.

WAP for this.

Question 1.b : How do you make the changes in previous code to return the maximum loss. Please note that the changes should be minimum only.

Question 1.c: Lets undo the Question 1.b's additional changes, and now lets you are given a limit on how many days one can hold the money, lets say "k", which means, the investor will give you the money for k days only. you have to again make the additional change to figure out the optimal start date and end date.

Few Example
input : -1 -6 10 2 -5 20 5 -10 6
days 0 1 2 3 4 5 6 7 8
Max Gain : End of first day to end of 6th day, amount is 32.
Max Loss : End of 6th day to end of 7th day, amount is -10.
if K is 3 then the max gain is 25, which is end of 4th day to end of 6th day.

Edits : Interviewer was expecting O(N) solution here.

Tech Screening round
Q.1 : a non decreasing sorted array is rotated by some random amount, write a routine to figure out this random amount.you can consider the clockwise rotation.
Write the test cases for it.
Interviewer wanted to see prod ready code.

Given a set of 'n' intervals S = {(starti, endi) | 1<= i <= n}
Find a maximum subset of S such that no pair of intervals in S' overlaps ?

How to debug deadlock or heap corruption from DUMP using WinDbg tool?

Design classes and interface for BookShelf

Given a file, read last n lines from the file

string ReadNLines(sttring fileName, int n);

Assume we have a very large file containing millions of lines of data. Only 2 lines are identical, rest are unique.
Each line is long enough that they may not fit in memory.
Design an efficient algorithm to determine identical lines?
And, then generalize it for 'n' identical lines.