Given that, there are 2 linked lists L1 and L2. Write an algorithm that finds the point of intersection of the two linked lists.

There is a temple, whose premises have a garden and a pond. It has 4 idols, each of Ram, Shiv, Vishnu and Durga. The priest plucks x flowers from the garden and places them in the pond. The number of flowers doubles up, and he picks y flowers out of them and goes to offer it to Lord Ram. By the time he reaches to the pond, he finds the remaining flowers also have doubled up in the meantime, so he again picks up y from the pond and goes to Lord Shiv. This process is repeated till all the Gods have y flowers offered to them, such that in the end no flower is left in the pond. Find x and y.

Given 2 arrays of numbers find if each of the two arrays have the same set of integers?

Suggest an algorithm which can run faster than NlogN.

What are the parameters required to implement a strcpy function

Find non repeating element in an arrayI have an array consisting of 2n+1 elements. n elements in it are married, i.e they occur twice in the array, however there is one element which only appears once in the array. I need to find that number in a single pass using constant memory. {assume all are positive numbers}

Eg :- 3 4 1 3 1 7 2 2 4

Ans:- 7

Find common elements in two unique sorted arraysWe have two unique sorted arrays. Need to find common elements from these arrays

Implement stack using linked listImplement stack using linked list.

Write a program to compact spaces in a stringWrite a program to compact spaces in a string i.e. Given a string you have to remove multiple occurrences of blank spaces by a single space and do that in a single pass of the arrays.

Implement queue using stack

Merge two sorted arrays without extra spaceMerge two sorted arrays without extra space.

Print a binary tree in level orderPrint a binary tree in level order. It means that all the nodes of the tree at the same vertical level are to be printed in one line. Insert a line end after one level.

Given a set of items, each with a weight (w

_{i}) and a value (v_{i}), determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Merge two unsorted array and remove the duplicate from the resultant array. exampleArray1 = {“are”,”you”,”there”}

Array2={“how”,”are”,”you”}

output={“how”,”are”,”you”,”there”}You are given a pointer to a node of a min heap. The value of this node changes. Write a function that fixes the min heap.Implement strstr function. Write a solid secure code.

Search an element in an array which has been circularly rotated by ‘n’.

How to remove duplicate data from an array efficiently? Provide more solutions in the form with additional memory with O(n), O(n^{2}) and O(nlogn).

Merge two sorted arraysWe have two sorted array. Without using additional memory we need to merge these two arrays such that the initial numbers are in the 1st array and the remaining numbers are in the second array.

Suppose you are getting an infinite binary stream of characters then after any point of time you need to print whether the no is divisible by 3 or not, how will you do that?

Modified two color sorting problem.Modified 2 color sort problem i.e. you are given an array of integers containing only 0s and 1s.You have to place all the 0s in even position and 1s in odd position. And if suppose, no. of 0s exceed no. of 1s or vice versa then keep them untouched. Do that in a single pass and without taking extra memory (modify the array in-place).

Reverse a linked list k at a timeYou are given a Linked List and a function declaration as node_ KReverse(node_ head, int k)

KReverse is a function that reverses the nodes of a Linked List k at a time and then returns the modified Linked List.

Constraints:

â€¢ If the no. of nodes in a link list is not a multiple of k then left-out nodes in the end should remain as it is.

â€¢ You have to retain the memory address of the nodes without modifying it i.e. you can’t just interchange the values in the nodes.

â€¢ No extra memory allowed.

Remove duplicate entries in an array.Write a code to remove duplicate entries in array of size N having elements only from 1 to N.

Given an array of size n+1 which contains all the numbers from 1 to n. Find the number which is repeated in O(n) time. How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to n?

**Convert a Binary Search Tree to a sorted doubly circular Linked list**Convert a Binary Search Tree to a sorted doubly circular Linked list

**Median of two sorted arrays**There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n).

This question doesn’t have a title. Add Title

**Space complexity of Quick Sort algorithm**

**What are dangling pointers**

**Remove duplicate elements in a string**Given a string *Str of ASCII characters, write the pseudo code to remove the duplicate elements present in them. For example, if the given string is “Potato”, then, the output has to be “Pota”. Additional constraint is, the algorithm has to be in-place( no extra data structures allowed).

