## Software Engineer Interview Questions

- 0of 0 votes
You are given an old touch smartphone numbers having dial pad and calculator app.

Aim: The goal is to type a number on dialpad.

But as phone is old, some of the numbers and some operations can't be touched.

For eg. 2,3,5,9 keys are not responding , i.e you cannot use them

But you can always make a number using other numbers and operations in Calculator. There could be multiple ways of making a number

.Calculator have 1-9 and +,-,*,/,= as operations. Once you have made the number in Calculator you can copy the number and use it.

You have to find minimum number to touches required to obtain a number.

#Input:#

There will be multiple Test cases .Each test case will consist of 4 lines

1) First line will consist of N,M,O

N: no of keys working in Dialpad (out of 0,1,2,3,4,5,6,7,8,9)

M:types of operations supported (+,-,*,/)

O: Max no of touches allowed

2) second line of input contains the digits that are working e.g 0,2,3,4,6.

3) Third line contains the valued describing operations, 1(+),2(-),3(*),4(/)

4) fourth line contains the number that we want to make .

#Output:#

Output contains 1 line printing the number of touches required to make the number

#Sample Test Case:#

1 // No of test cases

5 3 5 // N ,M, O

1 2 4 6 0 // digits that are working (total number of digits = N),

1 2 3 // describing operations allowed (1--> '+', 2--> '-', 3--> '*' , 4--> '/' )(total number is equals to M)

5 // number we want to make

Answer 3

How 4? 1+4= , "=" is also counted as a touch

2nd Sample Case

3 // No of Test cases

6 4 5 // N ,M, O

1 2 4 6 9 8 // digits that are working (total number of digits = N),

1 2 3 4 // describing operations allowed (1--> +, 2--> -, 3--> , 4-->/)

91 // number we want to make

6 2 4 // 2nd test case

0 1 3 5 7 9

1 2 4 // +, -, / allowed here

28

5 2 10

1 2 6 7 8

2 3 // -, allowed

981

#Output:#

2 // 91 can be made by directly entering 91 as 1,9 digits are working, so only 2 operations

5// 35-7=, other ways are 1+3*7=

9//62*16-11=

Order for computation will be followed as symbols entered, if + comes, it will be computed first

One more example: lets say 1,4,6,7,8,9 works and +,-,* works.

2,3,5 and / doesn't work.

If you have to type 18-> 2 operations. (Each touch is considered an operation),br> If you have to type 5 -> '1+4=' that requires 4 operations. There could be other ways to make '5'.

- 0of 0 votes
Complete the puzzle which simulates generic directory structures.

* The solution should be directory agnostic.

* Be succinct yet readable. You should not exceed more than 200 lines.

* Consider adding comments and asserts to help the understading.

* Code can be compiled with javac Directory.java

