## Recent Interview Questions

- 0of 0 votes
So recently to someone I know a question was ask how do you rotate a 2 dimensional array? He was asked to white board it. He could get diagram the problem but had trouble coding it.

This is not an easy answer because equal dimensional array are easy but require you know the trip that you divide the x and y dimension and then do four swapping rotation around the corners. Not equal X,Y are much harder. When I heard this question, I could get the equal dimensions done in an hour or two in a compiler. It took me two days to get the total program working. Here is the code:

{

#include <stdio.h>

int main()

{

#define xsize 4

#define ysize 8

int matrix[ysize*xsize] ;

typedef enum rotation

{

CW0,

CW90,

CW180,

CW270,

CCW0,

CCW90,

CCW180,

CCW270,

DONE0

} RotationTypes;

RotationTypes DesiredRotation = CW270;

#define min(a,b) ( (a) < (b) ? a : b)

int x,y,r,swap0, swap1,rotx,roty, rotidx;

//walk through every possibily

for (DesiredRotation = CW0; DesiredRotation <= DONE0 ; DesiredRotation++)

{

for (y=0;y<ysize;y++)

{

for (x=0;x<xsize;x++)

{

matrix[(y*xsize)+x] = y + x*10;

//print the base rotation for references

if ( DesiredRotation == CW0

|| DesiredRotation == CCW0

|| DesiredRotation == DONE0)

printf("%d ", matrix[(y*xsize)+x]);

}

if ( DesiredRotation == CW0

|| DesiredRotation == CCW0

|| DesiredRotation == DONE0)

printf("\n");

}

if ( DesiredRotation == CW0

|| DesiredRotation == CCW0

|| DesiredRotation == DONE0)

printf("\n");

//flips are generally more effeicient than rotation

//bu doing flips you only have to do one 90 degree

// type of rotation. flips work on uneven dimeions

if (DesiredRotation != CCW90 && DesiredRotation != CW270)

{

//horiztonal flip

for (y=0;y<ysize;y++)

{

for (x=0; x<xsize/2;x++)

{

swap0 = matrix[(y*xsize)+x];

matrix[(y*xsize)+x] = matrix[(y*xsize)+((xsize-1)-x)] ;

matrix[(y*xsize)+((xsize-1)-x)] = swap0;

}

}

//vertical flip

for (y=0;y<ysize/2;y++)

{

for (x=0; x<xsize;x++)

{

swap0 = matrix[(y*xsize)+x];

matrix[(y*xsize)+x] = matrix[(((ysize-1)-y)*xsize)+x] ;

matrix[(((ysize-1)-y)*xsize)+x] = swap0;

}

}

}

if (DesiredRotation != CW0

&& DesiredRotation != CW180

&& DesiredRotation != CCW0

&& DesiredRotation != CCW180

&& DesiredRotation != DONE0)

{

//do one CCW90 rotation which is the same as CW270

//if would be more effiecient to hard code every

//different combination but no way to make it elegant

int sqsize=min(ysize,xsize);

//first do the inplace square part because it is very efficient

for (y=0;y<sqsize/2;y++)

{

for (x=0;x<(sqsize+1)/2;x++)

{

rotx = x;

roty = y;

//store the top, left

int swap0 = matrix[(y*xsize)+x];

//rotate into top left from top right

matrix[(y*xsize)+x] = matrix[(x*xsize)+((sqsize-1)-y)];

//rotate into top right from bottom right

matrix[(x*xsize)+((sqsize-1)-y)] = matrix[(((sqsize-1)-y)*xsize)+((sqsize-1)-x)];

//rotate into bottom right from bottom left

matrix[(((sqsize-1)-y)*xsize)+((sqsize-1)-x)] = matrix[(((sqsize-1)-x)*xsize)+y];

//into into bottom left from original top left

matrix[(((sqsize-1)-x)*xsize)+y] = swap0;

}

}

//now the challenge is what to do with unequal array left overs

//we chose to hardcode inserting rotation and swapping until done

//we have to do two different sets of code if height is

//greater than width

if (ysize>xsize)

{

int rotinc=0;

int baseptr = sqsize*sqsize;

int rowsize = xsize;

for (x=xsize-1;x>=0;x--)

{

for (y=sqsize;y<ysize;y++)

{

//find where the extra non square starts after

//the sqaure part of the arrary

int rotptr = baseptr+((y-sqsize)*rowsize)+x;

//store it for later insertion

swap0 = matrix[rotptr];

//find where in the new dimensions

//the rotation from the end of the square should

//go

int swapptr = (((xsize-1)-x)*ysize)+y;

//swap upswards to make room for the

//insertion

while (rotptr>swapptr)

{

matrix[rotptr] = matrix[rotptr-1];

rotptr--;

}

//insert the rotation at the proper place

//which is now free

matrix[swapptr] = swap0;

}

//we have done one row so increase where the

//base pointer will be for the next time

baseptr+=ysize-sqsize;

//because we did one rotation the remaining rows

//are one rotation smaller

rowsize--;

}

}

//width is bigger than height

if (xsize>ysize)

{

int rotinc=0;

int rowsize = xsize;

for (x=sqsize;x<xsize;x++)

{

//insert happen at the begging of the array for

//this sizing

int swapptr = 0;

for (y=0;y<ysize;y++)

{

//find the rotation at the end of each row

int rotptr = rotinc+(y*rowsize)+sqsize;

//store it for latter use

swap0 = matrix[rotptr];

//swap upwards to made room for the insertion

while (rotptr>swapptr)

{

matrix[rotptr] = matrix[rotptr-1];

rotptr--;

}

//issert the rotation at the begining of the

//array

matrix[swapptr] = swap0;

//increasement the point

swapptr++;

}

//we have done one row so need to increase

//our start posiiton

rotinc+=ysize;

//we have done one row. the remain is one row smaller

rowsize--;

}

}

//print out the rotated and maybe flipped new array

for (x=0;x<xsize;x++)

{

for (y=0;y<ysize;y++)

{

printf("%d ", matrix[(x*ysize)+y]);

}

printf("\n");

}

} else {

//printout the vertical flipped only array

if (DesiredRotation != CW0

&& DesiredRotation != CCW0

&& DesiredRotation != DONE0)

{

for (y=0;y<ysize;y++)

{

for (x=0;x<xsize;x++)

{

printf("%d ", matrix[(y*xsize)+x]);

}

printf("\n");

}

}

}

printf("\n");

}

return 0;

}

}

