Software Engineer Interview Questions
- 0of 0 votes
AnswersC program to accept two strings and print characters which are not present in first string.
- genny October 26, 2015 in India
Example: 1 string: apple
2 string: aeroplane
output: ro| Report Duplicate | Flag | PURGE
Adobe Software Engineer Algorithm - 2of 2 votes
AnswersYou are given a set of points on x axis (consumers)
- emb October 22, 2015 in United States
Also you are given a set of points on a plane (producer)
For every consumer print the nearest producer.
Wanted something better than O(n^2) time.
Example:
consumers: 1 5 7
producers: (0, 3), (1,1), (3, 2), (8, 10), (9, 100)
Answer:
for 1 nearest producer is (1, 1), for 5 nearest is (3, 2), for 7 nearest is (3, 2)
Follow-up question: now both sets are sorted by x coordinate. Could you come up with a linear algorithm?| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersYou have some money in your bank account, the only function to withdraw money is uint16 Withdraw(uint16 value), if the value is greater than the money you have it returns 0, otherwise it withdraws the requested amount and returns the "value"
- mike.radula October 13, 2015 in United States
Write a function that withdraws all your money.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersRearrange characters in a string so that no character repeats twice.
- pcinterview October 10, 2015 in United States
Input: aaabc
Output: abaca
Input: aa
Output: No valid output
Input: aaaabc
Output: No valid output| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersHow would you implement an LRU cache using just a *single* container ? i.e., map or unordered_map ?
- pavel.em October 07, 2015 in United States
The cache must support operations:
1. value_t find(key_t) - find a certain value in cache
2. insert(key_t, value_t) - insert a new value to the cache (with optionally deleting an LRU entry)| Report Duplicate | Flag | PURGE
Software Engineer C++ - 3of 5 votes
AnswersThere are several people sitting in the cinema, some of them are couples, some are not, they decide to swap their seats so that the couples can seat together, please calculate the minimal swap numbers.
- xblwyc October 07, 2015 in United States
1. the swap can happen between any two position.
2. E.g. AABCCDB -> AADCCBB, ans is 1| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
Answersthere are N cities (numbered from 1 to N) in the game and connect them by N-1 highways. It is guaranteed that each pair of cities are connected by the highways directly or indirectly.The game has a very important value called Total Highway Distance (THD) which is the total distances of all pairs of cities. Suppose there are 3 cities and 2 highways. The highway between City 1 and City 2 is 200 miles and the highway between City 2 and City 3 is 300 miles. So the THD is 1000(200 + 500 + 300) miles because the distances between City 1 and City 2, City 1 and City 3, City 2 and City 3 are 200 miles, 500 miles and 300 miles respectively.
- hulei660066 October 06, 2015 in United States for bing
During the game the length of some highways may change. you want to know the latest THD.
sample input
3 5
1 2 2
2 3 3
QUERY
EDIT 1 2 4
QUERY
EDIT 2 3 2
QUERY
sample output
10
14
12| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 2of 2 votes
AnswersYou are given a permutation arr[N]. E.g. arr[3] = {2, 1, 0} or arr[5] = {0,1,2,4,3};
- emb October 05, 2015 in United States
Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, k-th order statistic on slice [a:b] of arr.
E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it - get [0,1,5] and take k-th element, that is - 5.
Implement request(a, b, k) function. You can preprocess input data, that is, assume there will be only one array and many request() calls.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswerTest Question
- rafitoapp1 October 02, 2015 in United States| Report Duplicate | Flag | PURGE
ThoughtWorks Software Engineer Java - 0of 0 votes
AnswersProblem Two: Conference Track Management
- rafitoapp1 October 02, 2015 in United States
You are planning a big programming conference and have received many proposals which have passed the initial screen process but you're having trouble fitting them into the time constraints of the day -- there are so many possibilities! So you write a program to do it for you.
• The conference has multiple tracks each of which has a morning and afternoon session.
• Each session contains multiple talks.
• Morning sessions begin at 9am and must finish by 12 noon, for lunch.
• Afternoon sessions begin at 1pm and must finish in time for the networking event.
• The networking event can start no earlier than 4:00 and no later than 5:00.
• No talk title has numbers in it.
• All talk lengths are either in minutes (not hours) or lightning (5 minutes).
• Presenters will be very punctual; there needs to be no gap between sessions.
Note that depending on how you choose to complete this problem, your solution may give a different ordering or combination of talks into tracks. This is acceptable; you don’t need to exactly duplicate the sample output given here.
Test input:
Writing Fast Tests Against Enterprise Rails 60min
Overdoing it in Python 45min
Lua for the Masses 30min
Ruby Errors from Mismatched Gem Versions 45min
Common Ruby Errors 45min
Rails for Python Developers lightning
Communicating Over Distance 60min
Accounting-Driven Development 45min
Woah 30min
Sit Down and Write 30min
Pair Programming vs Noise 45min
Rails Magic 60min
Ruby on Rails: Why We Should Move On 60min
Clojure Ate Scala (on my project) 45min
Programming in the Boondocks of Seattle 30min
Ruby vs. Clojure for Back-End Development 30min
Ruby on Rails Legacy App Maintenance 60min
A World Without HackerNews 30min
User Interface CSS in Rails Apps 30min
Test output:
Track 1:
09:00AM Writing Fast Tests Against Enterprise Rails 60min
10:00AM Overdoing it in Python 45min
10:45AM Lua for the Masses 30min
11:15AM Ruby Errors from Mismatched Gem Versions 45min
12:00PM Lunch
01:00PM Ruby on Rails: Why We Should Move On 60min
02:00PM Common Ruby Errors 45min
02:45PM Pair Programming vs Noise 45min
03:30PM Programming in the Boondocks of Seattle 30min
04:00PM Ruby vs. Clojure for Back-End Development 30min
04:30PM User Interface CSS in Rails Apps 30min
05:00PM Networking Event
Track 2:
09:00AM Communicating Over Distance 60min
10:00AM Rails Magic 60min
11:00AM Woah 30min
11:30AM Sit Down and Write 30min
12:00PM Lunch
01:00PM Accounting-Driven Development 45min
01:45PM Clojure Ate Scala (on my project) 45min
02:30PM A World Without HackerNews 30min
03:00PM Ruby on Rails Legacy App Maintenance 60min
04:00PM Rails for Python Developers lightning
05:00PM Networking Event| Report Duplicate | Flag | PURGE
ThoughtWorks Software Engineer Java - 1of 1 vote
AnswersTest Question, this is a test question
- rafitoapp1 October 02, 2015 in United States| Report Duplicate | Flag | PURGE
ThoughtWorks Software Engineer Java - 0of 0 votes
AnswersDesign a train system which suggests shortest path and transfer needed to reach from source to destination. What can be the optimization.
- hm September 30, 2015 in United States
For example:
A system may have 10 trains from t1 to t10.
There are total 100 stops in the system s1 to s100.
Each train has fixed set of stops. You could allow to change and transfer train of source and destination does not cover using just 1 train.
What all can be APIs, data structure, optimizations scalable option.| Report Duplicate | Flag | PURGE
Software Engineer Algorithm Problem Solving Software Design System Design Trees and Graphs design - 8of 8 votes
AnswersGiven an array int32 arr[] of size n, return the number of non-empty contigious subarrays whose sum lies in range [a, b]
That is, implement the following naive algorithm faster than O(n^2)def naive_algorithm(lst, a, b): result = 0 for i in xrange(len(lst)): for j in xrange(i, len(lst)): if a <= sum(lst[i:j + 1]) <= b: result += 1 return result
Examples:
count([1,2,3], 0, 3) = 3 # [1], [2], [3], [1, 2], [3] count([-2,5,-1], -2, 2) = 3 # [-2], [-1], [-2, 5, -1]
You may assume that there are no overflows, that is sum(|x_i|) <= MAX_INT - 1
- emb September 26, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersWrite Program for String Permutations using most efficient algorithm. Can you solve problem in O(n) time ?
- dev123 September 23, 2015 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 1of 5 votes
AnswersYou are given an array of n unique integer numbers 0 <= x_i < 2 * n
- emb September 23, 2015 in United States
Print all integers 0 <= x < 2 * n that are not present in this array.
Example:
find_missing([0]) = [1]
find_missing([0, 2, 4]) = [1, 3, 5] # because all numbers are [0, 1, 2, 3, 4, 5]
find_missing([]) = []
find_missing([0, 1, 4, 5]) = [2, 3, 6, 7] # because all numbers are [0, 1, 2, 3, 4, 5, 6, 7]
Quirks are about requirements:
Time complexity O(n) - BUT there should be some fixed constant C independent of size of input such that every element of array is written/read < C times, so radix sorting the array is a no go.
Space complexity O(1) - you may modify the initial array, BUT sorted(initial_array) must equal sorted(array_after_executing_program) AND you can't store integers outside range [0, 2n) in this array (imagine that it's an array of uint32_t).| Report Duplicate | Flag | PURGE
Google Software Engineer Brain Teasers - 1of 1 vote
AnswersYou are given large numbers of logs, each one of which contains a start time (long), end time (long) and memory usage (int). The time is recorded as MMDDHH (100317 means October 3rd 5PM) Write an algorithm that returns a specific time (hour) when the memory usage is the highest. If there are multiple answers, return the first hour.
- aijackmoore September 21, 2015 in United States
e.g. 100207 100208 2
100305 100307 5
100207 100209 4
111515 121212 1
Answer: 100207
(Need to consider different scenarios like the time slots could be very sparse)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersWrite a program to process the matrix. If an element is 0 at ith row and jth column, then make the whole ith row and jth column to 0.
- codealtecdown September 17, 2015 in United States
Constraints:
Space complexity should be O(1)
Time complexity - Only single pass is allowed. Note that single pass is not O(n). This is single pass : An element will read and written only ones.
Edit:
Recursion is not allowed since it is O(n) space on stack| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 2of 2 votes
AnswersGiven an array of task and k wait time for which a repeated task needs to wait k time to execute again. return overall unit time it will take to complete all the task.
- hm September 14, 2015 in United States
Example:
1. A B C D and k = 3
ans: 4 (execute order A B C D)
2. A B A D and k = 3
ans: 6 (execute order A B . . A D)
3. A A A A and k =3
ans: 13 (A . . . A . . . A . . . A)
4. A B C A C B D A and k = 4
ans: 11 (A B C . . A .C B D A )| Report Duplicate | Flag | PURGE
Twitter Software Engineer Algorithm - 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 - 0of 0 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;
};
To simplify you can modify the structure.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm C++ Trees and Graphs - 0of 0 votes
AnswersHow would you implement X-ray for Kindle? X-ray is an index of characters in a book that shows how often a character appears in the book, and at which places. I was explained how this index works, and what it will look like on the book. There re more details here: http://www.amazon.com/gp/help/customer/display.html?nodeId=200729910
- ravishchawla September 10, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 1of 1 vote
Answers. Given n strings consisting of ‘R’ and ‘B’. Two strings can be only combined if last character of first string and first character of second string are same. Given n strings, you have to output the maximum length possible by combining strings.
- ritwik_pandey September 09, 2015 in United States
I/P
RBR
BBR
RRR
output : 9| Report Duplicate | Flag | PURGE
Walmart Labs Software Engineer Algorithm - 2of 2 votes
AnswersThere's a very simple compression algorithm that takes subsequent characters and just emits how often they were seen.
- Phil September 08, 2015 in Netherland
Example:
abababaabbbaaaaa| Report Duplicate | Flag | PURGE
Booking.com Software Engineer Algorithm - 3of 3 votes
Answers$a = [3, 1, 4, 5, 19, 6];
$b = [14, 9, 22, 36, 8, 0, 64, 25];
# Some elements in the second array are squares.
- Phil September 08, 2015 in Netherland
# Print elements that have a square root existing in the first array.
# $b[1] = 9, it’s square root is 3 ($a[0])
# $b[3] = 36, it’s square root is 6 ($a[5])
# $b[7] = 25, it’s square root is 5 ($a[3])
# Result:
# 9
# 36
# 25| Report Duplicate | Flag | PURGE
Booking.com Software Engineer Algorithm - 2of 4 votes
AnswersYou are given a matrix n rows, m columns where each row is sorted in increasing order. Find median of the overall elements. What is the time complexity?
- emb September 07, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersYou are given a flat room 1x1 metres, a position of victim in it (v_x, v_y) and a position of a killer (k_x, k_y) both inside this room (in range [0, 1]).
- emb September 06, 2015 in United States
Then the killer shoots once at some direction. The bullet reflects of the walls as if it was a light ray - if it falls under angle X degrees, it will reflect at angle X degrees, if it gets into the corner it just reflects back. If the bullet hits guardian (see below) it stops and killer fails.
Write a function that will be given coordinates of victim and a killer and will return a list of coordinates of guardians such that it's impossible for a killer to kill victim.
That is, whichever direction the killer will shoot, the bullet will never reach victim, or will be stopped by a guardian.
Here is an example for the case when we assume the walls don't reflect bullet (for simplicity):
killer: (0, 0), victim: (1, 1). The solution to this simplified problem is to place 1 guardian between killer and victim e.g. on (0.1, 0.1).
Your task is to do this with accounting bullet reflection. E.g. in the previous case the killer can shoot at (1/3, 1), the bullet will reflect to (2/3, 0) and finally get to the victim at (1, 1).| Report Duplicate | Flag | PURGE
Google Software Engineer Brain Teasers - 0of 0 votes
AnswersImplement a method for the following signature:
void * alignedAllocate(size_t sizeInBytes, size_t alignment) { }
The method should allocate memory for the given size and the pointer should be aligned.
For example ifp = alignedAllocate(1000,64);
p%8 should be 0.
- thewhatwhat September 05, 2015 in United States
Implement a second method that deleted the pointer give p.
Extend the delete method to handle multiple p's.| Report Duplicate | Flag | PURGE
Google Software Engineer C C++ - 0of 0 votes
AnswersGiven a 2-dimensional square matrix, rotate the matrix clockwise. Imagine concentric circles. Input from stdin: first line is length, subsequent lines are rows of the matrix. Output the matrix to stdout. This was one of the questions. You have 2 hrs to complete it.
- Yev September 02, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer Java - 0of 0 votes
AnswersGiven a positive integer, rearrange its digits to find the greatest positive integer. Expected time/space complexity O(1). I was to do this in space O(1), time O(n).
- Yev September 01, 2015 in United States| Report Duplicate | Flag | PURGE
OptionsCity Software Engineer Java - 1of 1 vote
AnswersWrite function to determine if given unsigned 32-bit number is a power of 3
int is_power_of_3(uint32_t n)
return 1 if yes, 0 otherwise.
e.g.is_power_of_3(27) = 1 is_power_of_3(9) = 1 is_power_of_3(42) = 0 is_power_of_3(0) = 0
Expected the answer not to be straightforward loop, but something faster.
- emb August 28, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Math & Computation