## Coding Interview Questions

- 0of 0 votes
Input any string, count the maximum depth of parenthesis nesting, i.e. "abc(123(xyz))m(((n)))o" -> 3.

if input is null or contains a mismatch "a)b(c" or "a(b"

Also some other samples:

(((()))) -> 4

()()()() -> 1

- 0of 0 votes
Convert a binary tree into a In Order traversal circular list re-purposing the node's pointers Left & Right as Previous and Next respectively.

Hint: A single node Left & Right points to itself.

Note: This is not a binary search tree.

- 0of 0 votes
Write a function that takes an array of numbers and returns the maximum and minimum values.

Give BigO for runtime.

(This is a basic coding question. There are no real tricks or shortcuts.)

- 0of 0 votes
Given a list of employees and their bosses as a text file , write a function that will print out a hierarchy tree of the employees.

Sample input =

Sam, Ian, technical lead, 2009 / Ian, NULL, CEO,2007/ Fred, Sam, developer, 2010

The format is name, supervisor, designation, year of joining

The output should be

Ian CEO 2007

-Sam Technical lead 2009

- -Fred Developer 2010

- 0of 0 votes
(Variant of Children-Sum Problem better than O(n^2))

Given a tree, implement a function which replaces a node’s value with the sum of all its childrens’ value, considering only those children whose value is less than than the main node’s value.

Eg: input = 60->50->80->40 , output = 90->40->40->0

- 0of 0 votes
Given a function rev(int i) which reverses the segment of array ar[] from 0-i, Implement a function sort() using rev().

- 0of 0 votes
Find if a given number can be expressed in the form of p^q, where p and q are integers

- 0of 0 votes
Find all palindromes in a given string. Single letters are also considered as palindromes.

- 0of 0 votes
Given a number A, find the smallest number which has only 1s and 0s as its digits which divisible by the number A. For example: if the given number A is 4, the smallest number with 1s and 0s is which is divisible by 4 is 100.

- 1of 1 vote
{{

There are 3 machines M1, M2 and M3. Each machine is 90% full of its capacity with integers. Now you have to sort all the integers combined and then store the first 1/3rd in M1, second 1/3rd in M2 and last 1/3rd in M3.

Your objective is to minimize the number of sort operations and number of data transfer operations.

Each sort operation/data transfer operation is counted as 1 irrespective of the count of values that are being sorted/transferred.

}}

- 0of 0 votes
How to find efficiently the minimum of an array of integers that is the maximum of other arrays?

Example:

A = [126, 110, 130]

B = [125]

C = [105, 115]

The minimum element of array A that is the maximum of B and C is 126

- 0of 0 votes
Write a function that takes a string as an input and outputs an integer, e.g. turning "1234" into 1234.

- 0of 0 votes
Java coding

Given a file with the following entry

ID EMp_Name Manager_ID

1 "ABC" 2

2 "PRW" Null

3 "DEF" 2

4 "PRE" 3

5 "DKF" 4

Print the Respective Manager hierarchy in the below format

PRW | ABC |

| DEF | PRE | DKF

The Employe Manager table can be extended to Hold N entry

- 0of 0 votes
1) You have a folder full of .bin files that are proprietary.

2) You have a class called converter with a "binToTSV" method which you can pass the name of a .bin file and will generate a .tsv file.

3) The TSV file is a tab separated value file with a key on each line, and a value next to it spaced with a tab as such.

-------

num_connections 65

latency_ms 70

bandwidth 20

.... //etc.

-------

Q: Write a method to calculate the average latency and total bandwidth.

- 0of 0 votes
how to design a relation functionality. similar to facebook , how to hold friends objects for a user profile , so that that is easily searchable . how to use cache for this?

- 3of 5 votes
You are given two integer arrays A and B .

1<=i<=len(A) so i is iterator of array A

1<=j<=len(B) so j is iterator of array B

find all the pairs(i,j) such that : i < j and A[i]>B[j]

- 3of 3 votes
given a pre and post order kindof a traversal (2 arrays) create an n-ary treee out of it with struct of the form :

struct node {

int data;

struct node *child[MAX];

int child_num;

}

- 0of 0 votes
given matrix like :

a b e d

b c f e

a b d d

….

find the longest path of consecutive alphabets given a starting alphabet. You can move in all 8 directions. for eg. a->b(right)->c(down)->d(diagnal down)… len = 4 , find max such len

- 0of 0 votes
You are given a rectangular grid with 2 rows and N columns. The top row is labeled 1 and the bottom row is labeled 2. The columns are labeled from 1 to N in increasing order. Each cell in the grid contains a single character.

Consider a hamiltonian walk in this grid. Meaning, pick a starting cell, say (i,j), and consider a path that starts from (i,j) and goes through every cell in the grid exactly once. Note that you can only walk to adjacent cells, or cells that you share a common edge with. There may be several such paths. Let us concatenate the characters in the order in which the cells are visited during a walk. The string formed can be called the string for the walk.

