All Black’s HAKA

Some time back a friend of mine suggested me to see a video on Youtube. The video was about the All Black’s Haka. Any sports enthusiast and passionate person, like me :D, would love this holy ritual (if you call it so). This video which I provide in this post has subtitles and explains the Haka lyrics too. When I saw it for the first time, I could feel the intensity and the condition of the opposition team :D. No wonder why the Kiwis are the Best at Rugby.

Interview Questions 7

1. How will you write thread-safe strtok function.

2. Given a polygon and a point, you have to find that whether the point is inside the polygon or outside.

3. How to identify bits that alternate 1 and 0. Ex: 101010, 10101, 01010, 01

4. Given a set of points in a plane. Write a function to check if there exists a vertical line of symmetry in this plane.

5. What has to be done in order to be able to do a O(logn) binary search on a linked list.

6. Given a sorted array (ex. {1,2,3,4,5,6,7,8}). A random number from the array is taken and put the left side array to right side and left side array to right side. In the example; if 6 is randomly taken, the array will become like {7,8,6,1,2,3,4,5}
Question:
Given the above mangled array, write a searching algorithm to find a number present or not. That algo should not be of O(n) solution.

7. Write a function which takes a number as input and returns it next number. Condition: the next and given number should have equal number of 1’s in its binary format.
Example: 5 – 101 its next number 6-110. both have two 1’s.

10 reasons why your computer is better than your girlfriend

This one gives me hope 😀

1.) She doesn’t talk back to you. At best she beeps or gives you the silent treatment.

2.) She provides you with more information than your girlfriend will ever know.

3.) When you upgrade you know the costs up front.

4.) You can stare at tons of other girls and your computer will never get mad at you.

5.) You can shut her down whenever you get tired of her.

6.) Troubleshooting your computer is much easier than your GF.

7.) Your computer holds many valuable bits of information about your past and still likes you.

8.) You can press your computers buttons without any worry of repercussions.

9.) Your computer won’t sleep with your best friend or cheat on you.

10.) Your computer will cost a lot less than any girlfriend!

Why some men prefer dogs over women

Got it from a blog.. worth sharing here 😀

1. The later you are, the more excited your dogs are to see you.

2. Dogs don’t notice if you call them by another dog’s name.

3. Dogs like it if you leave a lot of things on the floor.

4. A dog’s parents never visit.

5. Dogs agree that you have to raise your voice to get your point across.

6. You never have to wait for a dog; they’re ready to go 24 hours a day.

7. Dogs find you amusing when you’re drunk.

8. Dogs like to go hunting and fishing.

9. A dog will not wake you up at night to ask, ‘If I died, would you get another dog?’

10. If a dog has babies, you can put an ad in the paper and give them away.

11. A dog will let you put a studded collar on it without calling you a pervert.

12. If a dog smells another dog on you, they don’t get mad. They just think it’s interesting.

13. Dogs like to ride in the back of a pickup truck.

And last, but not least:

14. If a dog leaves, it won’t take half of your stuff.

Programming Problems 15

1. In the shortest-path algorithm we are concerned with the total length of the path between a source and every other node. Suppose instead that we are concerned with the length of the longest edge between the source and every node. That is, the bottleneck of a path is defined to be the length of the longest edge in the path. Design an efficient algorithm to solve the single source smallest bottleneck problem; i.e. find the paths from a source to every other node such that each path has the smallest possible bottleneck.

2. Consider the shortest paths problem in the special case where all edge costs are non-negative integers. Describe a modification of Dijkstra’s algorithm that works in time O(|E|+|V|m), where m is the maximum cost of any edge in the graph.

3. Suppose you are given a weighted graph G = (V,E) and an edge e (belongs to) E. You are asked whether e is in some minimum spanning tree of G. Give a linear time algorithm for the problem.

4. A challenge that arises in databases is how to summarize data in easy-to-display formats, such as a histogram. A problem in this context is the minimal imbalance problem. Again suppose we have an array A containing n numbers, this time all positive, and another input k. Consider k indices j1, j2, . . . jk that partition the array into k+1 subarrays A[1, j1],A[j1 + 1, j2], . . . ,A[jk + 1, n]. The weight w(i) of the ith subarray is the sum of its entries. The imbalance of the partition is

