## Software Engineer Interview Questions

- 1of 1 vote
Google

1st round

Given a box with N balls in it, each ball having a weight, randomly choose pick one out base on the weight.

Input ball1-> 5kg, ball2 -> 10kg and ball3 -> 35kg,

then Prob(ball1 chosen) = 10%, Prob(ball2) = 20%,

Prob(ball3) = 70% ;

Follow-up:

Select a ball randomly based on weights. Once a ball is chosen, remove it. Next time select from the remaining balls. Go on until there is nothing left in the box.

- 2of 2 votes
Find whether string S is periodic.

Periodic indicates S = nP.

e.g.

S = "ababab", then n = 3, and P = "ab"

S = "xxxxxx", then n = 1, and P = "x"

S = "aabbaaabba", then n = 2, and P = "aabba"

follow up:

Given string S, find out the P (repetitive pattern) of S.

- 1of 1 vote
Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

Example:

HitCounter counter = new HitCounter();

// hit at timestamp 1.

counter.hit(1);

// hit at timestamp 2.

counter.hit(2);

// hit at timestamp 3.

counter.hit(3);

// get hits at timestamp 4, should return 3.

counter.getHits(4);

// hit at timestamp 300.

counter.hit(300);

// get hits at timestamp 300, should return 4.

counter.getHits(300);

// get hits at timestamp 301, should return 3.

counter.getHits(301);

Follow-up:

Due to latency, several hits arrive roughly at the same time and the order of timestamps is not guaranteed chronological.

Follow up 2:

What if the number of hits per second could be very large? Does your design scale?

- 0of 0 votes
If I need to read .txt file (inside +4000 words) and print 100 most repeated which structure is the easiest:

hash table?

binary tree?

linked list?

Thanks

- 0of 0 votes
Hi, my question is about linked list? If I read .txt file (there is 5000 words inside) in to linked list. Is it possible to print 100 mostly repeated words and print them ??

example:

cat cat dog dog dog

dog3

cat 2

Thank you in advance for any help you can provide.

- 1of 3 votes
Round3 Google

For N light bulbs , implement two methods

I. isOn(int i) - find if the ith bulb is on or off.

II. toggle(int i, int j) - i <= j. Switch state (switch on if it's off, turn off if it's on) of every bulb in range i to j.

All bulbs are off initially.

- 2of 2 votes
/**

* Google

* Given a list of non-negative numbers and a target integer k,

* write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

**/

- 0of 0 votes
Write a function that given a string would print the 'expanded' version of it.

For example a2[bc2[c]]d would print out abcccbcccd

Note:

The number before the opening and closing square brackets is the multiplier for the characters within the square brackets

Method Signature [Java]:`public String expanded(String str)`

- 3of 3 votes
Amazon

Given an ArrayList of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder.

- 2of 2 votes
Google

Given an array a[] and an integer k, a[i] means flower at position a[i] will blossom at day i. Find the first day that there are k slots between two blooming flowers.

- 1of 1 vote
Google

Given a string that represents time like "15:31", find the next time that is formed by the numbers in the string(a number can be used more than once). For "15:31", the answer should be "15:33".

- 0of 0 votes
Find the Kth most Frequent Number in an Array.

Example:`arr[] = {1, 2, 3, 2, 1, 2, 2, 2, 3} k = 2 Result: 3 Because '3' is the second most occurring element.`

Follow up: What if the array is extremely large?

- 1of 1 vote
Twitter

Create a simple stack which takes a list of elements.

Each element contains a stack operator (push, pop, inc) and a value to either push/pop or two values, n and m,

which increment the bottom n values by m.

Then print the topmost value of the stack after every operation. If the stack is empty, print "empty"

- 0of 0 votes
design a zigzag iterator, implement the prev() and hasPrev function

- 0of 0 votes
Create a SQL-like language parser that manipulates directories and files (The compiler/parser may be created in any other language).

To summarize, I want you to create a "file and directory manipulation language" with the following rules/syntax (you may create another commands):

CREATE DIR <path>

CREATE FILE <name> IN <path> [WITH <data>]

'WITH' insert the <data> in the file on the fly, but it's optional

GET DATA FROM <path/to/file>

Examples on how this language may be used:`import FDML ex = "Hey guys" data = FDML.get('GET DATA FROM "./path/to/file"'); FDML.statement("""CREATE DIR "./imgs"; CREATE FILE "test.txt" IN "./path/to/dir""") FDML.statement('CREATE FILE "welcome.txt" IN "./path/to/dir" WITH "{}"'.format(ex)) print(data)`

Or those commands can be run in a shell:

> fdml "CREATE DIR './dir'"

> /dir was created!

- 2of 2 votes
DropBox Dec 2017

Congrats to Brian landing @DropBox

Round 3：

Develop an web crawler API, find all sub-sites reachable from a given URL.

Given this method - vector<string> getURLs(string url);

Comparison of DFS vs BFS in the scenario

Follow up：

Support multi-thearding.

Round 4：

Build an ID allocator. Max ID value is given as MAX. Allocate IDs from 0 to MAX.

Must be able to handle when an ID gets released.

Must be able to handle exceptions.

Follow-up: Improve time/space efficiency.

Optimal approach:

Segment tree + bit map.

Looking for interview experience sharing and coaching?

Visit aonecode.com for private lessons by FB, Google and Uber engineers

ONE TO ONE real-time coaching on SYSTEM DESIGN, ALGORITHMS, and mock interviews.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

- 2of 2 votes
DropBox Dec 2017

Congrats to Brian landing @DropBox

Dropbox always has the most responsive HR and gives review on the interview within a week. The canteen is also one of the best in Bay Area.

Phone：

LC: game of life

What if the board is huge?

Store in disk

with bitmap

Load into memory, process and write to disk row by row

Visit AONECODE.COM for private lessons by FB, Google and Uber engineers

Our ONE TO ONE class offers

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)

ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),

latest interview questions sorted by companies,

mock interviews.

Members get hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

Onsite：

Round 1：

Given an array of byte and a file name, find if the array of byte is in file.

Solution: Rolling hash

Round 2：

Given an Iterator of some photo with IDs, find the top K most hit photo IDs.

Follow up: What if the input is from a stream? When iterator reaches the end, moments later new hits can be added to the iterator. Modify code for this scenario.

Lunch was great.

Then came a demo round. Discussed Dropbox Paper

- 0of 0 votes
Given an extremely large file that contains parenthesis, how would you say that the parenthesis are balanced?

The file cannot fit in the memory. How would you process the file and how would you store the intermediate results.

Walk me through the entire algorithm.`Examples: {[()]}, {[](){}}, [] are some valid examples.`

- 0of 2 votes
Given a matrix of each element is the height of the location, the side of the matrix has a river height h, water diffuse matrix results,

Follow up If there is a place where there is not drowning a person and a dog, people want to reach the dog's position without water, the river is highly uncertain,

Ask the maximum height h such that the number of steps taken by a person is less than or equal to a given k. Traverse the height h,

- 0of 0 votes
Consider there is a streaming service, which outputs Log object to your service. The Log object has fields like {timeStamp, userId, hashtag(used in the tweet), @userAddressUsedInTweet} etc. Imagine this streaming service has very high QPS. Design your service in such a way that it can output top K userId's within a configurable time window(example: last 1 hour, last 24 hour etc). This service should be extendable to get any top K category (Example: TopK userId's, TopK hashtags etc). What would you use to design such a service. Top K is defined by its frequency, example: 1,2,3,4,1,2,1,2,1,1,5 are the userIDs then the top 2 users are userId 1 and 2.

@EdgeCase:

1. Take into consideration how to store data in that window to get the topK user's.

2. The service should be highly available and should return the results quickly

3. Design and implement this service

- 0of 0 votes
C * R 2-D array, there are R, G, B, Y four types of elements, if no vertical and horizontal has three adjacent elements are the same type, then the 2-D array is valid

Let write a function to determine whether a 2-D array is valid.

follow-up how to generate such a valid 2-D array

- 0of 0 votes
`Give an Node { Node getLeft (); Node getRight (); String toString (); } Give a root node Node root * / \ + - / \ / \ 1 2 3 4 Return (1 + 2) * (3-4) If (1 + 2) + (3 + 4) does not need to be bracketed Only leaf nodes are numbers followup Give you * + 12-34 to return this tree`

