5 Tech Problems that will help ace your interview

March 21, 2017

Top companies like Google, Microsoft, frequent a lot of problems in interviews. The basic research will yield a lot of results, but we went a step further to pull out the most common problems. Knowledge of these problems will definitely give you an edge over your competitors in interviews.

### Profit Maximization :

**Input:**

First line contains number of test cases ‘T’. Each test case contains the integer value ‘N’, denoting the number of days followed by an array of oil barrel prices in N days.

**Output:**

The days on which the barrels should be bought and sold to maximize profit should be displayed as shown below. And if there is no possibility to make profit then print -1. Multiple deals have to be included in the same line. One cannot buy more than one barrels of oil at the same time. Meaning you have to sell the barrel before buying again.

**Example**

**Input:**

3

8

130 190 230 310 40 285 565 645

10

34 16 24 28 38 17 31 46 62 69

7

79 65 34 29 29 24 19

**Output:**

(0 3) (4 7)

(1 4) (5 9)

-1

### Word Reversal:

Given a string of length N reverse the order of words in it. Words are separated by dots.

**Input:**

The first line contains ‘T’, denoting the number of testcases. This is followed by individual test cases. Each case contains a string made up of spaces and characters.

**Output:**

For each test case, output a single line containing the string with the reversed words.

**Example:**

**Input:**

3

i.is.break.random.talk.lobo

ako.bobo

bad.like.alpha.cha lie

**Output:**

lobo.talk.random.break.is.i

bobo.ako

cha lie.alpha.like.bad

### Tree Balance:

Given a binary tree, find if it is height balanced or not. A tree is height balanced if the difference between heights of left and right subtrees is not more than one for all nodes of tree. Expected time complexity is O(n).

A height balanced tree

1

/ \

10 39

/

5

An unbalanced tree

1

/

10

/

5

**Input:**

The task is to complete the method which takes one argument, root of Binary Tree. The following characters use the mentioned format:

N M (L/R) , N mentions the root for the node M, L/R defines whether the element M is part of the left subtree or right subtree.

There are multiple test cases. For each test case, this method will be called.

**Output:**

The function should return true if tree is height balanced, else false.

**Example:**

**Input:**

2

2

1 2 L 2 3 L

4

10 20 L 10 30 R 20 40 L 20 60 R

**Output:**

False

True

**Sudoku Solver:**

Given an incomplete Sudoku matrix, in a 9×9 2-D square matrix (mat[][]), print a solution of the Sudoku. Assume that there will be only one unique solution.

For the above configuration the solution is

4 3 5 2 6 9 7 8 1

6 8 2 5 7 1 4 9 3

1 9 7 8 3 4 5 6 2

8 2 6 1 9 5 3 4 7

3 7 4 6 8 2 9 1 5

9 5 1 7 4 3 6 2 8

5 1 9 3 2 6 8 7 4

2 4 8 9 5 7 1 3 6

7 6 3 4 1 8 2 5 9

**Input:**

The first line of input contains an integer ‘T’ denoting the number of test cases. Then T test cases follow. Each test case contains 9*9(81) space separated values of the matrix mat[][] representing an incomplete Sudoku puzzle. Here, 0 represents an empty block.

**Output:**

For each test case in a new line print the space separated values of the solution of the the sudoku.

**Example:**

**Input:**

1

3 0 6 5 0 8 4 0 0 5 2 0 0 0 0 0 0 0 0 8 7 0 0 0 0 3 1 0 0 3 0 1 0 0 8 0 9 0 0 8 6 3 0 0 5 0 5 0 0 9 0 6 0 0 1 3 0 0 0 0 2 5 0 0 0 0 0 0 0 0 7 4 0 0 5 2 0 6 3 0 0

**Output:**

3 1 6 5 7 8 4 9 2 5 2 9 1 3 4 7 6 8 4 8 7 6 2 9 5 3 1 2 6 3 4 1 5 9 8 7 9 7 4 8 6 3 1 2 5 8 5 1 7 9 2 6 4 3 1 3 8 9 4 7 2 5 6 6 9 2 3 5 1 8 7 4 7 4 5 2 8 6 3 1 9

### Number of Cities:

A group of connected 1s forms a City now your task is to complete the method findCity which returns the no of Cities present. The function takes three arguments. The first is the boolean matrix A and then the next two arguments are N and M denoting the size of the matrix A .

**Input:**

The first line of input will be the no of test cases T. Then T test cases follow. The first line of each test case contains two space separated integers N and M. Then in the next line are the NxM inputs of the matrix A separated by a space.

**Output:**

The expected output will be the total no of cities present.

**Example :**

**Input**

1

3 3

1 1 0 0 0 1 1 0 1

**Output**

2

There are a lot of other questions that are frequented by many companies. While there is no way to know which problems you will be asked, it is best to remain prepared. This is a small list of questions, but you can search for the most commonly asked questions to improve your prep.

We will be releasing the solution in a week’s time so that you can have time to work on the problem from your end.

For other more interesting and challenging problems, log on to Xobin(https://xobin.com ) and interact with the bot.

Excellent post!