## Software Engineer / Developer Interview Questions

- 0of 0 votes
Phone interview question from January.

We have a maze with three types of spaces:

1. Walls

2. Offices

3. Hallway space

Given a maze, determine which non-wall space would minimize the sum of all distances between that space and every office. You can only move up, down, left, and right.

(Edit: ChrisK described the problem more clearly than I did: "find the field that minimizes the sum of the shortest path[s] from this field to each office space.")

Example:`WWWWWWWW WWW O WW WWW OW WWW WWWW WO WWWW WWW WWWW WO W WWWWWWWW`

O = office, W = wall, spaces are hallway spaces

You can represent the maze however you want. That is, you can use any data structures you want, and you don't necessarily have to use O for office, W for Wall, and spaces for hallways.

(I'm not sure if you can actually start from an office space, but that should be a trivial issue because you can always just start a position adjacent to an office.)

- 0of 0 votes
Game of Death:

Implement an algorithm that produces the next move in the game of death.

Basically given a two dimensional array it will have either values 1 (live cell) or 0 (dead cell)

1. A Live cell will live only if it has two or three live neighbors All other cases die.

2. A dead cell with exactly three live neighbors will live otherwise no change, dead

Transform the array by using above two rules

- 0of 0 votes
Make 100 HTTP GET requests to http://en.wikipedia.org/wiki/Main_Page and print the following statistics for the response time to stdout:

• 10th, 50th, 90th, 95th, 99th Percentile

• Mean

• Standard Deviation

Your solution must be parallel. You must make at least N (say 10, but should be configurable). Use ExecutorService in Java for making the requests at a time.

Explain design choices, known limitations and edge cases.

What challenges did you face? How would you improve the code if you had more time?

- 0of 0 votes
Design an algorithm that provided your current location and a list of ATMs locations in the area, get you the closest K ATMs to your location.

Assume you have a method getDistance(a, b) that calculates the distance between a and b.

Follow Up:

Make your solution O(k) space and O(n) time

- 0of 0 votes
Design an algorithm to find the shortest substring in a synopsis such that it contains all the words in a provided list.

So, search for the shortest substring that contains ['Hello', 'World'].

- 0of 0 votes
Design a system for a parking lot where drivers can also have memberships (but also support guest drivers). The parking lot has counter screens on each row.

- 0of 0 votes
Design a message board system like Reddit were users can reply with messages on posted topics. How will you handle system scalability.

- 0of 0 votes
Regex matching algorithms

You will be given a string and a pattern string consisting of only '*','?', and small letters. You have to return tree or false based upon the comparisons.

? repersent one char.

* means zero or n number of char for any positive n.

Example

abc, a?c : true

abc, a*?c : true

abc, * : true

abc, ?c : false

- 0of 0 votes
You are given following design architecture.

`[DB] <==> [Server]`

Now let's say user are complaining about our server being slow, how would you figure out where is the problem?

2) now let's say the problem is in server, where do you think the problem is in server?

3) What if you found our server is fast, how about now?

4) you have also found that the network call from server to DB is also fast, how about now?

5) Lets say, our server is also setting near the complaining user, how about now?

- 0of 0 votes
You are given two Queues where each queue contains timestamp price pair. You have to print <price1 price 2> pair for all those timestamps where abs(ts1-ts2) <= 1 second where ts1 and price1 are the from the first queue and ts2 and price2 are from the second queue.

Now let's say one queue is slow, what kind of modification you will make?

- 0of 0 votes
You are given an array of nodes where each node consists of node name, isValid flag, and parent Node index. so, this array actually represents a tree(forest). where root node has -1 as its index for the parent node. rest all node have their parent's index value.

You will be given this array and an index. You have to cut down the subtree from the index. Cutting down a tree means, making all the nodes of that subtree false(Isvalid flag).

He was expecting O(N) solution.

- 0of 0 votes
Define Reverse Polish notation calculator. Interviewer needed class design for the calculator. Please make sure that adding extra operator tomorrow should not make us change the class or any of its methods.

- 0of 0 votes
You are given an array of stock prices, You have to return maximum profit one can make when buying once and selling once. Consider, you are buying one stock only.

- 0of 0 votes
You are given set of strings, you have to print out the could of each distinct patterns. Please consider anagrams as same pattern and even the char count does not matter.

Ex:

abbba

ab

ba

abcd

abdc

adbc

aabddc

output:

ab: 3

abcd: 4

