Amr Ebaid

All The interviews we talk about here are considered a special case. They were made by specific interviewers, from a specific team, to specific applicants, for a specific job, on specific projects. They cannot be considered by no means a generalization of Google Interviews and cannot be taken as a rule or a standardization whatsoever.

Let me begin by saying that this was actually the most interesting and exciting interview I have been through... I really enjoyed it a lot, and was delighted by the challenging remarkable questions...

It was my last one for the internship, or that's what I though at least, and as much as I had been worried before it, I was really excited and thrilled through it...

Enough of the chitchat... Let the fun begin...

You have a list of n integers. It is required to find if there exist two elements that sum to K.

Well... As I always suggest, think loud and do not wait until you get the optimal... So, I immediately suggested a simple search over the whole list for each integer... That leads to an O(n^2) solution... It is slow, still a right solution...
Directly after that, it bumped into my head... Sort the list, then you can use Binary Search... That makes it better... an O(n log n) solution is absolutely better...
However, we can still do better... If there's only one thing I learned from those interviews, what would it be??? Hashing, Hashing, then Hashing. After that, Hashing. Finally, Hashing.
So, the optimal solution (or that's what I think) would be

Notice that it was one iteration over the list inserting and searching... an optimal O(n) solution...
Of course, it needed some improvements like the HashSet parameterization... but that was what I wrote on the go...

--------------------------------------------------------
How many trailing zeros exist in n!?

Well... I have always loved math... So, I adored that one... really...
The whole idea comes from the fact that trailing zeros come from a 5*2 multiplication or more specifically from any 5 or one of its multiples, as each of them is preceded by a 2, an even number to be exact, leading to a trailing zero at the result...

For example:
8! = 8*7*6*5*4*3*2*1 will contain one trailing zero coming from the 5 multiplied by 2...

So, Here it is... Count the fives... Divide n by 5, and that's it...
That's what you think...
Numbers after 25 violate that... as 25 is already a 5*5... that adds one extra zero...
So count the number of 25's too...
So, does 125, 625, and the list goes on...

To summarize, that was it

and I have been too picky not to use the power method... :))

--------------------------------------------------------
How to choose a random sample of size 10 from a list of n integers? What if the list length is unknown?

The first part was actually just a warm up... and it is obvious you will have a random number generator that generates numbers from 1 to n... using it 10 times, you get the sample...

Then, came the real fun... Sampling a stream of data that you have no idea about its length... The interviewer referred to the real application of this problem, that was sampling Google Search Queries...

Of course, I am not implying or referring whatsoever, that this is the real deal behind that really... It is just an example... No more...

Of course, I began to think loudly, and as I didn't get the right answer directly, I began to tell my interviewer what answers I know are wrong... So, I began to eliminate all ideas that are about sampling for each time interval, or sampling for each n-th item in the stream... and so on... as these are all not random samples...

He then gave me a hint... Again, Take care of hints... What would you do if the list size was 10... It would be all the required sample, I said... What if it was 11???

Later I knew this is called "Reservoir Sampling"... So, The whole idea comes that you take the first 10 elements as your sample... Whenever an element comes later... You choose whether to throw it away or replace one of the existing elements with it...

I suggested that, at element i, use a random number generator from 1 to i...
if it is from 11 to i... throw it away...
Otherwise, replace the element at the position the generator gave with that last element...

Of course, this is my own implementation.. Maybe, there are better ones, but I didn't look around...

Then, I surprised him, saying that my solution that way was wrong... from my belief that, If you are wrong, admit it... It is better that you say it, rather than (s)he finds it and doesn't tell you...

I argued that
element number 11 had a chance of 10/11 to get in, and 1/11 to get out..
element number 1000000 had a chance of 10/1000000 to get in and 999990/1000000 to get out...
I thought it is not fair...

He liked that I argue my own solution... Then he corrected my thought that
element number 11 had a great chance to get in, and a great one to get out...
element 1000000 had a small chance to get in, and a small one to get out...
At any time, if you calculate the probability of each item so far to be in the list, it would be equal-probable...

