## Software Engineer / Developer Interview Questions

- 0of 0 votes
You are given an N*N matrix. The matrix contains characters. Write a program to find a word in the matrix.The word can be found in either the rows or columns or the diagonals. The program should return true if the word is found and false if the word is not found.

- 0of 0 votes
This was asked in an Online written test that was timed (60 mins). And this question was one among the three.

"Write a method to merge three sorted integer arrays into just one array"

Nothing more or less was given. Since it was a written test I assumed that the 1st array had space towards to end which can fit the other two arrays. I can code this but given the timer limitations (of 20 mins per question) I thought it was a bit too much for me to handle unless there is a more obvious way to do this. I did it using two arrays and using the resultant array, I merged it with the 3rd array. That was the best i could think of at that time.

- 0of 0 votes
Amazon wants to implement a new backup system, in which files are stored into data tapes. This new system must follow the following 2 rules:

1. Never place more than two files on the same tape.

2. Files cannot be split across multiple tapes.

It's guaranteed that all tapes have the same size and that they will always be able to store the largest file.

Every time this process is executed, we already know the size of each file, and the capacity of the tapes. Having that in mind, we want to design a system that is able to count how many tapes will be required to store the backup in the most efficient way.

The parameter of your function will be a structure that will contain the file sizes and the capacity of the tapes. You must return the minimum amount of tapes required to store the files.

Example:

Input: Tape Size = 100; Files: 70, 10, 20

Output: 2

- 0of 0 votes
Reverse left node of BT.

1 (ROOT)

/ \

2 3

/ \

4 5

/ \

6 7

to

1

/

2 - 3

/

4 - 5

/

6 - 7

(6 is root)

- 1of 1 vote
Find a given element in sorted array.

arr= [1, 2, 3, 4, 5, 6]

follow up: If the sorted array is shifted left by unknown number, modify existing binary search to find a element in modified array

arr = [4, 5, 6, 1, 2, 3]

- 0of 0 votes
You're the guard of a prison, you want to keep an eye on the most dangerous prisoner. Each prisoner has a danger rank of his own and a group of friends (who also have danger ranks). You'll need to go through the prison and find out the prisoner who has the highest danger rank (his own + all his friends)

- 0of 0 votes
Enumerate all possible anagrams of a random string where capital letters, numbers, and symbols are not allowed to move within the string.

- 0of 0 votes
You're the guard of a prison, you want to keep an eye on the most dangerous prisoner. Each prisoner has a danger rank of his own and a group of friends (prisoners, who also have danger ranks). The guard has a list of prisoners with their corresponding danger ranks and he also has a list of the friends of each of the prisoners in the prison.

The danger rank is computed as follows: Prisoner 1 has a danger value of 5, his friends are Prisoner 2 and Prisoner 5, who have danger values of 3 and 4 respectively. So the danger value of Prisoner 1 is 5+3+4 = 12.

There could be any number of prisoners. Whichever prisoner has the highest value is the most dangerous(computed using the above method).

Friendship can be assumed to be symmetric.

Come up with an efficient algorithm to find the most dangerous prisoner?

- 0of 0 votes
You given and instruction called DBNZ ( Decrement and Branch if Not Zero)

which can be used as "DBNZ X L10".

This instruction decrement X by one and checks X, if X is not zero than branches line 10,

if it is zero than continue to next instructions.

By using DBNZ instruction implement CLEAR instruction.

CLEAR can be used as "CLEAR X" which means set X to zero.

By using DBNZ and CLEAR instructions implement NEGATE instruction

NEGATE can be used as "NEGATE X Y" which means set Y to negative of X ( Y = -X)

- 3of 3 votes
write an algorithm to find sum of numbers which are smaller than N and divisible by 3 or 5

Example:

N = 9 => 3 + 5 + 6 = 14

N = 10 => 3 + 5 + 6 + 9 = 23

- 0of 0 votes
design and implement a calculater that can calculate expressions like:

+ 2 4

* 8 ( + 7 12)

( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 )

(PS:all items are space delimetered.)

Example answers

+ 2 4 => 2 + 4 = 6

* 8 ( + 7 12) => 8 * ( 7 + 12 ) = 152

( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) => 7+8*12+2*(9+4)*7+3 = 148

- 1of 1 vote
there are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who)

Write two methods called "getNumber" and "requestNumber" as follows

Number getNumber();

boolean requestNumber(Number number);

getNumber method should find out a number that did not assigened than marks it as assiged and return that number.

requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assiged and return true.

design a data sturucture to keep those numbers and implement those methods

- 0of 0 votes
Suppose you receive 10 million mails in 10 seconds. How will you process them and find what might be the reasons to receive these many mails. Discuss different approaches to find the reasons.

- 3of 3 votes
1. qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number.

for example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3 where 33 less than 3 numbers (58 , 41 , 59), qaz of (25) = 4 and not 5 because the index of 33 is less than the index of 25, qaz of (26) = 3 , qaz of (58) = 1 , qaz of (41) = 1 , qaz of (59) = 0.

