Interview Questions 17

1. Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ? [Hint: This is a nice link to go through]

2. [Old school tricks :D] You are given have a datatype, say X in C. Determine the size of the datatype, without declaring a variable or a pointer variable of that type, and, of course without using the sizeof operator!

3. Reverse a string using only bitwise operators and without temporary storage.

4. Two rectangles are given. As a struct having {bottomleft-x, bottomleft-y, topright-x, topright-y}. You are given two rectangles R1, R2, determine if they intersect.[ Basic Geometry]

5. Write a Generic Swap Macro in C.

6. Given a list of machines where each machine has a hard disk limit and memory capacity and given a list of processes where each process requires certain hard disk space and memory, write an efficient algorithm to match processes to machines. (You may assume process to server mapping is 1:1).

7. A container is filled up with balls. Each ball has a value. Red = 7, Yellow = 5, Green = 2, Blue 2. Some balls are removed from the container and the product of their value is 147,000. How many red balls have been removed?

8. Find out Non-Decreasing subsequence of length k with maximum sum in an array of n integers ? [ Hint: here].

9. You have 21 chocolates and 91 roses, how many bouquets can you make without discarding neither a rose nor a chocolate. All the bouquets must have the same number of chocolates and roses for you.

10. If you want to search for a friend on Facebook, what are the possible strategies that you could use. You are a programmer and can also access Facebook’s Social Graph API. Make your own assumptions. How could you make it a ‘Friend Finder’ app?

Advertisements

Interview Questions 16

1. There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

2. A file is given with many 0s stored in continuous way , store it in another file such that when you store try saving the space by using minimum amount of space. When you want to create the original file , you should be able to do so with the new file created.

3. Propose a data structure that would store numbers, without any knowledge about them, and allow to perform the operations: insert, get median, as efficiently as possible. Modify/optimize your design, only this time the numbers are from a group V, which is |V|<<n. [Hint: O(logn), O(logn)]

4. Given N computers networked together, with each computer storing N integers, describe a procedure for finding the median of all of the numbers. Assume that a computer can only hold O(N) integers (i.e. no computer can store all N^2 integers). Also assume that there exists a computer on the network without integers, that we can use to interface with the computers storing the integers.

5. [Interesting] Calculate the Resistance in ohm’s that a knights move would require on an infinite plane of resistors of unit resistance.

6. Given a binary tree with the following constraints: a) A node has either both a left and right child OR no children b) The right child of a node is either a leaf or NULL write code to invert this tree.

7. Suppose you are getting an infinite binary stream of characters then after any point of time you need to print whether the no is divisible by 3 or not, how will you do that? [Hint: A nice example of finite automata based algorithm design :)]

8. An array is of size N with integers between 0 and 1024(repetitions allowed). Another array of integers is of size M with no constraints on the numbers. Find which elements of first array are present in the second array.

9. Design a datastructure to represent the movement of a knight on a chess board.

10. On a empty chessboard, a horse starts from a point( say location x,y) and it starts moving randomly, but once it moves out of board, it cant come inside. So what is the total probability that it stays within the board after N steps.

कहना सच्ची है मधुशाला

कहना सच्ची है मधुशाला

अपने युग में सबको अनुपम ज्ञात हुई अपनी हाला,
अपने युग में सबको अदभुत ज्ञात हुआ अपना प्याला,
फिर भी वृद्धों से जब पूछा एक यही उत्तर पाया –
अब न रहे वे पीनेवाले, अब न रही वह मधुशाला!।१२५।

एक बरस में, एक बार ही जलती होली की ज्वाला,
एक बार ही लगती बाज़ी, जलती दीपों की माला,
दुनियावालों, किन्तु, किसी दिन आ मदिरालय में देखो,
दिन को होली, रात दिवाली, रोज़ मनाती मधुशाला।।२६।

मुसलमान औ’ हिन्दू है दो, एक, मगर, उनका प्याला,
एक, मगर, उनका मदिरालय, एक, मगर, उनकी हाला,
दोनों रहते एक न जब तक मस्जिद मन्दिर में जाते,
बैर बढ़ाते मस्जिद मन्दिर मेल कराती मधुशाला!।५०।

यम आयेगा साकी बनकर साथ लिए काली हाला,
पी न होश में फिर आएगा सुरा-विसुध यह मतवाला,
यह अंतिम बेहोशी, अंतिम साकी, अंतिम प्याला है,
पथिक, प्यार से पीना इसको फिर न मिलेगी मधुशाला।८०।

मेरे अधरों पर हो अंतिम वस्तु न तुलसीदल प्याला
मेरी जीव्हा पर हो अंतिम वस्तु न गंगाजल हाला,
मेरे शव के पीछे चलने वालों याद इसे रखना
राम नाम है सत्य न कहना, कहना सच्ची मधुशाला।।८२।

मेरे शव पर वह रोये, हो जिसके आंसू में हाला
आह भरे वो, जो हो सुरिभत मदिरा पी कर मतवाला,
दे मुझको वो कान्धा जिनके पद मद डगमग होते हों
और जलूं उस ठौर जहां पर कभी रही हो मधुशाला।।८३।

और चिता पर जाये उंडेला पात्र न घृत का, पर प्याला
कंठ बंधे अंगूर लता में मध्य न जल हो, पर हाला,
प्राण प्रिये यदि श्राध करो तुम मेरा तो ऐसे करना
पीने वालों को बुलवा कऱ खुलवा देना मधुशाला।।८४।

– बच्चन

The above poem in Amitabh Bachchan’s voice. कहना सच्ची है मधुशाला.

Kumaar Vishwaas’ Poems

Got time to read some poems this weekend. Got hold of these 2 from Kumaar Vishwaas.

कोई दीवाना कहता है (कविता) / कुमार विश्वास

कोई दीवाना कहता है, कोई पागल समझता है !
मगर धरती की बेचैनी को बस बादल समझता है !!
मैं तुझसे दूर कैसा हूँ , तू मुझसे दूर कैसी है !
ये तेरा दिल समझता है या मेरा दिल समझता है !!

मोहब्बत एक अहसासों की पावन सी कहानी है !
कभी कबिरा दीवाना था कभी मीरा दीवानी है !!
यहाँ सब लोग कहते हैं, मेरी आंखों में आँसू हैं !
जो तू समझे तो मोती है, जो ना समझे तो पानी है !!

समंदर पीर का अन्दर है, लेकिन रो नही सकता !
यह आँसू प्यार का मोती है, इसको खो नही सकता !!
मेरी चाहत को दुल्हन तू बना लेना, मगर सुन ले !
जो मेरा हो नही पाया, वो तेरा हो नही सकता !!

भ्रमर कोई कुमुदुनी पर मचल बैठा तो हंगामा!
हमारे दिल में कोई ख्वाब पल बैठा तो हंगामा!!
अभी तक डूब कर सुनते थे सब किस्सा मोहब्बत का!
मैं किस्से को हकीक़त में बदल बैठा तो हंगामा!!

In his own voice Koi Deewana Kehta Hai

जिसकी धुन पर दुनिया नाचे / कुमार विश्वास

जिसकी धुन पर दुनिया नाचे, दिल ऐसा इकतारा है,
जो हमको भी प्यारा है और, जो तुमको भी प्यारा है.
झूम रही है सारी दुनिया, जबकि हमारे गीतों पर,
तब कहती हो प्यार हुआ है, क्या अहसान तुम्हारा है.

जो धरती से अम्बर जोड़े , उसका नाम मोहब्बत है ,
जो शीशे से पत्थर तोड़े , उसका नाम मोहब्बत है ,
कतरा कतरा सागर तक तो ,जाती है हर उम्र मगर ,
बहता दरिया वापस मोड़े , उसका नाम मोहब्बत है .

पनाहों में जो आया हो, तो उस पर वार क्या करना ?
जो दिल हारा हुआ हो, उस पे फिर अधिकार क्या करना ?
मुहब्बत का मज़ा तो डूबने की कशमकश में हैं,
जो हो मालूम गहराई, तो दरिया पार क्या करना ?

बस्ती बस्ती घोर उदासी पर्वत पर्वत खालीपन,
मन हीरा बेमोल बिक गया घिस घिस रीता तनचंदन,
इस धरती से उस अम्बर तक दो ही चीज़ गज़ब की है,
एक तो तेरा भोलापन है एक मेरा दीवानापन.

तुम्हारे पास हूँ लेकिन जो दूरी है समझता हूँ,
तुम्हारे बिन मेरी हस्ती अधूरी है समझता हूँ,
तुम्हे मै भूल जाऊँगा ये मुमकिन है नही लेकिन,
तुम्ही को भूलना सबसे ज़रूरी है समझता हूँ

बहुत बिखरा बहुत टूटा थपेड़े सह नहीं पाया,
हवाओं के इशारों पर मगर मैं बह नहीं पाया,
अधूरा अनसुना ही रह गया यूं प्यार का किस्सा,
कभी तुम सुन नहीं पायी, कभी मैं कह नहीं पाया

Interview Questions 15

1. Input Data : {[1,3],[2,4],[10,11],[4,6]}
Output: {[1,6],[10,11]}
We have to merge all the ranges that are overlapping. You can consider Input data as any Data structure.

2. Given a char array with words in it, find all ‘a’ characters and replace with xyz. Modify the input array, do not create a copy of the array.

3. How do you output the nodes from a binary search tree given a range

4. Implement a function
public long[] GetMultiplesOfTwoLessThan(int num)
eg if num is given as 30, output array should contain {1,2,4,8,16}. It shouldn’t contain 32 since 32 is more than the given number.

Another exp: if num is 300 then output will be {1,2,4,8,16,32,64,128,256}
Super optimized solution desired

5. Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square.

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

Variant: Print the same for a tree that is not complete.

7. Given 3 product categories and a respective file of a huge size containing only the list of order numbers in sorted manner. Write an algorithm (best possible time complexity to be achieved) which can find common order numbers in all 3 files.

8. Implement boolean ValidateIP(string inpIP)

9. Given a file in which the data is stored in the form

ABC
_DEF
_GEH
XYZ
_PQR
__STY

Construct an nary tree out of it in O(n) time such that DEF and GEH are the children of ABC and XYZ is the sibling of ABC, PQR is child of XYZ and STY is child of PQR. The spaces after the beginning of a line specify the relation of a node to its predecessors.

10. Why auto variables are not stored in heap?

11. Each cell of an N x N grid is either a 0 or a 1. You are given two such N x N grids, the initial grid and the final grid. There is a button against each row and each column of the initial N x N grid. Pressing a row-button toggles the values of all the cells in that row, and pressing a column-button toggles the values of all the cells in that column. You are required to find the minimum number of button presses required to transform the grid from the initial configuration to the final configuration, and the buttons that must be pressed in order to make this transformation.

Interview Question 14

1. Given a line segment of length n. You need to cut it into m pieces specified by position[n] array. The price of cutting a segment of length len in two parts is always len (irrespective of cut position). Give a dynamic programming solution to minimize the cost of cutting.

2. Given a BST, print all the values >=vmin and <=vmax. Time complexity should be better than O(n). O(logn + (vmax-vmin)) in worst case.
No parent pointers are available.

3. You have a huge graph of cities and cost of flight between them. Find the cheapest path from A to B. The graph doesn’t fit in memory.

4. Write a function

int count_div(int a,int b,int k);

That given three integer numbers a, b and k return number of integers from range [a..b] divisible by k, i.e.:
For example, for a=6, b=11, and k=2, your function should return 3, because there are 3 numbers divisible by 2 in the range [6..11], namely 6, 8 and 10.
You can assume that , and k>0.

5. Given is an array of integers. Element is called an extreme if no other element’s value is more distant from the average. Write a function

int extreme(int[] A);

That given an array of integers returns the index of an extreme (any one of them if there are many).

If no extreme exists, the function should return -1.
A[0]=9, A[1]=4, A[2]=-3, A[3]=-10
the index of an extreme is 3, because the average of the array is
(9 + 4 + (-3) + (-10)) / 4 = 0
and in this array no value is further from 0 than -10

6. Say you need to design a web application which needs to support friends of friends function(like in linked in, when you search a person, it will show you if this person is linked with you, your connection or your connections’ conection…), we expect to have millions of users and each user may have thousands of friends, how would you design/implement this function to make it scalable.

7. Given two n digit prime numbers, change the first number to the second by changing one digit at a time. The resulting intermediate numbers should also be prime.

8. Given an input array of integers of size n, and a query array of integers of size k, find the smallest window of input array that contains all the elements of query array and also in the same order.

9. There is an array
A[N][M] =
1 2 3
4 5 6
The array is rotated so that
A'[M][N] =
3 6
2 5
1 4
is obtained.
Establish the relation between A and A’ by using i, j, M, N

A[i][j] = A'[_][_]

10. Given a list of strings say N, how would you write a perfect hash function and ensure 0 collissions?

Interview Questions 13

1. Give a string, print total count of substrings (length>=2) which are palindromes. He was expecting better than O(n2) time complexity.

2. How do you implement a linked list without using dynamic memory allocation? So basically you need to use an array as a linked list.

3. Give an algorithm to compress a memory. To be more clear if you are given a memory of some stored data here and there and some empty and null memory in between, how will you fragment and compress your memory?

4. Given a 3d plane, and infinite points find kth closest point from a given point.

5. Given a statement which took an integer, incremented it by 1 and then branched to another location which you provide, implement addition of two numbers multiplication, etc using just that statement

6. You dont know the required size of the array.how will you allocate space for the array.for eg. if you allocate 100 blocks then user can have just 10 elements or 1000 elements.

7. What happens after entering URL address at the browser(details of how we get to see the web page)?

8. Sorted Array is rotated n times. You have to find the current index of the some element X. If element is not present then return the maximum element of the array in O(log n).

9. There is an array consisting of postive and negative integers. find the subarray whose sum is 0.

10. Given a dictionary of words and a string with all spaces removed, return whether the string is composed of valid words
e.g
helloworld-> hello world (valid)
isitniceinhere-> is it nice in here (valid)
zxyy-> invalid

%d bloggers like this: