Software Engineer / Developer Interview Questions
- 0of 0 votes
AnswersFriends have transitive property where if A is the friend of B, and B is the friend of C then A is also the friend to C. Like that we make friend circle.
- sonesh April 18, 2017 in United States
You have to find the number of such circles in a given list of friends
You are given a NxN matrix, where columns of each row will have either 'N' or 'Y', where 'N' represents not a friend and 'Y' represents Yes, they are friends.
Example :
YNY
NYN
YNY
The output is 2({0,2},{1}), as the 0 and 2 are friends of each other and 1 is another friend who is neither friend with 0 nor with 2.| Report Duplicate | Flag | PURGE
Two Sigma Software Engineer / Developer Graphics - 0of 0 votes
AnswersQ1. You are given a binary search tree (with unique values) and two values. You need to find their lowest common ancestor. (Expected Complexity O(log(n)) + O(1))
- sonesh April 13, 2017 in United States
Q2. Now let's assume the tree has duplicates, and when a duplicate number come, the insertion logic chooses left node. (Expected Complexity O(log(n)) + O(1))
Q3.Now let's assume the input tree is a binary tree instead of the binary search tree.(Expected Complexity O(n) + O(1))| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Trees and Graphs - 1of 1 vote
AnswersYou are given a vector of integers. You have to delete the odd numbers from it.
- sonesh April 13, 2017 in United States
Expected complexity is O(N) Time and O(1) space| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Arrays - 0of 0 votes
AnswersYou are given an unsorted binary array.
- sonesh April 10, 2017 in United States
Ex [0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1]
and a number K, which represents the number of swap operations allowed on this binary array.
you need to find out the maximum length continuous subarray that can be generated using K many swaps.
Ex if K = 3 in above case
[0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1] => [0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1] => [0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0] => [0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0]
so the answer is 9.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou are given a binary matrix whose each row is sorted. that means each row will have zeros at front and ones at the back. You need to find out the row which contains a maximum number of ones.
Ex :[0 0 0 0 0 0 0 1 1 1 1 1] [0 0 0 0 1 1 1 1 1 1 1 1] [0 0 0 0 0 0 1 1 1 1 1 1] [0 0 0 0 0 0 0 0 0 1 1 1] [0 0 0 0 0 0 0 1 1 1 1 1] [0 0 0 0 1 1 1 1 1 1 1 1]
Ans : second row and sixth with 8 ones. you will print [2,8] and [6,8];
- sonesh April 10, 2017 in United States
Update : Required complexity O(M+N) + O(1) only.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 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 - 2of 2 votes
AnswersProblem statement
- PraTrick April 10, 2017 in India
Given a set of hotels and its guests reviews, sort the hotels based on a list of words specified by a user. The criteria to sort the hotels should be how many times the words specified by the user is mentioned in the hotel reviews.
Input
The first line contains a space-separated set of words which we want to find mentions in the hotel reviews.
The second line contains one integer M, which is the number of reviews.
This is followed by M+M lines, which alternates an hotel ID and a review belonging to that hotel.
Output
A list of hotel IDs sorted, in descending order, by how many mentions they have of the words specified in the input. If the count is same, sort according to the hotel IDs.| Report Duplicate | Flag | PURGE
Booking.com Software Engineer / Developer - 0of 0 votes
AnswersGiven an array of integers:
- xjohnwu April 07, 2017 in UK
1. rearrange the array such that all non-zero members appear on the left of the array (order is not important)
2. return the number of non-zero members
e.g. [1,2,0,5,3,0,4,0] => [1,2,5,3,4,0,0,0] and return 5. The non-zero array members can be in any order.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersOne question containing multiple questions
- sonesh April 07, 2017 in United States
1) Define the structure of a function which takes an array of size n as input and returns True or False.
2) Write a function which takes an array as input and returns a string containing all the elements separated by a comma.
Ex : [0, -45, 9, 10] => "0,-45,9,10";
3) Write a function which takes two arrays ass input, and returns minimum common element in them.
Ex : [0, -90, 45, 10, 4], [4, 8, 90, 45] => 4
4) Now let's say, the function takes an array of arrays, and each array is sorted. now, returns their first common element.
Ex : [0, -90, 45, 10, 4], [4, 8, 90, 45], [-1, -3, -5, -7, 10, 4], [24, 35, 78, -90, 56, 4] => 4| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Arrays - 1of 1 vote
AnswersYou are given an array of integers both negative and positive.
- sonesh April 07, 2017 in United States
Print the maximum continuous sum of the array and if all the elements are negative, print the smallest of them.
Ex : [-20, -5, -2, -9] :> -2(-2)
Ex : [20, -19, 6, 9, 4] :-> 20(20)
Ex : [10, -3, 4, -2, -1, 10] -> 18 (10, -3, 4, -2, -1, 10)
Thanks velu007 for pointing out the mistake| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Algorithm - 1of 1 vote
AnswersDefine a graph using Adjacency list where node and graphs are different entities, for example, Node is a struct/class and graph is set of nodes.
- sonesh April 07, 2017 in United States
The graph is an acyclic directed graph(may be a forest not necessarily connected).
Write an assignment copy constructor for this graph.
Please note that the copy constructor should create a new copy of the graph, including all its edges and vertices. Interviewer called this deep copy.| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Graphics - 0of 0 votes
Answers* Definition for a binary tree node.
- ajay.raj March 27, 2017 in United States
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
Given an array of Binary Tree Node, check if all of these nodes can form a binary tree?
Public boolean canForm(TreeNode[] nodes){
}| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersCheck if two given binary trees(expression trees with two characters 'a' and 'b' and obviously operators like +,-,*) are mathematically equivalent?
- AlgoBaba March 16, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 1 vote
Answerusing System;
- sunil.sebastian March 16, 2017 in United States
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ArrayProblems
{
public class MultiplyTwoLargeNumber
{
public static string MultiplyBigNumbers(string s1, string s2)
{
char[] num1 = s1.ToCharArray();
char[] num2 = s2.ToCharArray();
//string=99
//char--> 9 , val --> 57(48+9)
//so s[i]-'0' will give val 9 and char as horizontal tab
char[] result = new char[num1.Length + num2.Length]; // Default 0 '/0' 2 ==> 50 '2'
int carry = 0;
int offset = 0;
for (int i = num1.Length - 1; i >= 0; i--)
{
int tail = result.Length - 1 - offset;
for (int j = num2.Length - 1; j >= 0; j--)
{
int resval = 0;
if(result[tail]!=0)
{
resval = result[tail] - '0';
}
int sum = resval+ ((num1[i] - '0') * (num2[j] - '0')) + carry; //remember to add result before taking mode
result[tail] = (char)((sum % 10) + '0');
carry = sum / 10;
tail--;
}
if (carry > 0)
{
int res = (result[tail] != 0) ? (result[tail] - '0') + carry : result[tail] + carry;
result[tail] = (char)(res + '0');
carry = 0;
}
offset++;
}
return new string(result);
}
}
}| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Arrays - 1of 1 vote
AnswersTurtle is on a N * N grid, with N obstacles. The turtle can only move F orward one position
- rathin91 March 07, 2017 in India
and can turn L eft or R ight. The grid has 4 directions N, E, W, S
Assuming that the initial position of turtle is 1, 1 (bottom left corner of the grid facing North) and
the grid has random obstacles in a few of its cells, given the movement instructions, find the
final position of turtle and printing the grid state will be an added plus. When there is an
obstacle, movement is not possible.
input :
FFFRRFLF
output:
2,3 E| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 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 - 0of 0 votes
AnswersGiven a diamond shape matrix, find the minimum path sum from top to bottom.
Each step you may move to adjacent numbers on the row below.
- ajay.raj March 02, 2017 in United States[ [2], [3,4], [6,5,7], [4,1,8,3], [2,5,4], [6,4], [1] ]
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersDesign a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)
- ajay.raj March 01, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 0 votes
AnswersGiven the weekly vacation numbers for various cities for an year (ie 12 * 4 = 48 weeks ) , design a tour which will maximize the number of vacations for a salesman. The salesman can choose to work in any city for the week , and can weekly change the city unlimited number of times , but has to remain in the city for the week . It's not necessary for the salesman to go to all cities , goal is to find the schedule which maximize the vacation for whole year. Input will be HashMap<string , int[48] vacation> where string is the city name and int[48] is city's vacation numbers for an year.
- yuvithomas February 27, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 7 votes
AnswersConsider a hotel where the guest is checked in and check out. Find a day when the maximum number of guests stay in a hotel.
- itsvks February 01, 2017 in Netherlands
example:
Input :
[
{check-in : 1, check-out 4},
{check-in : 2, check-out 5},
{check-in : 10, check-out 12},
{check-in : 5, check-out 9},
{check-in : 5, check-out 12}
]
Output : 5| Report Duplicate | Flag | PURGE
Booking.com Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven number N, Find the least number of perfect square number sum needed to get N.
- itsvks February 01, 2017 in Netherlands
Example :
n=5 (4+1) i.e. 2
n=7 (4+1+1+1) i.e. 4
n=12 (4+4+4) i.e 3
n=20 (16+4) i.e. 2| Report Duplicate | Flag | PURGE
Booking.com Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow to verify the string which contains alpha-bates,parenthesis and signglle/double quote
- djvirus January 21, 2017 in India
Ex: AB(CD{"GH"}) is valid
"A()B' is invalid| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhat is the smallest number *n* by which the given number *x* must be divided to make it into a perfect square?
- NoOne January 08, 2017 in Indian = find_number( x )
| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRunning with Bunnies
- shand January 03, 2017 in United States
====================
You and your rescued bunny prisoners need to get out of this collapsing death trap of a space station - and fast! Unfortunately, some of the bunnies have been weakened by their long imprisonment and can't run very fast. Their friends are trying to help them, but this escape would go a lot faster if you also pitched in. The defensive bulkhead doors have begun to close, and if you don't make it through in time, you'll be trapped! You need to grab as many bunnies as you can and get through the bulkheads before they close.
The time it takes to move from your starting point to all of the bunnies and to the bulkhead will be given to you in a square matrix of integers. Each row will tell you the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order. The order of the rows follows the same pattern (start, each bunny, bulkhead). The bunnies can jump into your arms, so picking them up is instantaneous, and arriving at the bulkhead at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any bunnies you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the bulkhead doesn't mean you have to immediately leave - you can move to and from the bulkhead to pick up additional bunnies if time permits.
In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the bulkhead to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is, each time a path is traversed, the same amount of time is used or added.
Write a function of the form answer(times, time_limit) to calculate the most bunnies you can pick up and which bunnies they are, while still escaping through the bulkhead before the doors close for good. If there are multiple sets of bunnies of the same size, return the set of bunnies with the lowest prisoner IDs (as indexes) in sorted order. The bunnies are represented as a sorted list by prisoner ID, with the first bunny being 0. There are at most 5 bunnies, and time_limit is a non-negative integer that is at most 999.
For instance, in the case of
[
[0, 2, 2, 2, -1], # 0 = Start
[9, 0, 2, 2, -1], # 1 = Bunny 0
[9, 3, 0, 2, -1], # 2 = Bunny 1
[9, 3, 2, 0, -1], # 3 = Bunny 2
[9, 3, 2, 2, 0], # 4 = Bulkhead
]
and a time limit of 1, the five inner array rows designate the starting point, bunny 0, bunny 1, bunny 2, and the bulkhead door exit respectively. You could take the path:
Start End Delta Time Status
- 0 - 1 Bulkhead initially open
0 4 -1 2
4 2 2 0
2 4 -1 1
4 3 2 -1 Bulkhead closes
3 4 -1 0 Bulkhead reopens; you and the bunnies exit
With this solution, you would pick up bunnies 1 and 2. This is the best combination for this space station hallway, so the answer is [1, 2].
Test cases
==========
Inputs:
(int) times = [[0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 0, 1], [1, 1, 1, 1, 0]]
(int) time_limit = 3
Output:
(int list) [0, 1]
Inputs:
(int) times = [[0, 2, 2, 2, -1], [9, 0, 2, 2, -1], [9, 3, 0, 2, -1], [9, 3, 2, 0, -1], [9, 3, 2, 2, 0]]
(int) time_limit = 1
Output:
(int list) [1, 2]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven points on a plane like (0,0), (1,0), (0,1), (1,1), (0,2), (2,2), (1,2). How many rectangles can be formed ?
- solveIt December 26, 2016 in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Algorithm - 0of 0 votes
AnswersI was asked to design a stock ticker system. Stock ticker is simply the shortened name of company and its current stock size. e.g. for Apple - "AAPL" -> "115"
- 256.cool December 14, 2016 in United States
He asked me to design a data structure to store incoming stream of stock tickers. Stream can contain same company more than once but all the values of it had to be stored. I used HashMap<String, List<Integer>>. Then he was adding more functionalities to system I don't exactly remember the questions now but one of them was related to calculating some ratio in constant time. Some of the questions were challenging.| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer System Design - 0of 0 votes
AnswersGiven a set find its power set. (This question is from CTCI) Interviewer then discussed the complexity of my solution. He asked me to explain him how the complexity is 2^n? As per my solution, I was iterating over an arraylist which contained the set elements so the size of list was getting doubled in every iteration. Hence the complexity (2^0 + 2^1 + 2^2 +.....+2^n-1 = 2^n)
- 256.cool December 14, 2016 in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a string, add some characters to the from of it so that it becomes a palindrome. E.g.1) If input is "abc" then "bcabc" should be returned. 2) input -> "ab" output -> "bab" 3) input -> "a" output -> "a"
- 256.cool December 14, 2016 in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou are given a binary tree. Each node in the tree is a house and the value of node is the cash present in the house. A thief can rob houses in alternate levels only. If thief decides to rob house at level 0 then he can rob houses in levels 2,4,6... or he can rob houses in levels 1,3,5,7...Find out the maximum possible amount thief can rob.
- 256.cool December 14, 2016 in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Trees and Graphs - 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