Algorithm Interview Questions
- 3of 3 votes
AnswersDesign a hit counter which counts the number of hits received in the past 5 minutes.
- aonecoding January 18, 2018 in United States
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?| Report Duplicate | Flag | PURGE
Dropbox Software Engineer Algorithm - 2of 4 votes
AnswersRound3 Google
- aonecoding January 16, 2018 in United States
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.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
Answers/**
- aonecoding January 13, 2018 in United States
* 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.
**/| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersAmazon
- aonecoding January 06, 2018 in United States
Given an ArrayList of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder.| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 3of 3 votes
AnswersGoogle
- aonecoding January 05, 2018 in United States
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.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswerTwitter
- aonecoding January 04, 2018 in United States
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"| Report Duplicate | Flag | PURGE
Twitter Software Engineer Algorithm - 1of 1 vote
AnswersPrint words in order which are occurring once in huge document. The RAM size 100MB and file size 10 GB.
- Optimist December 16, 2017 in India
Example: I am good. You are good.
Answer : I am You are
Note : It's not datastructure problem where we can simply make use of LinkedHashMap. The file size is going to be huge.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven 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.
- william.watts December 12, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersN 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.
- new December 07, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm Arrays Coding Data Structures - 0of 0 votes
AnswersCreate an algorithm to compare two database.
- Risu Raj December 06, 2017 in United States| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersAlgorithm to compare two database.
- Risu Raj December 06, 2017 in United States| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersPrint 0 1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1
- D PRAVEEN KUMAR December 05, 2017 in India
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| Report Duplicate | Flag | PURGE
Skill Subsist Impulse Ltd Data Scientist Algorithm - 2of 2 votes
AnswersMaximum Sum of Building Speed
- uppubhai December 04, 2017 in India
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| Report Duplicate | Flag | PURGE
Practo SDE1 Algorithm - 0of 0 votes
Answersin 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..
- caa0453 December 03, 2017 in United States
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)| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersLets 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].
- sachin323 December 02, 2017 in United States
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)| Report Duplicate | Flag | PURGE
Dropbox Software Engineer Algorithm - 3of 3 votes
AnswersCongrats on aonecode.com member V.S. on the offer from Microsoft and thanks for sharing with us the experience.
- aonecoding December 02, 2017 in United States
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!| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 0of 0 votes
Answersclass QueryVector
- CoolGuy December 01, 2017 in India
{
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.| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 3of 3 votes
AnswersGiven 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.
- md.lisul.islam November 22, 2017 in United States
[73, 74, 75, 71, 70, 76, 72] -> [1, 1, 3, 2, 1, nothing, nothing]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven an array which is in ascending order till some point and then descending order till end. find peak element
- careercupuser November 22, 2017 in United States| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 0of 0 votes
AnswersGiven a tree find shorted path to a specified element from root. Actual question is different but theory behind it is same.
- careercupuser November 22, 2017 in United States| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 4of 4 votes
AnswersYou have given height array of array. Generate the original array.
- sandeepmnit35 November 20, 2017 in India
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.| Report Duplicate | Flag | PURGE
Goldman Sachs Developer Program Engineer Algorithm - 0of 0 votes
AnswersHow to print nested array ?
- sandeepmnit35 November 20, 2017 in India
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?| Report Duplicate | Flag | PURGE
Goldman Sachs Developer Program Engineer Algorithm - 0of 0 votes
AnswersWrite code to find unmatched parentheses and return it in the below format:
- 1080ti November 18, 2017 in United States
((a) -> -10a1
(a)) -> 0a1-1
(((abc))((d))))) -> 000abc1100d111-1-1| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.
- Vijay November 17, 2017 in India
Example : Array : 2,5,6,7,8,8,9
Target number : 5
Output : 5
Target number : 11
Output : 9
Target Number : 4
Output : 5| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Arrays Coding Data Structures - 5of 5 votes
AnswersSuppose 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.
- Hitesh November 16, 2017 in India
Example:
Input String: 011100010
Pattern 1: 011
Pattern 2: 010
Output:
011 => 1
010 => 1| Report Duplicate | Flag | PURGE
Freight Tiger Software Developer Algorithm - 0of 0 votes
AnswersCount number of ways to paint a fence with N posts using K colors, where no FOUR consecutive fences can have the same color.
- Basmati November 09, 2017 in United States| Report Duplicate | Flag | PURGE
Adobe abc Algorithm - 0of 0 votes
AnswersRobot hand movement
- Shilpi_Roy November 08, 2017 in United States
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| Report Duplicate | Flag | PURGE
Software Developer Algorithm - 1of 1 vote
AnswersGiven two strings containing only numbers, return product of the two strings. Strings are large so conversion to interger is not possible.
- DO November 04, 2017 in United States for High Availability| Report Duplicate | Flag | PURGE
VMWare Inc Staff Engineer Algorithm - 0of 0 votes
AnswersYour 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.
- DO November 04, 2017 in United States for Compute| Report Duplicate | Flag | PURGE
Digital Ocean IC3 Algorithm - 0of 0 votes
AnswersGiven a linked list with next and random pointer, deepcopy the linked list and return new head.
- me.samyakjain November 03, 2017 in United States
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| Report Duplicate | Flag | PURGE
Facebook Android Engineer Algorithm