Software Engineer / Developer Interview Questions
- -2of 2 votes
AnswersHow to design an elevator system. Main thing to worry about is how would you notify the elevator that it needs to move up or down. and also if you are going to have a centralized class to control this behavior and how could you distribute the control.
- Guy February 11, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Object Oriented Design - 0of 0 votes
AnswersWrite an application in Java to simulate file system. For e.g. implement commands: ls -l (list contents of director sorted by name), cd .. (to go to parent directory), etc. It was a 2 hour remote programming test.
- techpanja February 11, 2014 in United States| Report Duplicate | Flag | PURGE
Samsung Software Engineer / Developer - -4of 6 votes
AnswersGiven a binary tree, how would you copy it from one machine to the other, assume you have a flash drive. I believe we should write the binary tree to file and have the other machine de-serialize it. But how should we do it?
- Guy February 10, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -2of 2 votes
Answersarray where indexes correspond to the tree node number of a parent node, and values correspond to current tree node number., root having number -1 Write code to recreate a tree. (I was confusing about what the array index and value really represent)
- Guy February 10, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - -11of 11 votes
Answerslargest number that an int variable can fit given a memory of certain size
- Guy February 10, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -5of 7 votes
AnswersImplement a class to create timer object in OOP
- Guy February 10, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Object Oriented Design - -9of 9 votes
AnswersWhat's the tracking algorithm of nearest location to some friends that are located in a grid region?
- Guy February 10, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -5of 7 votes
AnswersHow would you split a search query across multiple machines?
- Guy February 10, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - 0of 0 votes
AnswersFill in the following methods:
- abhinav February 09, 2014 in United Statespublic interface PointsOnAPlane { /** * Stores a given point in an internal data structure */ void addPoint(Point point); /** * For given 'center' point returns a subset of 'm' stored points that are * closer to the center than others. * * E.g. Stored: (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) * * findNearest(new Point(0, 0), 3) -> (0, 1), (0, 2), (0, 3) */ Collection<Point> findNearest(Point center, int m); }
| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm - 1of 1 vote
AnswersQuestion 2 / 2 (Weighted Stone Arrangement)
- kri1311 February 09, 2014 in India
You are given an infinite number of stones.
The 1st stone has the weight 1
The 2nd stone has the weight 3
The tth stone has the weight W(t) = 2 * W(t-1) + W(t-2)
Thus, the weights of the first 10 stones are
1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363
Note that you only have one stone of each weight.
You have a weighing machine which is the age old 2-pan balance. You wish to use this machine to measure the weight of an item whose weight is T. The item will always be kept on the right pan. A stone may be kept on either one of the pans. Also, it is not required to use all the stones.
The stones have a weird magnetic property, due to which, the kth stone cannot be in the same pan as the (k-1)th stone. This means that the stone with weight 239 cannot be in the same pan as the stone with weight 99, or in the same pan as the stone with weight 577; and so on.
For example,
T = 11 can be measured as
LEFT PAN: 1, 17
RIGHT PAN: 7
Note that the other alternative
LEFT PAN: 1, 3, 7
RIGHT PAN:
is Illegal since 3 cannot be in the same pan as 1 (or 7 cannot be in the same pan as 3).
T = 21 can be measured as
LEFT PAN: 41
RIGHT PAN: 3, 17
It can be proven that to measure any weight T, there exists a unique arrangement of stones that satisfy the given constraints and measure weight T. Thus, T = 11 or T = 21 can only be measured by the respective arrangements above.
You are given T in the input. Output the arrangement of stones that measures T.
Input Specification
The input contains a single positive integer T.
Output Specification
Output the weights of the stones used on the left pan in increasing order, one number per line. Then output a blank line. Followed by the weights of the stones used on the right pan in increasing order. Note that it is assumed that the item will be kept on the right pan.
If there is no stone kept on the right pan, simply output the weights of the stones used on the left pan in increasing order as above, followed by a blank line.
Constraints
1 ≤ T ≤ 1015
Sample Input 1
11
Sample Output 1
1
17
7
Sample Input 2
21
Sample Output 2
41
3
17
Sample Input 3
1000
Sample Output 3
3
41
239
1393
99
577| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Coding - 0of 0 votes
AnswerDirecti Off Campus Interview Process 2013-14
- kri1311 February 09, 2014 in India
.......................................................................
This is year 4096 and humans have found a medicine for immortality in the year 2048. Tukro a famous online social networking site founded in the year 3072 was celebrating its 1024th anniversary. To celebrate the occasion its CEO, Shark, and his team had launched a unique personalised video of length 17min 4sec for each user. The video consisted of a collage of all popular posts made by the user on Tukro.
Raka shared this video with all his friends without reviewing it. Immediately after he finished watching the 1024 second length clip he realised that he made a huge mistake. The video was made of all posts made by Raka, irrespective of the privacy settings of the individual post.
A post is compromised if a friend who was not supposed to see the original post, has seen it now. Raka wants to know how many of his posts have been compromised. Tukro provides the list of users who have watched the video till now. Help Raka find how many posts were compromised.
Raka has N friends, identified by a unique integer between 0 and N-1.
Raka has L lists of friends, identified by a unique integer between 0 and L-1.
Each list can be of length at the most N.
One friend cannot be added more than once to the same list.
A list must have at least one friend.
A friend may be added to multiple lists.
Visibility of a post in Tukro works through two filters
Include Filter: An array of lists, from the L lists above. Friends can view a post if they belong to any friend list, specified in the Include Filter.
Exclude Filter: An array of lists, from the L lists above. Friends can view a post if their name does not belong to any friend list, specified in the Exclude Filter.
Some caveats of the above are
If no Filter is active, the post is visible to all friends
If only Include Filter is active, a friend can see the post only if he is present in at least one of the lists of Include Filter.
If only Exclude Filter is active, a friend can see the post only if he is not present in any of the lists of exclude filter.
If both Include and Exclude Filters are active, a friend can see the post if and only if
he is present in at least one of the lists of include filter and
he is not present in any of the lists of exclude filter
if he is present in both an include filter list, and exclude filter list, he should not be able to see the post
Input Specification
First line contains a single integer N, the number of friends.
Second line contains a list of integers separated by a single space. The first integer V, represents the number of friends who viewed the video. There are V other integers in the line representing the ID's of friends who viewed the video.
Third line contains a single integer L representing the number of lists.
L lines follow. Each line representing a list. The first integer of the line A, denotes the size of the list; followed by A integers, each denoting the friends in the list.
Next line contains a single integer P denoting the number of posts in the video. 2 * P lines follow. Each pair denoting the Include Filter and Exclude Filters of one post respectively.
First two lines denote the Include and Exclude Filters for first post
Next two lines denote the Include and Exclude Filters of second post
and so on..
An include filter is represented by a list of space separated integers. The first integer B represents the number of lists in the filter. B may be 0, to denote that the include filter is not active. If B is more than 0, the include filter is active and the next B integers in the line denote the ID's of lists present in the include filter.
Exclude filters are also represented in the same format.
Output Specification
Print a single integer specifying the number of posts that are compromised according to the definition above.
Constraints
1 ≤ N ≤ 10000
1 ≤ V ≤ N
1 ≤ L ≤ 6
1 ≤ P ≤ 100000
Note that the constraints on N and P are large.
Your solution will exceed time limits if its complexity is O(N*P).
Even O(V*P) solutions may exceed time limit!
Note the small constraint on L.
Sample Input 1
10
8 1 2 5 6 0 9 8 7
4
2 4 3
2 7 6
3 0 1 5
3 2 8 9
4
0
1 0
1 1
0
0
0
3 1 2 3
0
Sample Output 1
1
Explanation
There are 10 friends. Their ID's are from 0 to 9
8 of them viewed the video = {0,1,2,5,6,7,8,9}
There are 4 lists
List-0 has 2 friends {3,4}
List-1 has 1 friend {7,6}
List-2 has 3 friends {0,1,5}
List-3 has 3 friends {2,8,9}
There are 4 posts
Post-0 doesn't have any include filter but has List-0 - {3,4} - in exclude filter
3, or 4, have not seen the video
Hence Post-0 is not compromised
Post-1 has an include filter of List-1 - {7,6} - and no exclude filter.
But other friends have seen the video
Hence Post-1 is compromised
Post-2 doesn't have any filters. Such a post was intended to be seen by anyone.
Hence Post-2 is not compromised.
Post-3 has a include filter of List-1, List-2 and List-3.
Their union is {0,1,2,5,6,7,8,9}
These are the exact friends who saw the video
Hence Post-3 is not compromised
Hence only 1 post is compromised.
Sample Input 2
5
2 2 3
5
1 0
1 1
1 2
1 3
1 4
4
3 2 3 4
1 0
3 1 2 3
0
3 0 1 3
0
3 2 3 4
1 0
Sample Output 2
1| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Coding - -5of 7 votes
AnswersGiven a list of strings. Produce a list of the longest common suffixes. If it asks for longest common substring, then building a suffix tree should be the way to go. But how should we implement this if it is for longest common suffixes?
- Guy February 09, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a source string say "xxyyxxx" and a destination string say "xxxxyyx" and the number of steps, determine whether the source can be changed to the destination in the given steps..
- hari.r.krishnaa February 08, 2014 in India
One step is where you can change x to y or y to x or rotate the whole string by 1 element either left of right..
Example:
xxxyyxx and yxxxxxy and steps 5
Answer would be yes, as we can reach the number by rotating 3 steps and swapping a character twice..| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 0of 0 votes
AnswersA number of intersecting bridges is given.Remove minimum number of bridge to make remaining bridges non-intersecting.
- george February 07, 2014 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - -6of 6 votes
AnswersIf you have data coming in rapid succession what is the best way of dealing with redundant data?
- Guy February 06, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 1of 1 vote
AnswersIn a book with N pages, pages are numbered from 1 to N. Find out how many times
- samar.pratap.singh.bundela February 06, 2014 in India for payments
each digit occurs in that book.
You are expected to complete the function getDigitslnBook, which takes an integer as input and
prints how many times each digits occur, one in a line.
The Nth line in the output denotes how many times the integer N-1 occurs in page numbers.
Constrains:
N will be between 1 and 1,000,000,000, inclusive.
The output will fit in an integer.
Sample lnputOO:
7
Sample Outputo : 0
1
0
0
Explanation :
The page numbers are 1,2, 3,4, 5, 6 and 7.
Sample lnput01: 11
Sample Output01:
1
4
Explanation:
Digit 1occurs 4 times, at 1,10 and 11.Rest of the digits occurs only once.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Math & Computation - -7of 7 votes
AnswersHow would you use Dijkstra's algorithm to solve travel salesman problem, which is to find a shortest path from a starting node back to the starting node and visits all other node exactly once.
- Guy February 06, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersI was asked a question in an interview.
- Park February 06, 2014 in India
On an office floor , there are e entities - Walls , Cubicles , Coffee Rooms.
In what data structure we should store this design that when a new member joins the company , the cubicle number which is empty and next closest to any coffee room should be assigned to it.
Basically , data structure DS.pop() should return that cubicle number in the most efficient way.
A Person can walk through cubicles to reach a coffee room but not through walls.| Report Duplicate | Flag | PURGE
Motorola Software Engineer / Developer Data Structures - -3of 5 votes
AnswersHow does trie handle scalability as opposed to hashtable? Assuming it is used for a dictionary. Sclability here should cover large size of input, running out of memory, or even running out of memory on multiple machines if distributed system is used.
- Guy February 06, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design - 0of 0 votes
AnswersGiven the following 3 by 3 grid where the (first row, first column) is represented by (0,0):
- RashnaRazdan February 05, 2014 in United States
0,1 1,2 3,3
1,1 3,3 3,2
3,0 1,3 null
we need to find if we can get to each cell in the table by following the cell locations at the current cell we are at. We can only start at cell (0,0) and follow the cell locations from that cell, to the cell it indicates and keep on doing the same for every cell.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a Text String T: abbbacctlkjlkcccaaabbb and pattern string P: ab[.]*c[.]*b, Find all occurances of P in T
- ssikka25 February 05, 2014 in United States for Amazon Prime| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a Text String T: aaabbbzzccc
- ssikka25 February 05, 2014 in United States for Prime
and pattern string P: ab , Find all occurances of P in T| Report Duplicate | Flag | PURGE
Amazon 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 - -3of 3 votes
AnswersFind a triplet that sum to a given value in an array of integers. I know it can be done in O(n^2) with either using a hashmap(space O(n)) or pre-sorting(space O(1)) the array. Is there any way to do this better than O(n^2)?
- Guy February 05, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 4 votes
AnswersDesign a program that would select which elevator in a building would be the most efficient, based on where the elevator is located and headed and where the user is located and headed.
- Guy February 04, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Object Oriented Design - 0of 4 votes
AnswersPrint all the elements in an array that have occurred an odd number of times. I know we can XOR all numbers, but that only solves the problem where there is only one odd number in the array. But I was asked to find all of them. Another method I can think of is to keep one hashset, then walk through the array, if the number is in the map, remove it. If the number is not present, add it. But this requires O(n) space. Is there any way to do this with O(n) time and O(1) space?
- Guy February 04, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answers
- juny February 04, 2014 in United Statespublic interface Intervals { /** * Adds an interval [from, to] into internal structure. */ void addInterval(int from, int to); /** * Returns a total length covered by intervals. * If several intervals intersect, intersection should be counted only once. * Example: * * addInterval(3, 6) * addInterval(8, 9) * addInterval(1, 5) * * getTotalCoveredLength() -> 6 * i.e. [1,5] and [3,6] intersect and give a total covered interval [1,6] * [1,6] and [8,9] don't intersect so total covered length is a sum for both intervals, that is 6. * * _________ * ___ * ____________ * * 0 1 2 3 4 5 6 7 8 9 10 * */ int getTotalCoveredLength(); }
| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm - -8of 8 votes
Answerssort the array so that the odd number in front of the even number and their relative order doesn't change in Time O(n) and Space O(1). I believe quickselect can do this, but it will change the relative order of the input.
- Guy February 01, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answers/**
- juny January 31, 2014 in United States
* Return the smallest character that is strictly larger than the search character,
* If no such character exists, return the smallest character in the array
* @param sortedStr : sorted list of letters, sorted in ascending order.
* @param c : character for which we are searching.
* Given the following inputs we expect the corresponding output:
* ['c', 'f', 'j', 'p', 'v'], 'a' => 'c'
* ['c', 'f', 'j', 'p', 'v'], 'c' => 'f'
* ['c', 'f', 'j', 'p', 'v'], 'k' => 'p'
* ['c', 'f', 'j', 'p', 'v'], 'z' => 'c' // The wrap around case
* ['c', 'f', 'k'], 'f' => 'k'
* ['c', 'f', 'k'], 'c' => 'f'
* ['c', 'f', 'k'], 'd' => 'f'
*/| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm