## Software Developer Interview Questions

- 0of 0 votes

AnswerGiven two tree nodes and the root of a tree, find the distance between both nodes in the tree.

- funk July 05, 2017 in United States for Infrastructure| Report Duplicate | Flag | PURGE

Facebook Software Developer - 0of 0 votes

AnswersGiven a String that contains parenthesis, remove the least amount of parenthesis from it such that it becomes balanced.

- funk July 05, 2017 in United States for Infrastructure| Report Duplicate | Flag | PURGE

Facebook Software Developer - 0of 0 votes

AnswersHow would you store very large numbers that can't be store in a regular Integer or BigInteger, and make calculations

- UCJava July 04, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon Software Developer Data Structures - 0of 0 votes

AnswersDesign an application for people to find a place near them where they can join a team to play their favorite sport. Exp. Soccer teams open to join that are scheduled to play at a certain time and place. The application would search for the available teams to join within certain area playing within some given time period,

- UCJava July 04, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon Software Developer Software Design - 1of 1 vote

AnswersYou have N toffee packets, each containing different number of toffees. The number of toffees contained in the ith packet is denoted by ci. You need to put these toffee packets in M boxes such that each box contains at least one toffee packet, and the maximum number of toffees in a box is minimum.

- praveensinghraghav96 July 02, 2017 in India

You can only choose consecutive toffee packets to put in a box.

Input

The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains two space separated integers N, M denoting the number of toffee packets and the number of boxes respectively. The second line of each test case contains N space separated integers c1, c2, ..., cN where ci denotes the number of the toffees in the ith toffee packet.

Output

For each test case, output a single line containing the maximum number of toffees in a box. Also, output -1 if such an assignment of toffee packets to boxes is not possible.

Constraints

1 ≤ T ≤ 20

1 ≤ N,K ≤ 100000

1 ≤ ci ≤ 1000

Example

Input:

1

4 2

10 3 5 7

Output:

13

Explanation

Below are the possible assignments of toffee packets to boxes.

10 [3 5 7]

10 3 [5 7]

10 3 5 [7]

For minimizing the maximum number of toffees in a box, we choose the second assignment, and hence the output should be 13| Report Duplicate | Flag | PURGE

Directi Software Developer - 0of 0 votes

AnswerAmr bought a new video game "Guess Your Way Out!". The goal of the game is to find an exit from the maze that looks like a perfect binary tree of height h. The player is initially standing at the root of the tree and the exit from the tree is located at some leaf node.

- praveensinghraghav96 July 02, 2017 in India

Let's index all the leaf nodes from the left to the right from 1 to 2^h. The exit is located at some node n where 1 ≤ n ≤ 2^h, the player doesn't know where the exit is so he has to guess his way out!

Amr follows simple algorithm to choose the path. Let's consider infinite command string "LRLRLRLRL..." (consisting of alternating characters 'L' and 'R'). Amr sequentially executes the characters of the string using following rules:

Character 'L' means "go to the left child of the current node";

Character 'R' means "go to the right child of the current node";

If the destination node is already visited, Amr skips current command, otherwise he moves to the destination node;

If Amr skipped two consecutive commands, he goes back to the parent of the current node

before executing next command;

If he reached a leaf node that is not the exit, he returns to the parent of the current

node;

If he reaches an exit, the game is finished.

Now Amr wonders, if he follows this algorithm, how many nodes he is going to visit before reaching the exit?

Input

First Line contains T the number of test cases

The next T lines contains 2 integers h, n

Output

Output T lines each containing an integer representing the number of nodes (excluding the exit node) Amr is going to visit before reaching the exit by following this algorithm.

Constraints

1 ≤ T ≤ 10

1 ≤ h ≤ 50

1 ≤ n ≤ 2^h

Example

Input:

1

2 2

Output:

2

Explanation

Example case 1. Amr would visit first root node then root->left node and then go to the root->left->right node which is the exit. hence 2 nodes visited before reaching the exit| Report Duplicate | Flag | PURGE

Directi Software Developer - 0of 0 votes

AnswersYou are walking down the escalator to catch a subway train. The escalator itself moves at a speed of Ve meters per minute. You can walk down the escalator at a relative speed of Vy meters per minute. The length of the escalator is L meters. Trains arrive T minutes apart. Let t be the time between your arrival to the station if you stand still on the escalator and the arrival of the last train before your arrival. Assume that t is a random variable uniformly distributed between 0 and T. Return the probability of catching an earlier train if you choose to walk down the escalator instead of standing still on it.

- praveensinghraghav96 July 02, 2017 in India

Input :

The first line of the input contains an integer Tc denoting the number of test cases. Each test case contains the following 4 lines

Ve - velocity of escalator

