## Software Engineer / Developer Interview Questions

- 0of 0 votes
You are given a matrix where some pixels are white and some are black. Basically there are different disjoint images in the matrix.

a) Expand/Shrink the images

b) Count the no of images

c) Color the images

d) Rotate the images

- 0of 0 votes
Given three points in a 2D plane with their (x, y) coordinates say if the origin lies inside the triangle formed by the three points.

- 0of 0 votes
Disconnect two nodes in a graph by removing minimum number of edges.

- 0of 0 votes
Given a matrix pattern containing only 'plus' & 'dots',search no of times that pattern is present in a very large file which has a very large matrix which contains 'plus' and 'dots'.

- 0of 0 votes
Objective: Write a function to find all the combinations of three numbers that sum to zero

Sample input:

[2, 3, 1, -2, -1, 0, 2, -3, 0]

Sample output:

2, -2, 0

1, -1, 0

3, -2, -1

3, 0, -3

3, 0, -3

- 0of 0 votes
write a function that has an int as input and return the equivalent String as an output

12 -> 'twelve'

4345 -> 'four thousand three hundred and forty-five'

7654567643 -> 'seven billion six hundred and fifty-four million five hundred and sixty-seven thousand six hundred and forty-three'

- 0of 0 votes
The input is a sequence x1,x2,...,xn of integers in an arbitrary order, and another sequence

a1,a2,..,an of distinct integers from 1 to n (namely a1,a2,...,an is a permutation of

1, 2,..., n). Both sequences are given as arrays. Design an 0(n logn) algorithm to order

the first sequence according to the order imposed by the permutation. In other words, for

each i, Xi should appear in the position given in ai. For example, if x = 17, 5, 1,9, and a =

3, 2, 4, 1, then the outcome should be x = 9, 5, 17, 1. The algorithm should be in-place, so

you cannot use an additional array.

- 0of 0 votes
Given a list of tuples representing intervals, return the range these intervals

covered.

e.g:

[(1,3), (2,5),(8,9)] should return 5

- 0of 0 votes
Consider a game of chess where there is a special queen which has the powers of a Queen as well as a Knight. For eg. in the following arrangement, squares marked with 'x' are in the attackzone of the special queen and the ones marked '0' are in the safe zone:

x O O x O O x

O x x x x x O

O x x x x x O

x x x Q x x x

O x x x x x O

O x x x x x O

x O O x O O x

Your task is to determine the number of ways in which you can place M such queens on a MxM chess board so that they are in equilibrium i.e. they are placed such that no queen is in the attack zone of the other.

Assume M<15. If you need coordinates to identify each square, you can assume that the top-left square is marked (1,1) and the bottom right square is marked (M,M).

- 0of 0 votes
Find x^y where y can be float. Any good algorithm for that?

- -1of 1 vote
C++ Program that uses Linked List to display an Address Book (Name, Address, and Phone number)

Note:phone numbers format: (xxx)-xxx-xxxx

Address should ..street...City...State...Zip

- 0of 0 votes
Write an efficient algorithm to the situation.There are 8 cubicles in a room. In each cubicle, there are 8 computers.

There are a total of 60 members.

Constraint#1 - A team can contain a minimum of 2 members and a maximum of 6 members.

Constraint#2 - In every cubicle, not more than 1 computer can be unallocated.

Constraint#3 - All team members of a team must be in the same cubicle.

- 0of 2 votes
A very interesting Question to be done in C or C++ as platform:

Given two input files.

Input file1.csv

Each line in the file describes a websites.

The first field is unique identifier for the site, the second field is the minimum amount in cents, the third field is a string that is the siteâ€™s URL:

2181, 320, abc.com

3288, 450, pqr.com

9662, 567, xyz.com

2675, 721, lmn.com

6434, 500, rst.com

8123, 5000, jjj.com

Input file2.csv

Each line in the file describes an ad. The first field is a 32Âbit unsigned integer which is the unique identifier for the ad , the second field which is the maximum amount in cents the ad is willing to pay to show on a site, the third field specifies the number of sites the ad wants to display on, followed by the site_ids of the sites.

9822, 450, 3, 2181, 9662, 66434

3421, 897, 3, 2675, 9662, 3288

8961, 342, 1, 9662

7623, 2000, 3, 2181, 2675, 9662

all integr fields are 32Âbit unsigned integer

In the above example, ad 9822 is willing to play on 3 sites(abc.com, xyz.com and rst.com) and pay a maximum amount of 450 cents. WAP that decides the appropriate ad by applying the following rules

1. An ad can be shown on this site only if the site is in the list of sites that the ad is interested in.

if no ad id found for a ite, then no ad is returned

2. The ad that is returned is chosen an auction thats is called second price auction. For ads to qualify for the second price auction,

auction for a site their bid_price should be greater than or equal to the reserve_price of the

site. The winner of the auction is the ad that has the maximum bid_price among these ads, and this

winning ad pays the second highest adâ€™s bid_price. For instance, if two ads with bid_price 500

and 600 are competing for a site that has a reserve_price of 400, then the ad that bid 600 wins,

but pays 500 (the second highest adâ€™s bid price).

3. In case of a tie between two or more ads, the ad with the lower ad_id wins and pays itâ€™s

bid_price. In case, the auction has only one ad that qualifies, then that ad wins and pays

reserve_price of that site.

4. In case there are no ads that qualify for the auction for a site Â either because no ad expresses interest

in playing on that site or because none of the ads have bid_price greater than or equal to

reserve_price of that site then no ad is returned.

Your server should accept input file path,first.csv and the second.csv as

arguments and wait for input. The input is the site_id and the adserver should return the ad_id of the ad that wins the second price auction and price the ad pays for the display. An input of Â1 ends the program. example:

$ ./adserver sites.csv ads.csv

2675

7623 897

3288

3421 450

6434

0 0

9999

0 0

8123

0 0

Â1

$

DIRECTIONS:

1. The code should compile at least on

http://www.compileonline.com/compile_cpp_online.php

2. Please note that will test your program on larger input files with 20K+ sites and

20K+ ads.

3. You have 1.5 hour to solve the problem, test and submit your solution. Your goal is to provide a working solution at least. You may submit additional code later if you think you can make it work better or faster.

For starters If I were to do this in Java:

Algo:

Step1: I/O

Store both the File Paths from STD IN

Take the SITE_ID as Input Then

Step 2: Pre Processing

Site_Map:

Create a Dictionary/HashMap of All the Site_ID and their Price

Ad_Map:

Create a Dictionary/HashMap of All the Ad_ID and the Ammount they Have

Site_to_Ad Map:

Create a Dictionary/HashMap of All the Site_ID and the Ad_IDs Interested to be on them.

Step 3: Auction Method

Iterate through the Site_to_Ad Map.

Fetch the Amount for Each ad_id from the Ad_Map

Compare it against the min price and if greater store it in a variable along with the ID. Fetch the Next ID and IF it is Higher, Replace and put this value in the variable. If there is a draw, compare the two ap_ids and store the one that has min ad_id value.

If min bid is not reached or if there are no ad_id values for that site, return no ad.

Add Constraints to the Auction block.

I believe in c++ we would use Dictionaries to achive this as we have HashMap in Java, can someone help m with the syntax.

- 2of 2 votes
Consider the array 3 5 7 6 3.

Return the pair of indices that forms the slice where the difference between the maximum and minimum in the slice <= 2.

Output:

(0,0) (1,1) (2,2) (3,3) (4,4) (5,5)

(0,1) (1,2) (1,3) (2,3)

Example slices: 3 5, 5 7, 1 3, 2 3.

The following link

https://codility.com/media/train/solution-count-bounded-slices.pdf

has O ( n ) solution. But couldn't understand the O (n ) solution. Could some one explain with an example?

- 0of 0 votes
How would you debug a Linux program taking too much memory.

- 0of 0 votes
There are 2 sets A and B of numbers where numbers are keep coming at high speed. At any given time, you need to find 'A UNION B', 'A INTERSECTION B', 'A - B' and 'B - A'.

How will you store numbers and how will you find these value in real time?

- 0of 0 votes
Get numbers that have 90% percentile rank from a collumn in db that contains integers. (their solution is using ntile)

- 0of 0 votes
Round 3 of the interview(in person)

On amazon website, what does the request most recent viewed items API look like?

On server side, design a data structure to cache the most recent viewed item for all clients( consider the size of amazon user)

- 0of 0 votes
Round 3 of the interview(in person)

Design a online chess game.

Detail design of the chess board, chess piece.

Detail design the "move" action

- 0of 0 votes
Round 3 of the interview(in person).

given a binary tree with each node contains a number (with negative, duplicate number), write program to find the level which have the most num of negetive number.

- 0of 0 votes
Word Wrap / String Justification algorithm.

Given a set of words and a length.

You are required to print the words such that the words on each line end almost on the same column and the number of trailing spaces at the end is minimized.

Given aaa bb cc ddddd and length is 5 print the following output.

aaa

bb cc

ddddd

- 0of 0 votes
Given two stations at random, show all possible routes between those stations (if any)

- Stations links are listed below

- Links between stations are bi-directional

- Routes generated should not have cycles

cambridge<>stansted

stansted<> harlow

harlow<>london

london<>hatfield

hatfield<>peterborough

cambridge<>hatfield

cambridge<>ely

peterborough<>ely

peterborough<>birmingham

birmingham<>manchester

manchester<>glasgow

glasgow<>edinburgh

edinburgh<>newcastle

newcastle<>thirsk

thirsk<>york

york<>manchester

york<>peterborough

- 1of 1 vote
Given a number N. find is it perfect square or not. cannot use any library functions.

- 0of 0 votes
Merge N sorted linked list of integers

Constraint was :

min comparison and no extra memory(i given a solution with min heap, they told heap will take O(N) memory. so cant use it).

- 0of 0 votes
Difference between Trie and N-array tree.

- 0of 0 votes
Merge N sorted linked list of integer

Constraint was :

min comparison and no extra memory(i given a solution with min heap, they told heap will take O(N) memory. so cant use it).

- 0of 0 votes
How would you maintain concurrency on a shared page being edited by multiple users simultaneously.

What if the page is being shared using a client- server mechanism. Represent the classes and explain the thread safety mechnism to avoid editing conflicts.

- -1of 1 vote
How Hashmap works internally? Resizing? Hashbuckets' separation?

- 1of 1 vote
Array of Integers. Given Integer X, return true iff there exist A,B, so that A+B=X. Hint: additional data structure might be needed.

- 1of 1 vote
How would you store a phone book. Unique phone numbers, possibly multiple same names with different phone numbers.