## Software Engineer / Developer Interview Questions

- 2of 2 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)?

- 0of 0 votes
f(n)=n⁄2 when n is even;f(n)=f(3n+1)when n is odd. Write recursive function to compute f(n).

- 0of 0 votes
A program P reads in 500 integers in the range (0,100) representing the scores of 500 students. It then prints the frequency of each score above 50. Implement program P in C language.

- 0of 0 votes
There are four coins a , b , c , d out of which three coins are of equal weight and one coin is heavier. Write a C program to find the heavier coin.

- 0of 0 votes
You are given a string X and integer k (0 <= k < length of X). For each value of k you can look at a sub-string of X starting from index 0 to index k and choose to reverse it. As an example, let X = LMNAP and k = 2. If you reverse the sub-string of X between 0 and 2 you will get NMLAP. Subsequently if choose k = 3 and reverse you will end up with ALMNP.

Given the string X as an input find lexicographically earliest possible string. In the example above, lexicographically ALMNP comes earlier than NMLAP.

Input:

AACAACAABBABACAACBCACCCAAABACABACACCBCCAAABABACBCC

Expected Output: AAAAAAAAAAAAAAAAAAAAAAACCBBBCCBCCCCBCBCCCBCCBBCBCC

Input:

BACBCBCACAACBCBBCCBACCCCAACCBCCAABACAABCAAAABBAABC

Expected Output: AAAAAAAAAAAAAAAAAABCBCBCCCBCBBCCBCCCCCCBCCBCBCBBBC

- 3of 3 votes
Given a undirected graph with weights, return the sum of the weight of each path between two nodes (shortest path between two vertices). Assume there are no cycles.

Example:`Input: A | 1 B 2 / \ 3 C D Output: 18 since A to B has weight 1 A to C has weight 3 A to D has weight 4 B to C has weight 2 B to D has weight 3 C to D has weight 5`

Edit: Thanks, wangchenClark0512, forgot about C to D

Edit2: @Lukas, The question is just the sum of the shortest paths between two vertices. Also, all edges are positive.

Edit3: Assume the graph has no cycles, did not get to the follow-up, but follow-up probably is probably change your algorithm so that is works for cycles

- 5of 5 votes
You are given a graph with no cycles, each node representing different cities and there are stadiums for baseball games in all cities.

Each node contains a value representing the population of the city, and a list of neighbors. (feel free to extend data structure)

Every time there is a baseball game at a city, everyone from all the different cities will go to the city with the baseball game.

Return the maximum traffic between a city and its neighbours when there is a game at that city, for all cities. (Does not have to be sorted)

The total run-time after returning everything should be O(n).

Examples:`Input: 1 2 \ / 5 / \ 4 3 Output: 1 14 2 13 3 12 4 11 5 4 Input: 38 / 8 / 7 / 1 2 \ / \ 5 15 / \ 4 3 Output: 1 82 2 53 3 80 4 79 5 70 7 46 15 68 8 38 38 45`

- 1of 1 vote
Given a length n, return the number of strings of length n that can be made up of the letters 'a', 'b', and 'c', where there can only be a maximum of 1 'b's and can only have up to two consecutive 'c's

Example:

findStrings(3) returns 19

since the possible combinations are: aaa,aab,aac,aba,abc,aca,acb,baa,bac,bca,caa,cab,cac,cba,cbc,acc,bcc,cca,ccb

and the invalid combinations are:

abb,bab,bba,bbb,bbc,bcb,cbb,ccc

- 0of 0 votes
Suppose you have a matrix in the form of a 2 dimensional array. Write a method to read the rows of the matrix alternatively from right to left, left to right so on and return them as a 1 dimensional array.

for eg:

1 2 3

4 5 6

7 8 9

should return 1 2 3 6 5 4 7 8 9