**Find unbiased decision out of a biased coin.**You are given biased coin. Find unbiased decision out of it?

**Find the missing number in the array**You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them.

**Cycle in a Linked List**You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.

**Find the first out of order character in a string**Write a method to return the index of first out of order letter in input string. String contains only letters either upper case or lower case. For example if there are strings ABCDAFGH and ABCDaF then we should return 4 and if we encounter any letter other than a-z or A-Z the method should return ERROR.

**What are Virtual Methods**

Find k^{th} number in a BST.

**Maximum and Minimum element of an array in least comparisons**You have given an array. Find the maximum and minimum numbers in less number of comparisons.

**Interleaving of strings**Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B. Ex: A=”abcd” B=”xyz” C=”axybczd”. answer is yes.

Output: An array of size n.Relationship:

elements of input array and output array have 1:1 correspondence.

output[i] is equal to the input[j] (j>i) which is smaller than input[i] and j^{th}is nearest to i^{th}( i.e. first element which is smaller).

If no such element exists for Input[i] then output[i]=0.Eg.

Input: 1 5 7 6 3 16 29 2 7

Output: 0 3 6 3 2 2 2 0 0

for(;0;)

printf(“\n guess”);

and why?

b) db relations are sorted on the primary key

c) B-trees require less memory than binary search tree

d) Data transfer from disc is in blocks

b) Quick

c) Heap

d) Radix

**Maximum and minimum number of tuples in a natural join**Consider the following relation schema pertaining to a students database:

Student (*rollno*, name, address) Enroll (*rollno*, *courseno*, coursename)

where the primary keys are in italics. The number of tuples in the Student and Enroll tables are 120 and 8 respectively. What are the maximum and minimum number of tuples that can be present in (Student *x* Enroll), where *x* denotes natural join?

^{2}-1) is div by 24.

Note: n is odd and >=3

hh:mm:ssHandle special cases carefully.

Order (OrderID, OrderDate)

OrderItem (ItemID, OrderID)Query:

1. List all orders put yesterday.

2. How many items were ordered yesterday?

3. List all orders which order more than 3 items yesterday.

4. How many orders which order more than 3 items yesterday?

a) When length of string is known.

b) When length of string is unknown. (you cannot calculate the length)Come up with as many test cases as you can.

Reverse every k nodes of the linked list.

**Anagrams**Given an array of strings, please make the function that accepts this array of strings and finds out the anagrams in it.

Also give the case where the linked list has a cycle.

**Merge k sorted list of size n**Merge k sorted list of size n into a single sorted list. Give the most efficient solution. Give its time complexity.

**Given a string find the first un-repeated character in it**Given a string find the first un-repeated character in it? Give some test cases.

We are given with two arrays A and B. Each of size N. Elements of array contains either 1 or 0. We have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A (between this interval) and sum of all elements of B (between this interval ) is equal. i.e.

a[p]+a[p+1]….+a[q]= b[p]+b[p+1]….+b[q]

**Write a program to remove duplicate elements from array**Write a program to remove duplicate elements from array. (Array contains elements in range 1…N). Algorithm must be O (N) in time and O (1) in space. Come up with as many test cases as you can.

b) given a string find all valid anagrams in a dictionary

c) typing prefix of a valid string suggests valid words

**Design class Phone-Book**Design class Phone-Book. The interviewer was interested in data structure and prototypes of different methods.

**Change making problem – Dynamic Programming**You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?

**Find whether a word can be formed by two words in a dictionary**Given a dictionary find out if given word can be made by two words in dictionary. For eg. given “newspaper” you have to find if it can be made by two words. (news and paper in this case).

Design classes for the following problem.A Customer Can have multiple bank accounts A Bank account can be owned by multiple customers When customer logs in he sees list of account, on clicking on an account he sees list of transactions.

**How does HTTP works?**How does HTTP works?

**Difference between COM and CORBA.**What is the difference between COM and CORBA?

**What is web service?**What is web service?

Given one unsorted integer array, find out all the unique element in the array.

eg: Input: {23,53,1,3,6,23,1,7,9,53,9} Ouput;{3,6,7}

**Palindromic Linked List**Check if a given linked list is palindrome or not

**Number of ways of summing to ‘n’**Given an integer n, you have to give the number of ways in which n can be represented as sum of positive integers.

How will you find out if the graph is connected or not?

How will you find out if it is a tree.

**Detect cycle in a directed graph**Given a directed graph **G**, write a program to detect the *cycle* in it.

**Queue with push_rear(), pop_front() and get_min() in constant time**Implement a *queue* in which *push_rear()*, *pop_front()* and *get_min()* are all constant time operations.

*e^x*using the Taylor’s series.

An O(n ) solution is expected with no Overflow.

**Traversal of a robot in mxn grid**A robot has to move in a grid which is in the form of a matrix. The robot can go

1) A(i,j) to A(i,j+1) or

2) A(i,j) to A(i+1,j).

Find an efficient way of computing the unique number of paths from A(0,0) to A(m-1,n-1) for the grid

represented by the matrix A of dimensions mxn.

**n**, write a function to print the n

^{th}row of

*Pascal’s triangle*

**Remove all occurrences of a string in another string**Given string input1, input2, remove wherever the occurrence of input2 in input1.

e.g:

**input1:**skjthshetheshetesm

**input2:**she input1 will become “skjththetesm”

Give the test cases.

**kth smallest element in two sorted arrays**Given two sorted arrays A, B of size

*m*and

*n*respectively. Find the k-th smallest element in the

union of A and B. You can assume that there are no duplicate elements.

**Maximum value in a Sliding Window**A long array A[] is given to you. There is a sliding window of size w which is moving from the

very left of the array to the very right. You can only see the w numbers in the window. Each

time the sliding window moves rightwards by one position. Following is an example:

The array is [1 3 -1 -3 5 3 6 7], and w is 3.

*Window position Max*

————— —–

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

————— —–

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

**Input:**A long array A[], and a window width ‘w’

**Output:**An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]

**Requirement:**Find a good optimal way to get B[i]

**Smallest substring containing all the characters**Given two strings string1 and string2, find the smallest substring in string1 containing all characters of string2 in O(n).

For Example:

Input string1: “Looks for minimum string”

Input string2: “mums”

Output string: “mum s”

**Buy and sell stocks**You have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to buy one share of the stock and sell one share of the stock, design an

algorithm to find the best times to buy and sell.

**Find element in a sorted rotated array.**Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently?

Description:

eg. Tree

A

B C

D.C -.F

FH

output:

A

B C

D.H -.F

Here C & F are repeated. If a node value is duplicated, the duplicated value which comes later in the BFS

of the tree should be eliminated, its left/right child should be linked to the deleted node’s parent

(if the children are not duplicated values).

Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree.

multiplications. Count the number of multiplications used.

3 non-collinear points ?

the hill works fine but the clock at the top doesn’t. How will you synchronize the two clocks.

Obviously, you can’t carry either of the clocks up or down the hill! And you have a horse to help

you transport yourself. And, the time required for going up the hill is not equal to the time

required to go down the hill.

unique integers that has been sorted in ascending order, then rotated by an unknown amount X

where 0 <= X <= (arrayLength â€“ 1). An array rotation by amount X moves every element array[i] to

array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the

array.

For example, given that the pattern=”abc”, replace “abcdeffdfegabcabc” with “XdeffdfegX”. Note that

multiple occurrences of abc’s that are contiguous will be replaced with only one ‘X’.

**Replace all occurrence of the given pattern to ‘X’**Replace all occurrence of the given pattern to ‘X’.

For example, given that the pattern=”abc”, replace “abcdeffdfegabcabc” with “XdeffdfegX”. Note that

multiple occurrences of abc’s that are contiguous will be replaced with only one ‘X’.

*strstr*(Search for a substring) function. Do not use any system library

such as

*strlen*.

*strstr*(Search for a substring) function. Do not use any system library

such as

*strlen*.

eg, â€œHello, my name is John.â€ -> 5

eg, Hello, my name is John. -> 5

**Multiplcation of an array without division**There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

Example:

A: {4, 3, 2, 1, 2}

OUTPUT: {12, 16, 24, 48, 24}

A: {4, 3, 2, 1, 2}

OUTPUT: {12, 16, 24, 48, 24}

**Linked list to a height balanced BST**Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

**loop in a list**Given a singly linked list, find if there exist a loop.

For example, the 32-bit integer “11” has binary representation

**00000000000000000000000000001011**, so the function should return 3.

{

return !(x & (x-1));

}

{

return !(x & (x-1));

}

Input: { a, b, b }, distance = 2

Output: { b, a, b }

Input: { a, b, b }, distance = 2

Output: { b, a, b }

That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.

In other words, print the boundary of the tree.

That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.

In other words, print the boundary of the tree.

bool foo(int y)

{

int x;

x = y – 1;

return ((x&y) == 0)

}

what is the function of doing?

**Number of 1s in an integer number.**Find out the number of binary 1s in an integer number.

**Searching in 2D sorted matrix.**Write an efficient algorithm that searches for a value in an n x m table (two- dimensional array). This table is sorted along the rows and columns, that is

Table[i][j] < Table[i][j + 1]

Table[i][j] < Table[i + 1][j]

Table[i][j] > Table[i + 1][j]

**Loop in a linked list**Write code to check if a linked list contains a cycle.

**Design a microprocessor**Your group designs a microprocessor for use in cell phones and palmtop computers. You currently fabricate your chips on a 0.25micron process. A new fabrication facility with a 0.13micron process has asked you if you would like to switch to their facility. What do you believe will be the three most important tradeoffs between remaining with the 0.25 micron fabrication process and switching to the 0.13 micron process?

What is the difference between DFS and BFS and compare them in terms of optimality and efficiency

Delete a node in a singly linked list given only a pointer to the node to be deleted.

How to find the second maximum in an unsorted array.

**Counter in a loop**In the loop:

int counter=0;

for(i=0;i<10;i++) for(j=i+1;j<10;j++) for(k=j+1;k<10;k++) for(l=k+1;l<10;l++) for(m=l+1;m<10;m++) counter++;

**Write a solid, secure code for strstr()**Write a solid, secure code for strstr().

**Implement a Queue using only Stacks**Implement a Queue using only Stacks and give the time complexity for queue and deque operations.

**Given a Binary Search Tree, iterate over the elements without using recursion**Given a Binary Search Tree, iterate over the elements without using recursion.

**Print a singly-linked list backwards, in constant space and linear time**Print a singly-linked list backwards, in constant space and linear time.

**Binary Search Tree to a Doubly Linked List**Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes).

**Given a string, remove all the duplicate characters**Given a string, remove all the duplicate characters (not necessarily consecutive).

**Write a function that computes log2() using sqrt()**Write a function that computes log2() using sqrt().

**Given sorted arrays of length n and 2n with n elements each, merge first array into second array**Given sorted arrays of length n and 2n with n elements each, merge first array into second array.

```
Given a Tree (not binary Tree), print only leaf nodes on its path from the root.
```

**Middle element in a linked list**Find the middle element in a singly linked list and code it.

**Given a file with a lot of words (10 million) find out the top 10% most frequently occurring words**Given a file with a lot of words (10 million) find out the top 10% most frequently occurring words.

**Searching words in a evrybig file**Given a large file, how will you store the words in the file so that searching of a word can be done in constant time? Also how will you find the 10 most frequently occurring words in the file?

**Validate a Binary Search Tree**Validate a Binary Search Tree, meaning given a binary tree find out whether it is a BST or not.

Write a routine that takes as input a string such as “aabbccdef” and outputs “a2b2c2def” or “a4bd2g4” for “aaaabddgggg”. Write a ship quality code.

Given a NxN matrix with 0s and 1s. now whenever you encounter a 0 make the corresponding row and column elements 0. Flip 1 to 0 and 0 remains as they are.Example

1 0 1 1 0

0 1 1 1 0

1 1 1 1 1

1 0 1 1 1

1 1 1 1 1

results in

0 0 0 0 0

0 0 0 0 0

0 0 1 1 0

0 0 0 0 0

0 0 1 1 0

**Difference between 32-bit OS and 64 bit OS.**What is the difference between a 32-bit OS and a 64-bit OS.

**Find the missing number.**You have a file in which there are supposed to be 4 billion numbers, starting from 1 to 4,000,000,000 but unfortunately one number is missing, i.e there are only 3,999,999,999 numbers, You need to find the missing number.

**What are DLLs?**What are DLLs? How are they used?

2. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

2. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

very left of the array to the very right. You can only see the w numbers in the window. Each

