## Software Engineer / Developer Interview Questions

- 0of 0 votes
Tech Screening

Question 1 : You will be given a stream of integers, and a integer k for window size, you will only receive the streams integers one by one. whenever you receive an integer, you have to return the maximum number among last k integers inclusive of current entry.

Interviewer was expecting O(N) solution for N asks.

Edits: Interviewer was expecting O(N) Time + O(1) avg case space complexity solution for N asks.

and integers are not given in a array, every time only one integer will be passed as input to your method.

- 0of 0 votes
Design an object oriented console application named universe that reads in a file containing the schema of a two

dimensional (2D) universe and outputs certain information about the universe.

A 2D universe is a simplified universe that contains galaxies, stars, and planets, all of which are located on a flat plane

specified using 2-coordinates (x-axis and y-axis).

There is only one universe and it contains one or more galaxies.

A galaxy may contain one or more stars located in it.

A star may contain zero or more planets located near it in the same galaxy.

A planet may belong to one or two stars located near it in the same galaxy (Planet E465D in the sample file below is an example).

In order to allow the objects to support more descriptive attributes and functionality in future revisions of the

application, all the object types described above should be represented using separate classes. Parent-Child relationships should also be represented using links between the various object instances.

The program will run with three arguments specified: the input-file, and the name of two objects of any type, A and B.

Example command-line: universe text.txt Alpha_Dra E465D

Based on the command line arguments specified, the program will compute and display:

1. The parents location for both object A and B. (If needed, assume the coordinate of the universe is 0,0)

2. The minimum distance between object A (Alpha_Dra) and B (E465D). This is the distance between the two objects

given locations.

3. Any of the two closest stars in the entire universe.

4. The farthest object from A, that is of the same type as A; and the farthest object from B, that is of the same type as

B. (if one exists)

The input file contains new-line separated lines each describing one object using the format:

Type|Unique-Name|X-Coordinate|Y-Coordinate|Parent’s-Name|

Example test.txt input file:

Galaxy|Draco|75434.2|89151.4|Universe|

Star|Beta_And|23315.83|-2234.73|Andromeda|

Star|Alpha_Dra|75243.25|84123|Draco|

Galaxy|Andromeda|2967.78|-2357.2|Universe|

Planet|P165EU|75242.42|84121.2|Alpha_Dra|

Star|Alpha_And|26413.83|-2727.73|Andromeda|

Planet|E465D|26412.4|-2726.51|Alpha_And|

Planet|E465D|26412.4|-2726.51|Beta_And|

Notes:

The Universe object that serves as a parent to the galaxies is implicit, and will not be explicitly defined in the input

file.

The input lines may occur in any order

The file may contain millions of lines.

Example output of running: universe test.txt Alpha_Dra E465D

Parent of Alpha_Dra is located at: 75434.2,89151.4

Parent of E465D is located at: 26413.83,-2727.73

Distance between Alpha_Dra and E465D: 99635.8

Closest two stars in the universe are: Alpha_And and Beta_And

- 1of 1 vote
Shuffle a given array such that each position is equally likely.

- 1of 1 vote
Rotate a array by N. N can be smaller of greater than the array length.

e.g {0,1,2,4,5,6,7} N =4 should return {5,6,7,4,0,1,2}.

1) I did this using extra array but next I was asked to do without extra array and in o(n) time.

- -1of 1 vote
I have telephonic interview with amazon ? What will they ask? do they ask on algorithms,OOPs, data structure?

- 1of 1 vote
Design and implement LRU Cache.

- 4of 4 votes
Say you have a keypad that has keys for the numbers 0 through 9 and the correct code is some sequence of 5 digits. This keypad does *not* reset after entering an incorrect sequence of 5 digits. ie. If the correct sequence is 12345, entering 7512345 will succeed in opening it because it ends in the correct sequence. If the keypad actually resets after every 5 digits pressed, then it would not succeed b/c it would interpret the above sequence as "75123" then "45".

1. Write an algorithm that will try to find the correct code for this keypad. Assume you have an API similar to KeyPad.pressKey(int n) where you pass in a number (0...9) and it returns true if the keypad unlocks and false if it's still locked.

Note that you could easily enter all digits of all numbers 00000 through 99999 resulting in 5*100000 key presses, but remember that the panel does not reset after every sequence of 5 digits, so find a way to do this more efficiently. Notice for example that entering the stream 3791283780 will test the length 5 sequences 37912, 79128, 91283, 12837, 28378, 83780; not only the two disjoint sequences 37912 and 83780.

Think of this keypad as remembering the last 4 keys pressed (and the order pressed); when the next key is pressed, if the last 4 keys + the current key equal the correct code, the keypad will unlock. Assume the keypad does all this internally, so you can just keep feeding it keypresses and it will eventually unlock if the last 5 keypresses entered is the correct code.

2. Generalize your algorithm to work for a keypad where you don't know the length of the correct sequence in advance.

- 0of 0 votes
Suppose you are given a puzzle that is represented as a matrix with 0s and 1s, where a 0 indicates you’re allowed to move into that position and 1 means you’re not allowed to move in that position. Write a function that given a start position and an end position, returns a boolean value indicating if there exists a path from start to end. you are only allowed to move up, left, right and down. Diagonal movement is not allowed.

Example #1

Input

0 0 1 0 1

0 0 0 0 0

0 1 1 1 1

0 1 1 0 0

start: 4,1

end 0,3

Output - true

Example #2

Input

0 0 1 1 1

0 1 0 0 0

1 1 1 1 1

0 0 0 0 1

start: 0,0

end: 1,2

Output - false

- 1of 1 vote
Implement a function that returns the i-th most popular item sold

at xyz company. You cannot rely on any libraries.

Class Item {

String itemId;

int quantitySold;

}

/**

find the i-th most popular item in the list

**/

String find(List<Item> items, int i) {

// your code goes here

}

- 0of 0 votes
Search in a sorted rotated array.

- 0of 0 votes
Merge K sorted singly linked list

- 0of 0 votes
paint a list of N houses and M colors, each combination has cost, minimize the total cost without color in row.

- 0of 0 votes
How do you traverse a binary tree and output the nodes in-order? Do it in O(1) space.

Hint: You can modify the tree.

- 1of 1 vote
Given an unsorted array, find Kth smallest element in it.

A = 12, 3, 17, 0, 9, 6, 100

K = 3 -> 6

- 0of 0 votes
write a function that takes two integers, k and n, with 0 ≤ k ≤ n, and prints out all subsets of size k of the integers 1, ..., n, one subset per line. The order of the subsets and the order of elements within the line doesn't matter.

example 1: print_subsets(k=1, n=2);

1

2

example: print_subsets(k=2, n=3);

3 1

2 3

1 2

- 0of 0 votes
Given two binary trees ( not BST) , return true if both of them have same inorder else return false.

Eg.`B / \ A C`

`A \ B \ C`

Both of the trees have same inorder ( A-B-C) hence function will return true

P.S.

Please note, we can write inorder method call it once for first tree and then second tree, and finally compare both inorder.

We want to parallely do inorder on both tree, if there is mismatch between inorder nodes of both trees, we can stop the traversal and return false

- 0of 0 votes
Bring up as many approaches: Your goal is to make faster web browser for phones. You can change the phones, the data center etc. There's a limited network bandwidth and the browsers from the companies can't be altered.

- 0of 0 votes
We've got Quad-trees making up a screen. Every box of the Quad-tree has either color white or black. How would you design the data structure of this Quad-tree?

And how would you count the number of pixels in a screen of a given color, given a Quad-tree?`int numberOfPixelsGivenColor(QuadTree* t, bool col)`

i used bool to specify white/black.

- 3of 3 votes
write a function:

`int median(int a, int b, int c)`

and then write another function:

`int median(int a, int b, int c, int min, int max)`

- 0of 0 votes
Then the more difficult question was how I'd reverse this.

Implement function:`GetStringsfromNumeronym(numeronym){...}`

h3e -> {house, halle, hocke....}

- 0of 0 votes
Started out with simple question - to get warmed up:

Implement a function:`makeNumeronym(string s){...}`

Ex: house -> h3e, marcus -> m3s

- 0of 0 votes
Given a singly linked list, swap the list items in pairs (reconnect the pointers, not simply swap the values). For example:

Before: A->B->C->D

After: B->A->D->C

- -1of 1 vote
Hardest bug you faced

- 2of 2 votes
Let's assume that there's an array that has nonzero natural numbers where all the numbers repeat an even number of times, except for one value that repeats an odd number of times. Can you write me a function that takes this array, and returns the value that occurs the odd number of times?

Ex : - [ 4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5 ]

- 1of 1 vote
During appraisal due to bell curve funda a manager is restricted to give promotion to only one of his team members. Three of his team members are equally competant. He wanted to select one by giving a puzzle. He called his three talented team members and blidfolded them. He placed a hat on each of their heads. Manager took off their blindfolds and gave following clues and conditions

1) Each hat is either white or blue

2) There is atleast one blue hat

3) Contest is fair for all the three team members

4) Each team member can see the hat of other team members but not his.

5) The team members should not communicate to each other.

The manager declared that who ever comes up first with right answer shall be given promotion.

The most talented of his team members came up with right answer and explanation.What is the answer and the logic behind that?

- 0of 0 votes
Design a hotel reservation system. To make it simple, we assume that the hotel has only one building and the building has only one floor. Design your objects so that they work better with a non-sql database, say a document-oriented database.

- 1of 1 vote
Assume we only take the least significant digit of each value in fibonacci sequence, and form the sequence of digits into pairs. In those pairs, the first value of one pair is the same as second value of its predecessor.

As we know the fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21...

so the pair sequence is:

[1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 3], [3, 1] ...

Write a function to output the first n pairs of this sequence.

void Outputpairs(int n)

- 4of 4 votes
Given an array Of integers build a new array of integers such that every 2nd element of the array is greater than its left and right element.

eg:

[1,4,5,2,3]

o/p:

[1,4,2,5,3]

Soln proposed:

Step 1:Sort The array -> O(nlogn)

Step 2:Use 2 indices: one starting at leftmost index and other at rightmost index.

and populate the new array alterntely using the left pointer(index) first and then the right pointer and then increment the pointer used. till both the pointers meet/cross each other. -> O(n).

- 1of 1 vote
given an expression like 3*4 + 8-9 (only +, - , * operators) as a string evaluate it strictly from left to right

- 0of 0 votes
snake sequence. same as in other interviews