CareerCup

This interview was held 3 years back. adding this question for others reference.

Design a picasa.i.e. A photo album application where user can store his pictures and share among the others using their email ids.

You need provide high level design for server and client.

I explained about
- storage on RDBMS database ( Interviewer was expecting some datwarehousing or NOSql over here but I could not explain as was not aware of it till that time)
- Different sizes of photo storage.
- Cache for recently accessed photos
- Cache for most accessed photos
- Regional servers
- Disaster management, clustering, HA

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.

You are given a large array of 10,000,000 bits. Each bit is initially 0. You perform several operations of the type "Flip all the bits between start_index and end_index, inclusive". Given a sequence of several such operations, perform all the operations on the array. Finally, split the array into sets of 4 bits - first four, next four, then next four and so on. Each set can represent a hexadecimal integer. There will be exactly 2,500,000 hexadecimal integers. Calculate the frequency of each of the hexadecimal integers from '0' to 'f' among the 2,500,000 integers, and print it. See Input / Output and explanation of Sample Input / Output for clarity.
Input

The first line of input contains an integer T (1 ≤ T ≤ 10), the number of test cases. Then follows the description of T test cases. You should assume that the array has exactly 10,000,000 bits and that the bits are all unset at the start of each test case. The first line of each test case contains an integer N (1 ≤ N ≤ 10,000), the number of operations performed. The next N lines contain two integers separated by a space, the start_index and end_index for the respective operation. Note that the flip operation is performed from start_index to end_index, inclusive. Also, the array is 1-indexed - meaning, the smallest index is 1 and the largest index is 10,000,000.
Output

For each test case, output 16 integers on a single line, separated by single space characters. The first integer should represent the number of times 0 occurs among the 2,500,000 hexadecimal integers created according to the problem statement. The second integer should represent the number of times 1 occurs among the 2,500,000 hexadecimal integers created according to the problem statement, and so on.
Constraints

1 ≤ start_index ≤ end_index
start_index ≤ end_index ≤ 10,000,000
Sample Input

2
2
1 4
9999997 10000000
2
3 6
5 8

Sample Output

2499998 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
2499998 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0

Explanation

In the first test case, after we perform the two operations and split the array into 2,500,000 groups of 4 bits, the first and the last group will have all 4 bits set - representing 'f' hexadecimal digit. All the other groups will have all 4 bits unset - representing '0' hexadecimal digit.
In the second test case, after we perform the two operations and split the array into 2,500,000 groups of 4 bits, the first two groups will have the state 0011. This represents the hexadecimal digit '3'. All the other groups will have all the 4 bits unset - representing '0' hexadecimal digit.

Dave's Father wants to make chocolates for his birthday. The volume of every chocolate will be 2 cm3. Every chocolate will be cuboid in shape. He has a box of a*b*c dimensions (again a cuboid). Given an input a,b,c write a function to find out if x number of chocolates of 2cm3 volume can fill the box completely. If so, find the number of chocolates too (x).

You are planning a big programming conference and have received many proposals which have passed the initial screen process but you're having trouble fitting them into the time constraints of the day -- there are so many possibilities! So you write a program to do it for you.

The conference has multiple tracks each of which has a morning and afternoon session.
Each session contains multiple talks.
Morning sessions begin at 9am and must finish by 12 noon, for lunch.
Afternoon sessions begin at 1pm and must finish in time for the networking event.
The networking event can start no earlier than 4:00 and no later than 5:00.
No talk title has numbers in it.
All talk lengths are either in minutes (not hours) or lightning (5 minutes).
Presenters will be very punctual; there needs to be no gap between sessions.


Note that depending on how you choose to complete this problem, your solution may give a different ordering or combination of talks into tracks. This is acceptable; you don’t need to exactly duplicate the sample output given here.

Test input:
Writing Fast Tests Against Enterprise Rails 60min
Overdoing it in Python 45min
Lua for the Masses 30min
Ruby Errors from Mismatched Gem Versions 45min
Common Ruby Errors 45min
Rails for Python Developers lightning
Communicating Over Distance 60min
Accounting-Driven Development 45min
Woah 30min
Sit Down and Write 30min
Pair Programming vs Noise 45min
Rails Magic 60min
Ruby on Rails: Why We Should Move On 60min
Clojure Ate Scala (on my project) 45min
Programming in the Boondocks of Seattle 30min
Ruby vs. Clojure for Back-End Development 30min
Ruby on Rails Legacy App Maintenance 60min
A World Without HackerNews 30min
User Interface CSS in Rails Apps 30min

Test output:
Track 1:
09:00AM Writing Fast Tests Against Enterprise Rails 60min
10:00AM Overdoing it in Python 45min
10:45AM Lua for the Masses 30min
11:15AM Ruby Errors from Mismatched Gem Versions 45min
12:00PM Lunch
01:00PM Ruby on Rails: Why We Should Move On 60min
02:00PM Common Ruby Errors 45min
02:45PM Pair Programming vs Noise 45min
03:30PM Programming in the Boondocks of Seattle 30min
04:00PM Ruby vs. Clojure for Back-End Development 30min
04:30PM User Interface CSS in Rails Apps 30min
05:00PM Networking Event

Track 2:
09:00AM Communicating Over Distance 60min
10:00AM Rails Magic 60min
11:00AM Woah 30min
11:30AM Sit Down and Write 30min
12:00PM Lunch
01:00PM Accounting-Driven Development 45min
01:45PM Clojure Ate Scala (on my project) 45min
02:30PM A World Without HackerNews 30min
03:00PM Ruby on Rails Legacy App Maintenance 60min
04:00PM Rails for Python Developers lightning
05:00PM Networking Event

Given a binary tree (not search tree), find the path which adds up to given sum.

Given a array of numbers, find all the numbers which add up to given sum.

There are buses taking various routes and each route has some stops. Given a matrix of stops and distances (distance between two stops for connected stops), find all cluster of stops of any size with all stops in a cluster fully connected and are at a distance not greater than D.

Assume that the routes are bi-directional.

Sort a matrix such that rows in ascending order and columns should be in descending order.

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.

Given a pond where all the stones are lined at a distance of one unit (C in each row and there are R such rows).

Each stone has a special value which denotes the length of the jump the frog can make i.e if frog is on stone (x,y) and value is k then frog can jump to (x+dx,y+dy) where dx+dy=k and frog doesn’t leave the bounds.

Find the min number of jumps to reach the stone at (R,C). Also print the path taken by frog to reach the stone.

Given 1000 elephant ,none of whom exact heights are known, there are statements given which will be of two forms

i- E_i is taller than E_j
OR
ii- E_i is smaller than E_j

Calculate the ascending order of the elephants(in terms of height).

For ex-
1) E1 is taller than E3
2) E3 is smaller than E2
3) E2 is taller than E1

Then order would be E3, E1, E2

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.

Asked like 8 different behavioral questions that were supposed to exemplify Amazon values. I was unprepared for this, as many people say Amazon doesn't do this.
For example, I was asked "Tell me about a time when you solved a complex problem with a simple solution", "Tell me about a time when you increased efficiency", "Tell me about a time when you made a judgement call to take an unknown risk", "Tell me about a time when you disagreed with your team about something and how you reconciled it"

Find all paths in binary tree that add up to a given sum.
Given a tree like this:

2
 3   5 
4 8 6 -2
           2

return {3,4}, {2,5}, {2, 5, -2, 2}

Design the "what other people bought feature." This was focused on database design/creating an api to lie on top of it, and he asked questions to see if I understood how dbs actually work(like what does group by do). I was given an example table with the schema of like
itemID, purchaseDate, customerID
He asked big O complexity of sql query as well.

Design Amazon Questions and Answers. This question was to see how I code, and how I would modularize things. He wanted me to code every single thing as realistically as possible on a whiteboard.

Design a push notification system for android. Assume that we have 1 million users this year, but next year we will have 15 million. Assume that Google can handle infinite notifications per second.

I would love to see this answered, as I did not answer it well.

You are given a String S that consists of characters '0' and '1' only.Return the smallest positive integer K such that it is possible to cut S into K pieces, each of them being a power of 5. If there is no such K, return -1 instead.
Examples
0)

"101101101"
Returns: 3
We can split the given string into three "101"s.

Note that "101" is 5 in binary.

1)

"1111101"
Returns: 1
"1111101" is 5^3.

2)

"110011011"
Returns: 3
Split it into "11001", "101" and "1".

3)

"1000101011"
Returns: -1

4)

"111011100110101100101110111"
Returns: 5

Design an Email sender, need to send 100,000000 emails and you have 5 machines how could you do it efficiently.

Given an URL you need to analyze all the images( they may be in 1000’s of number) and return the cumulative quality of images present in that url.
lets say: you can configure image quality as very good, good, average, poor..etc, so you have to return one value among them.The given URL may contain several other URLs and they also contain lot of images . you need to consider all of them. lot of questions like how to avoid visiting same url again,
how would you determine the quality of an image if you encounter an url that contains only an image..etc.

Design Elevator system. And then write an algorithm for that Design such that, the user request should be completed in logN time in a N story building with M elevators.

In an online teaching system, there are n number of teachers and each one teaches only one subject to any number of students.
And a student can join to any number of teachers to learn those subjects.
And each student can give one preference through which he can get updates about the subject or class timings etc.
Those preferences can be through SMS or twitter/facebook or email..etc.
Design above system and draw the diagram for above.

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);

Identify the output

Class A {
}

Class B {
}

B b = new B();
A a = (A) b;
sysout(b.getClass());
sysout(a.getClass());

Given Two classes A & B. How will B know if an instance of A is already created?