Re: [algogeeks] Google Interview Question: In how many intervals does a number exists

Read up on Interval trees . Programmers should realize their critical importance and responsibility in a world gone digital. They are in many ways similar to the priests and monks of Europe's Dark Ages; they are the only ones with the training and insigh

Re: [algogeeks] Google Interview Question: In how many intervals does a number exists

2->2 as 2 lies in [2,3] and [1,4] ? On Sun, Jun 9, 2013 at 12:50 PM, Monish Gupta wrote: > There are n Intervals. Given a set of m numbers, tell in how many > intervals does each number exists. > Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11} > For 2 -> 1 as 2 lies only in 1 in

[algogeeks] Google Interview Question: In how many intervals does a number exists

There are n Intervals. Given a set of m numbers, tell in how many intervals does each number exists. Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11} For 2 -> 1 as 2 lies only in 1 interval [2,3] For 4 -> 3 as 4 lies in 3 intervals For 11 -> 0 as 11 lies in none of the given 4 inte

[algogeeks] Google Facebook Pocket Gems Recruitment Drive

I was interested in knowing if anyone had the experience of going through any of the above mentioned companies interviews. What were the questions asked and the format ? --

[algogeeks] Google Interview question - Python

I got this question set in google interview, do any one have some knowledge how to do this, One way of imagining a lazy stream implementation in python is any class that implements the method: popNext() which returns the next element of the stream, if any, otherwise None. 1. Write the following c

Re: [algogeeks] google paper

1. Print the zig-zag traversal of a BST. 2. There is a language Googley. There are two global registers X and Y both of whom have the character 'A' stored in them. There are only two commands in the language. i) next ii) print next increments the character in the X register. After reaching 'Z', ag

Re: [algogeeks] google paper

Hi, Section A - objective type 10 technical questions in OS,Algorithms,DS,C. each carries one mark. no negative marks Section B - coding 2 questions first was very simple second - spiral level order traversal of a BST -- You received this message because you are subscribed to the Google Groups

Re: [algogeeks] google paper