time the sliding window moves rightwards by one position. Following is an example:

The array is [1 3 -1 -3 5 3 6 7], and w is 3.

*Window position Max*

————— —–

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7Input: A long array A[], and a window width w Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1] Requirement: Find a good optimal way to get B[i].

————— —–

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

**Find the Next Palindrome**A palindrome number is of the format 1234321.

Given a number x, find the smallest palindrome greater than x

**A queue with constant time operations**Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

multiplications. Count the number of multiplications used.

**Write C code to implement the strstr function.**Write C code to implement the strstr (Search for a substring) function. Do not use any system library such as strlen.

**Find an element in a rotated sorted array.**Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently

**Given a sorted, shifted array find the minimum element**Given a sorted, shifted array find the minimum element. For example in 34512 the minimum is 1, in 45123 the minimum is 1.

**Reverse a doubly Linked List**Reverse a doubly Linked List.

**Find the sub-array with the largest sum**You’re given an array containing both positive and negative integers and required to find the sub-array with the largest sum. You are expected to give O(N) time solution. Write a routine in C for the above.

**Find all unique triplets in a set which gives the sum of zero.**Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the set which gives the sum of zero.

For example, given set S = {-1 0 1 2 -1 -4},

One possible solution set is:

(-1, 0, 1)

(-1, 2, -1)

Note that (0, 1, -1) is not part of the solution above, because (0, 1, -1) is the duplicate of (-1, 0, 1). Same with (-1, -1, 2).

For a set S, there is probably no “the” solution, another solution could be:

(0, 1, -1)

(2, -1, -1)

For example, given set S = {-1 0 1 2 -1 -4},

One possible solution set is:

(-1, 0, 1)

(-1, 2, -1)

Note that (0, 1, -1) is not part of the solution above, because (0, 1, -1) is the duplicate of (-1, 0, 1). Same with (-1, -1, 2).

For a set S, there is probably no “the” solution, another solution could be:

(0, 1, -1)

(2, -1, -1)

For example, given set S = {-1 0 1 2 -1 -4},

One possible solution set is:

(-1, 0, 1)

(-1, 2, -1)

Note that (0, 1, -1) is not part of the solution above, because (0, 1, -1) is the duplicate of (-1, 0, 1). Same with (-1, -1, 2).

For a set S, there is probably no “the” solution, another solution could be:

(0, 1, -1)

(2, -1, -1)

**How will you save binary tree in a disk such that you can retrieve it later**How will you save binary tree in a disk such that you can retrieve it later?

**Match two board configurations of tic-tac-toe problem**How will you match two board configurations of tic-tac-toe problem?

**Find out non repeating numbers**Given an array having numbers from 1 to N in random order such that all numbers except two are repeating, find out the two numbers.

**Distance between Hash Map and Hash Table**Difference between HashMap and HashTable?

**Write a program to print the permutations of the array containing number in lexicographical order**Write a program to print the permutations of the array containing number in lexicographical order.

**Write an algorithm to print the Power set.**Write an algorithm to print the Power set .

The power set is the set of all subsets of a set.

For example, the power set of the set {a, b, c} consists of the sets:

{}

{a}

{b}

{c}

{a, b}

{a, c}

{b, c}

{a, b, c}

**Note that:**

*The empty set {} is in the power set*

The set itself is in the power set

**An array contains both negative and positive numbers, find out the largest sum formed by a consecutive sub-array**An array contains both negative and positive numbers, find out the largest sum formed by a consecutive sub-array. Write a solid code for it.

**Find if a string is Palindrome ignoring special characters.**Find if a string is Palindrome ignoring special characters.

**Give a Data Structure that will be helpful to do prefix search in a dictionary**Give a Data Structure that will be helpful to do prefix search in a dictionary.

**Write a program that prints an unordered sets of k elements chosen from a set of size n**Write a program that prints an unordered sets of k elements chosen from a set of size n.

Example, let the size of the give set be n and set = {0, 1, 2, 3, 4} and we need to find all the subsets of size 3, then there will be a total of 10 such subsets given as:

{0, 1, 2}

{0, 1, 3}

{0, 1, 4}

{0, 2, 3}

{0, 2, 4}

{0, 3, 4}

{1, 2, 3}

{1, 2, 4}

{1, 3, 4}

{2, 3, 4}

**Rotate an array to the left or right by a given number.**Given an array, rotate it to the left or right by a given number of steps.

**Find all elements that appear more than n/2 times in a given list.**Design an algorithm to find all elements that appear more than n/2 times in a given list. Then do the same for elements that appear more than n/4 times.

**Find Least height tree of an acyclic undirected unweighted connected graph?**Given an acyclic undirected unweighted connected graph, find its representation as a tree with the least height.

1) 10101010

The longest contiguous sub sequence that satisfies the problem is the input itself2)1101000

The longest sub sequence that satisfies the problem is 110100

**Remove extra brackets from a paranthesized expression**How to remove extra bracket from expressions like ((((A+B))

*C)) to give (A+B)*C in the most optimized way?

Remember the input expression will be valid expression and output expression generated must also be valid and should give the same result as the input expression.

**Find all the intervals (i, j) where the number of 0s and numbers of 1s are equal in an array of 0s and 1s**You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.

Example:

positions = 0 1 2 3 4 5 6 7 8

Array =0 1 0 0 1 1 1 1 0

One interval is (0, 1) because there the number of 0 and 1 are equal. There are many other intervals, find all in minimum time possible.

**Interval where number of 0s and 1s are equal**You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.

Example:

positions = 0 1 2 3 4 5 6 7 8

Array =0 1 0 0 1 1 1 1 0

One interval is (0, 1) because there the number of 0 and 1 are equal. There are many other intervals, find all in minimum time possible.

1. r := 0

2. for i := 1 to n – 1 do

3. for j := i + 1 to n do

4. for k := 1 to j do

5. r := r + 1

6. return(r)

What value is returned by the following function? Express your answer as a function of n. Give the worst-case running time using big-Oh notation.function pesky(n)

- r := 0
- for i := 1 to n do
- for j := 1 to i do
- for k := j to i + j do
- r := r + 1
- return(r)

**Find the number of occurrences of the words of the first line such that in a given sub string all the words of the line appear exactly once**You are given a file. There is a line at the top and a paragraph below it. You have to find the number of occurrences of the words of the first line such that in a given sub string all the words of the line appear exactly once, without bothering about the order in which they appear.

So if the first line is

*hello friend lets find strings*

” I do not think you will find the string in this line don’t be disappointed

friend hello find lets strings friend it seems you found two times here

hello friend lets find strings

friend friend hello hello lets strings find friend ”

There are a total of 4 occurrences of the words of the first line.

The occur as none in the first line, twice in the second and once each in the last two.

Give a solid working code.

^{th}largest element of the heap is greater than x or not. Your algorithm must take O(k) time.

**Complexity of build-heap procedure.**What is the complexity of build-heap procedure?

**Minimum number of comparisons required to find the largest and the second largest elements in an array**What is the minimum number of comparisons required to find out the largest and the second largest elements in an array.

If it makes your life easier you can use extra space. But try to keep it less.

**Reverse a string – word by word**Reverse a string – word by word.

For example a string like “This is good day” would be written as

“day good is This”

**K smalled elements from a set on N numbers**Find the k smallest elements from the set of n numbers in O(n) time complexity

**Kth largest number**Find the kth largest number in a given integer array in the least time and space complexity.

**Regular Expression Matching**Implement a function that takes two arguments –> one is a regular expression and the other is the string to be matched. The function matches the string against the regular expression and returns the result.

The regular expression supports only * and .

*means the character can come any number of times
. means single occurrence of any character*

So an expression like aabb* should be able to match strings such as
ab, aaab, abbb, aabbbb and so on.*

And an expression like .ab.* should be matched with any string containing at least one occurrence of ‘ab’

**Find a matrix of 3×3 such that each row, column and diagonal forms a valid word in the dictionary**You are given a list of 3 letter words, as a Dictionary. You need to find a matrix of 3×3 such that each row, column and diagonal in the matrix forms a valid word in the dictionary.

**Make a left right sibling tree**You are given a complete tree, with left and right pointers set as usual but there are another two pointer in the “node” named “left_sibling” and “right_sibling”. Write a function to set the sibling pointers to their respective values.

