Amazon interview Questions Cheatsheet

From: http://techinterviewsolutions.net/2012/08/13/amazon-interview-questions-cheatsheet/

List Intersection Problem

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 integersGiven 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 array

I 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 arrays

We 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 string

Write 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 stackImplement queue using stack

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

Print a binary tree in level order

Print 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 (wi) and a value (vi), 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.

Given an array containing just 0s and 1s sort it in place in one pass.

Search in a rotated array.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(n2) 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.

Display a square matrix spirally using only 2 ‘for’ loops.

This question doesn’t have a title. Add TitleLowest common ancestor in a BST

Given: binary tree, nodes, each node has a value

struct node
{
int value;
node * left;
node * right;
}

Given node value 1, and node value 2, determine the lowest common ancestor of these 2 nodes .

Given a BST (Binary search Tree) how will you find median in that?

Divisibility of a number by 3Suppose 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 listConvert a Binary Search Tree to a sorted doubly circular Linked list

Median of two sorted arraysThere 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).

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’.

This question doesn’t have a title. Add Title

A robot is located at the top-left corner of a row x col grid The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?

Space complexity of Quick Sort algorithm

What is the Space complexity of Quick Sort algorithm ? How can you find it?

What are dangling pointers

What are dangling pointers?

Write a function isBST(BinaryTree *node) to verify if a given binary tree is a Binary Search Tree (BST) or not.

Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.

Remove duplicate elements in a stringGiven 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).

Why can quicksort be said to be better than heapsort even when both of them have the same complexity.

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 arrayYou 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.

Reverse a Linked List without making recursive calls.

Cycle in a Linked ListYou 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 stringWrite 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

What are virtual methods? An example use-case for having a virtual destructor with a small code snippet showing that case.

Find kth number in a BST

Find kth number in a BST.

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

Interleaving of stringsThree 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.

Input: A unsorted array of size n.
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 jth is nearest to ith ( 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

Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.

What is the output of
for(;0;)
printf(“\n guess”);
and why?

Key factor for preferring B-tress to binary trees for indexing database relations:a) db has large no. of records
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

Choose algorithm for sorting in place and lowest worst case time complexity:a) Merge
b) Quick
c) Heap
d) Radix

Maximum and minimum number of tuples in a natural joinConsider 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?

Write a program for deck shuffling. And make sure that no card will get the same position as previously. i.e. after shuffle all card should have different position.

Prove that n(n2-1) is div by 24.
Note: n is odd and >=3

Given an analog clock, it’s hour hand and minute hand divide the clock in two sectors. Write a function to return where the second hand is located in larger section or smaller?Given time in format –
hh:mm:ssHandle special cases carefully.

Table:
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?

Given an array having n/2 distinct and n/2 unique elements. In a probabilistic sense what is the minimum number of comparisons to find the repeating number.

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

Print 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.

Find all the prime numbers less than or equal to a given integer n.

Write a program to reverse a string. Two cases –
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.

Alternately merge two Linked lists.

Implement strstr function. Write a solid secure code.

Check if a given linked list is palindrome or not.`

Find cycle in a directed graph. If multiple cycles are found print any but starting with the smallest node number.

Write the code to find the depth of a binary tree (balanced and unbalanced). What are the test cases to check the validity of the code?

Write a program to find a cycle in a linked list. Write the different test cases. If a cycle is found, how do we fix it?? What is the run-time of this algorithm.

Reverse every k nodes of the linked list.

Two coins are tossed. For the 1st coin if u get a head u stop, but for tail u toss it again till u get the head. The second coin is continuously tossed what is the ratio of the Head to Tail?

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

There is a binary tree (Not a BST) in which you are given three nodes X,Y, and Z .Write a function which finds whether y lies in the path b/w x and z.

Write a function that removes the nth element from the end of a single linked list.For example removeNthFromEnd ({1, 2, 3}, 1) should return {1, 2}
Also give the case where the linked list has a cycle.

Perform divide operation without using ‘/’ operator and give the most efficient solution.

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

You are given a sorted array such that all the numbers are repeated twice except one.Find that non repeated number in O(logn)

Given an array of size n. It contains numbers in the range 1 to N. Each number is present at least once except for 2 numbers. Find the missing numbers.

Given an array of size N. It contains numbers in the range 1-N. Find the numbers which aren’t present.

Given an array of size N. It contains numbers in the range 1-N. Find the numbers which are not present.

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

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

Given an array all of whose elements are positive numbers, find the maximum sum of a sub-sequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)

There are 2 sorted arrays one with size X and another with size X+Y which has only Y elements. Merge these arrays in to second array such that resultant array at end will be sorted.

Find the second largest element in an array with minimum no of comparisons and give the minimum no of comparisons needed on an array of size N to do the same.

Find longest interval:-
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 arrayWrite 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.

Write a function that takes an array of five integers, each of which is between 1 and 10, and returns the number of combinations of those integers that sum to 15. For example, calling the function with the array [1, 2, 3, 4, 5] should return 1, while calling it with [5, 5, 10, 2, 3] should return 4 (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3). You may assume that the input has already been validated.

How to preprocess dictionary so that below operations are best supporteda)   Search in dictionary
b)   given a string find all valid anagrams in a dictionary
c)   typing prefix of a valid string suggests valid words

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

Change making problem – Dynamic ProgrammingYou 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 dictionaryGiven 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).

Give two dice – one is a standard dice, the other is blank (nothing painted on any of the faces).The problem is to paint the blank dice in such a manner so that when you roll both of them together, the sum of both the faces should lie between 1 and 12. Numbers from 1-12 (both inclusive) equally likely.

2n+1 numbers in a list except for 1 num all had duplicates, how to find duplicate in O(n)

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 do you initialize a static member of a class with return value of some function?

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}

Use 2 stacks to implement a queue.

Count the number of unique element in array of numbers in minimum time complexity.

What is the data structure that can be used for implementing a T9 dictionary.

Write an algorithm to find if a tree is binary search tree or not in O(n).

Palindromic Linked ListCheck 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.

If you are given the name of the function at run time how will you invoke the function?

How to call a C++ function which is compiled with C++ compiler in C code?

An array of size 2n, has n unique elements and n occurrences of an element. Find the non-unique element in linear time?

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 graphGiven a directed graph G, write a program to detect the cycle in it.

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

Write code to evaluate the value of e^x using the Taylor’s series.
An O(n ) solution is expected with no Overflow.

Traversal of a robot in mxn gridA 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.

Given a positive integer n, write a function to print the nth row of Pascal’s triangle

Remove all occurrences of a string in another stringGiven 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 arraysGiven 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 WindowA 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

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 charactersGiven 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 stocksYou 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?

Find triplets in an integer array which satisfy a[i]^2 + a[j]^2 = a[k]^2 .

How to delete the duplicates in a Binary Tree?
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.

Write a C function for unsigned power(double x, unsigned int n) using minimum number of
multiplications. Count the number of multiplications used.

Write a function to find out longest palindrome in a given string.

Find the depth of a binary tree.

How many lines can be drawn in a 2D plane such that they are equidistant from
3 non-collinear points ?

Design a stack that supports push, pop, and retrieving the minimum element in constant time.

Which are the four storage classes in C.

There is a clock at the bottom of the hill and a clock at the top of the hill. The clock at the bottom of
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.

Implement the following function, FindSortedArrayRotation, which takes as its input an array of
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.

Find the intersection of two sorted arrays.

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’.

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’.

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

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

Count the number of words in a string, where a word is defined to be a contiguous sequence of non-space characters.
eg, “Hello, my name is John.” -> 5

Count the number of words in a string, where a word is defined to be a contiguous sequence of non-space characters.
eg, Hello, my name is John. -> 5

Multiplcation of an array without divisionThere 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}

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}

Linked list to a height balanced BSTGiven a singly linked list where elements are sorted in ascending order, convert it 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 listGiven a singly linked list, find if there exist a loop.

Write a function that takes an unsigned integer and returns the number of “1” bits it has.
For example, the 32-bit integer “11” has binary representation 00000000000000000000000000001011, so the function should return 3.

What does the following function mystery() do?bool mystery(unsigned int x)
{
return !(x & (x-1));
}

What does the following function mystery() do?bool mystery(unsigned int x)
{
return !(x & (x-1));
}

Given a binary search tree, print the elements in-order iteratively without using recursion.

Given a binary search tree, print the elements in-order iteratively without using recursion.

Given only putchar (no sprintf, itoa, etc.) write a routine putlong that prints out an unsigned long in decimal.

Given only putchar (no sprintf, itoa, etc.) write a routine putlong that prints out an unsigned long in decimal.

Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other.
Input: { a, b, b }, distance = 2
Output: { b, a, b }

Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other.
Input: { a, b, b }, distance = 2
Output: { b, a, b }

Given only putchar (no sprintf, itoa, etc.), Print a string in reverse order.

Given only putchar (no sprintf, itoa, etc.), Print a string in reverse order.

Print all edge nodes of a complete binary tree anti-clockwise.
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.

Print all edge nodes of a complete binary tree anti-clockwise.
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.

Implement the following function, FindSortedArrayRotation, which takes as its input an array of 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.

Given a matrix (2D array) of m x n elements (m rows, n columns), write a function that prints the elements in the array in a spiral manner.

Given a matrix (2D array) of m x n elements (m rows, n columns), write a function that prints the elements in the array in a spiral manner.

What is the difference between a const pointer and an array name?

You have two numbers represented by a linked list, where each node contains a single digit. Write a function that adds the two numbers and returns the sum as a linked list.

Reverse a string without using a third variable.

Write a program to find if a tree is balanced

bool foo(int y)
{
int x;
x = y – 1;
return ((x&y) == 0)
}
what is the function of doing?

What are pure virtual functions?

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

What does volatile keyword do and where in memory volatile variables are stored?

Merge one sorted Linked List to another

Give an example in which having a cache can degrade system performance.

Given a binary tree, write a code to convert it into its array representation. Each node has the links to its left child, its right child and the parent.

Explain how mutexes and semaphores work and how they are actually implemented.

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]

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]

What does appending static to a global variable/function do?

Write code for memcpy function.

You have an array of numbers from 1-50 in random order. One element is randomly deleted. Write code to find the missing element.

Write code to checking if linked lists merge.

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

Given an input array of size unknown with all 1’s in the beginning and 0’s in the end. Find the index in the array from where 0’s start, consider there are millions of 1’s and 0’s in the array .i.e array is very big e.g array contents 1111111…….1100000………0000000

There are three machines with different processing powers. They each take respectively 2, 10 and 20 units of execution time to finish a task requiring X effort. If we let all three machines work on same task, considering each quantum of task is independent of the other, so that not for a moment a machine has to wait for another one to finish, how long will it take for three machines to finish the given task.

The average performance of products in your market segment triples every 36 months. Your design engineers have proposed an optimization that will increase performance by 12%. The optimization will postpone the completion date of the project by 2 months. Should the engineers implement the optimization and postpone the completion date, or should they stick to the original schedule?

Design a microprocessorYour 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?

Explain derating factor.

Write a complete program check whether Graph is Connected or Not & also for whether Graph is Tree or not.

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

Design a stack which supports push, pop, min and max operations in O(1).

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.

Given preorder traversal of a Binary Search Tree. What can possibly be the inorder traversal of the tree.

If u could find the (n/4)th element of an array in O(n) time, then what is the worst time complexity of quick sort algo if this algorithm is used to decide the pivot element.

Find the min no of comparisons required to find both the max and min elements of an array containing 20 elements.

If a 2D array[0…m-1,0….n-1] is stored in column major format how will u find the (i,j) element?

The probability of finding the parking slot occupied is 1/3. You find it empty for 9 consecutive days. Find the probability that it will be empty on the 10th day.

Counter in a loopIn 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++;

Consider a set S of the first 10 natural numbers.Find the number of subsets that do not contain consecutive elements.

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

Implement a Queue using only StacksImplement 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 recursionGiven a Binary Search Tree, iterate over the elements without using recursion.

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

Binary Search Tree to a Doubly Linked ListConvert 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 charactersGiven 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 arrayGiven 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.

Given 2 trees, find out if they r exactly same or not.

Middle element in a linked listFind 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 wordsGiven a file with a lot of words (10 million) find out the top 10% most frequently occurring words.

Searching words in a evrybig fileGiven 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 TreeValidate a Binary Search Tree, meaning given a binary tree find out whether it is a BST or not.

Given 1000 bottles of juice, one of them contains poison and tastes bitter. Spot the spoiled bottle in minimum sips.

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

What is the difference between a thread and a process? Are Word and PowerPoint different processes or threads of a single process?

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?

Given a word and a file containing words in the dictionary find anagrams of that word.

Given a string find the first un-repeated character in it.

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.1. Would you rather go first or second? Does it matter?
2. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.1. Would you rather go first or second? Does it matter?
2. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

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

Find the Next PalindromeA palindrome number is of the format 1234321.

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

You have given an array. Find the maximum and minimum numbers in less number of comparisons.

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

Write a C function for unsigned power(double x, unsigned int n) using minimum number of
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 elementGiven a sorted, shifted array find the minimum element. For example in 34512 the minimum is 1, in 45123 the minimum is 1.

How is the spell checker routine (common to both, word and Powerpoint) used? Is the code copied 2 times for each of the processes in the main memory, if they are different processes or if word and powerpoint are two threads then how is it used?

If you are on a boat and you throw out a suitcase, will the level of water increase?

Given a simple program designed to take inputs of integers from 1-1000 and to output the factorial value of that number, how would you test this program? You do not have access to the code.

Reverse a doubly Linked ListReverse a doubly Linked List.

If you had an infinite supply of water and a 5 litre and 3 litre bucket, how would you measure exactly 4 liter? The buckets do not have any intermediate scales.

Find the sub-array with the largest sumYou’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)

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)

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)

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

Given an array, a start index, length and a dest index, copy the sub-array of given length from starting index to destination index.

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

Find out non repeating numbersGiven 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 TableDifference between HashMap and HashTable?

You are developing a web browser and need to display all visited links on a page. The visited links need to use a different color then that used to display scheme than the unvisited links. Now, given a history of links you have visited before, how would you go about writing the piece of code that makes the determination if you have seen this link before? Answer or not? The answer could be a simple string comparison, but then think about the time it will take for the client to render any HTML page. Alternatively, so, given a history of URLs, come-up with an elegant way (algorithm, data structure, etc.) to make the determination if a given link already exits in the history list?

Write a program to print the permutations of the array containing number in lexicographical orderWrite 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-arrayAn 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 dictionaryGive 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 nWrite 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 the element which appears n/2 times or more in a given array. Also find the same for element which appears n/4 and so on to n/k.

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.

You are given an array containing 0s and 1s. Give an O(n) time algorithm to find the maximum contiguous sub sequence which has equal number of 1s and 0s.Examples
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 expressionHow 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 1sYou 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 equalYou 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.

What value is returned by the following function? Express your answer as a function of n. Give the worst-case running time using the big-Oh notation for the function mystery(n)mystery(n)
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)

1. r := 0
2. for i := 1 to n do
3. for j := 1 to i do
4. for k := j to i + j do
5. r := r + 1
6. 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 onceYou 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.

There is an array based binary heap containing n numbers (the root stores the greatest number so it is a max-heap). You are a given an integer x and have to determine whether the kth 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 arrayWhat 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 wordReverse a string – word by word.

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

“day good is This”

Save a Binary Search Tree to a disk and then retrieve it.

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

How can you save a Binary Tree and re construct it later?

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

Regular Expression MatchingImplement 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 dictionaryYou 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 treeYou 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.

Given 50 red pens and 50 blue pens, two jars(A,B) initially empty. These 100 pens are to be distributed b/w the jars such that the probability of picking a red pen is maximum.

Maximum distance with 50 bikes and a tank of capacity 100 kmsThere 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

Given a list of strings, find out the number of strings which do not have an anagram present in the 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

Given a number x, less than 100. How will you generate true with probability x/100. So if x = 65, how will you generate true with probability 65/100. You can represent true by 1 and false by 0.

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

Given a set of intervals such as (10,20), (15,25), (28,40), (50,70), (0,9) (60,90) and build a data structure. Query the data structure for point x, and it find out all the intervals that contain this point x.

Destroy citiesByteland 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 CipherYour 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.