Software Engineer Interview Questions
- 0of 0 votes
AnswersA graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted edges given in K. If it creates a path, we have to discard the edge.
- neer.1304 July 03, 2019 in United States
Example: N = 4; K = {(1, 4)}; M = {(1, 2), (2, 3), (3, 4)}. Here, addition of edge (3, 4) will create a path between 1 and 4. Hence we discard edge (3, 4)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - -1of 1 vote
AnswersYou are given 2 strings which are exactly same but 1 string has an extra character. Find that character.
- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswerYou are given an array of million numbers and provided a range of index (say left, right). For multiple queries, each with input left and right indexes, output the maximum in that range.
- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven (x, y) coordinates, create a function such that each coordinate is uniquely mapped to an integer. Also make sure that given an integer, you should be able to find (x, y) coordinates. So F(x, y) = z and also that inverse F(z) = (x, y).
- neer.1304 July 03, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersWe have to paint n boards of length {A1, A2…An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get
- neer.1304 July 03, 2019 in United States
this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
Input : k = 2, A = {10, 10, 10, 10}
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter
gets 20 units of board and the total
time taken is 20.
Input : k = 2, A = {10, 20, 30, 40}
Output : 60.
Here we can divide first 3 boards for
one painter and the last board for
second painter.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswerSelect a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid).
- acoding167 June 19, 2019 in United States
Follow-up: Given multiple non-overlapped rectangles on the 2D grid, uniformly select a random point from the rectangles.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersGiven range of routing numbers, determine which bank it belongs to.
- neer.1304 June 08, 2019 in United States
Ex-
I/p -(123400,123500, BOA), (12538, 12548, GCU)…
For 123450 - Output BOA
12540 - Output GCU| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersFind whether string S is periodic.
- acoding167 June 07, 2019 in United States
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"
follow up:
Given string S, find out the P (repetitive pattern) of S.| Report Duplicate | Flag | PURGE
Facebook Software Engineer - -1of 1 vote
Answerswrite a JSON validator
- boony June 04, 2019 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersGiven two two integer arrays. Find the longest common subsequence.
- acoding167 June 02, 2019 in United States
eg: a =[1 5 2 6 3 7], b = [5 6 7 1 2 3]. return [1 2 3] or [5 6 7]| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersHas anyone interviewed with Microsoft, Fargo North Dakota? Care to share the experience and some interview questions?
- Glorious May 20, 2019 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer - 5of 5 votes
AnswersTree Game
- aonecode May 17, 2019 in United States
class TreeNode {
TreeNode parent; //parent node
TreeNode left; //left child
TreeNode right; //right child
}
Two people in a game, player scores by claiming nodes in binary tree, tree node class as shown above.
The player who eventually owns more nodes wins the game.
Player A and B each claims a node at first.
After the first round, a player will only be able to claim a node adjacent to any node owned by himself.
A tree node is adjacent to its parent, left right and right child.
A node owned cannot be re-claimed.
End game when all nodes are owned.
If player A gets the first claim at node N, find whether it is possible for player B to win.
If yes, find out which node player B should claim at his first move.
Follow up: if player B takes the first hand instead, which node should he pick?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGive m balls and n bins. Find out how many ways to assign balls to bins. Notice the buckets has no order. Like (1,2,3) and (3,2,1) are considered the same.
- acoding167 May 16, 2019 in United States
eg, m = 3, n = 2, return 2. (1, 2) and (3, 0)| Report Duplicate | Flag | PURGE
Amazon Software Engineer - 0of 0 votes
AnswerGiven items as Shirt, Trouser, Shoes, Tie, Belt, Shocks, and dependencies as -
- alisonlee659 May 15, 2019 in United States
Tie can be worn after Shirt
Belt can be worn after Shirt and Trouser
Shocks can be worn after Trouser
Shoes can be worn after Shocks
Find various orders in which the activity of wearing clothes can be completed.| Report Duplicate | Flag | PURGE
Amazon Software Engineer - 0of 0 votes
AnswersWrite your own class for key value store which has four methods:
- Desi May 14, 2019 in United States for ATG
put(key,value)
get(key)
getRandom() this should return a random value with equal probability
deleteWithKey(key)
I was allowed to use hashmap internally to store data.
this was my second technical phone interview because they wanted to get some more idea about my technical skills.| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 0of 0 votes
AnswersAt first Interviewer asked me to write a problem to solve sudoku and return error if sudoku is invalid.
- Desi May 14, 2019 in United States for ATG
I told him I already had seen the problem before and he said he really appreciates my honesty.
this was my second technical phone interview because they wanted to get some more idea about my technical skills.| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 0of 0 votes
AnswersGiven an array of integers find all combination of numbers (regardless of length) that add up to a particular sum. (Subset sum problem)
- pk May 14, 2019 in United States| Report Duplicate | Flag | PURGE
Uber Software Engineer - 0of 0 votes
AnswersGiven a list of files. Return all the unique lines from all files.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswerGiven a set of points, find the smallest rectangle by area.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven N shop coordinates on a 2-d plane, Find the nearest shop from a man whose coordinates are given.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGive you a text file, remove duplicated lines.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersA string consists of ‘0’, ‘1’ and '?'. The question mark can be either '0' or '1'. Find all possible combinations for a string.
- neer.1304 May 12, 2019 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven two two integer arrays. Find the longest common subsequence.
- acoding167 May 12, 2019 in United States
eg: a =[1 5 2 6 3 7], b = [5 6 7 1 2 3]. return [1 2 3] or [5 6 7]| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersGiven an integer 'n', create an array such that each value is repeated twice. For example
- robb.krakow May 09, 2019 in United States
n = 3 --> [1,1,2,2,3,3]
n = 4 --> [1,1,2,2,3,3,4,4]
After creating it, find a permutation such that each number is spaced in such a way, they are at a "their value" distance from the second occurrence of the same number.
For example: n = 3 --> This is the array - [1,1,2,2,3,3]
Your output should be [3,1,2,1,3,2]
The second 3 is 3 digits away from the first 3.
The second 2 is 2 digits away from the first 2.
The second 1 is 1 digit away from the first 1.
Return any 1 permutation if it exists. Empty array if no permutation exists.
Follow up: Return all possible permutations.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 1of 1 vote
AnswersGiven a List of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder.
- acoding167 May 07, 2019 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer - 2of 2 votes
AnswersImplement an iterator<WordAndCount> which takes iterator<String> and its next() method returns the count for same word in a row. I was also asked to implement hasNext method.
- Desi May 03, 2019 in United States
WordAndCount class had two properties:
1. Word
2. Count
I was asked to implement hasNext() and next() method which basically returns a WordAndCount object.
To make it clear, following is the example:
lets say Iterator<String> has following values:
{foo,foo,foo,bar,foo,bar,bar}
iterator<WordAndCount> next() method should return this:
{{foo,3},{bar,1},{foo,1},{bar,2}}
It seemed like an easy problem and because we ran out of time during coding i think interviewer didn't ask me the follow up question. Interviewer was nice and he told me he doesn't expect me to code in time limit but he only wants to see how i approach the problem.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 0 votes
AnswersGiven a nxn grid with 1's and 0's find the length of largest black square formed with 1's.
- Desi April 29, 2019 in United States for ATG
So for below example:
00000
11110
01111
01110
The largest square length is 3.
With dynamic programming it can be done in O(n^2) time
It was a technical screen but it was taken in person for an event.| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 1of 1 vote
AnswersWrite a program to find the given new program can be scheduled or not?
- veeru April 23, 2019 in United States
Already scheduled Programs: P1(10,5), P2(25,15)
New Programs: P3(18,7), P4(12, 10).
In P1(10, 5), where 10 is the starting time, 5 is the execution time.
As The P3(18, 7) starts at time 18 and executes for 7 mins i.e., the end time is 18+7 = 25. So this time slot is free and there is no overlap with already scheduled programs. Hence P3 can be scheduled.
As the P4 overlaps with P1, So P4 cannot be scheduled.| Report Duplicate | Flag | PURGE
Google Software Engineer Data Structures - 1of 1 vote
AnswersLonely Pixel
- acoding167 April 22, 2019 in United States
Given an N x M image with black pixels and white pixels, if a pixel is the only one in its color throughout its entire row and column, then it is a lonely pixel. Find the number of lonely pixels in black from the image. (O(NM))| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersGiven unsorted array, find how many elements can be found using binary search
- neer.1304 April 21, 2019 in United States
- ex : [5,4,6,2,8] -> Ans : 3 -> '6' and '8' and '5' can be found using binary search| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm