## Software Engineer / Developer Interview Questions

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

- 1of 1 vote
Given an array of integers and a sum 'S'. Find 2 integers in the array that add up to S.

- 0of 0 votes
Find the first unrepeated character in a given string. Solve this in a single pass.

- 1of 1 vote
Programming Challenge Description:

Develop a service to help a client quickly find a manager who can resolve the conflict between two employees. When there is a conflict between two employees, the closest common manager should help resolve the conflict. The developers plan to test the service by providing an example reporting hierarchy to enable the identification of the closest common manager for two employees. Your goal is to develop an algorithm for IBM to efficiently perform this task. To keep things simple, they just use a single relationship "isManagerOf" between any two employees. For example, consider a reporting structure represented as a set of triples:

Tom isManagerOf Mary

Mary isManagerOf Bob

Mary isManagerOf Sam

Bob isManagerOf John

Sam isManagerOf Pete

Sam isManagerOf Katie

The manager who should resolve the conflict between Bob and Mary is Tom(Mary's manager). The manager who should resolve the conflict between Pete and Katie is Sam(both employees' manager). The manager who should resolve the conflict between Bob and Pete is Mary(Bob's manager and Pete's manager's manager).

Assumptions:

There will be at least one isManagerOf relationship.

There can be a maximum of 15 team member to a single manager

No cross management would exist i.e., a person can have only one manager

There can be a maximum of 100 levels of manager relationships in the corporation

Input:

R1,R2,R3,R4...Rn,Person1,Person2 R1...Rn - A comma separated list of "isManagerOf" relationships. Each relationship being represented by an arrow "Manager->Person". Person1,Person2 - The name of the two employee that have conflict

Output:

The name of the manager who can resolve the conflict Note: Please be prepared to provide a video follow-up response to describe your approach to this exercise.

Test 1:

Test Input

Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie

Expected Output

Mary

Test 2:

Test Input

Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John

Expected Output

Mary

- 0of 0 votes
We tend to use computer to solve practical problems that actually earns or save dollars. Here is something that happens across the stock exchanges : people buy and sell stocks.

We generally use automated intelligent systems to buy and sell stocks. That part is too much mathematics, and beyond scope of this interview. There is another part. Suppose the system issues a buy order : buy 1000 Microsoft stock. Now, there are more than 1 ( in fact 10 ) active exchanges from where we can buy MSFT. There is a slight price delta, which keeps changing over time. There is another problem. In each stock exchange, prices are stacked, that is :

1. For first 100 stocks prices are 55$.

2. Next 200 stocks, prices are 55.2$.

... etc, and you got the idea. Even this stacks are changing over time.

Thus, here is the problem to solve. Design and implement a system such that one can buy n stocks with minimal price.

Also, in the same spirit, the same system should be able to sell n stocks with maximum payoff possible.

This is a non trivial problem, for Quant systems.

There are always k no of exchanges to hit.

- 0of 0 votes
This questing was something related to parse trees. I really don't remember the semantics but needed to extract the complete sentences from the provided parse tress.

Input: A full sentence: (S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a) (NN boy)) (VP (VBG eating) (NP (NNS sausages))))))

Output: James is a boy eating sausages

Input: (NNS Sausages)

Output: Sausages

Input: (NP(DT a) (NN boy))

Output: a boy

- -1of 1 vote
For a given string sentence, reverse it.

Input : Hello World

Output : Dlorw Olleh

Input: How Are You Doing Today

Output: Yadot Ginod Uoy Era Woh

- 0of 0 votes
You will be given a sequence of passages, and must filter out any passage whose text (sequence of whitespace-delimited words) is wholly contained as a sub-passage of one or more of the other passages.

When comparing for containment, certain rules must be followed:

The case of alphabetic characters should be ignored

Leading and trailing whitespace should be ignored

Any other block of contiguous whitespace should be treated as a single space

non-alphanumeric character should be ignored, white space should be retained

Duplicates must also be filtered - if two passages are considered equal with respect to the comparison rules listed above, only the shortest should be retained. If they are also the same length, the earlier one in the input sequence should be kept. The retained passages should be output in their original form (identical to the input passage), and in the same order.

Input: For each test case a single line comprising the passages (strings) to be processed, delimited by | characters. The | characters are not considered part of any passage.

Output: A single line of filtered passages in the same |-delimited format.

Input1: IBM cognitive computing|IBM "cognitive" computing is a revolution| ibm cognitive computing|'IBM Cognitive Computing' is a revolution?

Output1: IBM "cognitive" computing is a revolution

Input2: IBM cognitive computing|IBM "cognitive" computing is a revolution|the cognitive computing is a revolution

Output2: IBM "cognitive" computing is a revolution|the cognitive computing is a revolution

- 1of 1 vote
Hey guys, I was asked this question on Bloomberg's pre-interview screening exam and I was wondering how to go about it.

Find the tightest asymptotic bound for:

T(n) = n(T(n/2)^2)

so far I was able to get it to look like this (not sure if correct):

T(n) = 1 / (1 + T(n/2)^2)

From then I made a recursion tree which led me to think that T(n) might be exponential in this case. Do you have any idea where could I go from here? Do you think this has no tight asymptotic bound?

- 0of 0 votes
why we need interface ( pure virtual function or abstract class) in c++?

Instead of having abstract class we can have a base class with virtual function defined in it, and override that virtual function in derived class.

what would be the advantage and disadvantage with the above approach ( except we can create the object of the base class)?