Algorithm Interview Questions
- 0of 0 votes
AnswersFor a given set of non-negative integers get the number of subsets that add up to a target value k.
- vmayer99 April 30, 2018 in United States| Report Duplicate | Flag | PURGE
Linkedin Software Engineer Algorithm - 0of 0 votes
AnswersWrite a function to compute n^k. (don't forget negative exponents)
- vmayer99 April 30, 2018 in United States| Report Duplicate | Flag | PURGE
Linkedin Software Engineer Algorithm - 0of 0 votes
AnswersImagine a horizontal corridor bounded by y = y1 and y = y2 lines on a 2D-plane. There are N sensors with centers (x, y) each of which operates in a range (r) on the plane . So, they cover some circular areas on the plane. See the figure below.
o | _____o___o__|____________ y = y1 o |OOO __________oo|_____O______ y = y2 O | O _ _ _ _ _ _ | _ _ _ _ _ _ | o O | o O O | | O | |
The question is whether a path exist from x=-inf to x=+inf via corridor without being detected any radar.
Constraints:
1. You are free to move any direction only if you stay in the corridor.
2. You are free to go through corridor borders.
3. N sensors are given as list of (x, y, r) like [(1, 3, 2), (-1, -3, 4)]. x and y are signed integers. r is a unsigned integer.
4. y1 and y2 are integers.
My solution:
1. Create an intersection graph of N sensors by comparing them each other via Euclidean distance(x1 - x2)^2 + (y1 - y2)^2 <= (r1 + r2)^2
2. If there is a path between y=y1 and y=y2 through intersected sensors, there do not exist any path from x=-inf to x=+inf. Otherwise, there do exist a path. So, I used BFS to search such a path.
Worst Case Complexity:
1. O(n^2)
2. O(V + E) = O(n + intersection_count)Total: O(n^2)
My Best Case Optimization for Intersection Graph:
- engineer06 April 29, 2018 in United States
1. For each sensor, create two events for start and end of circles vertically. y = (y1 - r) and y = (y1 + r)
2. For each sensor, register those two events into an array.
3. Use a line sweep algorithm over 2, which is O(nlogn + intersection_count) and intersection_count may be n^2 at worst case.
I wonder if I should have had a better solution with the worst case < O(n^2).| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersYou are given the length and time of occurrence of packet and Queues which process packets. Total processing time for a packet is equal to the length of packet plus the waiting time in queue. For eg lets say we have only one queue for now, and A packet of length 5 comes at t = 1, and another packet of length 4 comes at t = 3. Total processing time for first packet is 5( no waiting time as queue is empty at t = 1) and at t = 3, 2 units of first packet is processed and 3 units remaining so, for second packet 3 units will be waiting time in queue plus 4 units for its length. Total processing time for 2nd packet is 7 units. If there are multiple queues you can add new packet in any of the other queues. Given the time and length of all incoming packets, we need to find the minimum no. of queues required such that total processing time of each packet is less than 10 units. Maximum possible no. of queues are 5. If you require more than 5 queues print -1.
Test Cases Format: First Line contains the number N, the total no. of packets and N following line contains two numbers ti, li where li is length of packet coming at time = ti units.
Test case1:
2
2 7
5 8
Test Case 2:
3
1 3
2 3
3 5
Test Case 3:
3
1 5
2 4
3 8
Output:
Case1: 2
Case2: 1
Case3: 2
Consider the following time table of incoming packets:time packets-length 1 8 2 5 3 2 4 6
If you put the packet in queue with minimum time then this will lead to 3 queues:
- ak4017 April 25, 2018 in United States
t = 1:
q1: 8
t = 2:
q1: 7
q2: 5
t = 3:
q1: 6
q2: 4, 2
t = 4:
q1: 5
q2: 3, 2
q3: 6
But its output should be 2 queues:
1) 8 in queue 1
2) 5 in queue 2
3) 2 in queue 1
4) 6 in queue 2| Report Duplicate | Flag | PURGE
Samsung Software Developer Algorithm - 6of 6 votes
AnswersFB On-site March
- aonecoding April 21, 2018 in United States
Q: Find number of Islands.
XXXOO
OOOXX
XXOOX
Return 3 islands.
1 1 1OO
OOO2 2
3 3OO 2
Followup: If the board is too big to fit in memory, how to get the number?| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswerGiven list of schedules for different flights in a month, determine maximum number of flights that can be in the air anytime in that month.
- sanjureddy.v April 14, 2018 in United States
Input : list of schedules for flights.- spread over a month.
output: a number - maximum flights that can be in the air
Assumptions: 1. All the given times are in a specific timezone( like GMT).
2. Given Schedules can be any time in the month| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 0of 0 votes
AnswerGiven a list of N threads detect a deadlock in the system.
- jddjjd007 April 12, 2018 in United States| Report Duplicate | Flag | PURGE
Google Algorithm - -1of 1 vote
AnswersA sample state of ‘a’:
- prasad.hybris April 03, 2018 in United States
[[2, NULL, 2, NULL],
[2, NULL, 2, NULL],
[NULL, NULL, NULL, NULL],
[NULL, NULL, NULL, NULL]]
FUNCTION foo()
FOR y = 0 to 3
FOR x = 0 to 3
IF a[x+1][y] != NULL
IF a[x+1][y] = a[x][y]:
a[x][y] := a[x][y]*2
a[x+1][y] := NULL
END IF
IF a[x][y] = NULL
a[x][y] := a[x+1][y]
a[x+1][y] := NULL
END IF
END IF
END FOR
END FOR
END FUNCTION| Report Duplicate | Flag | PURGE
Google Cloud Support Associate Algorithm - 0of 0 votes
AnswersYou have a 2 Dimensional Array.
- Rahul Vats March 30, 2018 in United States
1 2 3
4 5 6
7 8 9
Write code to generate all the 7 character strings without any duplicates starting from 4. You can move one block at a time and you can move either horizontally and diagonally. So for example, valid moves from 4 are 4 -> 1 and 4 -> 7. You can visit any node any number of times. so 4141414 is a valid string.| Report Duplicate | Flag | PURGE
Algorithm - 1of 1 vote
AnswersGiven a string as input, return the list of all the patterns possible:
'1' : ['A', 'B', 'C'], '2' : ['D', 'E'], '12' : ['X'] '3' : ['P', 'Q']
Example if input is '123', then output should be [ADP, ADQ, AEP, AEQ, BDP, BDQ, BEP, BEQ, CDP, CDQ, CEP, CEQ, XP, XQ]
- ngupta32@hawk.iit.edu March 30, 2018 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm Coding Data Structures - 0of 0 votes
AnswersLanguage : Java
- sarunreddy82 March 28, 2018 in United States
Given a binary tree, print boundary nodes of the binary tree counter-clockwise starting from the root.
For example, boundary traversal of the following tree is “20 8 4 10 14 25 22”
20
8 22
4 12 25
10 14| Report Duplicate | Flag | PURGE
xyz Algorithm - -2of 2 votes
AnswersQuestion 2: Given a number 'k', return the corresponding row, given the pattern:
- mche1987 March 27, 2018 in United States
k => output
0 => []
1 => ["0", "1", "8"]
2 => ["00", "11", "69", "96", "88"]
3 => ["000", "111", "101", "888", ...] // and so on ...| Report Duplicate | Flag | PURGE
Facebook SDE1 Algorithm - 0of 0 votes
AnswersQuestion 1: Given an input of an array of string, verify if, turned 180 degrees, it is the "same".
- mche1987 March 27, 2018 in United States
For instance:
[1, 6, 0, 9, 1] => return true
[1, 7, 1] => return false| Report Duplicate | Flag | PURGE
Facebook SDE1 Algorithm - 2of 2 votes
AnswersDropbox
- aonecoding March 21, 2018 in United States
Grid Illumination: Given an NxN grid with an array of lamp coordinates.
Each lamp provides illumination to every square on their x axis,
every square on their y axis, and every square that lies in their diagonal
(think of a Queen in chess).
Given an array of query coordinates,
determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on,…| Report Duplicate | Flag | PURGE
Dropbox Software Engineer Algorithm - 2of 2 votes
AnswersMarch 2018 Phone Interview FB
- aonecoding March 17, 2018 in United States
Calculate a moving average that considers the last N values.
Circular Queue (Interviewer didn't agree with the linked list queue that I suggested at first. Said the pointers took space)| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswerGiven two positive integers represented as linked lists, provide the sum of the numbers as a linked list.
- anonymous March 14, 2018 in United States1->2->3 4->5->6 ----------- 5->7->9 1->2->3 4->5 ----------- 1->6->8 4->5->6 7->8->9 ----------- 1->2->4->5
| Report Duplicate | Flag | PURGE
Bloomberg LP Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersA bus has to travel from A to B and the distance is d miles. There are many gas stations between A and B.
- Shilpi_Roy March 12, 2018 in United States
The bus has initially g gallon of gas in tank. 1 gallon of gas travels 1 mile.
Gas stations have inforamtion of remaining distance from station to destination b and max gas that can be filled from the station.
Find the minimum number of stops for bus without running out of gas ever.
eg: gas = 10 , distance = 20
gasStation[] = {{16,3}, {10, 7}, {14, 11},{11, 5}, {7, 6}}
o/p = 1
If bus stops at the stop{14,11} that is 14 miles away from destination and fills 11 gallon then it can reach destination with 1 gallon spare.
It can also stop as {16,3} and {10,7} but its 2 stops and at destination it runs out of gas.
Similarly {11, 5}, {7, 6} has 2 stops but has 1 gallon spare at destination.| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 4of 4 votes
AnswersFeb On-site Google
- aonecoding March 10, 2018 in United States
DP Problem. Given the length and width of a matrix, get the number of paths from bottom-left to bottom right.
You may only walk into those 3 directions ➡ (right) ↗ (upper-right) ↘ (lower-right) at each point.
Follow-up: optimize 2d DP to 1d DP of linear extra space.
Follow-up: what if some cells are blocked
System Design
Availability test/debug on distributed system. Discussed and drafted about failover, replication, NoSQL etc.
Interviewer seemed to be expecting more but time ran out.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a biased coin whose probability for Heads is 0.67 and Tails is 0.33, write an algorithm which will print the Heads and Tails with this probability.
- akisonlyforu March 08, 2018 in United States| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersAisles contain products. Product is only going to be in one Aisle.
- plasmalightwave March 04, 2018 in United States
Product{
AisleID: string
ProductID: string
Price: float
}
Given Array<Product>, find the N highest price combinations. Combination is 1 product from each aisle. You can choose only one instance of each product.
So if you had two aisles
1: {$5,$4,$2}
and
2: {$6,$1)
And they asked for the 2 highest combos you would give $6,$5 and $6,$4| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersA and B are playing a perfect 8-9 game. The rules are pretty simple. At each point, you can either insert an 8 at the end of the previous number or a 9. one 8 and one 9 forms a pair. a 9 can only be inserted if there is an 8 which does not form a pair. Perfect solution is the one which has all its numbers in pair. Find out all the possible perfect outcomes of the game in lexicographic order.
- valencia.lucky February 26, 2018 in India
Input-
Input 1: Max length of number
Output-
Your array must return an array of string s containing all possible outcomes.
Example 1:
Input: 4
Output: {"8899", "8989"}
Explanation: There can be only 2 possible outcomes out of 4 as nine must follow eight.
Example 2:
Input: 6
Output:{"888999","889899","889989","898899","898989"}
Explanation: The possible outcomes are 5.| Report Duplicate | Flag | PURGE
Wipro Technologies Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersAssume there is no software like google maps. you are given a map of world. Suppose you are somewhere in the hyderabad.
- syam February 17, 2018 in India
You will have to figure out all the paths from your location to Hyderabad airport.
I have given DFS approach. But the problem is that by doing DFS, a path can cross boundaries of Hyderabad and go so long away from Hyderabad
airport. DFS will take some much time. How to solve this problem?| Report Duplicate | Flag | PURGE
Accolite software Software Analyst Algorithm - 3of 3 votes
AnswersConvert a string with digits into a literal representation of the number like: 1001 to one thousand one
- aonecoding February 15, 2018 in United States| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 0of 0 votes
Answers
- getPDat February 14, 2018 in United StatesWe encode a string, s, by performing the following sequence of actions: Replace each character with its ASCII value representation. Reverse the string. For example, the table below shows the conversion from the string "Go VMWare" to the ASCII string "711113286778797114101": // Character G o V M W a r e // ASCII Value 71 111 32 86 77 87 97 114 101 // // We then reverse the ASCII string to get the encoded string 101411797877682311117. // // For reference, the characters in s are ASCII characters within the range 10 - 126 which include special characters. // // Complete the decode function in the editor below. It has one parameter: // encoded - A reversed ASCII string denoting an encoded string s. // // The function must decode the encoded string and return the list of ways in which s can be decoded. static Collection<String> decode(String encoded) { }
| Report Duplicate | Flag | PURGE
VMWare Inc Staff Engineer Algorithm - 2of 2 votes
AnswersGiven the list of the numbers. In this list, there are the numbers from the Fibonacci sequence.
- denis.zayats February 13, 2018 in Switzerland
Write the algorithm that retrieves all the numbers which belong to the Fibonacci sequence of numbers.| Report Duplicate | Flag | PURGE
MobiCastle Software Engineer Algorithm - 1of 1 vote
AnswersWrite a function that takes two numbers as strings and returns the result as a string:
- NA February 12, 2018 in UK
mul(l string, r string) : string
Assume the numbers might be too large to be parsed into a variable of any numeric type the language has.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersMinimum Continuous Subsequence: targetList & availabletTagsList are two lists of string.
- pragramticProgrammer January 31, 2018 in United States
Input:
targetList = {"cat", "dog"};
availableTagsList = { "cat", "test", "dog", "get", "spain", "south" };
Output: [0, 2] //'cat' in position 0; 'dog' in position 2
Input:
targetList = {"east", "in", "south"};
availableTagsList = { "east", "test", "east", "in", "east", "get", "spain", "south" };
Output: [2, 6] //'east' in position 2; 'in' in position 3; 'south' in position 6 (east in position 4 is not outputted as it is coming after 'in')
Input:
targetList = {"east", "in", "south"};
availableTagsList = { "east", "test", "south" };
Output: [0] //'in' not present in availableTagsList
Note: targetList will contain Distinct string objects.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - -1of 1 vote
AnswersGiven a list of characters, write a function to output a list of length of minimum non overlapping subsequences that can partition the input list.
- Shilpi_Roy January 25, 2018 in United States
For example:
Input : [a,b,c]
Output: [1,1,1]
Explanation: There are no repeated characters.
Input : [a,b,c,a]
Output: [4]
Explanation: The 'a' is repeated so one subsequence is between a to last a.
Input : [a,b,c,b,a,e,b,a,d,f,g,d,f,i,f,k,l,m,n,m,l]
Output: [8,7,6]
Explanation: max length from 1st 'a' to last 'a' is 8.
1st 'f' to last is 6 adding d to it = 7
so on| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 2of 2 votes
AnswerGoogle
- aonecoding January 20, 2018 in United States
1st round
Given a box with N balls in it, each ball having a weight, randomly choose pick one out base on the weight.
Input ball1-> 5kg, ball2 -> 10kg and ball3 -> 35kg,
then Prob(ball1 chosen) = 10%, Prob(ball2) = 20%,
Prob(ball3) = 70% ;
Follow-up:
Select a ball randomly based on weights. Once a ball is chosen, remove it. Next time select from the remaining balls. Go on until there is nothing left in the box.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersFind whether string S is periodic.
- aonecoding January 20, 2018 in United States
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"
follow up:
Given string S, find out the P (repetitive pattern) of S.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm