Recent Interview Questions
- 4of 4 votes
AnswersGiven a matrix with 1's and 0's, a rectangle can be made with 1's. What is the maximum area of the rectangle.
- bharadwaj.tanikella23 March 05, 2014 in United States
00010
11100
11110
11000
11010 In this test case the result needs to be 8.
How:
00010 00010
11100 11 100
11110 11 110
11000 11 000
11010 11 010
If you see above the 11's are used from the first two columns and last four rows making the area or count of 1's to be 8.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 4of 4 votes
Answers
- rockykumar1970 August 05, 2014 in IndiaDesign a data structure which has following operations: 1. void add(e) 2. void delete(e) 3. boolean contains(e) 4. e getRandom() 5. e getMostRecent() All operations should be preferably O(1)
| Report Duplicate | Flag | PURGE
SumoLogic Software Engineer in Test - 4of 4 votes
AnswersGiven N pens and n caps . Sort them. you cant compare pens with other pens and caps with other caps
- Anonymous July 29, 2011| Report Duplicate | Flag | PURGE
Google - 4of 4 votes
Answers# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.
- aonecoding February 08, 2017 in United States
# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:
# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
# For example:
# input = [(1,4), (2,3)]
# > 3
# input = [(4,6), (1,2)]
# > 3
# input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
# > 11| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 4of 4 votes
AnswersPrints all unique subsets of the string.
- mabodx February 11, 2014 in United States
Given a string write a function which prints all the subsets of the string. Now make the function to return only unique solutions.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 4of 4 votes
AnswersYou have a number L and N distinct integers between 1 and 100.
- BingBang February 10, 2013 in United States
You can use each number as many times as you want. Print the minimum subset size of these numbers which add up to L and how many ways are there to choose them (the order does not matter).
0<L,N<=100
examples:
input1:
L=7 N=6
2 1 5 4 3 6
output1:
2 3 (minimum 2 numbers, 3 ways to choose: 1 and 6, 2 and 5, or 2 and 4
input2:
L=7 N=3
4 2 6
output2:
0 0 (can't get 7 from 4,2 or 6)
input3:
L=14 N=3
8 7 1
output3:
2 1 (we choose 7 twice)
input4:
L=100 N=3
2 97 1
output4:
3 1| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven an int, write code to return the number of bits that are 1 in O(m) time, where m is the number of bits that are 1.
- ootah November 14, 2013 in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Bit Manipulation - 4of 4 votes
AnswersHow to serialize strings and pass it over the network and de-serialize the string? The string may contain any possible character out of 256 valid characters.
- rya November 13, 2010
The interviewer tried to give a hint "how do you escape characters in a string" !
Should the answer be use serializable in Java? Or is there a specific algorithm?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersGiven many coins of 3 different face values, print the combination sums of the coins up to 1000. Must be printed in order.
- aonecoding4 December 16, 2018 in United States
eg: coins(10, 15, 55)
print:
10
15
20
25
30
.
.
.
1000| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 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 - 4of 4 votes
AnswersGiven an non-negative int array and target number, check if the target can be equal to the sum of non-negative multiples of the numbers in the array.
- ajay.raj March 17, 2017 in United States
For example, I have three numbers 6,9,20. Ex: n = 47 then it can be determined that 47 = 9*3 + 20
n=23 then there are no combinations.
public boolean combinationSum(int[] nums, int target) {
}| Report Duplicate | Flag | PURGE
Google SDE1 - 4of 4 votes
AnswersLets say someone accidentally deleted all the whitespaces from a sentence. Write a program to reconstruct the sentence from that stripped out string. Assume you have access to a dictionary function that returns if a given string is a valid word or not.
- NS August 23, 2016 in United States
Example input: thisisavalidsentence
Output: this is a valid sentence
If multiple solutions are possible, any one valid solution should be given. Assume there is always a valid solution. No invalid input will be given.| Report Duplicate | Flag | PURGE
Amazon Algorithm - 4of 4 votes
AnswersThis question was asked in the Technical Design round.
- varun.venu September 22, 2015 in United States
How would you design a system to provide the top trending topcis in the last 5m/1hour/24hours
The most trending topic should appear first
A topic is said to be trending if it is shared the most. We are talking about a typical multi user environment (something like twitter, facebook).| Report Duplicate | Flag | PURGE
Linkedin Senior Software Development Engineer System Design - 4of 4 votes
AnswersGiven an unbalanced binary tree, write code to select a node at random (each node has an equal probability of being selected).
- tested.candidate July 14, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersGiven a big rectangular plot of land that has rectangular or square sized buildings (all sides of every building are parallel to the big rectangular plot)... find the location and dimensions of the largest square that can be built in this rectangular plot
- JSDUDE May 18, 2015 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 4of 4 votes
AnswersGiven an array of integers and a number. WAP to find the pairs which sum of upto given number.
- Nitin Gupta May 15, 2015 in India for Cloud & Enterprise team
I solved it. Then he asked about writing test cases for this function.
I wrote below test cases
1.) All the elements should be number.
2.) Length of array should not be 0.
3.) Array itself should not be null.
4.) Given number, arrayLength can be represented by 32bits or 64 bits.
5.) number should not be negative.
6.) Input does not has pair, It should return false
7.) Input has pair, It should return true
8.) Input has all negative values and pair exists, then function should return true
9.) Input has all negative values and pair does not exists, function should return false
He told that he is looking for more test cases. Can you guys think of some more complex test cases.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm Arrays C++ Data Structures - 4of 4 votes
AnswersGive a path get it's canonical form. So for example if you have path in the form e/../../a/d/./../b/c then you should return a/b/c.
I have the solution but it's not the most optimal or the best solution. I just wanted to see what others have.
- cyb March 09, 2015 in United Statespublic String canonicalPath(String path){ if(path == null || path.isEmpty()){ throw new RuntimeException("incorrect path provided"); } String[] chunks = path.split("/"); Stack<String> s = new Stack<String>(); List<String> arr = new ArrayList<String>(); for(String chunk: chunks){ if(chunk.isEmpty() || chunk == "."){ System.out.println("skipping"); }else{ if(!s.isEmpty() && s.peek().equals("..") && !chunk.equals("..")){ while (!s.isEmpty()) { if(s.peek().equals("..")){ s.pop(); }else{ s.pop(); break; } } s.push(chunk); }else{ s.push(chunk); } } } StringBuffer sb = new StringBuffer(); List<String> list = null; if(!s.isEmpty()){ list = new ArrayList<String>(s); } if(list != null){ for(String ss : list){ sb.append("/"+ss); } } return sb.toString(); }
| Report Duplicate | Flag | PURGE
Amazon Software Developer Data Structures - 4of 4 votes
AnswersYou are having a 500 MB RAM and you have a program which uses malloc to allocate 600 MB memory . What will happen , will it be allocated using the concept of virtual memory or not , if yes how?
- P3A July 23, 2013 in India| Report Duplicate | Flag | PURGE
Yahoo SDE1 Operating System - 4of 4 votes
AnswersYou have an array of numbers. You have to give the range in which each number is the maximum element. For Example, If array is 1, 5, 4, 3, 6 The output would be
- neer.1304 July 12, 2020 in United States
1 [1, 1]
5 [1, 4]
4 [3, 4]
3 [4, 4]
6 [1, 5]| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 4of 4 votes
AnswersYou have rand2() function which returns 0 or 1 with equal probability. You should implement rand3() using rand2().
- nfokin June 20, 2016 in Russia| Report Duplicate | Flag | PURGE
Yandex Software Engineer Algorithm - 4of 4 votes
AnswersConsidering a stream of integers coming in. Design a datastructre to store only n of them. Insert if if does not exist in the datastructre. And if it reaches n, remove the first one inserted into the datastructure.
- anonymous August 11, 2013 in India
Datastructure should provide, addition, deletion and search all in O(1) time.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 4of 4 votes
AnswersAll jumbled numbers of n digits in max (worst case) O(n) and min (avg case) O(log n) time.
- mani0119 October 08, 2017 in India
A number is a jumbled number if the _absolute_ difference between adjacent digits is <=1.
For an input n=3
output should be
100
101
110
111
121
122
...
and so on.
The problem is similar to the one listed here https://www.careercup.com/question?id=5729332770111488
But this problem also has a O(n or log n) limitation and the solutions listed in the above mentioned problem at the time of posting this question, do not satisfy the criteria
PS: 001 is not a 3 digit number.
210 is absolutely fine as the absolute difference between adjacent digits is <=1.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 4of 4 votes
AnswersYou are given 2 documents. We want to know how similar they are through N-Grams.
- um01 June 20, 2015 in United States
Given an input n (n = number of word in the Ngram) and two documents(strings) find the intersection of the NGrams of two document.
E.g doc1 = 'This is a dog'
doc2 = 'This is a cat'
n = 3
Ngrams for doc1 = 'This is a', 'is a dog'
Ngrams for doc2 = 'This is a', 'is a cat'
Output 'This is a'
Find a efficient way and give its complexity.| Report Duplicate | Flag | PURGE
Google Software Engineer - 4of 4 votes
AnswersWrite code/ logic to count number of words in a string delimited by " ". Anything apart form " " are ignore for the counting. String could be very big as big as 5 GB of data. So add logic to handle such large strings..
- Jai December 12, 2014 in United States
ex: aaa b c ddd e = Count (5)
aaaaaaaaaaa = Count(1)
a
b
c
d
Count(1) as there are no spaces rather carriage returns are found.
PS: In case above question is not clear do let me know.| Report Duplicate | Flag | PURGE
SDE-2 Arrays - 4of 4 votes
AnswersGiven a list of 4 billion integers, find an integer not in the list using 4MB of memory. (interview was in Java)
- dke.ade February 25, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Java - 4of 4 votes
AnswersFind the median of 2 sorted arrays
- Partha November 10, 2009| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays - 4of 4 votes
Answers/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
Find if a given binary tree has duplicate sub trees.
followup:
Find all duplicate subtrees in a binary tree
- ajay.raj March 03, 2017 in United StatesFor example, 1 / \ 2 3 / / \ 4 2 4 / 4 The following are two duplicate subtrees: 2 / 4 and 4 Therefore, return [ [2,4], [4] ].
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersGiven infinite array in which the first n cells contain integers in sorted order and rest filled with symbol $. Assume we don't know n value. Give algorithm that takes an integer k as input and finds a position in array in O(logn)
- pirate July 27, 2013 in India| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 4of 4 votes
AnswersDescribe the actions performed by two functions:
- asafiniu February 27, 2013 in United States
Publish(user, msg) - publishes a new post on behalf of 'user'
GetNewsFeed(user) - gathers 30 posts from 'user's friends to show on his/her news feed.
I was asked to map out the relations required for holding large amounts of data.
As a followup, I had to calculate the number of machines facebook would have to initially buy to start off using this news feed.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer System Design - 4of 4 votes
AnswersGiven a set of N points with x,y cords in a 2D plane. Find all possible squares that can be formed with vertices in this set.
- tryingtosolvemystery August 06, 2013 in United States| Report Duplicate | Flag | PURGE
Goldman Sachs Financial Software Developer