- 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
You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start at root, but need to end at a leaf, and it must go downwards (traveling only from parent nodes to child nodes).

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

public int pathSum(TreeNode root, int sum) {

}

}

- 0of 0 votes
Give a bunch of rectangles, randomly return a point within the rectangle, the probability to be proportional to the size of the rectangle.

Follow up1: If you want to repeatedly call the function to generate random points how to do.

Follow up2: If the rectangles overlap how to do?

- 0of 0 votes
A smart-set is a set of distinct numbers in which all the elements have the same number of 1s in their binary form. The set of all smallest elements from each smart-set

that can be formed from a given array of distinct positive numbers is known as the smartest-set.

So given an array of distinct numbers, outline the elements of the smartest-set in ascending sorted order.

Input Format

The first line of input consists of an integer t. This is the number of test cases. For each test case,

the first line of input contains an integer n. Here n is the number of elements in the array. The next line contains n space separated distinct integers which are the elements

of the array.

Output Format

The output will space separated integer elements of the smartest-set in ascending order.

Constraints

0 < t < 1000 (This is the number of test cases

2 < n < 10000 (This is the number of integer elements of the array)

1 < Xi < 100000 (This is the size of each element of the array)

Python coding

- 0of 0 votes
As clients search for the compressed posting of companions movement. Who is very certain a genuine proprietor is sign through the record as the trickster after hacking one's record peep to the next record and recover access to that one too. There are sure things that should be seen through various verticals and same applies for this situation too. Facebook support number is the best way get this doubt solved.

- 0of 0 votes
We have 4 swimmers A,B,C,D with their records in 4 types of swimming races i.e Freestyle, Frontstroke , Backstroke and Butterffly respectively.The data is given as 4 arrays each for one player where each element in the array represents their time in particular race.

We have to select these players for a relay race such that the total time is minimum.

- 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 0 votes
Magical binary strings are non-empty binary strings if the following two conditions are true:

The number of 0's is equal to the number of 1's.

For every prefix of the binary string, the number of 1's should not be less than the number of 0's.

A magical string can contain multiple magical substrings. If two consecutive substrings are magical, then we can swap the substrings as long as the resulting string is still a magical string. Given a magical binary string, str, perform zero or more swap operations on its consecutive magical substrings such that the resulting string is aslexicographically large as possible. Two substrings are considered to be consecutive if the last character of the first substring occurs exactly one index before the first character of the second substring.

-----

Input Format

a single binary string, str.

Constraints

It is guaranteed that str is a binary string of 1's and 0's only.

1 ≤ length(str) ≤ 50

It is guaranteed that str is a magical string.

Output Format

Find a string denoting the lexicographically largest magical string that can be formed from str.

Sample Input 0

11011000

Sample output

11100100

Explanation of sample

Given the magical string str = 11011000, we can choose two consecutive magical substrings, 1100 and 10, to swap such that the resultant string, str' = 11100100, is the lexicographically largest possible magical string possible. Thus, we return the value of str', which is 11100100, as our answer.

- 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
Question: Given a sorted integer array, return sum of array so that each element is unique by adding some numbers to duplicate elements so that sum of unique elements is minimum.

I.e., if all elements in the array are unique, return the sum. If some elements are duplicates, then increment them to make sure all elements are unique so that the sum of these unique elements is minimum.

Some examples:

input1[] = { 2, 3, 4, 5 } => return 19 = 2+3+4+5 (all elements are unique, so just add them up)

input2[] = { 1, 2, 2 } => return 6 = 1+2+3 (index 2 is duplicate, so increment it)

input3[] = { 2, 2, 4, 5 } => return 14 = 2+3+4+5 (index 1 is duplicate, so increment it)

- 0of 0 votes
Mr. Octopus has recently shut down hisfactory and want to sell off his metal rods to a local businessman.

In order to maximize profit, he should sellthe metal of same size and shape. If he sells metal rods of length ,he receives N x L xmetal_price. The remaining smallermetal rods will be thrown away. To cut the metal rods, he needs to pay cost_per_cut for every cut.

What is the maximum amount of money Mr.Octopus can make?

Input Format

First line of input contains cost_per_cut

Second line of input contains metal_price

Third line contains L, the number of rods Mr. Octopus has,followed by L integers in each line representinglength of each rod.

Output Format

Print the result corresponding to the testcase.

Constraints

1 <= metal_price, cost_per_cut <= 1000

1 <= L <= 50

Each element of lenghts will lie in range [1, 10000].

Sample Input#00

1

10

3

26

103

59

Sample Output#00

1770

Explanation Here cuts are pretty cheap. So we can make largenumber of cuts to reduce the amount of wood wasted. Most optimal lengths ofrods will be . So we will cut pieces of length from rod,and throw peice of length from it. Similarly we will cut piecesof length from rod and throw away a piece of length .From rod, we will cut pieces of length andthrow a piece of length . So in total we have pieces of length andwe have made cuts also. So total profit is

Sample Input#01

100

10

3

26

103

59

Sample Output#01

1230

- 2of 2 votes
given two strings a and b.

print out the minimum number of flips of the characters in a such

that a is an anagram of b.

- 0of 0 votes
JSON parsing is an essential toolkit in modern web development. Whether you are on the client side or server side, these methods need to be fast, efficient and dependable. But what if one day...

Suddenly, all of the JSON parser libraries went missing.

You have been called upon to save us all from impending doom.

Please re-implement the standard json parsing methods in your favorite language and restore the world to it's natural order.

Subproblem #1

Write a function, dictionaryToJson to convert a dictionary into a string.

For example, assuming you have dictionary like: dict(“a”: “apple”, “b”: dict(“b”: “blueberry”, “c”: “cranberry”)), the key field is always a string type, the value field could be a string type or a nested dictionary type. And the output would be "{a:apple,b:{b:blueberry,c:cranberry}}"

Subproblem #2

Write a reverse function, jsonToDictionary to convert a string into a dictionary.

Convert a string into the dictionary. e.g., given the input of “{a:apple,b:{b:blueberry,c:cranberry}}”, output dict(“a”: “apple”, “b”: dict(“b”: “blueberry”, “c”: “cranberry”)).

The names and values only contains letters. You can assume that there is no error in the input. You should not use regular expressions.

- 0of 0 votes
To a binary array, if you want to move 1 to the array side, 0 to the other side, Can only swap two adjacent elements each time, ask the least number of swap Why? For example, the number of min swaps for [0, 1, 1, 0, 0] is 2 (01100 -> 10100 -> 11000)

- 0of 0 votes
balanceSum, return to the array to meet the minimum sum equal to the minimum index. Title conditions are all positive numbers, the array length> = 3, there must be solution. If a = [1,2,1,3] returns 3 because a [1] + a [2] = a [4]

- 0of 0 votes
Give a string that outputs the largest alphabetical order of all consecutive substrings For example, "ab", substring has {"a", "ab", "b"}, output "b"

- 0of 0 votes
stream reading number, with timestamp, Design data structure to know the minimum value of the past year, the average,

- 0of 0 votes
sorting nested dictionaries

give a

{b: {cb: cranberry, bb: blueberry} a: apple, c: cherry}

{a: apple, b: {bb: blueberry, cb: cranberry}, c: cherry}

To sort the key output, if there is nested dictionaries, but also to sort

- 0of 0 votes
If xi<xj,yi<yj, we say (xj,yj)dominates(xi,yi). Given a set of number pairs (xi,yi),

how many indomitable pairs are there?

- 0of 0 votes
Mark likes to listen to music while travelling. His iPod™ contains

N songs and he wants to listen to L (not necessarily different) songs during

a trip. So he creates a playlist such that:

• Every song is played at least once.

• A song can be played again only if at least K other songs have been played

Mark wants to know how many different playlists are possible. Can you help Mark determine this number?

As the number can be very large,

display number modulo 1,000,000,007.

You are given N, K and L.

- 0of 0 votes
Given a List determine if contiguous elements of the List sum to an input number. For example: Array/List [6 5 3 2 1 7], and input number 8. The numbers 5 + 3 = 8. Or suppose an input number 10, the elements of the list 2 + 1 + 7 = 10.

- 0of 0 votes
Given number of pipes 1..n, Find two largest pipes of maximum length possible.

Ex: input - 1,2,3,4,6

Output - The maximum length possible is 8.

Pipe1 - 2,6

Pipe2 - 1,3,4

- 0of 0 votes
How to create account with Sbcglobal, i am currently in United Kingdom, then how to create email account.

- 0of 0 votes
Given the width, height, start point, end point of the grid, and a list of points, you have to go through these points, ask how many paths are there from the start point to the end point, you can only move from (i, j) down and right.

- -1of 1 vote
The design of two functions, cyclecount (num, mod), cycleHistogram (low, high, mod). Probably, cyclecount (num, mod) do digits square sum mod operation. For example mod (12), mod (5) -> square (1) + square (2) mod 5 = 0 -> square (0) mod 5 = 0. Stop return 2. Finished digits square sum after take mod, mod and before the formation of a repetitive cycle. Return form the size before the cycle. CycleHistogram (low, high, mod) will give a [low, high]. Then return a histogram which stores the number of [low, high] inside the cycle size 1,2,3,4,5.

- 0of 0 votes
I was given this question recently in an interview.. There are three threads and a counter that will increase from 1 to 100. Catch is that thread 1 increments counter from 1 to 20. Thread 2 increments from 21 to 80. Thread 3 increments from 81 to 100.

- 0of 0 votes
Bob And GCD

Bob has an array A of size N. He doesn't like arrays in which the GCD of all elements is not K. He can perform multiple operations on an array. In each operation, he can either increase or decrease the value of an element by 1.

You have to tell the minimum operation Bob will take to make GCD of all elements in an array equal to KK ?

GCD here is Greatest Common Divisor.

Input Format

The first line contains T, the number of test cases.

For Each Testcase :

The first line contains 2 integers - K and N respectively, separated by a space.

The second line contains N integers, separated by a space, in order of their position in array.

Input Constraints

1≤T≤10

1≤N≤10^6

1≤A[i]≤10^6

1≤K≤10^6

Output Format

For each test case, print minimum number of operations Bob take in a new line.

Sample Input

1

5 3

4 5 6

Ans - 2