## Software Engineer / Developer Interview Questions

- 0of 0 votes
Check if two given binary trees(expression trees with two characters 'a' and 'b' and obviously operators like +,-,*) are mathematically equivalent?

- 0of 0 votes
Given two strings representing very large integer numbers, find the Product. Do not use BigInt.

`using System; public class Program { public static void Main() { Console.WriteLine( GetProduct("18888888888888888888888888","19999999999999999999999999999999999999999999999999999999999")); } public static string GetProduct(string s1,string s2) { int digit1=0; int digit2=0; char[] str1=s1.ToCharArray(); char[] str2=s2.ToCharArray(); int carry; string[] result=new string[str1.Length]; string finalproduct=string.Empty; int padding=0; for(int i=str1.Length-1;i>=0;i--) { digit1=str1[i]-'0'; string resval=string.Empty; carry=0; int j; for(j=str2.Length-1;j>=0;j--) { digit2=str2[j]-'0'; int product=digit1*digit2+carry; carry=product/10; resval=resval+(product%10); } if(carry>0) { resval=resval+carry; } for(int k=0;k<padding;k++) { resval="0"+resval; } result[i]=resval; padding++; } int max=findMax(result); int count=0; int car=0; while(count<max) { int sum=0; for(int x=0;x<result.Length;x++) { if(count<result[x].Length) { sum+=result[x][count]-'0'; } } sum+=car; car=sum/10; int p=sum%10; finalproduct=p+finalproduct; count++; } finalproduct=car+finalproduct; return finalproduct.TrimStart('0'); } public static int findMax(string[] s) { int max=0; for(int i=0;i<s.Length;i++) { int len=s[i].Length; max=Math.Max(max,len); } return max; }`

}

- 0of 0 votes
Turtle is on a N * N grid, with N obstacles. The turtle can only move F orward one position

and can turn L eft or R ight. The grid has 4 directions N, E, W, S

Assuming that the initial position of turtle is 1, 1 (bottom left corner of the grid facing North) and

the grid has random obstacles in a few of its cells, given the movement instructions, find the

final position of turtle and printing the grid state will be an added plus. When there is an

obstacle, movement is not possible.

input :

FFFRRFLF

output:

2,3 E

- 3of 3 votes
`/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */`

Find if a given binary tree has duplicate sub trees.

followup:

Find all duplicate subtrees in a binary tree`For example, 1 / \ 2 3 / / \ 4 2 4 / 4 The following are two duplicate subtrees: 2 / 4 and 4 Therefore, return [ [2,4], [4] ].`

- 0of 0 votes
Given a diamond shape matrix, find the minimum path sum from top to bottom.

Each step you may move to adjacent numbers on the row below.`[ [2], [3,4], [6,5,7], [4,1,8,3], [2,5,4], [6,4], [1] ]`

- 0of 0 votes
Design a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)

- 0of 0 votes
Given the weekly vacation numbers for various cities for an year (ie 12 * 4 = 48 weeks ) , design a tour which will maximize the number of vacations for a salesman. The salesman can choose to work in any city for the week , and can weekly change the city unlimited number of times , but has to remain in the city for the week . It's not necessary for the salesman to go to all cities , goal is to find the schedule which maximize the vacation for whole year. Input will be HashMap<string , int[48] vacation> where string is the city name and int[48] is city's vacation numbers for an year.

- -2of 2 votes
Consider a hotel where the guest is checked in and check out. Find a day when the maximum number of guests stay in a hotel.

example:

Input :

[

{check-in : 1, check-out 4},

{check-in : 2, check-out 5},

{check-in : 10, check-out 12},

{check-in : 5, check-out 9},

{check-in : 5, check-out 12}

]

Output : 5

- 0of 0 votes
Given number N, Find the least number of perfect square number sum needed to get N.

Example :

n=5 (4+1) i.e. 2

n=7 (4+1+1+1) i.e. 4

n=12 (4+4+4) i.e 3

n=20 (16+4) i.e. 2

- 0of 0 votes
How to verify the string which contains alpha-bates,parenthesis and signglle/double quote

Ex: AB(CD{"GH"}) is valid

"A()B' is invalid

- 0of 0 votes
What is the smallest number *n* by which the given number *x* must be divided to make it into a perfect square?

`n = find_number( x )`

- 0of 0 votes
Running with Bunnies

====================

You and your rescued bunny prisoners need to get out of this collapsing death trap of a space station - and fast! Unfortunately, some of the bunnies have been weakened by their long imprisonment and can't run very fast. Their friends are trying to help them, but this escape would go a lot faster if you also pitched in. The defensive bulkhead doors have begun to close, and if you don't make it through in time, you'll be trapped! You need to grab as many bunnies as you can and get through the bulkheads before they close.

The time it takes to move from your starting point to all of the bunnies and to the bulkhead will be given to you in a square matrix of integers. Each row will tell you the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order. The order of the rows follows the same pattern (start, each bunny, bulkhead). The bunnies can jump into your arms, so picking them up is instantaneous, and arriving at the bulkhead at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any bunnies you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the bulkhead doesn't mean you have to immediately leave - you can move to and from the bulkhead to pick up additional bunnies if time permits.

In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the bulkhead to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is, each time a path is traversed, the same amount of time is used or added.

Write a function of the form answer(times, time_limit) to calculate the most bunnies you can pick up and which bunnies they are, while still escaping through the bulkhead before the doors close for good. If there are multiple sets of bunnies of the same size, return the set of bunnies with the lowest prisoner IDs (as indexes) in sorted order. The bunnies are represented as a sorted list by prisoner ID, with the first bunny being 0. There are at most 5 bunnies, and time_limit is a non-negative integer that is at most 999.

For instance, in the case of

[

[0, 2, 2, 2, -1], # 0 = Start

[9, 0, 2, 2, -1], # 1 = Bunny 0

[9, 3, 0, 2, -1], # 2 = Bunny 1

[9, 3, 2, 0, -1], # 3 = Bunny 2

[9, 3, 2, 2, 0], # 4 = Bulkhead

]

and a time limit of 1, the five inner array rows designate the starting point, bunny 0, bunny 1, bunny 2, and the bulkhead door exit respectively. You could take the path:

Start End Delta Time Status

- 0 - 1 Bulkhead initially open

0 4 -1 2

4 2 2 0

2 4 -1 1

4 3 2 -1 Bulkhead closes

3 4 -1 0 Bulkhead reopens; you and the bunnies exit

With this solution, you would pick up bunnies 1 and 2. This is the best combination for this space station hallway, so the answer is [1, 2].

Test cases

==========

Inputs:

(int) times = [[0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 0, 1], [1, 1, 1, 1, 0]]

(int) time_limit = 3

Output:

(int list) [0, 1]

Inputs:

(int) times = [[0, 2, 2, 2, -1], [9, 0, 2, 2, -1], [9, 3, 0, 2, -1], [9, 3, 2, 0, -1], [9, 3, 2, 2, 0]]

(int) time_limit = 1

Output:

(int list) [1, 2]

- 2of 2 votes
Given points on a plane like (0,0), (1,0), (0,1), (1,1), (0,2), (2,2), (1,2). How many rectangles can be formed ?

- 0of 0 votes
I was asked to design a stock ticker system. Stock ticker is simply the shortened name of company and its current stock size. e.g. for Apple - "AAPL" -> "115"

He asked me to design a data structure to store incoming stream of stock tickers. Stream can contain same company more than once but all the values of it had to be stored. I used HashMap<String, List<Integer>>. Then he was adding more functionalities to system I don't exactly remember the questions now but one of them was related to calculating some ratio in constant time. Some of the questions were challenging.

- 0of 0 votes
Given a set find its power set. (This question is from CTCI) Interviewer then discussed the complexity of my solution. He asked me to explain him how the complexity is 2^n? As per my solution, I was iterating over an arraylist which contained the set elements so the size of list was getting doubled in every iteration. Hence the complexity (2^0 + 2^1 + 2^2 +.....+2^n-1 = 2^n)

- 0of 0 votes
Given a string, add some characters to the from of it so that it becomes a palindrome. E.g.1) If input is "abc" then "bcabc" should be returned. 2) input -> "ab" output -> "bab" 3) input -> "a" output -> "a"

- 0of 0 votes
You are given a binary tree. Each node in the tree is a house and the value of node is the cash present in the house. A thief can rob houses in alternate levels only. If thief decides to rob house at level 0 then he can rob houses in levels 2,4,6... or he can rob houses in levels 1,3,5,7...Find out the maximum possible amount thief can rob.

- 3of 3 votes
Return the length of longest possible chunked palindrome string.

Examples :

Input : VOLVO

Output : 3

Explanation :

(VO)L(VO)

Input : merchant

Output : 1

Explanation : No chunks possible.

Input :

ghiabcdefhelloadamhelloabcdefghi

Output : 7

Explanation :

(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)

- 2of 2 votes
As an input, you have points on a 2D graph. You aim to find a straight line that can fit as my points as possible. Return, the maximum number of points you can fit.

- 1of 1 vote
Given a pattern and a string - find if the string follows the same pattern Eg: Pattern : [a b b a], String : cat dog dog cat

- 0of 0 votes
int bits(unsigned char v);

Which returns number of set bits in v.

A) Optimize for memory usage:

B) Optimize for speed:

- 0of 0 votes
Given a dictionary, 7 digit phone number and a phone pad where each number could have a list of alphabets attached to it, for eg. 2- {a,b,c}, 3-{d, e,f} and so on, find the list of possible meaningful strings that could be formed with the phone number.

- 0of 0 votes
1. Find if two strings are palindrome

2. Given a list of strings, check if concatenating any two string would form a palindrome. Brute force way to do this is O(n^3), he asked ways to optimize this.

- 0of 0 votes
Serialize and deserialize a binary tree

- 3of 3 votes
Tom works in a warehouse. A billion (1,000,000,000) boxes are arranged in a row. They are numbered from one to one billion (from left to right). Some boxes contain a basketball (at most one basketball in each box). In total, there are N basketballs.Tom wants to organize the warehouse. He would like to see all the basketballs arranged next to each other (they should occupy a consistent interval of boxes). In one move, Tom can take one basketball and move it into an empty box. What is the minimum number of moves needed to organize the basketballs in the warehouse?

Write a function:`class Solution { public int solution(int[] A); }`

that, given an array A containing N integers, denotes the positions of the basketballs (the numbers of the boxes in which they are placed) and returns the minimum number of moves needed to organize the basketballs in the warehouse.

For example, given: A = [6, 4, 1, 7, 10], your function should return 2 because the minimum number of moves needed to arrange all basketballs next to each other is 2. There are several ways to do it. For example, you could move the ball from the first box to the fifth, and the ball from the tenth box to the eighth. You could also move the ball from the first box to the fifth, and the ball from the tenth box to the third instead. In any case, you need at least two moves.

To be done in O(nlogn) Time complexity and O(1) space complexity

- 1of 1 vote
n points on a 2D space. You observe the points from (0,0) with viewing direction and viewing angle.

Given an array (xn,yn), and a viewing angle v (45 degree), find the direction that can observe max number of points.

- 2of 2 votes
Given a function getRandom that returns a random double in [0,1). Write a function getRandomPermutation(int n) that takes a positive integer n as argument and returns a random permutation of first n natural numbers.

- 0of 0 votes
For this problem, we would like you to think of a single line of text, and justify that text into a buﬀer,where the ﬁrst character of the line of text is in the ﬁrst spot in the buﬀer and the last character of textis in the speciﬁed slot in the buffer.

In ruby, you might deﬁne this function as follows:`def justify(line, length)`

It might be called like this:

`puts justify("The quick brown fox jumps over the lazy dog.", 52)`

It produces a string that looks like this:

`The quick brown fox jumps over the lazy dog. 1234567890123456789012345678901234567890123456789012 (You have 7 characters remaining in the buffer)`

- 0of 0 votes
What is indexing in a database?

What are the underlying data structures you think are involved in indexing of a database?

What are some upsides and downsides of using indexing?

- 0of 0 votes
Given an array of integers. Find the surpasser count of each element of the array.

"A surpasser of an element of an array is a greater element to its right"

ex -

Input: [2, 7, 5, 3, 0, 8, 1]

Output: [4, 1, 1, 1, 2, 0, 0]