## Software Engineer / Developer Interview Questions

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

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

- 0of 0 votes
You are given an array of words. from each word, you make a chain, in that, you remove one char at a time and you remove that char only when the remaining word is present in the input array.

For Example, if the input is {a, b, ab, ac, aba}

then the possible chains are

from 'a', there is no chain, the chain it 'a' itself (of length 1)

similarly, from 'b', the chain length is 1 one (length is defined by the number of words in the chain)

now from 'ab', there are two possibilities which are ({ab -> b when you remove a},{ab -> a when you remove b}). So the max length is 2 here

now from 'ac', we only have one possibility which is ({ac -> a when we remove c}), because, when we remove 'a', we left with 'c' which is not present in the input.

Now, you have to find the length of the biggest such chain.

Input: array of words

Output: length of the biggest such chain.

- 0of 0 votes
Friends have transitive property where if A is the friend of B, and B is the friend of C then A is also the friend to C. Like that we make friend circle.

You have to find the number of such circles in a given list of friends

You are given a NxN matrix, where columns of each row will have either 'N' or 'Y', where 'N' represents not a friend and 'Y' represents Yes, they are friends.

Example :

YNY

NYN

YNY

The output is 2({0,2},{1}), as the 0 and 2 are friends of each other and 1 is another friend who is neither friend with 0 nor with 2.

- 0of 0 votes
Q1. You are given a binary search tree (with unique values) and two values. You need to find their lowest common ancestor. (Expected Complexity O(log(n)) + O(1))

Q2. Now let's assume the tree has duplicates, and when a duplicate number come, the insertion logic chooses left node. (Expected Complexity O(log(n)) + O(1))

Q3.Now let's assume the input tree is a binary tree instead of the binary search tree.(Expected Complexity O(n) + O(1))

- 0of 0 votes
You are given a vector of integers. You have to delete the odd numbers from it.

Expected complexity is O(N) Time and O(1) space

- 0of 0 votes
You are given an unsorted binary array.

Ex [0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1]

and a number K, which represents the number of swap operations allowed on this binary array.

you need to find out the maximum length continuous subarray that can be generated using K many swaps.

Ex if K = 3 in above case

[0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1] => [0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1] => [0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0] => [0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0]

so the answer is 9.

- 1of 1 vote
You are given a binary matrix whose each row is sorted. that means each row will have zeros at front and ones at the back. You need to find out the row which contains a maximum number of ones.

Ex :`[0 0 0 0 0 0 0 1 1 1 1 1] [0 0 0 0 1 1 1 1 1 1 1 1] [0 0 0 0 0 0 1 1 1 1 1 1] [0 0 0 0 0 0 0 0 0 1 1 1] [0 0 0 0 0 0 0 1 1 1 1 1] [0 0 0 0 1 1 1 1 1 1 1 1]`

Ans : second row and sixth with 8 ones. you will print [2,8] and [6,8];

Update : Required complexity O(M+N) + O(1) only.

- 0of 0 votes
Implement a stack that in addition to push and pop has a function that returns the min value of the stack.

I came up with a O(logn) solution, but he wanted a O(1) for the whole algorithm.