Some Challenging Algorithmic/Programming Problems -For Beginners and Intermediate
Here are few algorithmic problems for beginners and intermediate level coders.These problems were asked in different interviews conducted by amazon,microsoft,google and few such top companies.
Ques 1 :Given an array, with positive and negative integers, arrange it in such a way that, positive numbers occupy even positions and negative numbers occupy odd position. All the remaining extra positive or negative integers should be stored at the end of the array. Remember, the elements of the array should remain in the same order.
EG: Input array {1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12}
output array {1,-2,3,-4,8,-5,9,-6,4,-7,10,11,12}
Level Of Problem 3/5
Level Of Problem 3/5
Ques 2: Given a 2D array of strings : A[][]={ fog, fool, food, fruit,for}.
Find a substring such that after removing this substring from beginning of all the strings in A , the length of remaining strings + length of substring is minimum.
example:
if substring is "f" then total length= 1+{2+3+3+4+2} = 15
if substring is "foo" total len is= 3+{3+1+1+5+3}=16
if substring is "fo" total len is= 2+{1+2+2+5+1}=13
since minimum is 13 so output should be "fo"
Level Of Problem : 3.5/5
Ques 3 : find the maximum no. of paths from (0,0) to (m,n) in a m*n matrix.
Ques 4: Find the max and min elements of an unsorted integer array using a minimal number of comparisons.Implement the solution in a language of your choice. Analyze the runtime complexity.
Ques 5:Implement the sqrt() function (don't use library function).
Ques 6: Convert a string representing a Roman number into a decimal. For Roman numbers -http://en.wikipedia.org/wiki/Roman_numerals
Ques 7 : how to merge two binary search tree into balanced binary search tree.. Let there be m elements in first tree and n elements in the other tree. Your merge function should take O(m+n) time with in constant space.
Examples:
A Balanced BST 1
90
/ \
70 110
A Balanced BST 2
60
/ \
5 800
output :-->
70
/ \
60 90
/ \
5 800
Ques 8: I have a list of several million words unsorted.
How can you find the largest and the smallest words that can be typed by a single hand on a qwerty-style keyboard? Following the rules of finger placement, a word can either be typed fully on the left-hand side of the keyboard, the right-hand side, or both. Find the largest and smallest left-hand word(s), and the largest and smallest right-hand word(s).
given: millions of words, unsorted
given: set of left-hand chars - a,s,d,f,...
given: set of right-hand chars - j,k,l...
Ques 9 :Write a function to find the height of a binary tree.
Ques 10 :Given an array of n numbers with repetition of numbers. You need to find the max length of continuous sub array with at max 3 unique elements.
For eg
array: 1 2 3 1 4 3 4 1 2
ans: 6 (3 1 4 3 4 1)
Solution: Time complexity O(n)
Extra Space O(1)