That is, the imbalance is the maximum deviation any partition has from the average size. Give an algorithm for determining the partition with the minimal imbalance given A, n, and k. (This corresponds to finding a histogram with k breaking points, giving k + 1 bars, as close to equal as possible, in some sense.)

5. Let P be a convex polygon with n vertices. A diagonal is a line segment that connects two vertices of P and lies in the interior of P. A decomposition of P into triangles by a maximal set of non-intersecting diagonals is called a triangulation of the polygon. Describe a O(n3) time algorithm to compute a triangulation of P such that the sum of the lengths of the diagonals included in the triangulation is minimized.

6. A palindrome is any string that is exactly the same as its reverse, e.g. I, DEED,RACECAR. Any string can be decomposed into a sequence of palindromes. For example, the string BUBBASEESABANANA (Bubba sees a banana) can be broken into plaindromes in many ways;here are a few examples:

BUB + BASEESAB + ANANA
B+U+BB+A+SEES+ABA+NAN+A
B+U+BB+A+SEES+A+B+ANANA

Describe and analyze an efficient algorithm to find the smallest number of palindromes into which an input string  can be decomposed. The algorithm should return the sequence of palindromes into the resulting decomposition.

Programming Problems 14

1. Suppose you want to travel from city A to city B by car, following a fixed route. Your car can travel m miles on a full tank of gas, and you have a map of the n gas stations on the route between A and B that gives the number of miles between each station.
Design an algorithm to find a way to get from A to B without running out of gas that minimizes the total number of refueling stops, in O(n) time.

2. Design a data structure that supports the following two operations on a set S of integers:
a. Insert(x; S), which inserts element x into set S, and
b. DeleteLargerHalf(S), which deletes the largest ceil(|S|/2) elements from S.
Show how to implement this data structure so both operations take O(1) amortized time.

3. An array contains first n positive integers not divisible by m(m>1 and m<n) in random order. Give an efficient solution in O(n) and only one extra space for to find m:

Input: n, array of integers in random order
Output: m

Example1
Input: 5, {2,5,7,1,4}
Output: 3

Example2:
Input: 4, {3,5,1,7}
Output: 2

4. There are 20 floors in a building. I step into the elevator with 5 other people. What is the probability that I do not have to press my button? (ie someone else chooses the same floor as me)

5. You are given an array of positive integers a[1..n] such that

1) a[1] < a[2] < … a[ n ]

Given a positive integer C find j and i such that

Choose(a[j], a[i]) = C

where Choose(b,a) = b choose a, the binomial coefficient = the number of ways of choosing a balls from a set of b balls. Assume you have a fast Choose(b,a) calculating function at your disposal.

6, Given an array A of N integers, equi(A) is any index i for which:
(1) i is a valid index into A, i.e. 0 <= i < N
(2) The sum of integers preceding (but not including) i is equal to the sum of integers following (again not including) i. i.e.:
A[0]+A[1]+…+A[i-1] = A[i+1]+A[i+2]..+A[N-1]

If there is no such index i, equi(A) = -1.

e.g.
equi [1,2,0,3] = 2, because A[0] + A[1] = 1 + 2 = A[3] = 3.
equi [0] = 0
equi [] = -1

Find if the given array has this property.

7. The sequence A is defined as follows:
Start with the natural numbers
1,2,3,…
Initialize count = 1;

while(there are uncrossed numbers)
{
pick the first uncrossed number say n.
set A[count] = n.
Cross out the number count+n and n.
Increment count.
}

Give a fast algorithm to determine A[n], given n.
Try getting an algorithm which is polynomial in log n.

8. Say that a list of numbers is k-close to sorted if each number in the list is less than k positions from its actual place in the sorted order. (Hence, a list that is 1-close to sorted is actually sorted.) Give an O(nlog k) algorithm for sorting a list of n numbers that is k-close to sorted.

%d bloggers like this: