A Break

This is my 50th post on this blog 🙂

I’ve come a long way I guess :P, these 50 posts used up a lot of my time which is good coz I had a lot of it to waste :D. Anyways I see that this blog has more than 125 awesum programming and interview problems and now even my resources have kinda dried out .. so I’ll give the blog a break and get myself upto something else.. maybe I’ll start a new serial ( any suggestions are welcome 🙂 ). I’ll be active towards the comments and feel free to ask for hints and solution confirmations. Also some of you have suggested to organize the blog, lemme see how much I can do in that regard :D.

I’ll try to get back soon..

Njoi

Advertisements

Interview Questions 6

Time for some relatively easy interview style problems 🙂

1. Given an array of integers A[N], find the maximum value of (j-k) such that A[k] <= k and j > k.(taken from this blog).

2. A certain program makes use of malloc and free several times. Anyway, you forgot to free one block of memory allocated with one malloc. What strategy do you use to check the place where the unpaired malloc is located? (taken from this blog).

3. Find the longest path in a DAG.

4. Given a>0 can you compute a^-1 without any division?

5. 100 digits are chosen at random. What is the probability to find two numbers, a and b, such that a^2=b and each digit is used just one time in forming the two numbers?

6. You are given a sequence of m distinct numbers extracted by a set of 1…n numbers, with m < n. Can you give an efficient algorithm for identifying a number non in the sequence. (taken from this blog)

7. Given stock values for a share per day for a company for last say 1 year. Find the maximum loss that any share holder could have made?. Assume that share holder can buy and sell only once.

8. Given an array of integers from 1 to N, and given a number X, how many ways are there to pick X elements from the array such that no two elements in the selected X elements are consecutive.

9. Given a log file which has customer id and corresponding to that id it has a page id visited by that customer. Given such log files for 3 consecutive days, design an algo to find those customers which visited the site on exactly 2 out of 3 days and visited at least 3 distinct pages. Discuss the design and space complexity. Optimize (question is not about using unix tricks)

10. Given a log file with first field being an url and second being the render time of that page. find the page with least render time. Url is accessed many times like 50 times or 100 times. every access has an entry so we have to find the average.

11. Which is the DS used in dictionary mode in mobile (t9)

12. Write a program which given a numerator and a denominator, prints the fractional value in a special format. eg. Numerator: 1, Denominator: 3. So Num/Denom = 0.3333333333, but output should be .(3) similarly 0.123123 as .(123) also 0.34232323 as 0.34(23)

13. Given a string construct a new string containing the occurrences of unique characters in it. You can
assume that only a-z & A-Z appear in the string with ‘a’ being different from ‘A’. Also the letters in the output string must be in the order of their occurrence in the input string.
e.g. for the string “ThunderBirdFirefox” you must return the string “T1h1u1n1d2e2r3B1i2F1f1o1x1”

14. Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

15. If the Fibonacci series is 1,2,3,5,8,13,….. then 10 can be written as 8 + 2 ==> 10010 and 17 can be written as 13 + 3 + 1 ==> 100101. Got it??
The Question was, given n, I need to get all possible representations of n in Fibonacci Binary Number System.
as 10 = 8 + 2 ==> 10010
also 10 = 5 + 3 + 2 ==> 1110

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

17. Given a string S of alphabets and 2 characters a,b find the minimum distance between instances of them such that position of a <= position of b.

18. You have all the English words with you. you would like to manage a dictionary so that you can look up when ever you have doubt. Which data structure would you like to use and why?

19. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. [O(1) space]

20. [ Beauty ] Write an Assembly Level Program [ALP] to find sum of first n natural numbers using the following Instructions
LDA num ; load Accumulator with num
DCR R ; decrement Register R
INR R ; increment Register R
MOV x,y ; move the contents of register y into register x
JZ label ; jump to label if A=0
DJNZ label; Decrement & Jump if A 0
you can use B & C registers in addition to A register

Programming Problems 13

Here is another set of problems, these are not just a piece of cake 🙂

1. [From CLRS] You are given an array of integers where different integers may have different number of digits, but the total number of digits over all the integers in the array is n. Give an algorithm to sort the array in O(n) time.

2. [From CLRS] Give an algorithm to sort n integers in the range 0 to n^2 – 1 in O(n) time.

