Software Engineer / Developer Interview Questions
- 77of 79 votes
AnswersYou have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.
- ericaturner0 April 01, 2013 in United States
For example,
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]
The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 44of 48 votes
AnswersPots of gold game: Two players A & B. There are pots of gold arranged in a line, each containing some gold coins (the players can see how many coins are there in each gold pot - perfect information). They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to "maximize" the number of coins collected by A, assuming B also plays optimally. A starts the game.
- 352905 February 12, 2013 in United States
The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?
At the end I was asked to code this strategy!| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 29of 29 votes
AnswersYou are given a binary tree with the following node structure:
struct Node { int data; // some data struct Node *left, *right; // References to left and right children struct Node *previous, *next; // References to previous and next nodes };
The tree is initialized with previous = next = NULL for all the nodes.
- codebuddy November 21, 2010
Using the previous and next pointers construct a doubly linked list such that each node's next is the node to its right at the same level and the last node's next is the first node at the next level.(similarly previous). The algorithm should have space complexity O(1). i.e., should be done without using extra data structures.You are given a binary tree with the following node structure| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 25of 27 votes
AnswersGiven a large network of computers, each keeping log files of visited urls, find the top ten of the most visited urls.
- chandeepsingh85 September 26, 2013 in United States
(i.e. have many large <string (url) -> int (visits)> maps, calculate implicitly <string (url) -> int (sum of visits among all distributed maps), and get the top ten in the combined map)
The result list must be exact, and the maps are too large to transmit over the network (especially sending all of them to a central server or using MapReduce directly, is not allowed)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - 25of 25 votes
AnswersThere is an island which is represented by square matrix NxN.
- amnesiac March 01, 2013 in India
A person on the island is standing at any given co-ordinates (x,y). He can move in any direction one step right, left, up, down on the island. If he steps outside the island, he dies.
Let island is represented as (0,0) to (N-1,N-1) (i.e NxN matrix) & person is standing at given co-ordinates (x,y). He is allowed to move n steps on the island (along the matrix). What is the probability that he is alive after he walks n steps on the island?
Write a psuedocode & then full code for function
" float probabilityofalive(int x,int y, int n) ".| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 21of 27 votes
AnswersYou are given two array, first array contain integer which represent heights of persons and second array contain how many persons in front of him are standing who are greater than him in term of height and forming a queue. Ex
- grave August 04, 2013 in India
A: 3 2 1
B: 0 1 1
It means in front of person of height 3 there is no person standing, person of height 2 there is one person in front of him who has greater height then he, similar to person of height 1. Your task to arrange them
Ouput should be.
3 1 2
Here - 3 is at front, 1 has 3 in front ,2 has 1 and 3 in front.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 21of 23 votes
AnswersGiven a undirected graph with corresponding edges. Find the number of possible triangles?
- redsanket March 25, 2014 in United States
Example:
0 1
2 1
0 2
4 1
Answer:
1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 19of 19 votes
AnswersGiven two strings a and b, find whether any anagram of string a is a sub-string of string b. For eg:
- Masterchief117 March 23, 2014 in United States
if a = xyz and b = afdgzyxksldfm then the program should return true.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer String Manipulation - 18of 22 votes
AnswersGiven a BST and a value x. Find two nodes in the tree whose sum is equal x. Additional space: O(height of the tree). It is not allowed to modify the tree
- pavel.em January 26, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 18of 18 votes
AnswersIf a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.
- diffuser78 June 07, 2013 in United States
For example:
Input: "1123". You need to general all valid alphabet codes from this string.
Output List
aabc //a = 1, a = 1, b = 2, c = 3
kbc // since k is 11, b = 2, c= 3
alc // a = 1, l = 12, c = 3
aaw // a= 1, a =1, w= 23
kw // k = 11, w = 23| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm Coding - 17of 21 votes
AnswersYou have the file with word at a single line.
- madeinindia March 24, 2014 in neitherland for perl backend
#input sample file
abactor
abaculus
abacus
Abadite
.
.
Zyrenian
#Output
******************************************************************a
*************b
**********************************c
**********************d
*******************************************************************************e
a) you have to count the character and create a histogram in alphabetical order.
b) now you have to produce a histogram with max 80 character in line in reference to max count
c) now same out based histrogram based on the character count| Report Duplicate | Flag | PURGE
Booking.com Software Engineer / Developer Perl - 16of 18 votes
AnswersOutput top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below:
- John July 15, 2014 in United States
1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 15of 15 votes
AnswersGiven an array having 16000 unique integers, each lying within the range 1<x<20000, how do u sort it. U can load only 1000 numbers at a time in memory.
- vgeek July 27, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 15of 15 votes
AnswersImplement a stack that in addition to push and pop has a function that returns the min value of the stack.
- theProgrammer April 10, 2017 in United States for Alexa
I came up with a O(logn) solution, but he wanted a O(1) for the whole algorithm.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 14of 14 votes
AnswersGiven a 2-D matrix represents the room, obstacle and guard like the following (0 is room, B->obstacle, G-> Guard):
- Obiwana March 10, 2014 in United States
0 0 0
B G G
B 0 0
calculate the steps from a room to nearest Guard and set the matrix, like this
2 1 1
B G G
B 1 1
Write the algorithm, with optimal solution.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 12of 14 votes
Answerswe will name a number "aggregated number" if this number has the following attribute:
- holmespanda November 16, 2012 in United States
just like the Fibonacci numbers
1,1,2,3,5,8,13.....
the digits in the number can divided into several parts, and the later part is the sum of the former parts.
like 112358, because 1+1=2, 1+2=3, 2+3=5, 3+5=8
122436, because 12+24=36
1299111210, because 12+99=111, 99+111=210
112112224, because 112+112=224
so can you provide a function to check whether this number is aggregated number or not?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 12of 12 votes
AnswersGiven 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree.
- bharat June 03, 2013 in India
Ex:
2 3 1
2 1 3
will construct the same tree
A1[]={2,1,3}
2
1 3
A2[]={2,3,1}
2
1 3| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 11of 15 votes
AnswersGiven an int array which might contain duplicates, find the largest subset of it which form a sequence.
- learner October 06, 2011 in -
Eg. {1,6,10,4,7,9,5}
then ans is 4,5,6,7
Sorting is an obvious solution. Can this be done in O(n) time| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Software Engineer / Developer Arrays Algorithm - 11of 13 votes
Answersinput [2,3,1,4]
- balahana March 07, 2014 in United States
output [12,8,24,6]
Multiply all fields except it's own position.
Restrictions:
1. no use of division
2. complexity in O(n)| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 11of 11 votes
AnswersThere are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers?
- CodeKaur August 04, 2014 in United States
Ex:
Servers capacity limits: 8, 16, 8, 32
Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8
For this example, the program should say 'true'.
Ex2:
Server capacity limits: 1, 3
Task capacity needs: 4
For this example, program should return false.
Got some idea that this needs to be solved using dynamic programming concept, but could not figure out exact solution.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 11of 11 votes
AnswersGive a N*N matrix, print it out diagonally.
- Mem February 28, 2014 in United States
Follow up, if it is a M*N matrix, how to print it out.
Example:
1 2 3
4 5 6
7 8 9
print:
1
2 4
3 5 7
6 8
9
This is the question in the phone interview.
Please share more questions.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 10of 12 votes
AnswersGiven an equation in the form 2^i * 3^j * 5^k * 7^l where i,j,k,l >=0 are integers.write a program to generate numbers from that equation in sorted order efficiently.
- Rohit July 29, 2013 in United States
for example numbers from that equation will be in the order 2,3,5,6,7,8,9.....and so on..| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 10of 10 votes
AnswersConsider a hash table with M slots. Suppose hash value is uniformly distributed between 1 to M, and it uses linked list to handle conflicts (if two keys hashed to the same slot). Suppose we put N keys into this M-slotted hash table, what is the probability that there will be a slot with i elements? i could vary from 0 to N.
- seanren7 August 13, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Hash Table - 10of 10 votes
AnswersGiven a function KNOWS(A,B), which returns 1 if A knows B (and not necessarily the other way around) and 0 if A does not know B.
- asafiniu February 27, 2013 in United States
A Celebrity is one who does not know anyone,
and one who is known by everybody.
For a list of N people, find all celebrities in linear time.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 10of 10 votes
AnswersYou want to create a staff to use in your martial arts training, and it has to meet some specific requirements.
- krvangala98 April 25, 2014 in United States
1. You want it to be composed of two smaller staves of equal length so that you can either use it as a single staff or as two smaller ones.
2. You want the full sized staff's center of gravity to be exactly in the middle of the staff.
You have a very, very long branch from which you can cut the pieces for your staff. The mass of the branch varies significantly throughout it, so you use just any two pieces of the same length. Given a description of the mass throughout the branch, determine the longest staff you can make, then return three integers on a single line, the first two indicating the first index of each half-staff, and the third indicating the length of each half-staff.
The input will be given on a single line as a string of digits [1-9], each digit representing the mass of a section of the branch. All sections are the same size and the maximum length of the string is 500. Here is an example:
41111921111119
11119 11119
If the indicated sections are cut from the branch they will satisfy your requirements. They are both the same length, and they can be put together as either 9111111119 or 1111991111, both of which have a center of gravity exactly in the center of the staff.
Center of gravity can be determined by taking a weighted average of the mass of each section of the staff. Given the following distances and masses:
Distance: 12345678
Mass: 22241211
Sum of the mass of each section: 2 + 2 + 2 + 4 + 1 + 2 + 1 + 1 = 15
Weighted sum of the masses:
2*1 + 2*2 + 2*3 + 4*4 + 1*5 + 2*6 + 1*7 + 1*8 = 60
Weighted sum / regular sum = 60 / 15 = 4
This means that the center of mass is in section 4 of the staff. If we wanted to use this staff the center of gravity would need to be (8+1)/2 = 4.5.
Here is an example problem:
131251141231
---- ----
If we take the sections indicated we get 1312 and 1231. By reversing the first one and putting them together we get 21311231
Sum of the mass of each section: 2 + 1 + 3 + 1 + 1 + 2 + 3 + 1 = 14
Weight sum of the masses:
2*1 + 1*2 + 3*3 + 1*4 + 1*5 + 2*6 + 3*7 + 1*8 = 63
Weighted sum / regular sum = 63 / 14 = 4.5
This puts the center of mass exactly in the center of the staff, for a perfectly balanced staff. There isn't a longer staff that can be made from this, so the answer to this problem is
0 8 4
Because the half-staves begin at indices 0 and 8 (in that order) and each is of length 4.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 9of 11 votes
AnswersGiven a number N, write a program that returns all possible combinations of numbers that add up to N, as lists. (Exclude the N+0=N)
- ootah November 14, 2013 in United States
For example, if N=4 return {{1,1,1,1},{1,1,2},{2,2},{1,3}}| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 9of 9 votes
AnswersGiven an array of integers, sort the array into a wave like array, namely
- Zen April 22, 2014 in United States
a1 >= a2 <= a3 >= a4 <= a5.....| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
AnswersGiven an array of integers, find all combination of four elements in the array whose sum is equal to a given value X.
- sai September 04, 2012 in India
For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and X = 23, then your function should print “3 5 7 8″ (3 + 5 + 7 + 8 = 23).| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 9of 9 votes
AnswersQuestion was "Given a pattern and a string input - find if the string follows the same pattern and return 0 or 1.
- David_Maxwell November 24, 2014 in United States
Examples:
1) Pattern : "abba", input: "redbluebluered" should return 1.
2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.
I can think of a brute-force solution for this question where we add the character in the pattern and n length of the string to a hashmap and recurse over the pattern array and string. But is there anything more efficient? This was a pretty difficult question in my opinion.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
Answersyou are given n-strings 1you have to find whether a chain can be termed with all the strings given number n? A chain can be formed b/w strings if last char of the 1st string matches with 1st char of second string. For example you are given
- Rahul Sharma October 03, 2013 in India
number of strings = 3
first string=sdfg
second string=dfgs
third string=ghjhk
they can be concatenated as ->
second first third
dfgs sdfg ghjhk (characters at concatenation points are same)
so concatenated string is-dfgsdfghjhk| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm