## Software Developer Interview Questions

- 0of 0 votes
There 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

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.

- 0of 0 votes
Write 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).

He wanted an O(n) algorithm.

- 1of 1 vote
Password Suggestor: Replace s with $ and a with @ and produce all password suggestions.

For Example: Password : P@ssword, P@$$word,pas$word etc..

- 1of 1 vote
For 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

- 0of 0 votes
Perform 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.

- 0of 0 votes
write a function that randomly return only odd number in range [min, max)

public int getRandomOdd(int min, int max){}

- 0of 0 votes
Given 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

- 4of 4 votes
Given an integer array which represents the heights of adjacent vertical bars standing on the ground.

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)).

- 1of 1 vote
Phone 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:

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

- 1of 1 vote
1. Difference between arrays and link list

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

- 0of 0 votes
/*

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

*/

- 1of 1 vote
The following code has a bug, find it and fix it

`Release() { m_refCount--; m.lock(); if (m_refCount == 0) { free(this); return 0; } m.unlock() return m_refCount; }`

- 1of 1 vote
Write 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"]

- 0of 0 votes
Given 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

- 1of 1 vote
You 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.

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.

- 0of 0 votes
Harry is trying to climb a pole. He climbs the pole in terms of hops. The height of the pole is k. Harry at a time can make a hop of:

1.) 1 unit

2.) n units

Find the minimum number of hops Harry would need to reach the top of the pole.

No constraints were mentioned by can be done in O(1) without any extra space.

- 0of 0 votes
This is a two-part question.

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.

- 0of 0 votes
Write a Code

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

- 0of 0 votes
Cross the River

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

- 0of 0 votes
Given 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 :

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

- 1of 1 vote
Given 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.

The rectangle at lower level has more priority than at higher levels.

- -1of 1 vote
Write a iterator wrapper to remove duplicates from collections without using temporary storage.

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

}

}

- 4of 4 votes
Given a string, find the longest substring with k distinct characters.

e.g - “aaaabbbb”, k = 2, “aaaabbbb”

“asdfrttt” k = 3, “asd”, “frttt”

[Telephonic Question]

- 3of 3 votes
/**

Given many coins of 3 different face values, print the combination sums of the coins up to 1000. Must be printed in order.

eg: coins(10, 15, 55)

print:

10

15

20

25

30

.

.

.

1000

*/

- 1of 1 vote
down vote

favorite

Consider the following series:

A := 1

B := A*2 + 2

C := B*2 + 3 and so on...

Write a program that:

-outputs the number corresponding to a given letter;

-given a string of letters like 'GREP', computes the sum of the numbers corresponding to all the letters in the string (i.e., G + R + E + P), as given by the above series; and

-given a large number (that would fit into a standard 32-bit integer), finds the shortest string of letters corresponding to it. You may use a greedy approach for the last part. Compute the values of the numbers corresponding to letters as and when required and DO NOT pre-compute beforehand and store them in a data structure.

- -3of 3 votes
Given a string and dictionary of words, form a word by removing minimum number of characters. Characters can be removed in-order only.

- 1of 1 vote
You are given a function getNum() that returns a random number in the range 1 to 10 million with repetitions. However, it may also return -1 when it no longer provides numbers. Write a function that calls getNum() continuously until it returns -1 (if a repetition, should not store it); as soon as u see -1, stop calling getnum() and print all the numbers seen so far in a sorted way. Condition: You have got very limited memory to work with.

- 0of 0 votes
Your program will simulate the creation of

subdirectories (folders) on one of the disks of a

computer. The input file to your program,

prog5.dat, will contain a sequence of commands

that a user might enter from a command line, and

the output file prog5.out will contain the

operating system’s responses to these commands.

Below is an example of an input file, and on the

right is the listing of the corresponding output

file.

dir

mkdir sub6

mkdir sub3

mkdir sub4

dir

mkdir sub4

cd sub3

cd sub3

mkdir sub3

mkdir sub6

mkdir sub4

dir

cd sub6

mkdir sub666

dir

up

up

dir

up

Problem 5 by team X

Command: dir

Directory of root:

No subdirectories

Command: mkdir sub6

Command: mkdir sub3

Command: mkdir sub4

Command: dir

Directory of root:

sub3 sub4 sub6

Command: mkdir sub4

Subdirectory already exists

Command: cd sub3

Command: cd sub3

Subdirectory does not exist

Command: mkdir sub3

Command: mkdir sub6

Command: mkdir sub4

Command: dir

Directory of root\sub3:

sub3 sub4 sub6

Command: cd sub6

Command: mkdir sub666

Command: dir

Directory of root\sub3\sub6:

sub666

Command: up

Command: up

Command: dir

Directory of root:

sub3 sub4 sub6

Command: up

Cannot move up from root directory

End of problem 5 by team X

- 1of 1 vote
Each test file starts with an integer ‘t’ - the number of testcases.

In each of the next ‘t’ lines, you are given a string of ‘n’ characters [ either ‘(‘ or ’)’ or ‘*’ ].

Your task is to find the number of distinct balanced parentheses expressions you can make by replacing the ‘*’ with either ‘(‘ or ‘)’ or removing the ‘*’

Note : You have to replace each ‘*’ with one of ‘(‘ or ‘)’ or remove it. If removed, assume the string has reduced by 1 character.

Duplicate strings are not allowed. The final expressions to be counted have to be distinct

As the answer may be large, please output it modulo 1000000007 (10^9+7)

Output one integer per line corresponding to each testcase.

Constraints :

1 <= t <= 20

1 <= n <= 100

0 <= Number of ‘*’ in the input string <= min(n,10)

Sample Input:

2

(*(*)*)

*(*(**)*

Sample Output

5

9

Explanation

The five possible valid solutions are for the first input are :

((()))

()(())

()()()

(())()

(())

The nine possible valid solutions are for the second input are :

(((())))

(()(()))

(()()())

(()())

((()))

()(())

()()()

()()

(())

- 0of 0 votes
The original question can be found from here :

franklinchen.com/blog/2011/12/08/revisiting-knuth-and-mcilroys-word-count-programs/

Read a file of text, determine the *n* most frequently used words, and print out a sorted list of those words along with their frequencies.

In the same spirit of the history:

1. Do it using pure shell scripting

2. Do it in the favourite language of your choice

Try to minimise code and complexity.