Software Engineer / Developer Interview Questions
- 4of 4 votes
AnswersGiven an integer array. Perform circular right shift by n.
- wolfengineer November 09, 2013 in United States
Give the best solution.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Arrays - 4of 4 votes
AnswersI Got this Crazy Question on PHONE INTERVIEW AT GOOGLE:
- hhh April 11, 2013 in United States
Design and implement a class to generate random numbers in an arbitrary probability distribution given by an array of integer weights, i.e. for int[] w return a number, n, from 0 to w.length - 1 with probability w[n] / sum(w). Using an existing random number generator with a uniform distribution is permitted.
Example distribution:
w = 1, 2, 3, 2, 1
Example probabilities:
w / sum = 1/9, 2/9, 1/3, 2/9, 1/9
Example results:
n = 0, 1, 2, 3, 4
Documentation:
Class java.util.Random
public int nextInt(int n)
Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability.
Parameters:
n - the bound on the random number to be returned. Must be positive.
Returns:
the next pseudorandom, uniformly distributed int value between 0 (inclusive) and n (exclusive) from this random number generator's sequence
Throws:
IllegalArgumentException - if n is not positive| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 4of 4 votes
AnswersGiven an array Of integers build a new array of integers such that every 2nd element of the array is greater than its left and right element.
- Gaurav Shah March 17, 2015 in United States for Chrome Team
eg:
[1,4,5,2,3]
o/p:
[1,4,2,5,3]
Soln proposed:
Step 1:Sort The array -> O(nlogn)
Step 2:Use 2 indices: one starting at leftmost index and other at rightmost index.
and populate the new array alterntely using the left pointer(index) first and then the right pointer and then increment the pointer used. till both the pointers meet/cross each other. -> O(n).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersGiven an m x n matrix where each row element is sorted, but the columns do not appear in sorted order, write a function to print each matrix element in sorted order.
- seanchen11235 March 06, 2015 in United States
Example matrix:
matrix = [
[20, 40, 80],
[5, 60, 90],
[45, 50, 55]
]
Your function should print 5, 20, 40, 45, 50, 55, 60, 80, 90.
Add on: Assume that we are space-constrained such that we can only hold one row in memory at a time. Optimize your function to work under such constraints as efficiently as possible.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 4of 4 votes
Answersgive an algorithm for finding duplicate parenthesis in a expression.
example :
- rahul May 02, 2014 in United States(( a + b ) + (( c + d )))
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Stacks - 4of 4 votes
AnswersReturn the length of longest possible chunked palindrome string.
- AlgoBaba December 08, 2016 in United States
Examples :
Input : VOLVO
Output : 3
Explanation :
(VO)L(VO)
Input : merchant
Output : 1
Explanation : No chunks possible.
Input :
ghiabcdefhelloadamhelloabcdefghi
Output : 7
Explanation :
(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven arrays for N (>= 2) users, each representing the IDs of hotels visited, find the common IDs of the hotels visited amongst the users.
- PraTrick April 26, 2017 in India
Input:
userA = { 2, 3, 1 }
userB = { 2, 5, 3 }
userC = { 7, 3, 1 }
Output:
{3}
Assumptions:
Arrays are unsorted.
Cases:
1) Each array consists of distinct hotel IDs
2) Each array may contain duplicate hotel IDs| Report Duplicate | Flag | PURGE
Booking.com Software Engineer / Developer - 4of 4 votes
AnswersGiven the relative positions (S, W, N, E, SW, NW, SE, NE) of some pairs of points on a 2D plane, determine whether it is possible. No two points have the same coordinates.
- united November 02, 2014 in United States
e.g., if the input is "p1 SE p2, p2 SE p3, p3 SE p1", output "impossible".| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersImplement a method called printNonComments() which prints out a extract of text with comments removed.
- Ash June 30, 2014 in UK
For example, the input:
hello /* this is a
multi line comment */ all
Should produce:
hello
all
You have access to a method called getNextLine() which returns the next line in the input string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 4of 4 votes
Answersdesign a method which consumes an integer and output the corresponding column number in Microsoft Excel ( ex. A, B, C......Z, AA, AB....ZZ....)
- chandeepsingh85 September 25, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersFind the latest version of released software. For e.g1. 2 and 2.2.. latest is 2.2.
- techpanja October 02, 2013 in United States
eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed as string in above format.| Report Duplicate | Flag | PURGE
Ebay Software Engineer / Developer Java - 4of 4 votes
AnswersWrite code to generate all possible case combinations of a given lower-cased string. (e.g.
- An Enthusiast March 25, 2014 in United States"0ab" -> ["0ab", "0aB", "0Ab", "0AB"])
| Report Duplicate | Flag | PURGE
Yelp Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven an array of pairs of the form <a, b>. We have to find a sub-array such that the 1st element in the pairs are in increasing order and the sum of 2nd element of the pairs in the sub-array is maximum possible
- geekofthegeeks November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersWAP a program to find a contineous subset whose sum is divisible by 7. We are given a array of number (negative+positive).
- yogi.rulzz October 26, 2013 in India
calculate the complexity of your algorithm| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 4of 4 votes
AnswersDesign a data structure that supports kind of full text search but in numbers.
- coredo July 14, 2015 in United States
We are given file with lot of 10-digits numbers, for example:
1234 567 890
4124 123 123
3123 123 322
On a given number X we should return all numbers that contain X.
For example, if the number 123 was given, we should return all numbers (from the list above) because 123 is in all of them.
If the number 41 was given we should return only the middle number - because the number 41 is only in it.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Data Structures - 4of 4 votes
AnswersConsider the array 3 5 7 6 3.
- Gaile April 10, 2014 in United States
Return the pair of indices that forms the slice where the difference between the maximum and minimum in the slice <= 2.
Output:
(0,0) (1,1) (2,2) (3,3) (4,4) (5,5)
(0,1) (1,2) (1,3) (2,3)
Example slices: 3 5, 5 7, 1 3, 2 3.
The following link
https://codility.com/media/train/solution-count-bounded-slices.pdf
has O ( n ) solution. But couldn't understand the O (n ) solution. Could some one explain with an example?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
Answersgiven an 2D matrix M, is filled either using X or O, you need to find the region which is filled by O and surrounded by X
- smit February 14, 2014 in India
and fill it with X.
example 1:
X X X X X
X X O O X
X X O O X
O X X X X
Answer :
X X X X X
X X X X X
X X X X X
O X X X X
example 2:
X X X X X
X X O O X
X X O O O
O X X X X
answer 2:
X X X X X
X X O O X
X X O O O
O X X X X| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven a undirected graph with weights, return the sum of the weight of each path between two nodes (shortest path between two vertices). Assume there are no cycles.
Example:Input: A | 1 B 2 / \ 3 C D Output: 18 since A to B has weight 1 A to C has weight 3 A to D has weight 4 B to C has weight 2 B to D has weight 3 C to D has weight 5
Edit: Thanks, wangchenClark0512, forgot about C to D
- djway August 18, 2016 in United States
Edit2: @Lukas, The question is just the sum of the shortest paths between two vertices. Also, all edges are positive.
Edit3: Assume the graph has no cycles, did not get to the follow-up, but follow-up probably is probably change your algorithm so that is works for cycles| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 4of 4 votes
AnswersGiven two strings, find that the if the letters in both the strings are same? i.e. can we be able to make string2 out of string1 by shuffling the words and vice versa.
- saikrishna chunchu April 17, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 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
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
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
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
AnswersWhat is the data structure you will use to model Tennis tournament of size number of players n=8. Splitted into 2 groups? What is the complexity of finding the winner and the runner.
- hari@hbiz.in September 26, 2012 in India| Report Duplicate | Flag | PURGE
Synopsys R&D Software Engineer / Developer Data Structures