# Two numbers question

Tags: , | Posted by Admin on 5/10/2012 7:37 AM | Comments (1)
A friend of mine is interviewing for a job. One of the interview questions got me thinking, just wanted some feedback. There are 2 non-negative integers: i and j. Given the following equation, find an (optimal) solution to iterate over i and j in such a way that the output is sorted. 2^i * 5^j So the first few rounds would look like this: 2^0 * 5^0 = 1 2^1 * 5^0 = 2 2^2 * 5^0 = 4 2^0 * 5^1 = 5 2^3 * 5^0 = 8 2^1 * 5^1 = 10 2^4 * 5^0 = 16 2^2 * 5^1 = 20 2^0 * 5^2 = 25 Try as I might, I can't see a pattern. Your thoughts?

# Task: Find meeting point

Tags: | Posted by Admin on 3/13/2012 11:11 AM | Comments (7)
There is a matrix, m x n. Several groups of people locate at some certain spots. In the following example, there are three groups and the number 4 indicates there are four people in this group. Now we want to find a meeting point in the matrix so that the cost of all groups moving to that point is the minimum. As for how to compute the cost of moving one group to another point, please see the following example. Group1: (0, 1), 4 Group2: (1, 3), 3 Group3: (2, 0), 5 . 4 . . . . . 3 5 . . . If all of these three groups moving to (1, 1), the cost is: 4*((1-0)+(1-1)) + 5*((2-1)+(1-0))+3*((1-1)+(3-1))

# Jim's experience

Posted by Admin on 3/1/2012 12:04 PM | Comments (1)
There were 3 rounds of interview.In the first round they asked s string related question.1. Given a string and set of characters, find the shortest substring which contains all the characters in the string.In the 2nd round2.Given a 2d sorted matrix (known as tableau) . where rows and cols are sorted, write an algo to find an element.In the 3rd round they asked about garbage collection in java, about my projects and a question related to graphs I dont remeber exactly at this point.

# Geometric question

Tags: | Posted by Admin on 2/23/2012 10:35 AM | Comments (10)
Given 2n points on a circle.find the number of ways to draw n non intersecting chords.

# Easy questions & solutions

Tags: , | Posted by Admin on 2/21/2012 11:10 AM | Comments (0)
You 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. Solution:The question can be elucidated as follows.Given an array of size N-1 containing numbers less than N and with out any duplicates!! We knew that there is a number missing from the array say K .Let S be the sum of the elements of the array. Sum of first N natural numbers=N*(N+1)/2 and S=N*(N+1)/2 – K.Now putting this other way around we get K=N*(N+1)/2 -S !! Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y. We solve this problem by solving 2 essential equations. They are X+Y=N*(N+1)/2 -S               (1) X*Y=N!/P             (2) where S and P are the cumulative sum and product of the array entries. You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place. Solution:The problem of checking whether there is a cycle or not can be solved using 2 pointers one moving in increments of 1 and the other in increments of 2.If there is a cycle then these 2 pointers meet at some node say N1 inside the cycle otherwise the fast pointer reaches the end of the list.This is a O(N) solution. Now coming to the identification of the node at which looping took place.After our identification of cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow pointer to count the no of nodes in the cycle.(After traversing the whole cycle P1 and P2 shall again be at the same node).Let this size be K.Now take one of the pointers to the head node and count the no of nodes till N1.Let this number be X.Now use one of these pointers to reverse the cycle starting from N1.Only the cycle gets reversed.Now again traverse from head node to N1.Let the number of nodes this time be Y.Let the no of nodes from head to the start node of the cycle be Z Now X+Y=2*Z+K .Hence solve for K and then having figured out the start node N2 of the cycle.Now as the cycle is reversed having figured out this start node its next node is the looping nodes so set the looping nodes next pointer to NULL and reverse the list further till you reach N2.Questions on my project please be prepare well about your projectHow do you search for a word in a large database.How do you build address bar in say gmail. i.e. if you press ‘r’ then you get all email starting from ‘r’, and if you press ‘ra’ then you will get emails starting from ‘ra’.