Vy - your relative velocity with the escalator

L - length of escalator

T - Time Period of Trains

Output

For each test case, output a single line containing the expected probability having an absolute or relative error less than 10^-6.

Constraints

0 ≤ Tc ≤ 5 * 10 ^ 7

1 ≤ Ve ≤ 1000

1 ≤ Vy ≤ 1000

1 ≤ L ≤ 10 ^ 5

1 ≤ T ≤ 10 ^ 6

Example

Input:

2

10

10

20

2

10

10

100

4

Output:

0.5

1.0

Explanation

Example case 1. If you stand still, it'll take you 20/10 = 2 minutes to reach the bottom of the escalator. If you choose to walk, it'll make you 20/(10+10) = 1 minute. In the second case you save 1 minute and in 50% of the cases it'll allow you to catch an earlier train.

Example Case 2. Here, if you choose to walk instead of stand still, you will save 5 minutes and you will certainly be guaranteed to catch an earlier train.| Report Duplicate | Flag | PURGE

Directi Software Developer - 3of 3 votes

AnswersFind out if the given string forms a valid lottery number.

- AnonD June 09, 2017 in United States

- A valid lottery number contains 7 unique digits between 1 and 59.

e.g.

4938532894754 (yes) -> 49 38 53 28 9 47 54

1634616512 (yes) -> 1 6 34 6 16 51 2

1122334 (no)| Report Duplicate | Flag | PURGE

Facebook Software Developer - 0of 0 votes

AnswersThere are three row of houses. There are N houses in each row. Each house can be painted with three colors: red, blue and green. The cost of painting each house with a certain color is different. You have to paint all the houses with following constaints

- jmincoder2 May 16, 2017 in United States

No two adjacent houses in a row have the same color.

Houses in a column have three different colors

You have to paint the houses with minimum cost. How would you do it?

Note: The cost of painting house 1 red is different from that of painting house 2 red in any row. Each combination of house and color has its own cost.| Report Duplicate | Flag | PURGE

Amazon Software Developer Algorithm - 2of 2 votes

AnswersWrite a function that takes an array of positive and negative integers and a number. This function should return true if the array contains a contiguous sub array that sums up to the number (2nd input).

- JSDUDE May 09, 2017 in United States

He wanted an O(n) algorithm.| Report Duplicate | Flag | PURGE

Snap Inc Software Developer Arrays - 2of 2 votes

AnswersPassword Suggestor: Replace s with $ and a with @ and produce all password suggestions.

- Interviewee2017 May 03, 2017 in United States

For Example: Password : P@ssword, P@$$word,pas$word etc..| Report Duplicate | Flag | PURGE

Amazon Software Developer - 1of 1 vote

AnswersFor a given Sum and N print all the combinations

For Example Sum = 16 and N=2

Then Answer :

16,0

15,1

14,2

13,3

12,4

11,5

10,6

9,7

8,8

7,9

6,10

5,11

4,12

3,13

2,14

1,15

0,16`private void recursivePrint(int sum, int n, int data[], int len, int originalSum) { if (n == 0) { int sum1 = 0; for (int j = 0; j < len; j++) { sum1 += data[j]; } if (sum1 == originalSum) { for (int j = 0; j < len; j++) { System.out.print(data[j] + " "); } System.out.println(); } return; } for (int i = 0; i <=sum; i++) { // System.out.println(" len: "+len+" sum: "+sum+" i: " + i+" n:"+n) data[len] = i; recursivePrint(sum - i, n - 1, data, len + 1, originalSum); } } }`

Need a better solution so that we can store previous results by using hashmaps

- NoMind April 23, 2017 in India for Azure| Report Duplicate | Flag | PURGE

Microsoft Software Developer - 0of 0 votes

AnswersPerform an efficient DeepCopy of a linked list whose node is like below:

`public class Node { public int Value {get;set;} public Node Next{get;set;} public Node Random{get;set;} }`

The Random field points to any random node in the list.

- Abcd April 20, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon Software Developer Data Structures - 1of 1 vote

Answerswrite a function that randomly return only odd number in range [min, max)

- ajay.raj April 11, 2017 in United States

public int getRandomOdd(int min, int max){}| Report Duplicate | Flag | PURGE

Google Software Developer - 1of 1 vote

AnswersGiven an array of unique numbers. Find the number of pairs that make up the difference. This must be solved in under O(N^2)

`function getPairs(int[] array, int k){ HashMap<Integer,Integer> values = new HashMap<Integer,Integer>(); for(int i = 0; i < array.length; i++){ if(!values.containsKey(array[i])){ values.put(array[i],1); } } int pairs = 0; for(int i = 0; i < array.length; i++){ int diff = array[i] - k; if(values.containsKey(diff)){ pairs++; } } return pairs; }`

This will give O(N) time. O(N) Space

- mcg1coding April 10, 2017 in United States| Report Duplicate | Flag | PURGE

Fidessa Software Developer Arrays - 4of 4 votes

AnswersGiven an integer array which represents the heights of adjacent vertical bars standing on the ground.

- viveksingh.ds April 08, 2017 in India

The width of each bar is 1. Now you have to pick two bars and remove all the remaining such that when

rain falls the water collected between two bars is maximum. Note that the distance between bars

remains the same after removing the remaining bars.

eg:

1. [10,5,6,12,14] ans: 30 (10*3)

2. [3 16 10 5 6 12 20 18] ans: 80 (16*(number of integers between 16 and 18)).| Report Duplicate | Flag | PURGE

Directi Software Developer Problem Solving - 1of 1 vote

AnswersPhone Interview, New Grad - Software Developer

Imagine you are given 10,000 files each containing 1 Million integers. I would you sum all of them and give the final result?

---> Interviewer wanted to test scalability, distributed concepts.

He has written the basic code and wanted to improve upon that.

Here's the basic code.`public getSum(String[] file_names) { int sum = 0; for(String f: file_names) { sum = sum + sumOfFile(f); } return sum; }`

Questions:

- confides123 March 25, 2017 in United States for Developer Tools

What's wrong with above code? Ans: Integer overflow

How would you implement sumOfFile?

What if 'sumOfFile' takes lot of time to finish computing?

How do you fasten the program?

Overall scalability etc| Report Duplicate | Flag | PURGE

Google Software Developer Distributed Computing - 1of 1 vote

Answers1. Difference between arrays and link list

- JSDUDE March 08, 2017 in United States for Alexa

1.1 How to prepend each of the above with extra data

2. Hash-table. What datastructure to use to create one. How to resolve collision| Report Duplicate | Flag | PURGE

Amazon Software Developer Data Structures - 0of 0 votes

Answers/*

- JSDUDE March 08, 2017 in United States for Alexa

Amazon employees are encouraged to learn and be curious, and this means employees can transfer teams within the company easily.

This usually means they'll move to a new building, and for those who have parking, they'd need to swap parking spots.

The task is that given a list of employees who want to swap parking spots, write a function that can match them up 1 to 1.

The output can simply be tuples of aliases.

Each alias should only be matched once.

Input-

alias fromBuilding toBuilding

adrian building1 building2

john building2 building1

andrew building3 building2

william building4 building3

John building2 building4

Doe

output-

adrian,john

*/| Report Duplicate | Flag | PURGE

Amazon Software Developer Algorithm - 0of 2 votes

AnswersThe following code has a bug, find it and fix it

- sergio March 05, 2017 in United Kingdom for Bing`Release() { m_refCount--; m.lock(); if (m_refCount == 0) { free(this); return 0; } m.unlock() return m_refCount; }`

| Report Duplicate | Flag | PURGE

Microsoft Software Developer Algorithm - 1of 1 vote

AnswersWrite a function that receives a string an returns a list of all the substrings (of length >= 2) composed by consecutive characters. E.g input : "BCCDE" , output: ["BC","CD","CDE","DE"]

- sergio March 05, 2017 in United Kingdom for Bing| Report Duplicate | Flag | PURGE

Microsoft Software Developer Algorithm - 0of 0 votes

AnswersGiven a linked list rotate it on the Kth element. For example, given 1->2->3->4->5 the list should be transformed into 4->5->1->2->3

- sergio March 05, 2017 for Bing| Report Duplicate | Flag | PURGE

Microsoft Software Developer Algorithm - 1of 1 vote

AnswersYou have a string of numbers, i.e. 123. You can insert a + or - sign in front of ever number, or you can leave it empty. Find all of the different possibilities, make the calculation and return the sum.

- twinmind March 03, 2017 in United States

For example;

+1+2+3 = 6

+12+3 = 15

+123 = 123

+1+23 = 24

...

-1-2-3 = 6

...

Return the sum of all the results.| Report Duplicate | Flag | PURGE

Facebook Software Developer Algorithm - 0of 0 votes

Answers[redacted]

- tohhubeta February 23, 2017 in United States| Report Duplicate | Flag | PURGE

Expedia Software Developer General Questions and Comments - 0of 0 votes

AnswersThis is a two-part question.

- xyz February 18, 2017 in United States

Part one: Design one or more classes to represent the intersections and streets

in a city. Streets can be either one-way or two-way.

Part two: Using the classes from the previous question, determine whether there is a pair of intersections (A,B) such that there is exactly one route from A to B.| Report Duplicate | Flag | PURGE

Google Software Developer - 0of 0 votes

AnswersWrite a Code

- ruchitraj93 February 14, 2017 in India

Steve is going to throw a party at his place tonight.He needs to visit two shops near his home-the first shop is d1 meters away from his place,the second shop is d2 meters away from his place, and there are d3 meters between these two shops.Calculate the minimum distance he needs to walk to visit both both shops and return back home. Steve always start from his palce.He can only travel using these 3 routes.HE can use any route any amount of time necessary,the only thing he needs to achieve is the minimum distance.

Find the minimum distance Steve has to walk to visit both shops and return home.

input: 1,1,1

output: 4

input: 10,20,30

output: 60| Report Duplicate | Flag | PURGE

Practo Software Developer Java - 0of 0 votes

AnswersCross the River

- itsvks February 10, 2017 in India

Saatwik, an elite programmer love the woods. Once he was in one of his trips to the mighty Himalayas , he encountered a strange problem. As we all know that, Himalayas has abundant river streams and forests. While travelling in one of the forest, he was trapped by the river stream flowing. As the stream flow was fast, he couldn't cross by swimming across water, he must find some other way to cross it.

River is present throughout the X axis and its boundary is marked by y coordinates (i.e. from y=A to y=B) .

--------------------------------------------------------------------------------- (y=A)

..................................................................................................

..................................................................................................

..................................................................................................

---------------------------------------------------------------------------------- (y=B)

Now, You are provided with some rocks along with their centres and radius respectively. Currently Saatwik is present on the shore having y=B . We can't jump between the rocks but we can move from one rock to other if both overlap at some points. You need to tell whether Saatwik will be able to cross the river by using any number of rocks or not . If he can, then output the minimum number of rocks taken to achieve it otherwise output −1

Input :

First line of input will contain T denoting number of test cases. For each of the test cases, First line will contain N denoting number of rocks. From second line onward, there will be N lines containing 3 integers X,Y,R where (X,Y) denotes the coordinates of the centre of that rocks and R stands for its radius. Last line will contain two integers A and B denoting the upper and lower boundary of the river respectively.

Output:

Output the required answer in a separate line for each of the test case.

Constraints :

1≤T≤10

1≤N≤5000

−109≤X,Y,A,B≤109

1≤R≤109

B<A

Sample Input

1

3

1 1 2

1 2 1

3 4 1

3 0

Sample Output

1

Explanation

At first we can step onto the first rock from the river shore. Then we can cross river directly or can move to second rock and then cross it. Note that we can't use third rock as it is beyond the reach from the other rocks.

Time Limit: 2.0 sec(s) for each input file

Memory Limit: 256 MB

Source Limit: 1024 KB| Report Duplicate | Flag | PURGE

Cleartrip.com Software Developer Algorithm - 0of 0 votes

AnswerGiven an array A of size N, where the ith integer of the array is A[i] and has a value ranging between 1 and 1000 inclusive, you need to help Monk with the following task :

- itsvks February 10, 2017 in India

Given 3 additional numbers K, X and Y, you need to report the number of un-ordered pairs of elements (i,j) from this array, such that (1≤i<j≤N), (A[i]+A[j])%K=X, and (A[i]×A[j])%K=Y.

Input Format :

The first line contains 4 space separated integers N, K and X and Y. The next line contains N space separated integers where the ith integer denotes A[i].

Output Format :

Print the required number of ordered pairs of array elements on a single line. As the answer could be rather large, beware of integer overflows.

Constraints :

2 ≤ N ≤ 10 raised to power 5

1 ≤ K ≤ 10 raised to power 6

0 ≤ X, Y < K

1≤A[i]≤1000

Sample Input

5 2 1 0

1 2 3 2 1

Sample Output

6| Report Duplicate | Flag | PURGE

Cleartrip.com Software Developer Algorithm - 1of 1 vote

AnswersGiven a set of possibly overlapping rectangles in different levels (All of which are "not rotated", can be uniformly represented as (left-bottom,right-top) tuplets), return a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area.

- hulk February 09, 2017

The rectangle at lower level has more priority than at higher levels.| Report Duplicate | Flag | PURGE

Facebook Software Developer Algorithm Data Structures - -1of 1 vote

AnswersWrite a iterator wrapper to remove duplicates from collections without using temporary storage.

- dmh February 04, 2017 in United States

For Example:

ArrayList A = {RAT,CAT,BAT}

ArrayList B = {RAT,CAT,MAT}

ResultIterator itr = new ResultIterator();

itr.next() should display {RAT,CAT,BAT,MAT}

Program skeleton:

class ResultIterator {

ResultIterator(iterator itr1, iterator itr2) {

}

bool hasnext {

// implement this method

}

E next() {

// implement this method

}

}| Report Duplicate | Flag | PURGE

Amazon Software Developer Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window