# Mind boggling

Tags: , | Posted by Admin on 7/4/2012 9:16 AM | Comments (0)

# 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’.

# 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).

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

# Developer Interview: Part Four (plus just two questions)

Tags: , | Posted by Admin on 11/12/2008 2:20 PM | Comments (0)

# Similar questions with expect phone interview Google

Tags: , , | Posted by Admin on 10/30/2008 9:53 AM | Comments (0)

# Think you could get hired by Google?

Tags: , , | Posted by Admin on 9/11/2008 3:11 AM | Comments (0)

# A few questions with answers

Tags: , | Posted by Admin on 8/31/2008 1:33 PM | Comments (8)

# Solutions to Crazy Questions at Google Job Interview

Tags: | Posted by Admin on 8/31/2008 1:18 PM | Comments (0)

# Five Technical Interviews

Tags: , , | Posted by Admin on 8/31/2008 12:42 PM | Comments (0)

Tags: | Posted by Admin on 8/31/2008 9:01 AM | Comments (2)

Tags: | Posted by Admin on 8/31/2008 8:58 AM | Comments (0)

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

Tags: , | Posted by Admin on 6/10/2008 1:25 PM | Comments (0)
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]: 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: 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: 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  Original story