* Code should be executed as: java -ea Directory (-ea option it's to enabled the assert)

*/

/**

* change the code here.

*/

class Shell {

Shell cd(final String path) {

return this;

}

public String path() {

return "/";

}

}

public class Directory {

public static void main(String[] args) {

final Shell shell = new Shell();

assert shell.path().equals("/");

shell.cd("/");

assert shell.path().equals("/");

shell.cd("usr/..");

assert shell.path().equals("/");

shell.cd("usr").cd("local");

shell.cd("../local").cd("./");

assert shell.path().equals("/usr/local");

shell.cd("..");

assert shell.path().equals("/usr");

shell.cd("//lib///");

assert shell.path().equals("/lib");

}

}

- 1of 1 vote
4/5 Round at Uber

Coding: Given a 2D array of either '\' or '/', find out how many pieces this rectangle is divided into graphically.

For a 2X2 matrix with

/\

\/

The matrix split into 5 pieces - the diamond in middle and the four corners. Return 5 as the answer.

5/5 Round at Uber

Design Excel.

- 0of 0 votes
2/5 Round at Uber

Bar raiser - Behavioral questions. Coding: Find if a set of meetings overlap. Meeting has a starttime and an endtime with accuracy to minute. All meetings take place in the same day. Do this in O(n) time.

3/5 Round at Uber

Coding: Subset sum. Follow-up: Optimize the solution.

- 0of 0 votes
1/5 Round at Uber

Manager : Behavioral questions. Basic system design concepts. Publish/subscribe model. Discussion on Uber architecture.

- 0of 0 votes
I've got these trees of integers; they're like regular trees, but they can share nodes.

I need to know if any branch of this tree sums to 100.

7

/ \

8 6

/ \ / \

2 3 9

/ \ / \ / \

5 4 1 100

Follow up question was how would you change the code to handle negative numbers.

- 2of 2 votes
Uber

1. Mirror Binary Tree

2. String pattern matching

The matching should cover the entire input string (not partial).

The function prototype should be:

bool isMatch(String str, String pattern)

Some examples:

isMatch("aa","a") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa","a{1,3}") → true

isMatch("aaa","a{1,3}") → false

isMatch("ab","a{1,3}b{1,3}") → true

isMatch("abc","a{1,3}b{1,3}c") → true

isMatch("abbc","a{1,3}b{1,2}c") → false

isMatch("acbac","a{1,3}b{1,3}c") → false

isMatch("abcc","a{1,3}b{1,3}cc{1,3}") → true

In pattern string, a char followed by {lower, upper} means that the char occur lower to upper(exclusive) times. e.g. a{1, 3} -> a occurs 1 or 2 times.

- 0of 0 votes
given a list of numbers, put with + - * / any two number, find the maximum value you can get.

int getMaxNumber(int[] nums){

}

- 2of 2 votes
3.1 design: design fb inbox search —> just focus on the post

4.1 binary tree to circular double linked list.

4.2 two arrays, find the common elements of two sorted array. if one array is small, the other is very big.

- 1of 1 vote
2.1 career discussion

2.2 divide two numbers with no / or %

- 2of 2 votes
1/4 round of FB on-site interview, Master Degree, Hired

1.1 diameter of tree

1.2 find the point which have the maximum overlap of intervals

- 3of 3 votes
1 year exp. Interviewed at Cambridge, MA

Round1

LC304. Follow-up: given a char stream instead a string as the input, get the longest substring with at most K distinct characters.

Round2

Find out the area of a number of squares on a plane, an advanced version of LC223.

Had no clue on that problem at all so the interviewer kindly gave another one LC305.

Round3

Similar to LC393 but the interviewer made a slightly different rule for encoding.

Follow-up: decode with utf-16. It took quite a while for me to understand the rules.

Round4

Card game rule: the hand is drawn from a pack of cards (no jokers).

Play cards ONLY when they are

1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).

2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).

Find out whether the player is able to play the whole hand given.

e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.