- 0of 0 votes
I have applied for Software Engineer at a startup company in India, I have asked the following question.

You are building an application with ORM model say django, you have set of models, urls. Let's say an user is hitting api /user/account/profile/xxx/yyy like this. You have to check whether user has permission to access or not. If user has access to /user/ then he has access to the whole URL, like wise if he has access to /user/account/ he has access to whole URL. User table looks like below and it has a field called prefix which contains URL prefix of that particular user.

Users

userid | prefix | username | firstname | lastname

1 /user/ lokesh1729 lokesh sanapalli

2 /user/account lokesh1729 lokesh sanapalli

What is the most efficient way to check if a particular user has access to an API or not???

I gave a brute-force approach that first we will check if he has access to /user/ then /user/account then /user/account/profile and so on, if he has access to a prefix and we will process the request.

He is not satisfied with the answer. Can anyone tell me what might be the answer for this???

- 0of 0 votes
Lets say we have to find a tallest line of the horizon from a given 2D array of the preprocessed image. The line starts at left most column of the Martrix and end at right most column of the matrix. To calculate the line you can only move left to right to 3 position, diagonally up , horizontally right and diagonally right i.e from a[i][j] you can move to a[i-1][j+1], a[i][j+1] and a[i+1][j+1].

When moving to the right we need to pick the highest value in the cell . We will do this for very row in column 0 i.e a[0][j] then we will pick the smallest value of the path we have got. The ans will the smallest of the all values we got from traversing all the path

I know this bit vague and I had hard time understanding the question but this what I understood

Lets say we have 3*3 array {{5,4,8}, {1,5,9}, {2,6,10}} . Now if we start from a[1][0] the possible path we can have

1 -> 6 -> 10 as we have to pick the highest value . Once we have this path we pick the smallest value on this path which is 1 . We repeat this for all rows in a[i][0] then among all those values pick the smallest one

Find the best line from the matrix.

I said we can do BFS to find best path but interviewer said time complexity of that is too high, need to do better than that.

Time complexity for BFS I think is Rows * 3^Colms as from any given cell we have 3 options to go to right (please confirm this as I not sure about it)

- 2of 2 votes
Congrats on aonecode.com member V.S. on the offer from Microsoft and thanks for sharing with us the experience.

Coding Question 1 - Find all the paths between two nodes

Coding question 2 : Max sum in adjacent sub array

Design Question - Design a ticketing System

Design Question 2 - Design a system which allows multiple agents to read different data from same tables. Latency should be low. Algorithm should rank agents through some logic and assigned work according to that so that each agents are reading different set of rows from same table. Scale it for 20 million active agents .

Follow up - If Data Sharding is allowed, what will be the Shard Id and how the partition will look like? How your system will respond if there are agents which are also writing at same time. Consistency should be given high preference over availability.

Looking for coaching on interview prep?

Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!

Customized course covers

System Design (for candidates of FB, LinkedIn, AMZ, Google & Uber etc)

Algorithms (DP, Greedy, Graph etc. every aspect you need in a coding interview & Clean Coding)

Interview questions sorted by companies

Mock Interviews

Our members got into G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

- 1of 1 vote
A city bus station information, example, bus No. 1 stops at abcd station, bus No. 2 stops at cefg station. Then a-d you only need to take No. 1, thus return 1, a-g is 2, because you need to transfer at station c,

ask for a minimum bus you need to take to reach to another station. You can design any data structures.

- 0of 0 votes
Third question was to find length of longest AP in given set of numbers.

- 0of 0 votes
Find the nth number that contains the digit k or is divisible by k. (2 <= k <= 9)

Example –

if n = 15 & k = 3

Answer : 33

(3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 31, 32, 33)

- 0of 0 votes
Given 2 numbers m and n , find if the sum m+n has the same number of digits as n . If true then print m+n otherwise print n.

- 3of 3 votes
Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature.

[73, 74, 75, 71, 70, 76, 72] -> [1, 1, 3, 2, 1, nothing, nothing]