# Graph Theory: Find cycles

Tags: , | Posted by Admin on 1/18/2012 11:34 AM | Comments (0)
Given an undirected graph, design a O(V+E) algo to detect whether there is a triangle in the graph ot not.

# How to find the Least Common Ancestor for 2 nodes of a binary tree ?

Tags: , | Posted by Admin on 1/16/2012 5:32 PM | Comments (0)
Question: How to find the Least Common Ancestor for 2 nodes of a binary tree? This sounds like "On finding lowest common ancestors: simplification and parallelization", by Baruch Schieber and Uzi Vishkin, SIAM J. Comput. Vol 17, No 6, December 1988. A google search leads me tohttp://ia700208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf. I actually wrote an implementation of this for fun - it is in a zip file miscellaneous for-fun Java code that you can find off a link from http://www.mcdowella.demon.co.uk/programs.html. (The algorithm needs linear space and time for pre-processing, then runs at O(1) per query).

# Find the Closest intersection point in plan

Tags: , | Posted by Admin on 1/12/2012 12:45 PM | Comments (0)
Jim was asked following question in interview recently: Let suppose you have, following grid on Cartesian coordinate system ( Quadrant I). o - x - x - x - o | | | | | x - x - x - o - x | | | | | x - o - o - x - x where, o => person at intersection and x => no person at intersection class Point { int x; int y; boolean hasPerson; } Point findNearestPointWhereAllPeopleCanMeet(Point[] people) { } Implement a routine where given a list of people location (points), find a location(point) such that is closest point to all given point. How would you solve this problem ?

# 150 fresh questions

Posted by Admin on 1/26/2011 2:16 PM | Comments (0)

# Just single question

Tags: , , | Posted by Admin on 5/16/2010 11:19 PM | Comments (0)
Question Come out with an algorithm for getting the column number provided the column name in a excel sheet and vice versa. Excel has a naming convention of A,B..Z,AA,AB,AC..ZZ,AAA… This had to be converted to the column numbers. A will be 1 and AA will 27.. Also the algorithm to find the name provided column number.   Answer #include <string> #include <iostream> using namespace std; int ExcelColNum (char *name) {     int s = 0;     for (int i=strlen(name)-1, e=1; i>=0; –i, e*=26) {         s += e*(name[i]-’A'+1);     }     return s; } string ExcelColName (int num) {     string name;     for ( ; num; num/=26) {         name.insert (name.begin(), ‘A’+(num-1)%26);     }     return name; } int main(void) {     cout << "AAA ==> " << ExcelColNum ("AAA") << endl;     cout << "703 ==> " << ExcelColName (703) << endl;     return 0; }   Results are, AAA ==> 703 703 ==> AAA

# Google Interview Questions – Some Resolution

Tags: , , | Posted by Admin on 7/25/2009 10:43 PM | Comments (0)
All the below questions are to be done in O(n) time complexity. 1>Given an array of size n-1 whose entries are integers in the range [1, n], find an integer that is missing. Use only O(1) space and treat the input as read-only. 2>Given an array of size n-2 whose entries are integers in the range [1, n], find two integer that are missing. 3>There is an array A[N] of N integers. You have to compose an array B[N] such that Output[i] will be equal to the product of all the elements of A[] except A[i]. or Example: INPUT:[4, 3, 2, 1, 2] OUTPUT:[12, 16, 24, 48, 24] Solve it without division operator and in O(n). Solution : 1>Let the missing number be M. We know that the sum of first N natural numbers is N*(N+1)/2. Traverse through the array once and calculate the sum. This is the sum of first N natural numbers – M or S=N*(N+1)/2 – M. Therefore M = N*(N+1)/2 – S. 2>Similar approach to the first one. Traverse the array once and calculate its sum and multiplication. Let the sum be S and multiplication be M. Let the missing numbers be P and Q. From above we know that P+Q = N*(N+1)/2 – S. Also P*Q = N!/M. So we can get P and Q from these two equations. 3> Lets first see the C++ solution. void solution(vector<int> A) { int N=A.size(),i,j; vector<int> L(N,0); vector<int> R(N,0); vector<int> B(N,0); for (i=0,j=N-1; i=0 ;i++, j–) { L[i] = i==0? 1 : A[i-1] * L[i-1]; R[j] = j==N-1? 1 : R[j+1] * A[j+1]; } for (i=0; i { B[i] = L[i] * R[i]; printf(“%d “,B[i]); } } Most is clear from the program. Anyways, through the L and R we calculate the multiplication of terms to the left and right of i-th term. then finally we multiply it to get the result.

Tags: , , | Posted by Admin on 11/25/2008 9:24 AM | Comments (0)
Was removed by author's request. But you can still read original story of BadMagicNumber experience in google interview.

# Google Interview Question: Product of other Elements in an Array in O(n)

Tags: , | Posted by Admin on 11/3/2008 2:12 PM | Comments (8)
Last time I was interviewed for a software development engineer position, the recruiter asked me some of the classical Microsoft interview questions, such as “How Would You Move Mount Fuji?” or “How many gas station are there in your country?“. It was the first time for me to be asked such questions but having obtained the job I think my answers were good enough. After that day, I looked for other well-known interview questions and I discovered that Google has a totally different approach, focusing on algorithms, data structures and complexity. For instance, one of Google interview questions says: There is an array A[N] of N integers. You have to compose an array Output[N+1] such that Output[i] will be equal to the product of all the elements of A[] except A[i]. Example: INPUT:[4, 3, 2, 1, 2] OUTPUT:[12, 16, 24, 48, 24] Solve it without division operator and in O(n). Without the two constraints at the end of the puzzle it would have been straightforward, but now we have to be smart. Actually, the product of all elements of A[] except A[i] is equal to the product of all elements before A[i] and those after A[i]. We can traverse A[] twice, once from left to right and once in the opposite way and multiply all the elements we find before A[i]. We’ll pretend to have a new array called Output[] to store the output of the first pass, assigning Output[i] the product of all elements preceding A[i]: view plaincopy to clipboardprint? let rec firstpass product input =      match input with      | [] -> []      | x::xs -> product :: firstpass (product * x) xs  let rec firstpass product input = match input with | [] -> [] | x::xs -> product :: firstpass (product * x) xs For the second pass we need to move from right to left, but this can be done by reversing the input arrays and moving as usual: view plaincopy to clipboardprint? let secondpass product input arr =      let rev_input = List.rev input      let rev_arr = List.rev arr      let rec rev_secondpass product (input:list<int>) arr =        match arr with        | [] -> []        | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]        rev_secondpass product rev_input rev_arr  let secondpass product input arr = let rev_input = List.rev input let rev_arr = List.rev arr let rec rev_secondpass product (input:list<int>) arr = match arr with | [] -> [] | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)] rev_secondpass product rev_input rev_arr Both firstpass and secondpass expect an integer argument called product, which will be always be 1 at the beginning and will be used to store the intermediate products during the recursive calls. With these functions we can just define an input array and apply them to get the result. The following is the complete F# code: view plaincopy to clipboardprint? #light    let input = [ 4; 3; 2; 1; 2 ]    let answer values =       let rec firstpass product input =      match input with      | [] -> []      | x::xs -> product :: firstpass (product * x) xs      let secondpass product input arr =      let rev_input = List.rev input      let rev_arr = List.rev arr      let rec rev_secondpass product (input:list<int>) arr =        match arr with        | [] -> []        | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]        rev_secondpass product rev_input rev_arr      values |> firstpass 1 |> secondpass 1 values