[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true.

- 1of 1 vote
given a string of number, you can add a + or * sign between any two numbers, find the maximum value you can get

ex. s = "89" --> 8 * 9 = 72

int maxNumber(String s){}

- 1of 3 votes

- 0of 0 votes
A new species has been discovered and we are trying to understand their form of communication. So, we start by identifying their alphabet. Tough Mr. Brown managed to steal a vocabulary that has words in it in ascending order and a team already identified the letters. So, we have now ordered words as sequences of numbers, print every letter once in ascending order.

[3,2]

[4,3,2]

[4,1,1]

[1, 2]

[1, 1]

alphabet: [3, 4, 2, 1]

- 2of 4 votes
Master Degree 2 year exp

1st Round.

Behavioral - most challenging project.

Tech - bit manipulation

2nd Round. A matrix has 0s and 1s only.. All the 1s in every row are to the of 0s. Find out the leftmost 1 in the entire matrix.

3rd Round.

A dp problem.

Find out how many ways you can make change of N cents given coins of values [a1, a2, a3...], each type of coin got infinite supplies.

Arrangement of coins don't matter.

4th Round.

Design news feed.

A user wrote a post with the basic user info, pictures and time etc (I even drafted a basic UI on whiteboard).

How to obtain these information and store them.

If a new feature with a button is added. How to maintain availability of old service to users who did not update the app.

Did not dive further into scaling.

5th Round.

User groups - If I made a certain post visible to a user group, how to store the post? how to push the post to the chosen group. If there are new friends who aren't assigned to any group just yet, how to treat them as if they were in the same 'unassigned' group?

DB sharding is involved.s

- 1of 1 vote
Find the length of longest arithmetic progression in array.

For example, in the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, and 7

- 1of 1 vote
Given a string, find the longest substring without repeating any character.

- 1of 1 vote
Design a service that keeps track of mobile users as they check in at different locations. This service will get informed of each check-in in real time (a user/location pair) and must be able to answer the following queries in real time:

1. Where is user U right now?

2. What users are at location L right now?

The following requirements apply:

1. A user can only be at one location at a time. If user U checks in at location X and then at location Y, they are no longer at location X.

2. A check-in only valid for at most 2 hours. If user U checks in at location X and then does nothing for 2 hours, they are no longer at location X.

The service should have durable enough storage that you can restart it without losing all of your data It should not store everything in memory.

what kind of DB will you use and how data will be organized and any indexes. If storage is spread out over multiple databases(locations), how is that done?

scalability/availability consideration, how will be distribute multiple servers. what happens when the traffic goes 10x all of sudden. What happens if one of the server goes down.

- 2of 2 votes
Google full-time phD candidate w/ work experience.

Q1. On a 1 meter walkroad, randomly generate rain. The raindrop is 1 centimeter wide.

Simulate how raindrops cover the 1 meter [0~1] road. How many drops does it take to fully cover the 1meter?

Q2. Find out the maximum number of isosceles triangles you can make from a plane of points(cannot reuse points)

Q3.Longest holiday - Every city has a different days of holidays every week. You may only travel to another city at the weekends. What is the max days of holiday you can get this year.

Q4.

Design merchandising product data storage service

- 0of 0 votes
Give you an unsorted integer iterator

and a percentage that is expressed in double (for example, 0.4 for 40%),

and find the number of the sorted array at the percentage position.

Example: Enter [1 3 2 5 4 6 7 9 8 10], and 0.6, you will return 6

public int findNumber(Iterator<Integer> nums, double percent){

}

- 0of 0 votes
An ABC notation in a tree is defined as folllows:

1. "0" means travel left

2. "1" means travel right

3. "Undefined" means hit the root

4. "Not Found" means not present in tree

Given a BST insertion order, {5,2,8,3,6,9,1} find the ABC notation for 6, 1, 10, 2 which is "10","00","NotFound", "0"

- 4of 4 votes
Google On-site in May

Create a class with a collection of integers.

Enable 3 APIs:

void append(int x),

int get(int idx),

void add_to_all(int x)，//add x to all numbers in collection

These methods should run in O(1) time.

Follow-up

In addition, implement

void multiply_to_all(int x)

The same required to run in O(1) time

- 2of 2 votes
Given a n*m size 2D array with integers from 1 to n*m - 1 in it.

Integers are not sorted. The last position of the matrix stays a movable block.

For each time, you can swap the movable block with any adjacent number.

And eventually you will have the integers sorted and the movable block returned

to its starting position. Think about an approach to print the path.

(You can assume it always have at least a solution)

- 0of 0 votes
How to get the repeating decimal pattern of a division? (e.g 1/3, 1/6)

- 1of 1 vote
Given input - xyzonexyztwothreeeabrminusseven as a string, return an integer as the sum of all numbers found in the string

Output - 1 + 23 + (-7) = 17

- 1of 1 vote
Given a preorder traversal of a BST, print out the inorder transversal of the BST

public void printInorder(int[] nums){}

- 0of 0 votes
Implement circular buffer with read & write functions

- 0of 0 votes
Coding III

Implement int divide(int a, int b) without division or mod operation.

## Round IV

Behavioral Questions + Project Walk Through + Coding (Validate BST)

## System Design V

Design memcache to enable read, write and delete (single server, non-distributed infrastructure).

Which data structure to go with?

Eviction rules?

How to minimize segmentation?

How to handle concurrency?

## Extra

After two weeks they called me to an extra round of system design.

How to store social graphs?

How to handle concurrent read/write requests(read heavy) on one server.

- 0of 0 votes
Coding I

Flatten a linked list.

Each node in the list carries a piece of data and a pointer. The data could be in a normal data type such as an integer, or a pointer that points to another list node.

The interviewer gave no specification on how the list node class was defined. You may look at each list node as if it has two pointers - one of them points to the next node; the other points to the ‘data’ which could be either a node or an integer. There also needs to be a function to tell you about the node data is actual data or a pointer.

I solved the problem with recursion. During the process, any nodes that don’t carry an integer get removed.