**Maximum distance with 50 bikes and a tank of capacity 100 kms**There are 50 bikes with a tank that has the capacity to go 100 kms. Using these 50 bikes, what is the maximum distance that you can go ?

**Finding non-anagramic strings in a list**

**Sort array of 3 distinct integers**

Sort an array that contains multiple occurrences of 3 integers (1,2,3).

For example input: 121221123323

output: 111122222333

**Reverse characters of each word in a sentence**

Given a linked list containing characters that form a string such as

——— “my career stack” ———

Reverse the characters of each word, keeping the order of the words same such that the output will be

——— “ym reerac kcats” ———

**Allocate and unallocate numbers randomly from a list**

You are given an array containing some numbers. You need to write the following two functionsint allocate()

void deallocate (int)

allocate– allocates a number randomly from the list and once the number has been allocated it cannot be reallocated

deallocate– takes a number as input and deallocates that number, such that it can now be allocated in subsequent random number list.

**Minimum cost for painting a row houses in three different colors**There are N houses in a row. Each house can be painted in either Red, Green or Blue color. The cost of coloring each house in each of the colors is different.

Find the color of each house such that no two adjacent house have the same color and the total cost of coloring all the houses is minimum.

**Find the intervals from a set of intervals in which a given point lies**

**Destroy cities**Byteland consists of N cities numbered 1..N. There are M roads connecting some pairs of cities. There are two army divisions, A and B, which protect the kingdom. Each city is either protected by army division A or by army division B.

You are the ruler of an enemy kingdom and have devised a plan to destroy Byteland. Your plan is to destroy all the roads in Byteland disrupting all communication. If you attack any road, the armies from both the cities that the road connects comes for its defense. You realize that your attack will fail if there are soldiers from both armies A and B defending any road.

So you decide that before carrying out this plan, you will attack some of the cities and defeat the army located in the city to make your plan possible. However, this is considerably more difficult. You have estimated that defeating the army located in city i will take up ci amount of resources. Your aim now is to decide which cities to attack so that your cost is minimum and no road should be protected from both armies A and B.

Input:

The first line contains the number of test cases T. T test cases follow. The first line of each test case contains N and M. The next N lines describe the cities in Byteland. The ith line contains a letter ‘A’ or ‘B’ signifying the army division located in city i and the cost ci of defeating that army. The next M lines descibe the roads in the city. The ith line contains xi and yi, the numbers of the cities connected by a road.

Output:

Output T lines, one corresponding to each test case containing the cheapest cost of accomplishing your goal.

Sample Input: 3

3 3

A 1

A 1

B 1

1 2

1 3

2 3

3 3

A 1

A 1

B 10

1 2

1 3

2 3

6 4

A 10

A 10

A 10

B 10

B 10

B 10

1 2

2 3

4 5

5 6

Sample Output: 1

2

0

Explanation:

In the first example, the city 3 should be attacked which costs 1 unit. In the second example, it is cheaper to attack cities 1 and 2 rather than attack city 3. In the third example, there is no road defended by both armies and so there is no need to attack any city.

**Decode messages encoded with Substitution Cipher**Your task is to decode messages that are encoded with substitution ciphers. In a substitution cipher, all occurrences of a character are replaced by a different character. For example, in a cipher that replaces “a” with “d” and “b” with “e”, the message “abb” is encoded as “dee”.

The exact character mappings that are used in the substitution ciphers will not be known to you. However, the dictionary of words that were used will be given. You will be given multiple encoded messages to decode (one per line) and they may use different substitution ciphers. The same substitution cipher is used on all of the words in a particular message.

For each scrambled message in the input, your program should output a line with the input line, followed by the string ” = ” (without the quotes), followed by the decoded message.

Example:

input file:

//dict

hello

there

yello

thorns

//secret

12334 51272

12334 514678

output:

12334 51272 = hello there

12334 514678 = hello thorns

**Test cases for overlap of rectangles**

Given a function, func( rect a, rect b), which takes two rectangles as argument and tells if two rectangles overlap or not. Write all possible test cases for this.

**Number of occurrences of a number in a sorted array.**Given a sorted array, find the number of occurrences of an element in the array. Give an an O(logn) time solution.

**Given a preorder and a postorder traversal, construct the tree.**Given a preorder and postorder traversal of a Binary Tree, construct the tree using these two traversals.