Probability and Statistics Gurus are so welcome to throw some words here...

Again, as I always advise my students, Probability and Statistics are vital for CS students... Do not underestimate them... That was just an example, you cannot imagine how important you will find them later in your career...

That was my last one... but not the last in this series... We still have a lot to go...

Hope you enjoyed that one as much as I did...

See you in the next one, fellas...

Sunday, January 10, 2010

Google Interviews - 3

Google Interviews - 1

Google Interviews - 2

Well... Long time no see, but the point is that this series requires a special mood, and I haven't had it long ago...

Anyway, here we go again with the third interview in our series...

The first half of the interview was a bit theoretical... and was a general conversation about these points
1- My Graduation Project (An open-source debugger for Ruby as a dynamic programming language) and how we separated between the debugger core and its different UIs (command-line interface, Eclipse plug-in, MS Visual Studio plug in)
2- How to modify it for C++ as a static language
3- Since I was applying for a position of a Software Engineer Intern for Arabic Applications (Although, later I joined the AdSpam team, not the Arabic team), how developing Arabic applications or for Arabic users can be different
4- What I had in mind for a project for my internship

The second half discussed the problem of finding the median of a list in two situations:

Finding the median in an ordinary list: I suggested sorting the list and getting the element in the middle. Of course, this is not optimal, as you can improve that to O(n) by using a median-of-medians-like technique with k-sorting or partitioning like in Quick Sort. However, the interviewer didn't stay long at this point as he was more interested in the next situation

The other situation was in case the list is too large to be stored in one machine, so it is divided to multiple lists on m machines... so, I suggested sorting each list on its machine and traversing the lists simultaneously as in Merge Sort to get the element that should be in the middle... I don't know till now whether this is the optimal or not, but that's what I could come up with at that time... and since I got accepted for the internship, I assumed it was correct...

That would be the third interview... Hope you liked it...

Wednesday, December 23, 2009

Google Interviews - 2

Google Interviews -1

Well... here we go with our second post in this interesting, I hope, series...

and again I must declare...

All The interviews we talk about here are considered a special case. They were made by specific interviewers, from a specific team, to specific applicants, for a specific job, on specific projects. They cannot be considered by no means a generalization of Google Interviews and cannot be taken as a rule or a standardization whatsoever.

Fortunately, I also still have all the questions of this interview in my mind... Honestly, I have written them expecting this day...

Write a simple code to reverse a string.

The first question was just a warm up to break the ice...
I wrote it like that... The whole idea was to traverse only the half of the string, and to state that it won't differ in case of odd length strings due to integer division
We have n points on a 2D space, and we need to find the largest number of points on a single straight line.

At the beginning, I came with the straight-forward O(n3) solution... to construct a line with each pair of nodes, and iterate over all nodes calculating how many lie on this line...

Then ordinary improvements were added for some optimization...i.e.
i = 1 .. n
j = i .. n
Still O(n3)

After that, I headed towards Dynamic-Programming trend, and thought of Memoization... to store already found points on a single line and avoid recalculations... Still O(n3) in the worst case...

At last, after a hint from my interviewer that for any two nodes on a single line the equation y=ax+b is constant no matter what the nodes are - Of course, it was not stated in this clear way, I knew the optimal solution will be Hashing leading to O(n2) optimal solution...
for each pair of nodes
add or increment the (a,b) pair
representing equation constants
at the end, the maximum encountered pair, which can be monitored during iterating nodes to save another extra iteration, can give us the required maximum number of nodes on a single line...

This was the question of the interview, and took almost the whole 30-40 minutes...

P.S. This question was encountered by many applicants to Google Internships as far as I heard and found... It's kinda popular...

This makes me wanna add two pieces of advice of my own... that I found extremely useful...

Think loudly and don't wait until you get the optimal solution... speak what you think directly no matter how primitive it can be. They care more about the way you think...
Respond to hints... It is a very positive point in your favor... Eventually, it is not required that you get the perfect solution to problems you face during work directly, but it is crucial that you can find it after thinking and researching...

This was it for this time... Hope you like and enjoy it...

See you all soon with the next interview...

Tuesday, December 15, 2009

حتى يغيروا ما بأنفسهم

مش عارف أنا ليه بأكتب الكلام ده... مع إنه غالبا مش حيقدم و لا يأخر... و مش حيوصل لناس كتير... بس أهه عالأقل أفرغ اللى فى نفسى بدل ما أطق و أتفرس

كلنا دايرين ليل نهار نشتم فى أم الحكومة و المسئولين... ربنا يجعل كلامنا خفيف عليهم... و على رأى من لا يؤخذ برأيه... اللى لا هو عادل و لا هو إمام... "إنما إحنا... إحنا .. إحنا ولاد كلب...إحنا بنضايق الزعماء وبنعكنن عليهم هما فاضينلنا الناس دى"ـ

يقول الله عز و جل

"إِنَّ اللَّهَ لا يُغَيِّرُ مَا بِقَوْمٍ حَتَّى يُغَيِّرُوا مَا بِأَنْفُسِهِمْ"

و رُوى أن سيدنا على بن أبى طالب - كرم الله وجهه - قال حين تولى خلافة المسلمين: "كنا نحن فكان فينا أبو بكر و عمر... و كنتم أنتم فكنت أنا فيكم"ـ

فعلى كده احنا نبوس إيدنا وش و ضهر... إن... بسم الله الرحمن الرحيم... بسم الله الرحمن الرحيم... فخامة الزعيم المبجل المفدى.. هو زعيمنا... احنا باللى بنعمله ما نستاهلش حتى ان احنا يكون لينا حكام زى دول... ده بس من رحمة ربنا و رأفته و عفوه إن الوضع كده مش أسوأ... مش قلتلكم ... احنا ولاد كلب... نستاهل ضرب البلغ

و أنا من موقعى هذا أشكر السادة المسئولين و أحييهم و أشكرهم إنهم بيعاملونا بما يملى عليهم ضميرهم مش بما نستحق ... لأن لو بما نستحق... كان مفروض نص الشعب يعدم فى ميدان عام رجما بالصرم

أنا فعلا بأتكلم جد ... و جد الجد كمان... المفروض إن احنا الأول نتغير عشان نستاهل يكون فينا ناس كويسة تحكمنا و ترتقى بينا... و أنا مش حأتكلم كلام كبير عن العمل و احترام الوقت و الالتزام و الأخلاق و المعاملات و احترام الآخر عشان أنا فقدت الأمل فى الحاجات دى.. عالأقل فى وقتنا الحاضر

أنا هنا حأتكلم عن مواقف بسيطة بأشوفها فى الشارع كل يوم... حاجات تافهة و صغيرة بس بتنرفزنى و بتطلع زرابينى... حاجات نقدر بكل سهولة نغيرها... و مش حأقول إن خلاص لو الحاجات دى اتغيرت الحياة حتبقى بمبى و المشاكل حتخلص و الشباب يلاقى شغل و يتجوز و المرتبات تعلى و الناس تبقى محترمة و المواصلات تفضى و الشوارع تنضف و كله يبقى فل الفل

لكن عالأقل أنا حأبقى مبسوط شوية ... و فى النهاية... ده البلوج بتاعى و أنا حر أكتب اللى أنا عايزه فيه... أمال أبعبر عن نفسى فييين؟؟؟

و مبدأيا ... أنا آسف على أى قباحة تصدر منى هنا... بس العالم دى طلعتنى عن شعورى

الحاجات دى ترتيبها لا يعنى أى شئ من حيث الأهمية أو الأولوية... ده بس حسب ما افتكرت أو قابلت فى الشوارع

