Recent Interview Questions
- 6of 6 votes
AnswersYou are given a matrix with N rows and N columns. Elements in matrix can be either 1 or 0. Each row and column of matrix is sorted in ascending order.
Find number of 0-s in the given matrix.
Example:0 0 1 0 1 1 1 1 1 Answer: 3 0 0 0 0 Answer: 4
Update: Expected complexity is O(log(N)). The best I've seen in comments is still O(N).
- emb June 26, 2016 in United States
Update2: Alright, guys, sorry for a bit of trolling. Obviously this is not possible to do faster than O(N). Here is why: take a diagonal (N, 1), (N-1, 2), ... (1, N). Suppose input matrix has all 0's above this diagonal and all 1's under this diagonal. So only diagonal elements vary. Clearly, diagonal elements do not depend on each other. So we have to analyze each diagonal element which is O(N).
Nice job, @gen-y-s :)| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 6of 6 votes
AnswersTwo container of 5 L and 3 L are given. Then are is 9.5L water given you need to make 4L water with minimum attempts and water wastage.
- Sachdefine January 11, 2014 in India for Kindle| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer Brain Teasers - 6of 6 votes
AnswersGiven an array of elements, return an array of values pertaining to how many elements are greater than that element remaining in the array.
- PradeepN October 27, 2015 in United States
Brute force is obvious, but must be done faster than O(n^2)
Ex. [3,4,5,9,2,1, 3]
Return [3, 2, 1, 0, 1, 1, 0]
First element is 3 because 3<4,5,9. Second element is 2 because 4< 5,9 etc| Report Duplicate | Flag | PURGE
Google Algorithm - 6of 6 votes
AnswersYou visited a list of places recently, but you do not remember the
- UserOne November 05, 2013 in United States
order in which you visited them. You have with you the airplane
tickets that you used for travelling. Each ticket contains just the
start location and the end location. Can you reconstruct your journey?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 6of 6 votes
AnswersGiven a sorted array of size N of int32, find an element that repeats > ceil(N / 2) times. Your algo may assume that there will be always such element. Space/time O(1).
- emb January 18, 2016 in United States
Follow up question: Now element repeats > ceil(N / 4) times. Space/time O(1)| Report Duplicate | Flag | PURGE
Google Intern - 6of 6 votes
AnswersPost order traversal for an N-ary tree iterative way.
- hm September 14, 2015 in United States
Given,
struct Node {
int val;
vector<Node*> children;
};
Without modifying original structure.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm C++ Trees and Graphs - 6of 6 votes
AnswersGiven an input array
- gowthamganguri August 30, 2013 in India
a={1,2,3,6,2,8----}
product of all numbers=p=a[0]*a[1]*---a[n-1] where n is size of array
output arrau should be b={p/a[0],p/a[1],p/a[2]-----}. you should not use division operator.Time complexity should be less than o(n2).| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 6of 6 votes
AnswersGiven an array such that every next element differs from the previous by +/- 1. (i.e. a[i+1] = a[i] +/-1 ) Find the local max OR min in O(1) time. The interviewer mentioned one more condition that the min or max should be non-edge elements of the array
- xyz March 30, 2015 in United States
Example: 1 2 3 4 5 4 3 2 1 -> Local max is 5
1 2 3 4 5 -> No local max or min exists
5 4 3 2 1 -> No local max or min exists| Report Duplicate | Flag | PURGE
Facebook Software Developer Algorithm - 6of 6 votes
AnswersGiven a array int a[]={2,5,1,9,3,7,2,8,9,3} and the no. of swap operations.We are allowed to do swap operations.
swap constraint: exchange only adjacent element.
Find the max number that can be formed using swap operations.
- koustav.adorable May 11, 2014 in Indiapublic static int[] maximize(int arr[],int swapsAllowed);
| Report Duplicate | Flag | PURGE
Amazon Web Developer Coding - 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 - 6of 6 votes
AnswersWrite a function that accepts two or more strings and returns the longest common substring in all of them.
- Barry Fruitman March 20, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 6of 6 votes
Answers/**
- aonecoding January 27, 2017 in United States
Given many coins of 3 different face values, print the combination sums of the coins up to 1000. Must be printed in order.
eg: coins(10, 15, 55)
print:
10
15
20
25
30
.
.
.
1000
*/| Report Duplicate | Flag | PURGE
Facebook Software Developer Algorithm - 6of 6 votes
AnswersPaper Cut into Minimum Number of Squares
- ajay.raj March 02, 2017 in United States
Given a paper of size A x B. Task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.
Examples:
Input : 13 x 29
Output : 9
Explanation :
2 (squares of size 13x13) +
4 (squares of size 3x3) +
3 (squares of size 1x1)=9
Input : 4 x 5
Output : 5
Explanation :
1 (squares of size 4x4) +
4 (squares of size 1x1)
geeksforgeeks provides a solution, but it is not right
http://www.geeksforgeeks.org/paper-cut-minimum-number-squares/| Report Duplicate | Flag | PURGE
Google - 6of 6 votes
AnswersYou are given two string named str1 and str2. Your task is to find the minimum window in str1 which contains all characters from string str2.
- Rahul Sharma November 09, 2013 in India| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Coding - 6of 6 votes
AnswersQ: If you were given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]
- aonecoding January 27, 2017 in United States
and then another series [A != C, D != H, ..., F != A ]
Check whether the equations combined is valid.
For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series.| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 6of 6 votes
Answers5th Round
- aonecoding April 13, 2017 in United States
Open-ended question What happens when you type a url in the browser and hit enter?
Second question Given an array of integers, print all the numbers that meet the following requirement - when the number is greater than every number on its left and smaller than every number on the right.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 6of 6 votes
AnswersGiven a non-directed, strongly connected graph where the node values are letters of the alphabet, write an algorithm that prints out all possible permutations of strings. What is this called?
- william.brandon.lee83 January 18, 2016 in United States
For example:
V = A,B,C
Printout
ABC
ACB
BAC
BCA
CAB
CBA
BAC etc.| Report Duplicate | Flag | PURGE
IBM Software Engineer / Developer Algorithm - 6of 6 votes
AnswersYou are given a 2d rectangular array of positive integers representing the height map of a continent. The "Pacific ocean" touches the left and top edges of the array and the "Atlantic ocean" touches the right and bottom edges.
- JD March 14, 2015 in United States
- Find the "continental divide". That is, the list of grid points where water can flow either to the Pacific or the Atlantic.
Water can only flow from a cell to another one with height equal or lower.
Example:
Pacific ~ ~ ~ ~ ~ |__
~ 1 2 2 3 (5) ~
~ 3 2 3 (4)(4) ~
~ 2 4 (5) 3 1 ~
~ (6)(7) 1 4 5 ~
__ (5) 1 1 2 4 ~
|~ ~ ~ ~ ~ Atlantic
The answer would be the list containing the coordinates of all circled cells:
[(4,0), (3,1), (4,1), (2,2), (0,3), (1,3), (0,4)]| Report Duplicate | Flag | PURGE
Facebook Algorithm - 6of 6 votes
AnswersComponents of computer systems often have dependencies -- other components that must be installed before they will function properly. These dependencies are frequently shared by multiple components. For example, both the TELNET client program and the FTP client program require that the TCP/IP networking software be installed before they can operate. If you install TCP/IP and the TELNET client program, and later decide to add the FTP client program, you do not need to reinstall TCP/IP.
- Byll September 26, 2014 in United States
For some components it would not be a problem if the components on which they depended were reinstalled; it would just waste some resources. But for others, like TCP/IP, some component configuration may be destroyed if the component was reinstalled.
It is useful to be able to remove components that are no longer needed. When this is done, components that only support the removed component may also be removed, freeing up disk space, memory, and other resources. But a supporting component, not explicitly installed, may be removed only if all components which depend on it are also removed. For example, removing the FTP client program and TCP/IP would mean the TELNET client program, which was not removed, would no longer operate. Likewise, removing TCP/IP by itself would cause the failure of both the TELNET and the FTP client programs. Also if we installed TCP/IP to support our own development, then installed the TELNET client (which depends on TCP/IP) and then still later removed the TELNET client, we would not want TCP/IP to be removed.
Write a program to automate the process of adding and removing components. To do this we will maintain a record of installed components and component dependencies. A component can be installed explicitly in response to a command (unless it is already installed), or implicitly if it is needed for some other component being installed. Likewise, a component, not explicitly installed, can be explicitly removed in response to a command (if it is not needed to support other components) or implicitly removed if it is no longer needed to support another component.
I found a reference to this problem online.. Check this for i/o details. This is the exact same problem
http://www.cs.cornell.edu/Info/Courses/Spring-98/CS211/assgts/assgt3/assgt3.pdf| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm - 6of 6 votes
AnswersGiven an array of integers, find out how many unique BST can be generated from the array.
- kieth October 07, 2018 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Trees and Graphs - 6of 6 votes
AnswersWhen a child is forked then it inherits parent's file descriptors, if child closes the file descriptor what will happen ? If child starts writing what shall happen to the file at the parent's end ? Who manages these inconsistencies , kernel or user ?
- cinderella April 09, 2012 in United States for 3D graphics| Report Duplicate | Flag | PURGE
Intel Software Engineer / Developer - 6of 6 votes
AnswerPhone Interview with Collabedit.
- Sagar Shah February 11, 2015 in United States
/** Compute the value of an expression in Reverse Polish Notation. Supported operators are "+", "-", "*" and "/".
* Reverse Polish is a postfix mathematical notation in which each operator immediately follows its operands.
* Each operand may be a number or another expression.
* For example, 3 + 4 in Reverse Polish is 3 4 + and 2 * (4 + 1) would be written as 4 1 + 2 * or 2 4 1 + *
*
* @param ops a sequence of numbers and operators, in Reverse Polish Notation
* @return the result of the computation
* @throws IllegalArgumentException ops don't represent a well-formed RPN expression
* @throws ArithmeticException the computation generates an arithmetic error, such as dividing by zero
*
* <p>Some sample ops and their results:
* ["4", "1", "+", "2.5", "*"] -> ((4 + 1) * 2.5) -> 12.5
* ["5", "80", "40", "/", "+"] -> (5 + (80 / 40)) -> 7
*/| Report Duplicate | Flag | PURGE
Linkedin Android Engineer Data Structures - 6of 0 votes
AnswersImagine there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels;
- Edde May 12, 2007| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 6of 0 votes
AnswersReverse a linked list iteratively, do it first with single pointers and then do it again with double pointers. Now do it again recursively but not tail-recursive, and then do it again tail-recursively. What do you do if it has a loop?
- Anonymous September 22, 2008| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Coding - 5of 15 votes
AnswersGiven a function
- mabid.mahmood July 15, 2014 in United States
getRandomTripplet()
which returns a random triplet of letters from a string. You don't know the string using calls to this function you have to correctly guess the string. the length of the string is also given.
Lets say the string is helloworld the function getRandomTriplet will return things like
hlo
hew
wld
owo
the function maintains the relative order of the letters. so it will never return
ohl since h is before o in the string.
owe since w is after e
The string is not known you are only given length of the string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 13 votes
AnswersGiven n, output the numbers from 0 to 2^n-1 (inclusive) in n-bit binary form, in such an order that adjacent numbers in the list differ by exactly 1 bit.
- xxyyzz February 23, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 9 votes
AnswersQ: Given a sorted 2D N x N array (where array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]), can you write a function that converts this to a sorted 1D array?
- pdoggeth October 18, 2013 in United States
The obvious and naive way that I thought of was to convert the entire array into a 1D and do a mergesort on it, but there must be a better way than that. I'm wondering what the better and more efficient way is.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 9 votes
AnswersWrite a Program for Dictionary which has functionality of lookup and insert . This program should be able to add words on the fly
- Guy February 05, 2014 in United States
I wrote simple code using HashTable
follow up
1) Now we are getting too many words what happens
me: Hashtable will dynamically resize resulting into performance hit . Also they might get hashed to same location as well as we might run out of main memory
2) Okay you are out of main memory , How will you scale this program
me: I will create buckets of HashTable lets say 26 buckets for one for each alphabet and would put them on different machines
3) Lets say you are out of memory on those machines too
me: Okay I need to put them on secondary storage . Here we can have fileSystem or Database . I chose database . I will create simple DB schema of BucketNumber and word .
I will use buckets on main memory as cache , if we are not able to find a word in the bucket then query databse with bucket number and words then remove the least number times looked up word (every time we lookup a word we increament the count i.e value in key,value pair on hashtable) from that bucket and add this word .
I mentioned that bottleneck in this case will be every time a word is not present we need to query DB which usually has high latency which will result into performance hit
4) Lets say we are okay with latency but what if we are getting inserting words between that are only between only in two buckets ex. words starting from a and b only.
Now that I think about it, is it better to do this in a trie? What do you guys think?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer System Design