the question is to find the max qaz.

it can be solved simply using 2 loops which takes time of O(n^2).

that's ok but how can we solve this problem in O(nlogn).

I have an approach and know the algorithm I got during the interview but it take a 40 of me to find it and write the code, but it was hard to think about it during the interview in that way.

I want to know if somebody can think and write the code in less than 20 minutes !!!

- 1of 1 vote
Write a function that receives a stream of pairs: id (some unique integer) + weight (positive real number).

The stream ends with the special pair {0,0}.

The function should return one the unique ids at random, with probability proportional to its weight (compared to the total weights sum when stream has ended).

Stream size and weights sum are unknown in advance, and you are allowed O(1) memory consumption.

Example: If this was the stream: {1,2},{2,2},{3,4},{4,10}, then id 2 would be returned with probability 1/9.

- 1of 1 vote
Write a class that receives in the constructor a vector of strings representing a browser history (URLs), and a method for "auto-complete":

The method that receives a string representing a partial URL typed by the user and returns a vector of all possible completions of this partial URL (prefix).

- 1of 1 vote
You are given a binary search tree and a positive integer K. Return the K-th element of the tree.

No pre-processing or modifying of the tree is allowed.

- 2of 2 votes
You are given an array of distinct numbers. You need to return an index to a "local minimum" element, which is defined as an element that is smaller than both its adjacent elements. In the case of the array edges, the condition is reduced to one adjacent element.

Reach a solution with better time complexity than the trivial solution of O(n).

If there are multiple "local minimums", returning any one of them is fine.

- 0of 0 votes
You are given a positive integer number N. Return the minimum number K, such that N can be represented as K integer squares.

Examples:

9 --> 1 (9 = 3^2)

8 --> 2 (8 = 4^2 + 4^2)

15 --> 4 (15 = 3^2 + 2^2 + 1^2 + 1^2)

First reach a solution without any assumptions, then you can improve it using this mathematical lemma: For any positive integer N, there is at least one representation of N as 4 or less squares.

- 0of 0 votes
You are given a double linked list and an array of pointers to elements in this list (no assumptions can be made on the array - number of pointers, order and duplicates allowed).

Return the number of sequences of elements (groups of consecutive elements), pointed by the array.

For example, if this is the array (number relates to index in the list, not the actual pointer value): 9,1,3,7,8,5,2.

Then output is 3, representing these sequences: [1,2,3], [5], [7,8,9]

- 0of 0 votes
Given a 2D array of size nXn with values from 1 to n^2 permuted in the 2D array i.e no duplicates.

Find the longest snake in the array such that snake can go upward, downward, right, left and each and every adjacent value in the snake should differ by 1.

Ex:

2 5 6

3 4 9

1 7 8

Answer is 5. [2,3,4,5,6].

- 1of 1 vote
2D matrix with 0s and 1s. Try to find out how many countries in this matrix?

For example:

[[1,1,1,0]

[1,1,0,0]

[0,0,0,1]]

return 3, because one for 1s, one for 0s, and one for the last one.

another example:

[[1,1,1,1]

[0,0,0,0]

[1,0,0,1]]

return 4

- 1of 3 votes
You are given a 2D Array that contains only 0s and 1s in sorted order. i.e. First Os and then 1s.

Array:

0 0 0 1

1 1 1 1

0 0 1 1

0 1 1 1

You have to figure out the row that contains maximum number of 1s.

e.g. in above case we have row 2 as the answer.

- 1of 1 vote
Given two sorted arrays, mergesort them into 2nd array that has enough space to accommodate both.

- 0of 0 votes
Given two sorted arrays, merge sort in the 2nd array that has enough space to accommodate both

- 0of 0 votes
Given a string write a function to return the length of the longest sub string with only unique characters

- 1of 1 vote
Inplace reverse a sentence

You given a sentence of english words and spaces between them.

Nothing crazy:

1) no double spaces

2) no empty words

3) no spaces at the ends of a sentence`void inplace_reverse(char* arr, int length) { // your solution }`

Example:

input "I wish you a merry Christmas"

output "Christmas merry a you wish I"

Constrains: O(1) additional memory

- -2of 2 votes
Question deleted as duplicate (where are all moders? :)

- 4of 4 votes
The closest common ancestor in a tree forest.

`class Node { Node* parent; // == null for root of tree Node* left; Node* right; } Node* tree_forest[]; // array of pointers which points to roots of each tree respectively Node* closest_common_ancestor(Node* n1, Node* n2) { // your solution }`

Example:

`| a | j | / \ | / | b c | h | / / \ | |d e f |`

for e and d CCA is a

for e and f CCA is c

for e and c CCA is c

for h and d CCA is null

Constrains: O(1) additional memory

- 0of 0 votes
Design a URL system.

He even wanted to know what kind of algorithm to use, improve the speed, availability etc.