3. Suppose we are given a collection A = {a1, a2, ….., an } of n positive integers that add upto N. Design an O(nN)-time algorithm to determine whether there is a subset B ⊂ A, such that the sum of the elements in the set B is equal to the sum of the elements in the set A-B.

4. [Code this one to trust your algorithm :)]Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of n words of lengths l1, l2, l3, ……,ln, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. Our criterion of “neatness” is as follows. If given line contains words i through j, where i ≤ j, and we leave exactly one space between words, the number of extra space characters at the end of the line is M – j + i – Σj{k=i} lk, which must be non-negative so that words fit on a line. We wish to minimize the sum, over all lines except the last, of the numbers of extra space characters at the ends of the lines. Design an algorithm to print a paragraph of n words neatly on a printer.

5. [Nice one, do give a shot :)] Given a directed graph G, with V vertices and E edges. Each edge in E is associated with a real number ‘r’,a reliabilty factor with r between 0(exclusive) and 1(inclusive). You are also given a pair of nodes u and v. Find the most reliable path in the given graph from u to v.

Input will be the graph represented as a matrix with the following format:
* the number of vertices n. (therefore, A is an nxn matrix)
* The elements of A, row-wise: (total n*n numbers)
A(i,j) = 0 denotes that the edge (i,j) is not present
A(i,j) between 0 (exclusive) and 1 (inclusive) indicates
that the edge (i,j) is present with reliability A(i,j).

Output: Your output will be a sequence of vertices giving the path from u to v such as 1,4,3,5,8,6,7 with u=1 and v=7. The output is thus a comma separated list of vertices giving the path from u to v.

Njoi

This is NOT the way to start ;)

Thankfully I got this pretty soon 😉

HE: I’m a photographer I’ve been looking for a face like yours!
SHE: I’m a plastic surgeon. I’ve been looking for a face like yours

HE: May I have the pleasure of this dance?
SHE: No, I’d like to have some pleasure too !

HE: How did you get to be so beautiful?
SHE: I must have been given your share !

HE: Will you come out with me this Saturday?
SHE: Sorry! I’m having a headache this weekend !

HE: Go on, don’t be shy. Ask me out!
SHE: Okay, get out!

HE: I think I could make you very happy
SHE: Why? Are you leaving?

HE: What would you say if I asked u to marry me?
SHE: Nothing. I can’t talk and laugh at the same time!

HE: Can I have your name?
SHE: Why, don’t you already have one?

HE: Shall we go and see a film?
SHE: I’ve already seen it!

HE: Do you think it was fate that brought us together?
SHE: Nah, it was plain bad luck !

HE: Where have you been all my life?
SHE: Hiding from you.

HE: Haven’t I seen you someplace before?
SHE: Yes, that’s why I don’t go there anymore.

HE: Is this seat empty?
SHE: Yes, and this one will be if you sit down .

HE: So, what do you do for a living?
SHE: I’m a female impersonator.

HE: Hey baby, what’s your sign?
SHE: Do not enter.

So, be aware next time when you go to any girl and try to impress her 🙂

100 Most Funny One-liners

Found these on a blog .. copied it down here 🙂

1 I asked God for a bike, but I know God doesn’t work that way. So I stole a bike and asked for forgiveness.
2 Do not argue with an idiot. He will drag you down to his level and beat you with experience.
3 I want to die peacefully in my sleep, like my grandfather.. Not screaming and yelling like the passengers in his car.
4 The last thing I want to do is hurt you. But it’s still on the list.
5 Sex is not the answer. Sex is the question. “Yes” is the answer.
6 Women might be able to fake orgasms. But men can fake a whole relationship.
7 We live in a society where pizza gets to your house before the police.
8 Having sex is like playing bridge. If you don’t have a good partner, you’d better have a good hand.
9 We never really grow up, we only learn how to act in public.
10 Men have two emotions: Hungry and Horny. If you see him without an erection, make him a sandwich.
11 Light travels faster than sound. This is why some people appear bright until you hear them speak.
12 War does not determine who is right – only who is left.
13 If I agreed with you we’d both be wrong.
14 The early bird might get the worm, but the second mouse gets the cheese.
15 Politicians and diapers have one thing in common. They should both be changed regularly, and for the same reason.
16 Children: You spend the first 2 years of their life teaching them to walk and talk. Then you spend the next 16 years telling them to sit down and shut-up.
17 If sex is a pain in the ass, then you’re doing it wrong…
18 Knowledge is knowing a tomato is a fruit; Wisdom is not putting it in a fruit salad.
19 Evening news is where they begin with ‘Good evening’, and then proceed to tell you why it isn’t.
20 A bus station is where a bus stops. A train station is where a train stops. On my desk, I have a work station..
21 My mother never saw the irony in calling me a son-of-a-bitch.
22 I didn’t fight my way to the top of the food chain to be a vegetarian
23 If you think nobody cares if you’re alive, try missing a couple of payments.
24 I thought I wanted a career, turns out I just wanted paychecks.
25 If God is watching us, the least we can do is be entertaining.
26 Better to remain silent and be thought a fool, than to speak and remove all doubt.
27 If 4 out of 5 people SUFFER from diarrhea… does that mean that one enjoys it?
28 Some people are like Slinkies … not really good for anything, but you can’t help smiling when you see one tumble down the stairs.
29 How is it one careless match can start a forest fire, but it takes a whole box to start a campfire?
30 Did you know that dolphins are so smart that within a few weeks of captivity, they can train people to stand on the very edge of the pool and throw them fish?
31 A bank is a place that will lend you money, if you can prove that you don’t need it.
32 Going to church doesn’t make you a Christian any more than standing in a garage makes you a car.
33 Never, under any circumstances, take a sleeping pill and a laxative on the same night.
34 To steal ideas from one person is plagiarism. To steal from many is research.
35 A computer once beat me at chess, but it was no match for me at kick boxing.
36 I saw a woman wearing a sweat shirt with “Guess” on it…so I said “Implants?”
37 Why does someone believe you when you say there are four billion stars, but check when you say the paint is wet?
38 A clear conscience is usually the sign of a bad memory.
39 The voices in my head may not be real, but they have some good ideas!
40 Good girls are bad girls that never get caught.
41 Women will never be equal to men until they can walk down the street with a bald head and a beer gut, and still think they are sexy.
42 Laugh at your problems, everybody else does.
43 The shinbone is a device for finding furniture in a dark room.
44 Whenever I fill out an application, in the part that says “If an emergency, notify:” I put “DOCTOR”. What’s my mother going to do?
45 He who smiles in a crisis has found someone to blame.
46 The main reason Santa is so jolly is because he knows where all the bad girls live.
47 I didn’t say it was your fault, I said I was blaming you.
48 Artificial intelligence is no match for natural stupidity.
49 God must love stupid people. He made SO many.
50 Behind every successful man is his woman. Behind the fall of a successful man is usually another woman.
51 The sole purpose of a child’s middle name, is so he can tell when he’s really in trouble.
52 Never get into fights with ugly people, they have nothing to lose.
53 Always borrow money from a pessimist. He won’t expect it back.
54 Never hit a man with glasses. Hit him with a baseball bat.
55 My opinions may have changed, but not the fact that I am right.
56 Some people say “If you can’t beat them, join them”. I say “If you can’t beat them, beat them”, because they will be expecting you to join them, so you will have the element of surprise.
57 Some cause happiness wherever they go. Others whenever they go.
58 It’s not the fall that kills you; it’s the sudden stop at the end.
59 Crowded elevators smell different to midgets.
60 Hospitality: making your guests feel like they’re at home, even if you wish they were.
61 You do not need a parachute to skydive. You only need a parachute to skydive twice.
62 Nostalgia isn’t what it used to be.
63 I discovered I scream the same way whether I’m about to be devoured by a great white shark or if a piece of seaweed touches my foot.
64 A bargain is something you don’t need at a price you can’t resist.
65 My psychiatrist told me I was crazy and I said I want a second opinion. He said okay, you’re ugly too.
66 I intend to live forever. So far, so good.
67 Money can’t buy happiness, but it sure makes misery easier to live with.
68 A diplomat is someone who can tell you to go to hell in such a way that you will look forward to the trip.
69 We have enough gun control. What we need is idiot control.
70 You’re never too old to learn something stupid.
71 I should’ve known it wasn’t going to work out between my ex-wife and me. After all, I’m a Libra and she’s a bitch.
72 A little boy asked his father, “Daddy, how much does it cost to get married?” Father replied, “I don’t know son, I’m still paying.”
73 With sufficient thrust, pigs fly just fine.
74 Women may not hit harder, but they hit lower.
75 Knowledge is power, and power corrupts. So study hard and be evil.
76 There’s a fine line between cuddling and holding someone down so they can’t get away.
77 I don’t trust anything that bleeds for five days and doesn’t die.
78 Worrying works! 90% of the things I worry about never happen.
79 Why do Americans choose from just two people to run for president and 50 for Miss America?
80 I always take life with a grain of salt, …plus a slice of lemon, …and a shot of tequila.
81 If at first you don’t succeed, skydiving is not for you!
82 I used to be indecisive. Now I’m not sure.
83 When in doubt, mumble.
84 I like work. It fascinates me. I sit and look at it for hours.
85 To be sure of hitting the target, shoot first and call whatever you hit the target.
86 Jesus loves you, but everyone else thinks you’re an asshole.
87 A bus is a vehicle that runs twice as fast when you are after it as when you are in it.
88 A TV can insult your intelligence, but nothing rubs it in like a computer.
89 Just remember…if the world didn’t suck, we’d all fall off.
90 I got in a fight one time with a really big guy, and he said, “I’m going to mop the floor with your face.” I said, “You’ll be sorry.” He said, “Oh, yeah? Why?” I said, “Well, you won’t be able to get into the corners very well.”
91 Some people hear voices.. Some see invisible people.. Others have no imagination whatsoever.
92 You are such a good friend that if we were on a sinking ship together and there was only one life jacket… I’d miss you heaps and think of you often.
93 When tempted to fight fire with fire, remember that the Fire Department usually uses water.
94 Hallmark Card: “I’m so miserable without you, it’s almost like you’re still here.”
95 Virginity is like a soapbubble, one prick and it is gone.
96 Change is inevitable, except from a vending machine.
97 If winning isn’t everything why do they keep score?
98 If you keep your feet firmly on the ground, you’ll have trouble putting on your pants.
99 If you are supposed to learn from your mistakes, why do some people have more than one child.
100 Whoever coined the phrase “Quiet as a mouse” has never stepped on one.

Have very less time to memorize all of them 😛

Programming Problems 12

A few more questions which I dug up from my laptop :). I feel that people are taking interest in problems now so I’ll try to solve more problems and put them here or I’ll re-post the older problems. Enjoy 🙂

1. Given an integer array of length n, find 2 numbers which has maximum XOR.

2. Given a string and a array of smaller strings. Design a method to find out every occurence of smaller implementation in larger string.

3. A semi-connected graph is a graph that for each pair of vertices u,v, there is either a path from u to v or a path from v to u. Give an algorithm to test if a graph is semi-connected.

4. Suppose you have a tree. A binary tree (for something like simplicity :P). You are traversing it (using infix, postfix or prefix) to search for a node. You find your required node. You just realized that you need to know the path from this node back to the root node (and/or vice versa). Given the following description of the structure of the tree node that you “cant” change:

struct node
{
         Data data;
         node *right,*left;
};

To make it more intresting (or maybe just the application of the above problem) suppose you find the node A and a node B in consecutive searches. Now what will your strategy be to show a path from A to B. (not neccesarily from the root of the whole tree, but possibly).

5. Print a 2D Youngs Tableau (rows and columns sorted ) in sorted order in less than O(n^3).

6. Input : You have been given a sequence of integers.
Now without actually constructing BST from the given sequence of integers (assuming the sequence is pre-order) determine if each node of BST has single child (either left or right but not both).
Output : YES if given integer sequence corresponds to such a BST. otherwise say NO.

Ex. Say NO for 16,10,8,9,29,27,22.
Say YES for 10,19,17,14,15,16

Some Adult Pic Jokes

I was browsing through the pictures stored on my laptop and got hold of some of these interesting and hilarious adult pic jokes. I don’t mean any offence to the reader/viewers, I just happen to find them funny enough to share. Besides, I don’t think I have any female visitors, so it’s safe too :P.

I would strongly encourage you guys to also read the names of the image files they make the pics even more hilarious 😛

If there happen to be any American/New Yorker passing by, would you please tell me why is this pic hilarious. I just couldn’t get the punch of it 😦

Let me know if this was annoying or funny 🙂

%d bloggers like this: