## Algorithm Interview Questions

- 0of 0 votes
N different couple go to cinema with 2N different seats. They take their place randomly. You could make swap operations. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.

- 0of 0 votes
Create an algorithm to compare two database.

- 0of 0 votes
Algorithm to compare two database.

- 0of 0 votes
Print 0 1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1

Follow the below rules

Intialiazation should not be done by 0 i.e. I= 0 should not be done

Only one time a loop or tertiary conditions or increment or decrement should be done

No nested loops or nested conditions only 1 loop or 1 condition should be used

Ex if() or for {}

One loop and 1 condition can't be use.. u can use either this or that

- 0of 0 votes
Maximum Sum of Building Speed

You are the king of Pensville where you have 2N workers.

All workers will be grouped in association of size 2,so a total of N associations have to be formed.

The building speed of the ith worker is Ai.

To make an association, you pick up 2N workers. Let the minimum building speed between both workers be x, then the association has the resultant building speed x.

You have to print the maximum value possible of the sum of building speeds of N associations if you make the associations optimally.

Constraints

1≤N≤5∗10 ^4

1≤Ai≤10^4

Input

First line contains an integer N, representing the number of associations to be made.

Next line contains 2N space separated integers, denoting the building speeds of 2N workers.

Output

Print the maximum value possible of the sum of building speeds of all the associations.

Sample Input

2

1 3 1 2

Sample Output

3

- 0of 0 votes
in a NxN matrix, a robot is moving in a direction. there are some blocks where it can change its direction(left/right/uturn/up/down). find an optimal path to go between 2 points..

travel rule :

1) robot must move in right direction from the starting point...

2) robot move in a clock wise direction

3) some square road block is there, where robot can not pass( can be 1x1 or 3x3 .. size is odd no square) but can go adjacent to wall in clockwise direction.

4) 1 cell = 1 step

plz help me with the algo.. or pesudo code.. how to determine the moving direction ( right or moving clockwise)

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

- 0of 0 votes
class QueryVector

{

QueryVector(vector values)

{

// Implement

}

vector GetIndices(list filters)

{

// Implement

}

}

Say for example vector is like

{“an”, “apple”, “day”, “keeps”, “doctor”, “away”, “apple”, “iphones”, “cool”, “doctor”, “recommends”}.

GetIndices(“apple”) should return (1, 6)

GetIndices(“doctor”,”cool”) should return (4,8,9)

GetIndices(“random”) should return empty vector ()

GetIndices(“random”,”keeps”,”day”,”doctor”) should return empty vector (2,3,4,9)

Important:

1. There can be millions of values in the input vector of string

2. GetIndices can be called repeatedly and it should be optimized

3. How storage optimization is considered and bitmaps etc are used.

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

- 0of 0 votes
Given an array which is in ascending order till some point and then descending order till end. find peak element

- 0of 0 votes
Given a tree find shorted path to a specified element from root. Actual question is different but theory behind it is same.

- 1of 1 vote
You have given height array of array. Generate the original array.

Input: [6,3,0,2,2,0,0]

Output : [ 1,5,7,3,2,6,4]

A[i] value in input array is the number of greater element on right side.

- 0of 0 votes
How to print nested array ?

Input : [1, 5, 8, [9, 10, 24, 20, [39, 48], 89], 105, 99]

Output : 1, 5, 8, 9, 10, 24, 20, 39, 48, 89, 105, 99.

Which data structure you will use to store the values?

- 0of 0 votes
Write code to find unmatched parentheses and return it in the below format:

((a) -> -10a1

(a)) -> 0a1-1

(((abc))((d))))) -> 000abc1100d111-1-1

- 1of 1 vote
Given an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.

Example : Array : 2,5,6,7,8,8,9

Target number : 5

Output : 5

Target number : 11

Output : 9

Target Number : 4

Output : 5

- 0of 0 votes
Suppose you have an input character stream (StreamReader) and you have a list of pattens like ABCAS, ASGKT. KHTSD etc. You need to read the stream one by one character and you need to keep count on number of each pattern found so far and when EOF occures just print all the patterns along with count.

Example:

Input String: 011100010

Pattern 1: 011

Pattern 2: 010

Output:

011 => 1

010 => 1

- 0of 0 votes
Count number of ways to paint a fence with N posts using K colors, where no FOUR consecutive fences can have the same color.

- 0of 0 votes
Robot hand movement

Given a (1) string message (consisting of only upper case alphabets), and (2) width of keyboard, output the movements required by an automated robot hand to print out the string message.

The robot hand can move right, left, up or down. It cannot move diagonally.

Ex 1:

String message: “HI”

Width: 26

Output: R8, T, R1, T

Ex2:

String message: “HELLO”

Width: 13

Output: R8, T, L3, T, R7, T, T, D1, L10, T

- 0of 0 votes
Given two strings containing only numbers, return product of the two strings. Strings are large so conversion to interger is not possible.

- 0of 0 votes
Your code is inside a service that receives a large stream of integers, large enough that it can't be stored on any disk. You don't know the how many integers will be there on the stream. You have to write a sampler which selects K integers such that likelihood of selecting any integer from the stream is equal.

- 0of 0 votes
Given a linked list with next and random pointer, deepcopy the linked list and return new head.

