## SDE-2 Interview Questions

- 0of 0 votes
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.

- -1of 1 vote
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).

- 0of 0 votes
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

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

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

- 0of 0 votes
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.

- 1of 1 vote
Sort a matrix such that rows in ascending order and columns should be in descending order.

- 0of 0 votes
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.

- 0of 0 votes
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

- 0of 0 votes
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.

- 0of 0 votes
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.

- 0of 0 votes
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

- 0of 0 votes
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.

- 2of 2 votes
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"

- 0of 0 votes
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}

- 0of 0 votes
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.

- 0of 0 votes
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.

- 0of 0 votes
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.

- 0of 0 votes
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

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

- 0of 0 votes
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.

- 0of 0 votes
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.

- 0of 0 votes
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.

- 0of 0 votes
How to debug deadlock or heap corruption from DUMP using WinDbg tool?

- 0of 0 votes
Design classes and interface for BookShelf

- 1of 1 vote
Given a file, read last n lines from the file

string ReadNLines(sttring fileName, int n);

- 0of 0 votes
Identify the output

`Class A { } Class B { } B b = new B(); A a = (A) b; sysout(b.getClass()); sysout(a.getClass());`

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

- 0of 0 votes
Log file contains UserId.Every day has new log file.Given range of n days find top 10 users?

- 0of 0 votes
Given an int[] multiply all numbers except index I/p {1,2,3,4} O/P {24,12,8,6} How can you minimize multiplication