ـ1ـ الأستاذ ـالمحترم ابن المحترم ـ اللى عربيته بتتخبط فى الشارع يقف زى ما ربنا شاء و الخبطة حصلت فى نص الشارع و ينزل يتناقش هو و المحترم التانى عشان يشوفوا مين ابن التيييييييييييت الغلطان فيهم... الدنيا ما وقفتش يابا عشان عربيتك اتخبطت و الناس التانية وراها مصالح و أشغال .. و فيه طلبة عندها امتحانات.. و ناس عيانة محتاجة توصل بسرعة للمستشفى.. وناس وراها سفر.. و بلاوى متلتلة... و مش حيحصل أى حاجة لو ركنتوا على جنب انتو الاتنين - و أى حد تانى عايز يتفرج أو يشعللها قبل ما يسلك - و طلعوا ..... .. بعض على راحتكم... الشارع مش شارع أبوك يا محترم انت و هو

ـ2ـ الأم الظريفة النضيفة اللى بتبقى مع ابنها فى الشارع أو العربية و الهوليجان الصغير بيشرب عصير و لا بيبربر فى منديل و عايز يرمى الزبالة... تقوم بكل جرأة و صفاقة و قلة حيا... تقوله افتح الشباك و ارميها... النظافة من الإيمان يا مدام... و مش حأقدر أقوللك اللى فى نفسى عشان بس بأخاف ربنا

ـ3ـ الراجل المحترم الكبارة اللى بيعدى هو و المدام عالكورنيش فوق النفق... و الله لولا إنى مش فاضى... و لولا خايف يجيلى مرض نفسى أو عقدة ذنب... كنت خبطك انت و هى و كل اللى معاك... و لو فلتت أو خبطك و ما متش ألفلك و أخبطك تانى.. ما النفق تحتك يا بنى آدم ... و حأمشيها بنى آدم.. و لا هو انتحار و السلام

ـ4ـ سواقين الميكروباصات و التاكسيات ـ أطال الله فى أعماركم ـ أرجوكم... معلش استحملوا الغلابة اللى زيى اللى ما لهمش فى السواقة و تعالوا على نفسكم و ما تحاولوش تسرعوا أما أدى إشارة إنى داخل يمين.. معلش ... أصلى حمار و ما ليش فيها... و ما بأعرفش أدخل الشارع اليمين من الحارة الرابعة فى نص الشارع زى المحترفين أمثالكم

ـ5ـ النقطة دى ما لهاش أى علاقة بالموضوع و مش حتحل أى مشاكل و لا حتخلى أى حاجة أحسن ... بس حتريحنى أنا والسلام

البنات المحترمات المبجلات .. و المرة دى فعلا مش تأريأة .. اللى كاتبين عالفيسبوك

Interested in women

أرجوكم ... بلدنا بتتفهم غلط... لو عملوا إحصائية حيفتكروا إن نص مصر و لا مؤاخذة

الحاجات كتير و لا تعد و لا تحصى ... و كل ما أفتكر أو أقابل تصرف جديد أو بنى آدم جديد من المحترمين اللى مش بيخلصوا دول حأقول... يمكن يتغير و لو تصرف واحد من التصرفات دى و أهه أبقى شفت حاجة حلوة قبل ما أموت

و ما زال للحديث بقية... ما دام فى العمر بقية... و فى الشعب ابن التيييييييييييييت ده بقية

Thursday, December 10, 2009

Google Interviews - 1

Well... Here we go with another series... As you may know, I had an internship at Google, Mountain View, last summer... Although I applied for the position of a Software Engineer Intern with the Arabic Team, I eventually joined the AdSpam team, the team that detect and fight spam in the ads framework... It was quite a rich interesting experience and some of the best and most amazing days I had in my life...

Here, we go with the interviews I and some other applicants had after applying for that position, to show what can be expected in Google interviews for Software Engineers...

it is a bit late to post this now, as I had already finished the internship more than two months ago... but I had some stuff to do... and didn't have the mood for it...

Well... Back at MV, I asked about whether this is allowed or not, and I have to declare the following:
All The interviews we talk about here are considered a special case. They were made by specific interviewers, from a specific team, to specific applicants, for a specific job, on specific projects. They cannot be considered by no means a generalization of Google Interviews and cannot be taken as a rule or a standardization whatsoever.

However, they can give you a meaningful hint on what you expect to find in a Google interview...

I have to state that all answers provided here are the interviewee's answers, which can be optimal, correct but not optimal, or in some cases wrong... Sometime, I may even state no answers if I don't have any... However, I tried as much as I could to gather the correct answers...

Enough with the chitchat, let's start with the first interview we have in this series...

====================================

I remember all the questions of this interview... It was my own first interview for the internship...

Of course, there was some side talk and some chatting, but the main questions were:

What are the differences between a struct and a class in C++?
I recall answering this completely wrong and falling for the trick that a struct cannot contain functions declaration... Although, I was only asked that question cause I stated that I know about C++ in my resume...
However, I found after the interview immediately about the right solution which you can find in details here
http://blog.stevedoria.net/20050913/differences-between-cpp-classes-and-structs
and here
http://www.jaggersoft.com/pubs/StructsVsClasses.htm#inheritance differences
We have an array of student names and need to find duplicates.
Of course, it is a simple question to test how to correctly code it in Java using a HashTable or a HashSet.
How many bits you need to represent an integer between 1 and 4,000,000?
That was the last question and I felt it was a dessert or something... You know 1,000 needs 10 bits, so 1,000,000 needs 20 bits, and 4,000,000 needs 22 bits...
If we have a list of N items, find if there exists a set of elements with summation equal to K
That was the first question and the hardest... It is a typical Subset Sum problem... with a dynamic programming solution... It is so much similar to the Kanpsack problem... all what was needed is a quick skeleton of the code, especially the recurrence relation...
http://en.wikipedia.org/wiki/Subset_sum#Pseudo-polynomial_time_dynamic_programming_solution
http://en.wikipedia.org/wiki/Knapsack_problem

====================================

Hope you enjoy this series... and see you all soon with the next interview...

Sunday, November 29, 2009

CSED Googlers Interviews - 2

Well... following our previous post with Dr Adel Youssef, here is our second interview...

It was so funny and enjoyable...

The interview was with Dr Mohammad Galal El Feky... He is a very generous funny friendly gentleman... He is very Egyptian (if this can be an adjective)... He helped us a lot back there in Mountain View... We enjoyed a lot of football matches, lunches, Ramadan breakfasts, pool games and Weekend outings... and he has always been there to show us around and make it so damn enjoyable and joyful all the time...

I'd like to take this opportunity to thank him for all his efforts, time and help... and for this lovely interview that I enjoyed so much especially that it was at Slice Cafe (that explains the blender voice that appears every now and then)

Dr Mohammad has joined Google on 2005 and since then he has worked with the AdSpam team and then with the Arabic Team. He received a PhD in Computer Science from University of Purdue.

I hope you enjoy the interview as much as I did when making it...

Part 1

Part 2

Part 3

Enjoy...!!!

Amr Ebaid

About Amr...

How many?

Followers

Subscribe via e-mail

Labels

Lijit Search

لا لجدار العار - حملة المليون توقيع

Find

Headlines

Monday, February 1, 2010

إنهم يحرقون مصرنا

Friday, January 22, 2010

Google Interviews - 4

Sunday, January 10, 2010

Google Interviews - 3

Wednesday, December 23, 2009

Google Interviews - 2

Tuesday, December 15, 2009

حتى يغيروا ما بأنفسهم

Thursday, December 10, 2009

Google Interviews - 1

Sunday, November 29, 2009

CSED Googlers Interviews - 2

Ads

Ads

Blog Archive

See also...

Good Ones...

Amr Ebaid

About Amr...

How many?

Followers

Subscribe To

Subscribe via e-mail

Labels

Lijit Search

لا لجدار العار - حملة المليون توقيع

Find

Headlines

Monday, February 1, 2010

إنهم يحرقون مصرنا

Friday, January 22, 2010

Google Interviews - 4

Sunday, January 10, 2010

Google Interviews - 3

Wednesday, December 23, 2009

Google Interviews - 2

Tuesday, December 15, 2009

حتى يغيروا ما بأنفسهم

Thursday, December 10, 2009

Google Interviews - 1

Sunday, November 29, 2009

CSED Googlers Interviews - 2

Ads

Ads

Blog Archive

See also...

Good Ones...