- 0of 0 votes
You are given three type of data sets.

Type 1

Data size: 4 billion

Distinct Data: 1000

Type 2

Data Size: 4 billion

Distinct Data: 2 billion

Type 3

Data Size: 1000

Each Data is of length 100 million byte

What kind of data structure would you use to answer search/insert/remove queries for each data types?

- 0of 0 votes
Q 4. You are given a binary tree, and you have to return list of lists of node. where same level nodes should be in the same list, nodes are in opositive order in next list from the previous list

Ex:`4 / \ 3 5 / \ \ 1 10 -4`

Output would be

[[4], [5, 3], [1, 10, -4]]

Desigred Complexity : O(N) + O(N).

- 0of 0 votes
Q 3. You are given a LinkedList and a number K. You have to reverse it in the groups of K

Ex :

[1] -> [2] -> [3] -> [4] -> [5] -> null, K = 3

output: [3] -> [2] -> [1] -> [5] -> [4] -> null

Desired Complexity: O(n) + O(1)

- 0of 0 votes
Q 2. You are given a chess game board of size NxN. You have find out positions(i,j), where you can place N queens so that, none of the queens can kill each other without making their first move.

- 1of 1 vote
Q 1. You are given an array of integers, contains positive, negative and zeros. You have to written subarray whose sum is maximum in this array.

Desired Complexity is O(N) + O(1)

- 0of 0 votes
Q 7. You are getting a stream of integers, You have to find the median of these in real time(or with minimum complexity).

- 0of 0 votes
Theoretical Questions

Q 1. Any design patterns you have used, please explain in details

Q 2. Difference between a process and a thread

Q 3. How threads/processes can communicate with each other.

Q 4. What is latency and throughput, what is there the difference?

Q 5. When to use merge sort over quick sort and vice-versa.

Q 6. What is hashmap, how would to implement one.

- 1of 1 vote
Given arrays for N (>= 2) users, each representing the IDs of hotels visited, find the common IDs of the hotels visited amongst the users.

Input:

userA = { 2, 3, 1 }

userB = { 2, 5, 3 }

userC = { 7, 3, 1 }

Output:

{3}

Assumptions:

Arrays are unsorted.

Cases:

1) Each array consists of distinct hotel IDs

2) Each array may contain duplicate hotel IDs

- 0of 0 votes
You are given an array of integers and a number K. You have to find the any continue sub-array whose elements sum is K. Please note that, the array may have positive, negative, and zeros as its element.

The desired complexity is O(N).

Example:

Input: [7 0 9 -10 0 789], K = 0

Output: Array from index 1 to Index 1.

Input: [1 2 3 5 -10] K = 0

Output: Array from Index 1 to Index 4.

If K = -2, Output would have been SubArray from Index 2 to Index 4.

- 0of 0 votes
You are given an integer array. You have to return/print an array where kth element of this array is the multiplications of all the elements from 0 to k-1 and from k+1 to n-1.

Example

input: [1 2 5 6]

output: [60 30 12 10]

- 0of 0 votes
You are given a BST of integers and an integer K. You have to find the smallest greater integer then K in the BST.

Ex`40 --- 50 --- 80 | | | 45 20 --- 30 | | 10 K = 35 Output: 40`

- 0of 0 votes
We define a k-subsequence of an array as follows

1) it is a subsequence of consecutive elements in the array

2) the sum of the subsequence's elements s, is evenly devisible by k(i.e. s % k == 0)

Given an integer and input array, find out the number of k-subsequences.

Example: k=3 and array be [1 2 3 4 1]

Output: 4 ({1 2},{1,2,3},{2,3,4},{3})

- 0of 0 votes
You are given an array with duplicates. You have to sort the array with decreasing frequency of elements. If two elements have the same frequency, sort them by their actual value in increasing order.

Ex: [2 3 5 3 7 9 5 3 7]

Output: [3 3 3 5 5 7 7 2 9]

- 0of 0 votes
You are given two string (like two statements). You have to remove all the words of second string from first string and print the remaining first string. Please maintain the order of the remaining words from the first string. You will be only removing the first word, not all occurrence of a word.

Example: Str1 = "A Statement is a Statement", Str2 = "Statement a"

Output: "A is Statement"

- 0of 0 votes
You are given an integer, print its 4th least significant bit

- 0of 0 votes
You are given a rotated sorted array of size N. You have to search a given number into it.

Example: [4,6,8,14,90,-9,-2,0,3], Search -2.