Node {

char val,

Node next,

Node random }

A {

val: ’a’

next: D

random: G}

D {

val: ’d’

next: G

random: A}

G {

val: ’g’

next: null

random: D}

-----------

| |

| V

A -> D -> G -> null

-------------

| |

| V

A' -> D' -> G' -> null

- 1of 3 votes
Congrats to aonecode's member F.L.

Got offers from - Youtube(G), LinkedIn, Airbnb, Square, Wish, Blend and NextDoor!

Thanks for sharing the interview experience with us.

Youtube Interview

- Phone: Find anagrams of string A from string B (sliding window)

- Phone: Find if two frames in a screen are equal. Frames may overlap. (equal method)

Onsite:

- LC41 first missing positive

- LC499+LC505 The maze

- LC161 one edit distance

- Similar to hangman but make guesses based on a dictionary.

Assume a dictionary has words - {house, morse, jesus} and ‘morse’ is the answer. If your first guess is ‘house’, output will be ‘_o_se’, which indicates 3 letters are correct. (Here the arrangement of letters does not matter. Your guess can be ‘co’ and if answer is ‘ok’ then the output is gonna be ‘_o’ which indicates letter ‘o’ in answer. )

Try to get the answer with minimum guesses.

(Interviewer expects pre-processing the dictionary. Key: letter; Value: frequency. Begin with combinations of most frequent letters first)

- 1of 3 votes
Congrats to F.L.

Got offers from - Youtube(G), LinkedIn, Airbnb, Square, Wish, Blend and NextDoor!

Thanks for sharing the interview experience with us.

LinkedIn

Phone:

- Questions from LC tagged LinkedIn.

Onsite:

- Get sqrt(x). Output a floored integer if result is not a perfect square. sqrt(18) = 4

- Implement BST, insert, delete, search.

- Design a dashboard for service logs stats (sort and aggregate). Scale from 1 to more machines. Discuss async and realtime as different scenarios.

- 2of 2 votes
Facebook

-Phone: LC304 & longest arithmetic sequence. Return the sequence.

- 3of 3 votes
Wish Interview

-Phone: Two sum, Three sum, N sum(recursion)

Onsite:

-Implement merge sort (recursion&iteration)

-Merge two sorted arrays: one of length m+n, the other n; store the result in the longer array

-Given a number print diamond:

Given 1

Pirnt 1

Given 3

Print

1

121

1

Given 5

Print

1

121

12321

121

1

- Rank N people in a game. There may be a tie among participants. How many possible ways of ranking there is.

- Design: Define a bot as an IP that hits the web app over M times in the past T seconds (not necessarily hits on the same page. Also take into account different API calls.) How to design a bot detector layer and where to place it in the system.

- -1of 1 vote
What is the Big O of that algorithm? What happens at runtime?

- 1of 1 vote
What's the algorithm to transform the sentence "the brown fox ran fast" in "eht nworb xof nar tsaf" (reverse any word)

- 0of 0 votes
Today Jin has given a task to Shino, Shino has to travel from cell

(

1

,

1

)

(1,1) to cell

(

N

,

M

)

(N,M) in a grid of size

N

∗

M

N∗M. But in order make this task interesting for Shino, Jin has decided to keep some special candies in some

K

K special cells of the grid, where each candy has an amount of happiness associated with it.

Shino can travel only in right & down direction in the grid, as he is too careful & does not want to fall out of grid. Now, we call the value of a path the happiness of all cells lying on the path. All non-special cells have happiness equal to

0

0.

Now, you need to find and print the sum of the values of all paths from

(

1

,

1

)

(1,1) to

(

N

,

M

)

(N,M), traveling only right and down to an adjacent cell.

As Shino is not good at counting help him find the answer.

Input Format

The first Line contains a single integer

T

T denoting number of test cases

The next line contains

3

3 space separated integers,

N

N,

M

M and

K

K where N * M is the size of grid & K denoting number of special cells

The next

K

K lines contains three integers

X

i

,

Y

i

,

H

i

Xi,Yi,Hi where

(

X

i

,

Y

i

)

(Xi,Yi) is cell coordinate &

H

i

Hi is the amount of happiness Shino will get from a candy at cell

(

X

i

,

Y

i

)

(Xi,Yi)

Constraints

1

≤

T

≤

3

1≤T≤3

1

≤

N

,

M

,

K

≤

10

5

1≤N,M,K≤105

1

≤

X

i

≤

N

,

1

≤

Y

i

≤

M

1≤Xi≤N,1≤Yi≤M

1

≤

H

i

≤

10

5

1≤Hi≤105

Output Format

For each test case you will output a single integer denoting the total amount of happiness Shino will get. As the answer can be quiet large you can output answer modulo

10

9

+

7

109+7

Sample Input

1

2 2 2

1 2 4

2 1 7

Sample Output

11

- 1of 1 vote
You are a game developer working on a game that randomly generates levels. A level is an undirected graph of rooms, each connected by doors. The player starts in one room, and there is a treasure in another room. Some doors are locked, and each lock is opened by a unique key. A room may contain one of those unique keys, or the treasure, or nothing.

Implement a representation for a level and write code that, given a level and starting room, returns true if the treasure can be reached by the player—likely requiring them to find certain other keys first—or false if there is no solution.