Flipkart Interview Experience

Machine Coding Round

Problem Solving Round

1) Find diameter of a binary tree and tell the time complexity. Optimise the solution.
http://www.geeksforgeeks.org/diameter-of-a-binary-tree/

2) Given a dictionary and two words start and target of same length. Find smallest path from start to target if exist, such that adjacent words in the chain only differ by one character and each word in the chain is a valid word (exists in dictionary).
http://www.geeksforgeeks.org/length-of-shortest-chain-to-reach-a-target-word/

Example

Input:  Dictionary = {POON, PLEE, SAME, POIE, PLEA, PLIE, POIN}
             start = TOON
             target = PLEA
Output: 7
Explanation: TOON - POON - POIN - POIE - PLIE - PLEE - PLEA

DailyHunt Interview Experience

First Round (F2F)

1. Calculate angle between hour and minute hand in a clock.
http://www.geeksforgeeks.org/calculate-angle-hour-hand-minute-hand/

2. Given a binary representation of a number, find the longest contiguous sequence of 0s between 2 1.
For example , if binary representation of a number is 1000100, then answer should be 4.

If binary representation of a number is 1000, then it should return 0.

3. Difference between comparable and comparator.

4. What happens internally when we remove a key from HashMap.

Microsoft Interview Experience

Online Coding Test 

1.  Given a boolean matrix mat[N][N] of size MXN, modify it such that if a matrix call mat[i][j] is 1, then make all cells of its row and column as 1.

http://www.geeksforgeeks.org/a-boolean-matrix-question/

2. Given a positive integer n, generate all possible unique ways to represent n as sum of positive integers.

http://www.geeksforgeeks.org/generate-unique-partitions-of-an-integer/

3.  There is an array of strings. For example:
Victor, Veronica, Farah, Veronica, Farah, Veronica
Farah and Veronica occurs maximum no of times. As Veronica comes after Farah in alphabetical order, output should be Veronica.

F2F Round 1

1. Clone a linked list with next and random pointers

http://www.geeksforgeeks.org/clone-linked-list-next-arbit-pointer-set-2/

2. Generate 0 and 1 with 25% and 75% probability

http://www.geeksforgeeks.org/generate-0-1-25-75-probability/

3. Given an infinite stream of integers, find Kth largest element at any point of time.

http://www.geeksforgeeks.org/kth-largest-element-in-a-stream/

F2F Round 2

1. Design an entry and exit system for a mall where at max n people can be there at one point of time inside mall

2. Given a matrix where each cell contains x no of gold coins and a constraint that you can only move right or down from top left corner to bottom right corner, find the maximum no of coins that you can collect. Write a code for the same.

F2F Round 3

1. Print all possible partition of a given string into dictionary words. (Variant of word break problem)

http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/

http://ideone.com/53LMkr

Uber interview Questions

1. Telephonic Round

1) Design an expiry cache similar to redis cache.
http://blog.gainlo.co/index.php/2016/05/17/design-a-cache-system/

2) Add 1 to a linked list

A number is represented in linked list such that each digit corresponds to a node in linked list. Add 1 to it. For example 1999 is represented as (1->9->9->9) and adding 1 to it should change it to (2->0->0->0).
http://www.geeksforgeeks.org/add-1-number-represented-linked-list/

3) Given a array in which numbers are in the unsorted order, find if any triplet a, b , c  exist such that x < a+b+c < y.

For example, let's say array is:
0.5, 0.1, 1.1, 0.9, 12, 12, 98
Check whether any triplets exist where 1 < a+b+c < 2

Design Level Questions

  1. Design twitter

https://www.interviewbit.com/problems/design-twitter/

2. Design a key-value store

http://blog.gainlo.co/index.php/2016/06/14/design-a-key-value-store-part-i/

3. Design a cache system
http://blog.gainlo.co/index.php/2016/05/17/design-a-cache-system/

4. Design hit counter
http://blog.gainlo.co/index.php/2016/09/12/dropbox-interview-design-hit-counter/

5. Design tiny url
http://n00tc0d3r.blogspot.in/

6. Design elevator system
http://thought-works.blogspot.in/2012/11/object-oriented-design-for-elevator-in.html

7. Design parking system

8. Design monitoring system.
Hint: Observer Pattern
https://www.careercup.com/question?id=5121055761891328

9. Design your own hash map

10.  Design restaurant reservation system.
https://www.careercup.com/question?id=5733795254763520

11. How Uber scales?
http://highscalability.com/blog/2015/9/14/how-uber-scales-their-real-time-market-platform.html

12. Design bookmyshow.com
https://www.careercup.com/question?id=6193420734300160

13. Design ATM
http://www.math-cs.gordon.edu/courses/cs211/ATMExample/

14. Design crossroad traffic signal system

// Facebook Interview Question
15. Design an instagram API which supports following feature:

• Upload Photos
• Follow/Unfollow
• Get User Feed

// Google Interview Question
16.  Design a system to return an unique ID for each request. For most of requests, the ID value should increase as time goes, the system should handle 1000 requests per second at least.

timestamps alone is not valid since there might be multiple requests with same timestamps.

https://www.callicoder.com/distributed-unique-id-sequence-number-generator/

Helpful links to refer for design questions:

https://www.interviewbit.com/

https://geekibuti.blogspot.in/

Amazon Interview Experience

Round1 (Written)

1. Find the maximum element in an array which is first increasing and then decreasing. Time Complexity should be less than O(n).

http://www.geeksforgeeks.org/find-the-maximum-element-in-an-array-which-is-first-increasing-and-then-decreasing/

2.  Given an expression in string, check for balanced parenthesis.
http://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/

3. Find the level in binary tree which has maximum no of nodes. Print no of nodes and level.

Round2 (Face to Face)
1.  Print a binary tree in vertical order.
http://www.geeksforgeeks.org/print-binary-tree-vertical-order/

2. Search for an element in rotated and sorted array
http://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/

Round3 (Face to Face)

Design for scheduling jobs in distributed system. Give all the apis which will be exposed to user .
What all components will be involved at the backend. What data structures will be used etc.


Round4 (Face to Face)
1. Given a matrix with each cell containing no. of gold coins and a constraint that you can only move right or down from the top left corner to bottom right corner, find the path that gives you maximum gold coins and maximum no of gold coins that can be collected. (Dynamic Programming)

2. There are trillions of stars in sky and you are given distance of each start from the earth. You have to find million stars with least distance form the earth.

3.  There are n conference rooms and all are booked for a particular interval of time.
Let's say there are 3 rooms and their time slot of booking are:
Room1: {1,3} {6,7}, {8,9}
Room2: {2,5}, {9,10}
Room 3: {3,7}

Find the total no of hours in which all the rooms are unoccupied.
For above case, if we consider total no of hours as 20, all rooms are vacant for (20-8)=12 hours.
Solution:
1. Sort all the intervals based on start time.
2. Merge all overlapping interval
3. Find total no of hours covered by those intervals.
4. Subtract from total hour and return.

4. There are n workers and their wages are given for each day. If a worker work on day 1, he can only work after 3rd day. If he works on 3rd day, he can work after 5th day. Choose the day in such a way that he can maximize profit.
For ex: wages[] ={5, 1, 1, 10, 8, 3,5,12}
Maximum profit here is (5+10+12)=27  (Dynamic programming question)
http://ideone.com/ELwiJa

Round5 (Face to Face)
Manager Round
1. Find kth non repeating element in in stream of integers.
2.  Merge 2 sorted array to get sorted result array.
3. You are given an array whose each element represent height of the array. The width of every tower is 1. It starts raining. How much water is collected between the towers?
Ex: [1,3,5,7,2] = answer is 2 units between 5 and 7
4. You are having a conflict with your manager regarding how to prioritize your task . How would you convince him?
5. What is the biggest technical goof up you had lately?
6. What are you passionate about?

LinkedIn Interview Experience

Round 1 (Telephonic)
Data Structure

1.  Write code to find maximum contiguous sum in an array of integers.
2.  Write code to find maximum contiguous product in an array of integers.
3.  Given a nested listed of integers, return the sum of all integers reverse weighted by their depth.
     When I started taking time for it, question was simplified to find weighted by their depth.
     For ex: {{1,1}, 2, {1,1}} should return (1*2+1*2) + (2*1) + (1*2+1*2) = 10

Round 2 
Whiteboard Coding Round

1. Given a list of tuples representing intervals, return the range these intervals covered.
For ex: [1,3], [2,5], [8,9] should return 5.

2.  There is a list of Points given , let's say:
     {0,3}, {0,6}, {0,9}, {1, 8}, {1,5} . Find out 3 points whose distance is minimum from a given Point P {1,3}. Focus was to optimize on time complexity.

Round 3 
Whiteboard Coding Round

1. Find out maximum no of collinear points in a plane. Also find out the line formed by them.

Round 4
Design Round

1.  There is a set of let's say 10 servers which are receiving thousands of client request per second.
There is a function given isMalicious( String ip) which returns true of an ip is malicious.
Server should drop the ip if it is malicious.  Design such a system so that call to function isMalicious() is minimum.

Round 5
Host Manager Round

1. Tell me about yourself
2. Describe about the current project and various question on it like what were the challenges faced etc.
3. What are the steps that you will follow if you are assigned some task.

Round 6
Technical Communication

1. Talk about any interesting project that you have done in your career.
2. Lots of questions on project like how it will work in multithreaded environment, why certain design or technology was adopted. Could we have done something better ? etc. etc.