Among all the possible walks, and their respective strings, find out the lexicographically smallest string. We know that the length of the strings are all the same - to be precise, 2N. Thus, the lexicographically smallest string is simply the alphabetically smallest string if you compare the characters from left to right.

Input

The first line of input contains a number T, the number of test cases. Then follow T test cases. Each test case contains 3 lines. The first line contains the number N, the number of columns in the grid. It is well known of course that the grid contains 2 rows. The next two lines contain the description of the grid in the form of two strings; the string of N characters in row 1 from left to right and the string of N characters in row 2 from left to right, respectively. Each character will be a lowercase engish letter.

Output

Output a single line for each test case. The line must contain a string with 2N characters. This string should be the lexicographically smallest string for some hamiltonian walk in the grid.

Constraints

1 = T = 100

1 = N = 10

Sample Input

2

3

abc

def

10

ababaaabab

bababababa

Sample Output

abcfed

aaababababababababab

Explanation

In the first test the possible strings are { abcfed, adebcf, adefcb, badefc, bcfeda, cbadef, cfedab, cfebad, dabcfe, dabefc, defcba, edabcf, efcbad, fedabc, fcbade, fcbeda }. The smallest string is abcfed.

- 1of 1 vote
given n > 0 fair dice with m > 0 "sides", write an function that returns a histogram of the frequency of the result of dice rolls. For example, for two dice, each with three sides, the results are:

(1, 1) -> 2

(1, 2) -> 3

(1, 3) -> 4

(2, 1) -> 3

(2, 2) -> 4

(2, 3) -> 5

(3, 1) -> 4

(3, 2) -> 5

(3, 3) -> 6

And the function should return:

2: 1

3: 2

4: 3

5: 2

6: 1

- 6of 6 votes
Given a string (1-d array) , find if there is any sub-sequence that repeats itself.

Here, sub-sequence can be a non-contiguous pattern, with the same relative order.

Eg:

1. abab <------yes, ab is repeated

2. abba <---- No, a and b follow different order

3. acbdaghfb <-------- yes there is a followed by b at two places

4. abcdacb <----- yes a followed by b twice

The above should be applicable to ANY TWO (or every two) characters in the string and optimum over time.

In the sense, it should be checked for every pair of characters in the string.

- 0of 0 votes
Implement bool regex() Function.

- 1of 1 vote
Implement bool isBST(Tree * root)

- 1of 1 vote
You are given a string S. Each character of S is either ‘a’, or ‘b’. You wish to reverse exactly one sub-string of S such that the new string is lexicographically smaller than all the other strings that you can get by reversing exactly one sub-string.

For example, given ‘abab’, you may choose to reverse the substring ‘ab’ that starts from index 2 (0-based). This gives you the string ‘abba’. But, if you choose the reverse the substring ‘ba’ starting from index 1, you will get ‘aabb’. There is no way of getting a smaller string, hence reversing the substring in the range [1, 2] is optimal.

Input:

First line contains a number T, the number of test cases.

Each test case contains a single string S. The characters of the string will be from the set { a, b }.

Output:

For each test case, print two numbers separated by comma; for example “x,y” (without the quotes and without any additional whitespace). “x,y” describe the starting index (0-based) and ending index respectively of the substring that must be reversed in order to acheive the smallest lexicographical string. If there are multiple possible answers, print the one with the smallest ‘x’. If there are still multiple answers possible, print the one with the smallest ‘y’.

Constraints:

1 ? T ? 100

1 ? length of S ? 1000

Sample Input:

5

abab

abba

bbaa

aaaa

babaabba

Sample Output:

1,2

1,3

0,3

0,0

0,4

- 5of 5 votes
Given a number M (N-digit integer) and K-swap operations(a swap

operation can swap 2 digits), devise an algorithm to get the maximum possible integer?

Examples:

M = 132 K = 1 output = 312

M = 132 K = 2 output = 321

M = 7899 k = 2 output = 9987

M = 8799 and K = 2 output = 9987

- 0of 0 votes
Suppose you want improve the performance of search queries, using a cache. Each search queries is in form of a string and returns a list of ad id's in the form of longs.

Design a class with the appropriate data structure(s) that can manage a cache of search queries.

- 1of 1 vote
Write a recursive method to get the multiplication of two numbers such that there are minimum number of addition operations.

- 5of 5 votes
Given three arrays A,B,C containing unsorted numbers. Find three numbers a, b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum

Please provide as efficient code as you can.

Can you better than this ???

- 0of 0 votes
what all design patterns are used in designing a shopping cart and explain?

- 0of 0 votes
Given an array[0, n-1], each number of the array is positive int. Your task is adding the operators,"+","*", "(",")" (add, multiply, parenthesis) to maximize the result . The position in the array is Fixed.

For example, "2,1,1,2", you can get (2+1)*(2+1)=9.

Follow up, if the number may be negative , how to solve it ?