From: http://techinterviewsolutions.net/2012/08/13/amazon-interview-questions-cheatsheet/
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.
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
Eg :- 3 4 1 3 1 7 2 2 4
Ans:- 7
Find common elements in two unique sorted 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.
Array2={“how”,”are”,”you”}
output={“how”,”are”,”you”,”there”}
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’.
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.
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 .
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).
This question doesn’t have a title. Add Title
Space complexity of Quick Sort algorithm
What are dangling pointers
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).
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.
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
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.
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
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 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?
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.
AnagramsGiven 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 nMerge 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 itGiven 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 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.
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).
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 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.
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.
An O(n ) solution is expected with no Overflow.
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.
e.g:input1: skjthshetheshetesm
input2: she input1 will become “skjththetesm”
Give the test cases.
union of A and B. You can assume that there are no duplicate elements.
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?
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’.
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’.
such as strlen.
such as strlen.
eg, “Hello, my name is John.†-> 5
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}
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.
loop in a listGiven 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 listWrite code to check if a linked list contains a cycle.
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?
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 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++;
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.
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.
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].
Find the Next PalindromeA palindrome number is of the format 1234321.
Given a number x, find the smallest palindrome greater than x
A queue with constant time operationsImplement 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 elementGiven 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 ListReverse a doubly Linked List.
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)
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 laterHow will you save binary tree in a disk such that you can retrieve it later?
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?
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.
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 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
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.
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.
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 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.
Complexity of build-heap procedure.What is the complexity of build-heap procedure?
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”
K smalled elements from a set on N numbersFind the k smallest elements from the set of n numbers in O(n) time complexity
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.
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
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 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
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.
相关推荐
Python3 interview prep cheatsheet and examples
clojure-cheatsheet, 用于Emacs的Clojure Cheatsheet 用于Emacs的难以置信方便的 Clojure Cheatsheet，更新为 Clojure，打包成简单，快速，可以搜索的离线形式： 状态准备使用基于 Clojure 1.7.0.安装如果你连接到 ...
R ggplot2 cheatsheet
conda cheat sheet，4.6.1 版本。有了这份 conda cheat sheet 再配合 help 命令，基本能解决 conda 使用中的大部分问题。这份 cheat sheet 从官网搬运，上传到 CSDN 资源主要是为了网络环境不太理想的 Python 学习者...
markdown-cheatsheet, 用于 Github README.md的Markdown Cheatsheet Markdown Heading HeadingMarkup : # Heading 1 #-OR-Markup : ============= (below H1 text)标题 2Mark
Python 3 Cheat Sheet 2012-2013 - Laurent Pointal Mémento v1.2.1bis Official Python documentation on http://docs.python.o
CheatSheet for Mac是专门用来查看应用程序快捷键的工具，安装好cheatsheet软件后，在软件界面长按Command键即可快速查看快捷键列表，非常的便捷，想要了解更多关于软件的快捷键，那就赶紧试试cheatsheet for mac吧...
opencv_cheatsheet
CSS 3 Cheatsheet
acm-cheat-sheet, Acm Cheat Sheet
CheatSheet for Mac，mac下的快捷键查看工具，版本1.0.1，免费。
x86 assembly cheatsheet
JavaScript Cheat Sheet by Dave Child (DaveChild) via cheatography.com/1/cs/7/ 打印出来贴墙上便于随时查找有用信息
x64_cheatsheet
Vim cheatsheet中文版 绝对珍藏版 很不错的
cheatsheet for mac 自动显示快捷键, 不错的资源,亲测可用!
python_cheatsheet_完美总结 新手也可以参考这些问题以获得全面的 Python 知识
test heuristics cheat sheet
英伟达 NVIDIA 推出的 RAPIDS 的 cheatsheet，方便大家使用的时候查阅！
atlassian git cheatsheet