one Q is zig zag traversal in a tree nd d other one is like - A new language is defined called "googley " and it has two register only 'X' and 'Y' and only two commands are avialable "next" and "print" each one has some specific function (i don't remember now) and now u are given a string and u h

Re: [algogeeks] google paper

Can you share the coding questions asked. Thank you. On Fri, Aug 10, 2012 at 10:29 PM, Abhishek Kumar wrote: > two coding Qs + some mcqs(more than 1 option correct),time is 1.5 hr.. > > > On Fri, Aug 10, 2012 at 4:06 PM, deepikaanand wrote: > >> Somebody from DCE plz tell the paper pattern of goo

Re: [algogeeks] google paper

two coding Qs + some mcqs(more than 1 option correct),time is 1.5 hr.. On Fri, Aug 10, 2012 at 4:06 PM, deepikaanand wrote: > Somebody from DCE plz tell the paper pattern of google... > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > T

[algogeeks] google paper

Somebody from DCE plz tell the paper pattern of google... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BjLRVjRlekIJ. To post to this group, send email to

Re: [algogeeks] [Google question]

seems like Hungarian algorithm will work . On Wed, Aug 1, 2012 at 12:18 PM, vikas rai wrote: > There is a set of 9 students and 3 schools Every school can be alloted > atmax 3 students .Every school and student has its coordinates .Now we have > to allot student in such a way that the sum of dis

[algogeeks] [Google question]

There is a set of 9 students and 3 schools Every school can be alloted atmax 3 students .Every school and student has its coordinates .Now we have to allot student in such a way that the sum of distance from all the student to the school should be minimum. We have to solve this in less than O(n^3)

Re: [algogeeks] Google : Print in interleaved fashion

http://www.geeksforgeeks.org/archives/17743 On Tue, Jul 10, 2012 at 11:16 PM, Navin Kumar wrote: > Given two strings .Print all the interleavings of the two strings. > Interleaving means that the if B comes after A .It should also come after > A in the interleaved string. > ex- > AB and CD > ABCD

[algogeeks] Google : Print in interleaved fashion

Given two strings .Print all the interleavings of the two strings. Interleaving means that the if B comes after A .It should also come after A in the interleaved string. ex- AB and CD ABCD ACBD ACDB CABD CADB CDAB -- You received this message because you are subscribed to the Google Groups "Alg

[algogeeks] [Google] Finds all the elements that appear more than n/3 times

Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use stan

[algogeeks] Google Developer Group, New Delhi - HACK 2012 - Code for a Cause !

Dear all, On behalf, of *Google Developer Group New Delhi *(formerly known as* GTUG New Delhi*) , I would like to inform you that we are going to host *H-A-C-K - "Code for a Cause", *a hackathon, on *16-17th June* at the *Indian Habitat Center, New Delhi*. *HACK- "Code for a Cause"* is being org

Re: [algogeeks] Google Q : all anagrams next to each other

@ashish : couldnt get u.. can u give an example?? On Tue, May 22, 2012 at 5:45 PM, Prem Krishna Chettri wrote: > What I Could possibly think of is > > For each string S1 that is an anagram of some string S, use Map and Store > the Key Value as (S1,S). Now there is a trick here abt how to reduce

Re: [algogeeks] Google Q: longest word made of subwords within the list

think in term of following input case :- best test testbest than i guess you will come to knw why i got confused at first place. *madammadam* *testtesttest * ignore this type of test case. On Wed, May 23, 2012 at 12:40 AM, Prem Krishna Chettri wrote: > Thank you to understanding Me.. > > Well

Re: [algogeeks] Google Q: longest word made of subwords within the list

Thank you to understanding Me.. Well For Trie.. I don't hv to say much more to say except the basic need which says "Collect Common Prefix" . If it didnt ring the bell.. than Hv a look at strings MADAM and MADAMIAMADAM stored in your TRIE .. Just draw a pictorial representation. On Wed, May 2

Re: [algogeeks] Google Q: longest word made of subwords within the list

yes ,longest word can be found while inserting each word it the TRIE. *By tracking Second and First Longest word found** -- *confused me ...what you were trying to say. tracking can be done but become little difficult if input is something like this :- best bestest test testbest testbesttest bt

Re: [algogeeks] Google Q: longest word made of subwords within the list

@krishna : tracking just second and first longest word would be enough?? what if input has word which is made by repeating small word again and again test tester testertest testing testingtester testtesttesttesttest // added word and by saying O(n) .. n= total number of alphabets in the file rit

Re: [algogeeks] Google Q : all anagrams next to each other

Anyways we need to sort all the words atleast once, one way is To travel throught the list sorting each word and making a pair of the orginal and the sorted word. For Ex. If one of the original word in list is "aanchal" sorted is "aaachln". So store the pair <"aanchal", "aaachln"> Now sort this l

Re: [algogeeks] Google Q: longest word made of subwords within the list

Yea this is a Straight Cut Trie Question No Doubt.. Perhaps DWAG may be taken into consideration.. T(O)=O(n) can be done easily.. ( By tracking Second and First Longest word found soFar and updating otherwise accordingly) Can someone do it better? On Tue, May 22, 2012 at 6:15 PM, Ashish Goel w

[algogeeks] Google Q: longest word made of subwords within the list

write a program to find the longest word made of other words. For instance, If my file has the following words (sorted): test tester testertest testing testingtester The longest word should be testingtester. Trie is the solution, what is the best Order possible? Best Regards Ashish Goel "Think pos

Re: [algogeeks] Google Q : all anagrams next to each other

What I Could possibly think of is For each string S1 that is an anagram of some string S, use Map and Store the Key Value as (S1,S). Now there is a trick here abt how to reduce Time Complexity here... Now its easy to put all string which has correspondence S next to each other. This is Simple o

[algogeeks] Google Q : all anagrams next to each other

Write a method to sort an array of strings so that all the anagrams are next to each other. What i could think of is preparing a multi linked list( multimap) whereby the key for each string is the sorted representation of the string(eg if string is gac, its sorted representation is acg). Walk of a

Re: [algogeeks] google

Hi, Regd OS, 1.deadlock 2.diff between linux, windows and solaris in terms of internals design 3.diff between mutex and semaphore 4.spin lock 5.interrupts 6.steps in page fault handling 6.steps involved in booting an os 7.what is kernel 8.paging & segmentation 9.process scheduling algorithms 10.

Re: [algogeeks] google

sorry dude it came to ITBHU with tag of marketing so i could not be helpful to u in this case. On 4/1/12, Deepak Garg wrote: > hey guys! > > google is coming to our college, their main requirements is from > operating systems and computer networks. > > can some one post the sample questions for

[algogeeks] google

hey guys! google is coming to our college, their main requirements is from operating systems and computer networks. can some one post the sample questions for it.. thanks Deepak -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to th

Re: [algogeeks] Google Question Invoice -bills

the DP is not clear, can you give example on how this DP would work for n invoices and k bills? Why is F(0,k) = 1? Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Mon, Mar 26, 2012 at 2:16 PM, atul anand wrote: > it is similar to sum-subset pro

Re: [algogeeks] Google Question Invoice -bills

: * algogeeks@googlegroups.com > *Subject: *Re: [algogeeks] Google Question Invoice -bills > > @umer : dp approach is given in above post. > > On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq wrote: > >> Well, they have specified in the question that "you are dealing wit

Re: [algogeeks] Google Question Invoice -bills

You can use dp to find subsets . But how is dp used for the overall probkem Sent from BlackBerry® on Airtel -Original Message- From: atul anand Sender: algogeeks@googlegroups.com Date: Mon, 26 Mar 2012 16:52:08 To: Reply-To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Google

Re: [algogeeks] Google Question Invoice -bills

@umer : dp approach is given in above post. On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq wrote: > Well, they have specified in the question that "you are dealing with > big-data sets". So, recursion won't be a good option I guess. > > Can we solve it with dynamic programming technique? > > > On

Re: [algogeeks] Google Question Invoice -bills

Well, they have specified in the question that "you are dealing with big-data sets". So, recursion won't be a good option I guess. Can we solve it with dynamic programming technique? On Mon, Mar 26, 2012 at 2:24 PM, atul anand wrote: > one way to do it , is say first combination for invoice 80=

Re: [algogeeks] Google Question Invoice -bills

one way to do it , is say first combination for invoice 80= 50 + 30 now remove 80 and 30 from the input bills while finding combination from 210 , check if it is possible if yes , we got one solution not select another invoice combination 80= 50 + 10 + 20 now dont consider these values while find c

Re: [algogeeks] Google Question Invoice -bills

Ok now you have combination of each invoice . What is the approach to take mutual exclusive combinations for so that sum of all bills equals sum of all invoices On Mon, Mar 26, 2012 at 2:16 PM, atul anand wrote: > it is similar to sum-subset problem following recurrance will solve this > problem

Re: [algogeeks] Google Question Invoice -bills

it is similar to sum-subset problem following recurrance will solve this problem , you need to run algo for each invoice to find all combination F(n,k) = F(n,k-1) or F(n - a[k], k-1) base case :F(0,k)=1 for k>=0 F(n,0)= 0 for n>0. On Mon, Mar 26, 2012 at 1:34 PM, Ankush Ba

[algogeeks] Google Question Invoice -bills

There are 210 Invoices and 1700 bills – these bills add up to these invoices The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices. For Example : there were 2 invoices for 80, 210 and you have bills

Re: [algogeeks] Google written test

@Gene : your code will work fine by changing the argument passed from main(), you just need to call rite f(n, 1, 1); from main instead of f(n, 1, 0); On Mon, Mar 19, 2012 at 10:10 AM, atul anand wrote: > @all : i guess question is on Fibonacci coding. > > here you can find the algo :- > > http

Re: [algogeeks] Google written test

@all : i guess question is on Fibonacci coding. here you can find the algo :- http://en.wikipedia.org/wiki/Fibonacci_coding On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh wrote: > @Ravi... there should be only one answer as for fibonacci representation > of a number we have to include the part

Re: [algogeeks] Google written test

@Ravi... there should be only one answer as for fibonacci representation of a number we have to include the part of the fibonacci number just less than the number then remaining part of the sum is filled by fibonacci numbers starting from 1 suppose we have to convert 6 into fibonacci representati

Re: [algogeeks] Google written test

@ if for a given number more than 1 answer exist then whats the answer??? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeek

Re: [algogeeks] Google written test

20 multiple choice questions out of which around 10 were from the GATE '12 paper. 1 coding question: Represent a no in its Fibonacci representation. Ex- 15 can be represented as 100010 (1*13+0*8+0*5+0*3+1*2+0*1) On Sat, Mar 17, 2012 at 6:39 PM, Ronit Douglas wrote: > Hello! > > I got to know th

[algogeeks] Google written test

Hello! I got to know that Google visited several colleges in last week. They will be visiting my campus on 20th. Please let us know pattern & questions if you know. Thanks, - RD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to thi

[algogeeks] Google written

Hello All! Google is going to visit my campus soon. Hence, I want to know - - Format of the test - Qs - in case you remember - Coding question in the apti Please reply if you have information about this. Thanks :) -- You received this message because you are subscribed to the Google

Re: [algogeeks] google question

i guess this would work... n=number of nodes h=height; pour=quantity poured; capacity = capacity of each cup n=pow(2,h+1) -1; call(capacity,pour,0,n) node* fillCup(float capacity,float pour,int left,int right) { node *root; int mid; if(left > right) return NULL; root=(node *)malloc(sizeof(node))

[algogeeks] google question

|_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| Each cup has capacity C and once a cup gets full, it drops half extra amount to left child and half extra amount to right child for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C) will be divided equally to left an

Re: [algogeeks] Google-Puzzle

max subsum problem Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Sat, Feb 25, 2012 at 1:03 PM, karthikeya s wrote: > You have a circular track containing fuel pits at irregular intervals. > The total amount of fuel available from all the pits t

[algogeeks] Google-Puzzle

You have a circular track containing fuel pits at irregular intervals. The total amount of fuel available from all the pits together is just sufficient to travel round the track and finish where you started. Given the the circuit perimeter, list of each fuel pit location and the amount of fuel they

Re: [algogeeks] Google Question--Suggest Algo

Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg wrote: > You have an array with *n* elements. The elements are either 0 or 1. You > want to *split the a

[algogeeks] Google Question--Suggest Algo

You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k << n. After you split the array into k subarrays. One element of each subarray

[algogeeks] Google interview question

Hi Guys I saw this question http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm But couldn't get the solution which has been accepted, nor could work out one on my own. Please help! -- Nitin Garg "Personality can open doors, but only Character can keep t

Re: [algogeeks] Google Question--Suggest Algo

Can u provide a pseudo code for the same and c if it works On Thu, Nov 17, 2011 at 2:37 AM, sravanreddy001 wrote: > Start with counting sort of the input. > Use shuffling algorithm on it. > > Store index as cumulative sums of counts. > > -- > You received this message because you are subscribed

[algogeeks] Google Question--Suggest Algo

Start with counting sort of the input. Use shuffling algorithm on it. Store index as cumulative sums of counts. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogee

[algogeeks] Google Question--Suggest Algo

Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other. Input: { a, b, b }, distance = 2 Output: { b, a, b } How to approach this question ? -- You received this message because you are subscribed to the Google Groups "Algorit

Re: [algogeeks] Google Interview Question

lol!!! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit thi

Re: [algogeeks] Google Interview Question

FFS. here you go: http://lmgtfy.com/?q=google+careers On Sat, Oct 1, 2011 at 2:09 PM, Deepak Garg wrote: > hey can pls share the link. > > thnks > > > On Sat, Oct 1, 2011 at 2:04 PM, Rathish Kannan wrote: > >> apply through google careers site... >> >> -- RK :) >> >> >> >> On Sat, Oct 1, 20

Re: [algogeeks] Google Interview Question

hey can pls share the link. thnks On Sat, Oct 1, 2011 at 2:04 PM, Rathish Kannan wrote: > apply through google careers site... > > -- RK :) > > > > On Sat, Oct 1, 2011 at 2:02 PM, Deepak Garg wrote: > >> hey,,,what is the process of attending google offcampus process. >> >> kindly let us kn

Re: [algogeeks] Google Interview Question

apply through google careers site... -- RK :) On Sat, Oct 1, 2011 at 2:02 PM, Deepak Garg wrote: > hey,,,what is the process of attending google offcampus process. > > kindly let us know.. > > > On Sat, Oct 1, 2011 at 1:52 PM, Rathish Kannan wrote: > >> off campus. >> >> -- RK :) >> >> >> >>

Re: [algogeeks] Google Interview Question

hey,,,what is the process of attending google offcampus process. kindly let us know.. On Sat, Oct 1, 2011 at 1:52 PM, Rathish Kannan wrote: > off campus. > > -- RK :) > > > > On Sat, Oct 1, 2011 at 11:59 AM, arvind kumar wrote: > >> Hi >> Are u attending off-campus or on-campus interview? >> >>

Re: [algogeeks] Google Interview Question

off campus. -- RK :) On Sat, Oct 1, 2011 at 11:59 AM, arvind kumar wrote: > Hi > Are u attending off-campus or on-campus interview? > > On 10/1/11, R@TH!$H wrote: > > Hi, > > > > I am attending Google interview on Monday. Please help me with sample > > questions. > > > > Thanks & Regards, >

Re: [algogeeks] Google Interview Question

Hi Are u attending off-campus or on-campus interview? On 10/1/11, R@TH!$H wrote: > Hi, > > I am attending Google interview on Monday. Please help me with sample > questions. > > Thanks & Regards, > Rathish Kannan > > -- > You received this message because you are subscribed to the Google Groups >

[algogeeks] Google Interview Question

Hi, I am attending Google interview on Monday. Please help me with sample questions. Thanks & Regards, Rathish Kannan -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubs

Re: [algogeeks] google os ques on pipelining

bharatkumar bagan...can u plz explain why u multipiled (160+5) with 999 ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeek

Re: [algogeeks] google os ques on pipelining

for the first instruction : 150+5+120+5+160+5+140=585 ns for the rest of the instructions , though pipeline max(150,120,160,140)=160 (160+5)*999=164835 ns we assume that there will be no extra stalls existed in our system -585 + 164835 =165420 ns =165.4 us... correct me if I'm wrong .

[algogeeks] google os ques on pipelining

A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns (nano seconds) respectively. Registers that are used between the stages have a delay of 5 ns each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will approximately be a. 120 us (m

[algogeeks] Google Intern

Hi all CAn any1 temme d process followed by GOOGLE for internship-off-campus and on-campus(both)? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group,

[algogeeks] google maps

How do you implement google maps ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For mor

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

@Abhishek:nice algo dude.. On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav wrote: > Hey i tried it now and got to another solution > O(log n) solution: > 1. try searching for the number , if found,return the node, otherwise, you > will ultimately reach a leaf node say 'nd' > 2. Now the two can

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

1. I think if the given tree is BST then this problem cannot be solved in o(log n), It can be solved in o(n) Reason: If the given BST is skewed with numbers inserted in either ascending/descending order. Now the given number to be searched is the the one which is the leaf node of a BST, then there

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

@atul yes sure why not... On Sat, Aug 20, 2011 at 1:39 PM, Naman Mahor wrote: > i think there will be three candidate.. > 1. TreeSuccessor(nd) 2. TreePredecessor(nd) 3. nd it self. > > > On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav < > algowithabhis...@gmail.com> wrote: > >> Hey i tried

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

i think there will be three candidate.. 1. TreeSuccessor(nd) 2. TreePredecessor(nd) 3. nd it self. On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav wrote: > Hey i tried it now and got to another solution > O(log n) solution: > 1. try searching for the number , if found,return the node, oth

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

can any 1 suggest an algo without global vars pls On Sat, Aug 20, 2011 at 1:29 PM, Abhishek Yadav wrote: > yes you are right thanks for correcting me, there would be 3 canditates. > > > On Sat, Aug 20, 2011 at 1:28 PM, Kunal Patil wrote: > >> @Abhishek: >> Its not always that you reach a leaf t

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

yes you are right thanks for correcting me, there would be 3 canditates. On Sat, Aug 20, 2011 at 1:28 PM, Kunal Patil wrote: > @Abhishek: > Its not always that you reach a leaf through the node. > But still your logic seems correct. > There would be 3 candidates for minimum: > -->predecessor > -

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

@Abhishek: Its not always that you reach a leaf through the node. But still your logic seems correct. There would be 3 candidates for minimum: -->predecessor -->current node -->successor. On Sat, Aug 20, 2011 at 1:13 PM, Abhishek Yadav wrote: > No your solution is correct tooits just that in

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

No your solution is correct tooits just that in your solution number of comparisons done with the original number are more, while in my solution they get down to 2. otherwise complexities of both the solution would be O(log n). I am stressing on no. of comparisons because in these kind of quest

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

is there anything wrong in my algo? do tell me. On 20 August 2011 12:56, Abhishek Yadav wrote: > Hey i tried it now and got to another solution > O(log n) solution: > 1. try searching for the number , if found,return the node, otherwise, you > will ultimately reach a leaf node say 'nd' > 2. Now

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

Hey i tried it now and got to another solution O(log n) solution: 1. try searching for the number , if found,return the node, otherwise, you will ultimately reach a leaf node say 'nd' 2. Now the two candidates for the answer would be 1. TreeSuccessor(nd) 2. TreePredecessor(nd) Now

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

why traverse the whole tree? at each root keep the difference in a min_diff and min_ele. if the entered value is less root then move to left or right. repeat above two until whole tree is checked or min_diff becomes 0. pseudo code: min_diff = INF; // global variables min_ele = 0; find_min_diff(

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

yes, the interviewer said that there is a solution in O(log n) On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan wrote: > ur traversing the tree once so it shud be o(n).does the question demand > 0(logn) ? > > On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav < > algowithabhis...@gmail.com> wrote: >

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

ur traversing the tree once so it shud be o(n).does the question demand 0(logn) ? On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav wrote: > what would be the complexity of your solution O(n) or O(log n)..? > > On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan wrote: > >> traverse bst inorder and e

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

what would be the complexity of your solution O(n) or O(log n)..? On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan wrote: > traverse bst inorder and each time u encounter a node find the difference > between the element and given element in question . if the absolute > difference is minimum after

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

traverse bst inorder and each time u encounter a node find the difference between the element and given element in question . if the absolute difference is minimum after traversing the tree that is the element . u can getback the element using another element which keeps sign of the element so that

[algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

Given a BST and a number, Find the closest node to that number in the BST. Give an algorithm for that. Let there be binary search tree having nodes with values 12,34,64,23,64,25,76,6 and the number given is 28, then the answer would be 25 as it is the closest node. -- You received this message be

Re: [algogeeks] Google Telephonic interview

@Anand Shastri, if tasks enter randomly in runtime, structure needs to add a member start_time, which will be different from reference_time (till now u been considering it as same start time of every task). finally GOOD work!! surender On Fri, Aug 5, 2011 at 9:42 AM, Gaurav Menghani wrote: > The

Re: [algogeeks] Google Telephonic interview

Then that has to be mentioned in the question. Premature optimization is the root of all evil, in the words of Don Knuth. On Fri, Aug 5, 2011 at 9:38 AM, Anand Shastri wrote: > what if new task gets added every time. > > On Thu, Aug 4, 2011 at 8:24 PM, Gaurav Menghani > wrote: >> >> Instead of a

Re: [algogeeks] Google Telephonic interview

what if new task gets added every time. On Thu, Aug 4, 2011 at 8:24 PM, Gaurav Menghani wrote: > Instead of a heap, sort the array once. Pick the first element every > time, and remove it from the array, or just move the 'head pointer' > ahead. > > On Fri, Aug 5, 2011 at 8:01 AM, Anand Shastri >

Re: [algogeeks] Google Telephonic interview

Instead of a heap, sort the array once. Pick the first element every time, and remove it from the array, or just move the 'head pointer' ahead. On Fri, Aug 5, 2011 at 8:01 AM, Anand Shastri wrote: > /* Create a Timer Task that takes in the running time and it's associated >    function to be call

Re: [algogeeks] Google Telephonic interview

/* Create a Timer Task that takes in the running time and it's associated function to be called after its running time is elapsed */ #include #define NUM 5 typedef void (*funcToBeCalled)(void); typedef struct timer TIMER; struct timer { int runningTime; funcToBeCalled func; }; static TIM

Re: [algogeeks] Google Telephonic interview

Obviously you need to run the task that a closet running time. For Example Task 1 : running time = 2 secs Task 2: running time = 4 secs This means I want to run the task 1 after 2 secs and task 2 after 4 second. How I hope the question is clear to you know On Thu, Aug 4, 2011 at 11:37 AM, moh

Re: [algogeeks] Google Telephonic interview

there is nothing like "search min or max time and then call function" given . It can be the case: "call the functions in order of nodes or times saved in objects". M i wrong? On Thu, Aug 4, 2011 at 11:56 PM, Anand Shastri wrote: > You mean to say linked to maintain all time task with its correspo

Re: [algogeeks] Google Telephonic interview

You mean to say linked to maintain all time task with its corresponding running time and associate function. In that case how will find the task which has the closed running time. If you use min heap it would be easy to find the task that has closest runing time in O(1) complexity. On Thu, Aug 4,

Re: [algogeeks] Google Telephonic interview

why are u maintaining heap? can't we use link list here? On Thu, Aug 4, 2011 at 11:16 PM, Anand Shastri wrote: > *You have given a structure which has two member, One which stores the > time and other stores the function pointer Your function has to call the * > *function stored in the fuction po

[algogeeks] Google Telephonic interview

*You have given a structure which has two member, One which stores the time and other stores the function pointer Your function has to call the * *function stored in the fuction poitner after the time given in the structure elapses. Design that function? * Approach: To design this function I would

[algogeeks] Google Interview preparation

I have my google interview at the end of this month. can any body provide me some tips/suggestions/questions ? I am sure some of you guys here must have appeared in google interviews before, your help will be very valuable and much appreciated. Thanks -- You received this message because you ar

Re: [algogeeks] Google Interview Question

Your code does not works proper;y for all cases On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan wrote: > Here is the recursive algo: > > Rearrange(A,p,q) > 1. if p is not equal to q do the following > 2. r ← (p+q)/2 > 3. Exchange A[(p+r)/2..r] ←→ A[(p+q)/2 +1 ..(r+q)/2]. > 4. Rearrange(A,p,r) > 5.

Re: [algogeeks] Google Interview Question

Here is the recursive algo: Rearrange(A,p,q) 1. if p is not equal to q do the following 2. r ← (p+q)/2 3. Exchange A[(p+r)/2..r] ←→ A[(p+q)/2 +1 ..(r+q)/2]. 4. Rearrange(A,p,r) 5. Rearrange(A,r+1,q) 6. return On Mon, Aug 1, 2011 at 1:45 PM, Abhishek Gupta wrote: > A is an array of size 2n such

Re: [algogeeks] Google Interview Question

It is a bit tricky without using external memory .It is like insertion sort. correct me if i am wrong. for(i=n;i<2*n;i++) { x=a[i]; for(j=i-1;;j--) { if(j==0 || a[j-1]=='c') // 'c' indicates some character you can check its ascii value break; a[j+1]=a[j];

Re: [algogeeks] Google Interview Question

It is a bit tricky without using external memory correct me if i am wrong. for(i=n;i<2*n;i++) { On 1 August 2011 02:42, shady wrote: > when was this question asked in Google ? approximate date ? position ? > > > On Mon, Aug 1, 2011 at 1:45 PM, Abhishek Gupta wrote: > >> A is an array of size 2

  1   2   3   4   >