## Algorithm 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'.

- 2of 2 votes
Apple phone interview

Given an API to find all IPv4 addresses in a log file, find all IPs that occurred only once.

Follow-up: What if the log comes from a data stream.

Follow-up: If the machine has 4GB RAM, is there going to be a problem?

- 0of 0 votes
The memmove() function copies n bytes from memory area src to memory area dest. The memory areas may overlap: copying takes place as though the bytes in src are first copied into a temporary array that does not overlap src or dest, and the bytes are then copied from the temporary array to dest.

- 0of 0 votes
Suppose there are N number of clusters, B number of machines and number of tasks in clusters are stored in an array named a. The goal is to minimize the single most overloaded machine and every cluster must be given at least one machine. Output should be one integer representing the number of the tasks in the busiest machine (rounded up).

1<=N<=500000

N<=B<=2000000

1<=ai<=5000000

for example, N=2,B=7, a=[200,450], output should be 100.

Any ideas?

Thanks

- 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.

- 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.

- 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

- 0of 0 votes
Phone interview question from January.

We have a maze with three types of spaces:

1. Walls

2. Offices

3. Hallway space

Given a maze, determine which non-wall space would minimize the sum of all distances between that space and every office. You can only move up, down, left, and right.

(Edit: ChrisK described the problem more clearly than I did: "find the field that minimizes the sum of the shortest path[s] from this field to each office space.")

Example:`WWWWWWWW WWW O WW WWW OW WWW WWWW WO WWWW WWW WWWW WO W WWWWWWWW`

O = office, W = wall, spaces are hallway spaces

You can represent the maze however you want. That is, you can use any data structures you want, and you don't necessarily have to use O for office, W for Wall, and spaces for hallways.

(I'm not sure if you can actually start from an office space, but that should be a trivial issue because you can always just start a position adjacent to an office.)

- 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.

- 0of 0 votes
Identifying if all the elements of a set (in enterity) is present in a list of sets.

For example checking for set1 = {1,2} in {1,2,3}, {5,6} should return true as {1,2} is present in {1,2,3}. Similiary it will be true for {1,2,8,9}, {1,2,4}

But checking for {1,2} in {1,5,6}, {2,3,1} should return false as {1,5,6} does not contain all elements of {1,2} 2 is missing

- 1of 1 vote
Given string a and string b, find all the occurences of the anagrams of a in b.

- 0of 0 votes
Game of Death:

Implement an algorithm that produces the next move in the game of death.

Basically given a two dimensional array it will have either values 1 (live cell) or 0 (dead cell)

1. A Live cell will live only if it has two or three live neighbors All other cases die.

2. A dead cell with exactly three live neighbors will live otherwise no change, dead

Transform the array by using above two rules

- 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

- 0of 0 votes
Design an algorithm that provided your current location and a list of ATMs locations in the area, get you the closest K ATMs to your location.

Assume you have a method getDistance(a, b) that calculates the distance between a and b.

Follow Up:

Make your solution O(k) space and O(n) time

- 0of 0 votes
Design an algorithm to find the shortest substring in a synopsis such that it contains all the words in a provided list.

So, search for the shortest substring that contains ['Hello', 'World'].

- 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
Question regarding largest possible sum of subarray of size K.

- 0of 0 votes
First asked how you can write a tree in a file?

Next question was lets say value of one node is changed, how can you update that in that file without writing the whole tree in file again?d

- 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

- 0of 0 votes
There are around 40 million files in a directory which needs to be transferred to another system via FTP in order of oldest file first. What's the ideal way to iterate over files and store it in a data structure from where it can be transferred?

- 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.

- 0of 0 votes
Given a m x n array filled with 1's & 0's. Find all the rectangles which are filled with all the 1's.

Note : - It is guaranteed that there won't be any overlapping rectangles.

- 1of 1 vote
Find Famous person in the list of persons.

A person is a famous person if he doesn't know anyone in the list and everyone else in the list should know this person.

The function isKnow(i,j) => true/ false is given to us. No need to worry about it.

Goal is to find the famous person in O(n) complexity.

- 0of 0 votes
Given a stream of objects, O1, O2, O1, O3, O4... Provide an algorithm to identify the first unique object at any given point in time.

So for example, in the above, after receiving the first Object, it is unique. After receiving the second, the first is still the first unique object. After receiving the 3rd, the 1st object is no longer unique (you've not seen O1 twice), so O2 is not the first unique object. etc...

- 2of 2 votes
FB on-site two weeks ago last round of coding . (This problem is also in the internal question bank of G.)

There is a robot in a room. The initial location of the robot is unknown. The shape or area of the room is unknown.

You have a remote that could walk the robot into any of the four directions - up, left, down or right.

Here is the move method: boolean move(int direction), direction: 0, 1, 2, 3. If the robot hits the wall, the method returns false.

Otherwise returns true and the robot moves on to the direction given.

Find out the area of the room.

e.g.

X

XXX X

XXXXX 'X' marks the floor plan of the room.

A room like such has an area of 10.

- 0of 0 votes
Last Monday phone interview of G.

Given a vector/list of doubly linked list pointers (a pointer is the directed linkage of two nodes), count how many independent blocks of linked lists there are for the pointers given.

- 0of 0 votes
Find the first non repeating character in a string. For example if the input string "abcdeabc", non repeating character is "e"