## Coding Interview Questions

- 0of 0 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

- 4of 4 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 ?

- 0of 0 votes
Write a function which, given two integers (a numerator and a denominator), prints the decimal representation of the rational number "numerator/denominator".

Since all rational numbers end with a repeating section, print the repeating section of digits inside parentheses; the decimal printout will be/must be

Example:

1 , 3 = 0.(3)

2 , 4 = 0.(5)

22, 7 = 3.(142857)

etc..

- 0of 0 votes
Write a program to find distinct value out of an array. If you didnt find any duplicates return a empty array.

- 0of 0 votes
If you run the same program twice, what section would be shared in the memory?

Follow up, is the text portion of memory share? Why not?

- 0of 0 votes
Write a function that accepts an n-dimension array and prints its values--For array of any dimension.

What is the layout of multi-dimensional array in the memory?

- 0of 0 votes
Given a number n, write a function that writes a Fibonacci sequence to number n.

- 0of 0 votes
It was part of a bigger question --a large piece of code.

Implement << operator. What are the differences of implementation as a member function and a non-member function

- 0of 0 votes
What does an iterator in C++ point to in case of a vector vs. list. Where would it point to if the prior links are deleted in the list? In case of a vector if it points to a specific index, where would it point to if the prior indexes are deleted?

- 0of 0 votes
What C++ data structures would you use to implement LRU cache? Show implementation.

- 0of 0 votes
How would you implement this:

`object["String for a security name"]["another string"] = another_object`

- 0of 0 votes
What are the various ways of doing IPC in Unix/Linux? How do you implement it?

- 0of 0 votes
Design a system like friend's functionality in facebook. should have all features of facebook's friends functionality. like for each person , he can have any number of friends , he will get suggestions for new firends , showing common friends if we visits any other profile . algo should be scalable , robust .

- 1of 1 vote
Find the longest words in a given list of words that can be constructed from a given list of letters.

Your solution should take as its first argument the name of a plain text file that contains one word per line.

The remaining arguments define the list of legal letters. A letter may not appear in any single word more times than it appears in the list of letters (e.g., the input letters ‘a a b c k’ can make ‘back’ and ‘cab’ but not ‘abba’).

Here's an example of how it should work:

prompt> word-maker WORD.LST w g d a s x z c y t e i o b

['azotised', 'bawdiest', 'dystocia', 'geotaxis', 'iceboats', 'oxidates', 'oxyacids', 'sweatbox', 'tideways']

Tip: Just return the longest words which match, not all.

- 2of 2 votes
Write a code to test whether string s2 is obtained by rotating the string s1 by 2 places.

e.g S1="amazon" S2="azonam" return true

S1="quality" S2="lityqua" return false

- 0of 0 votes
Write a code to find duplicate elements in array and total count of duplicate elements.

eg. arr={5,3,4,6,7,5,3,2,1}

Duplicate elements:- 5,3

Total duplicate count:- 2

- 0of 0 votes
Design a phone book such that fields are searchable with name , with number. Later enhanced teh question asking searchable with address as well.

- 11of 11 votes
Output top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below:

1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...