Recent Interview Questions
- 5of 5 votes
Answersdesign a system to return an unique ID for each request. For most of requests, the ID value should increase as time goes, the system should handle 1000 requests per second at least.
- codingfunnyguy December 04, 2013 in United States
timestamps alone is not valid since there might be multiple requests with same timestamps.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - 5of 5 votes
AnswersI have table with columns (Employee, Manager, Salary). Need to calculate aggregate salary for all employees corresponding to top-level managers in one SQL. For example
- breakrulez May 10, 2013 in United States
Input table is :
Emp Manager Salary
A T 10
B A 11
C F 13
D B 5
Result should be :
Top-Lvl Manager Salary(agg)
T 26
F 13
Manager-Employee layering can go multiple levels.| Report Duplicate | Flag | PURGE
Database SQL - 5of 5 votes
AnswersWe have a day to work and we have different kinds works do to which has start-time and end-time. We have to choose the different works so that we can achieve the maximum number of minutes in a day to work. Chosen works should not overlaps to each other.
- Rahul August 22, 2013 in India
Ex-1:
Start-Time End-Time
W1: 6:00 9:30
W2: 9:00 12:30
W3: 12:00 14:30
W4: 10:00 10:30
W5: 11:00 13:30
Solution: W1 + W4 + W3(or W5)
Ex-2:
Start-Time End-Time
W1: 6:00 8:30
W2: 9:00 11:00
W3: 12:30 14:00
W4: 8:00 9:00
W5: 10:30 14:00
W6: 9:00 11:30
Solution : W1 + W6 + W3 = 390min| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 5of 5 votes
AnswersAs input, you are given two sets:
- kbex07 February 11, 2013 in United States
1) set R of n1 non-overlapping rectangles, whose sides are parallel to the x- and y-axes (ie: not rotated rectangles). Each rectangle denoted by bottom left & top right corner coordinates.
2) set P of n2 points
- let n = n1 + n2
For each point 'p' in set P, find the rectangle 'r_p' in set R that contains 'p'. If 'p' is not enclosed by any rectangle, then 'r_p' is undefined. Otherwise, 'r_p' is unique because of the non-overlapping set.
Goal: come up with a divide-and-conquer pseudocode to solve the general problem in O(n(logn)^2) time.
Asked about points that are on the edge of the rectangle, and they said it was up to me whether to include those or not, just a matter of "<" vs "<=", etc. comparisons. Because it's just pseudocode they were looking for, they were not too concerned with the actual structure of the return value, just that the D&C algorithm showed the logic.
Struggled with it for awhile and they simplified the problem to a ~special case with the constraint where all rectangles of R intersected a horizontal line 'L', and instead give a O(nlogn) algorithm to solve the same problem. I suspect this would've been a subproblem/subroutine of the more general case, but again got a bit lost.| Report Duplicate | Flag | PURGE
Facebook Algorithm - 5of 5 votes
AnswersLet A = A[1], . . . , A[n] be an array of n positive integers. Let s = A[1] + · · · + A[n] be the sum of all the numbers in the array. For 1 ≤ i ≤ n, let S(i) = s − A[i].
- Denjar June 01, 2013 in United States
Design a linear time algorithm (O(n)) to compute S[1], . . . , S[n] only with plus operations (you are not allowed to use the minus operation)| Report Duplicate | Flag | PURGE
Algorithm - 5of 5 votes
Answersyou have given array of Size N and two numbers M, K. K is size of subarray and M is count of subarray.
- SK January 21, 2015 in India
You have to return sum of max M subarray of size K (non-overlapping)
N = 7, M = 3 , K = 1
A={2 10 7 18 5 33 0} = 61 — subsets are: 33, 18, 10 (top M of size K)
M=2,K=2
{3,2,100,1} = 106 - subsets are: (3,2), (100,1) 2 subsets of size 2| Report Duplicate | Flag | PURGE
Directi Senior Software Development Engineer Algorithm Dynamic Programming - 5of 5 votes
Answerswrite a program to give an array such that:
- doctorking5891 April 29, 2014 in United States
1. the data value is from 1 to n
2. the length of it is 2*n
3. the two elements with same value keep the same number distance.
for example, when n = 3, the length of array is 6, the array should be like: 2, 3, 1, 2, 1, 3. there are two elements between "2" pair, and three elements between "3" pair and one element between "1" pair| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 5of 5 votes
AnswersYou are given an array of n elements. The elements have are n-bit long too.
- Anon123 January 04, 2014 in United States
Now n here represents the number of employees in a company. Element with index 0 is information about employee 0, at index 1 is information of employee 1....
For each element, the bits represent whether that employee works (not same team... just works) with employee at that index.
Ex. element 0 = 0110 => emplyee 0 works with employee 1 and 2
element 1 = 1001 => emplyee 1 works with employee 0 and 3
...
Put employees in groups in which they work. The transitive property is applicable here i.e. if A works with B and B works with C, ABC will be in one group.
The solution needs to efficient in terms of run time and memory. I hope the above is clear.| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 5of 5 votes
Answers100 doors are closed , In first pass i open all of them , in 2nd pass i toggle every 2nd door , in 3rd pass i toggle every 3rd door , i continue it till 100th pass .. find all the doors that will remain open after 100 passes.
- anag June 26, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Brain Teasers - 5of 5 votes
Answerswaf to rotate array by k unit
- pintuguptajuit(PINTU GUPTA) March 25, 2013 in India
size of array n=6
1 2 3 4 5 6
k=2
output
5 6 1 2 3 4| Report Duplicate | Flag | PURGE
Microsoft SDE1 - 5of 5 votes
Answersfind the sum of all 4 digit numbers formed from 1 , 2, 3, 4 whithout rep .
- anag June 26, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Brain Teasers - 5of 5 votes
AnswersYou are given a campus map with the Google buildings, roads and Google
bikes. You have to help the employee find the nearest Google bike.
Campus map:
- john August 29, 2018 in United States. - Free path/road # - Building B - Google bike Employee location - (x, y) - (1, 2) . . . . . # . . E . . # # # # # . # . B . . . . . . . . . B
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersWrite a program to print all the permutations of the given input string.
- chandan.jc May 10, 2012 in United States for Software| Report Duplicate | Flag | PURGE
NetApp Intern Algorithm - 5of 5 votes
AnswersWrite the code for a change vending machine.
- Java Coder October 12, 2008| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
Answers[Google] Design Text Editor (Doubly Linked List)
- aonecoding4 December 04, 2018 in United States
Build a text editor class with the following functions,
moveCursorLeft(),
moveCursorRight(),
insertCharacter(char) //insert the char right before cursor
backspace() //delete the char right before cursor
Follow-up
Implement undo() //undo the last edit. Can be called multiple times until all edits are cancelled.
All functions above should take O(1) time.
Example
( '|' denotes where the cursor locates. 'text' shows what's been written to the text editor. )
Start with empty text
text = "|"
insertCharacter('a')
text = "a|"
insertCharacter('b')
text = "ab|"
insertCharacter('c')
text = "abc|"
moveCursorLeft()
text = "ab|c"
moveCursorLeft()
text = "a|bc"
backspace()
text = "|bc"
moveCursorLeft()
text = "|bc" (nothing happens since cursor was on the leftmost position)
undo()
text = "a|bc"
undo()
text = "ab|c"
undo()
text = "abc|"
undo()
text = "ab|"
undo()
text = "a|"| Report Duplicate | Flag | PURGE
Google Software Engineer - 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 - 5of 5 votes
Answers
- skc25pma February 02, 2015 in India for Media.netA tree is given in which each edge is having some weight associated with it and you are given a number K. So starting from root in K-steps how much maximum weight you can collect. You can traverse in any direction either from parent to child or child to parent. You can visit a node multiple times. Eg: O 5/ \ 6 O O 24/ 1 \ \11 For K=1, ans=6 For K=2, ans=29 etc..
| Report Duplicate | Flag | PURGE
Directi Software Engineer - 5of 5 votes
AnswersCongrats on aonecode member A.P. for signing the offer with FB! Thanks for sharing the experience with us.
- aonecoding May 24, 2018 in United States
phone:
postorder tree traversal recursive -> iterative
add two binary number
on-site:
1 ring buffer
2 merge intervals
3 Leetcode alien dictionary
4.sort list of words| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 5of 5 votes
AnswersGiven a stream of integers where probability of a smaller number being first in stream is more than probability of larger number in stream.
- James March 17, 2021 in United States
Implement a method that returns true if you have already seen that element in stream otherwise return false.
eg. stream could look like 1,2,3,5,6,11,7,3......
more examples - 3,4,1,2,5,9,22,12
---
I explained using a hashset but that solution was not viable because of the space requirement.
I don't think I handled this question well. So would love people's opinion on it.| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 5of 5 votes
AnswersA happy number is defined by the following process. Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers.
- sk2244 March 19, 2019 in India
Input:
Your program should read lines of text from standard input. Each line contains a single positive integer, N.
Output:
If the number is a happy number, print 1 to standard output. Otherwise, print 0.| Report Duplicate | Flag | PURGE
Sabre Holdings Java Developer Java - 5of 5 votes
AnswersWhat is the difference between a class method and an instance method?
- Mauricio.Malf February 21, 2013 in Netherlands| Report Duplicate | Flag | PURGE
Booking.com Software Engineer / Developer Object Oriented Design - 5of 5 votes
AnswersGoogle On-site in May
- aonecoding June 15, 2017 in United States
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| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersTree Game
- aonecode May 17, 2019 in United States
class TreeNode {
TreeNode parent; //parent node
TreeNode left; //left child
TreeNode right; //right child
}
Two people in a game, player scores by claiming nodes in binary tree, tree node class as shown above.
The player who eventually owns more nodes wins the game.
Player A and B each claims a node at first.
After the first round, a player will only be able to claim a node adjacent to any node owned by himself.
A tree node is adjacent to its parent, left right and right child.
A node owned cannot be re-claimed.
End game when all nodes are owned.
If player A gets the first claim at node N, find whether it is possible for player B to win.
If yes, find out which node player B should claim at his first move.
Follow up: if player B takes the first hand instead, which node should he pick?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswerWhy facebook?
- androidenthusiast March 12, 2018 in United States
What was the biggest technical problem that you solved?
Do you have any apps on google play?
Give me a scenario where the requirements were ambiguous, what did you do?| Report Duplicate | Flag | PURGE
Facebook Android Engineer Behavioral - 5of 5 votes
AnswerQ .2 candles each burns for 1 hr each ,calculate 45 min time
- dearamitdubey@googlemail.com March 25, 2013 in India
by burning them in one go .
Ans :
burn the first candle from both the side, parallel to first one , burn the other from single side only, once the first is burnt completely 30 mins are over and second is already half burned .
now start burning the second one from the other side .
you have 45 mins calculated.
!!! Bam !! again kid stuff !!| Report Duplicate | Flag | PURGE
Samsung Financial Software Developer - 5of 5 votes
AnswersDesign a voting system. 100M users will be logging in within a window of 24h (not necessarily uniformly). Every user will be able to choose from a fixed list of options. If the user has already voted the system should not let them to vote a second time. Additional constraint: only the first 100K votes are accepted. If the quota is exceeded any attempt to vote should be rejected.
- adr September 12, 2019 in United States| Report Duplicate | Flag | PURGE
Software Engineer System Design - 5of 5 votes
AnswersAsked me to write an API. Then ask:
- joyfeng November 19, 2015 in United States
Consider how the API could support 3rd party applications which need to perform some logic based on the structure and content of a filter in a type-safe manner.| Report Duplicate | Flag | PURGE
unknown Software Engineer / Developer Java - 5of 0 votes
AnswersGiven a string where there are numbers and some numbers are repeated, e.g. 13413124...,
- Anonymous December 29, 2008
design a data structure for it and the data structure should store positions of each number.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm