Second Phone Interview At Google

when i hear that google planning to open branch in the middle east at jordon and there is open job vacancies for arabic fluent software engineers i am applied from the job and after two or three weeks my cell phone ring i am replied and found google calling me to organize two phone interview with me
i dont remember the questions of the first interview so i decided to write the second interview after finishing it

its my second interview at google
the interview was at 8:00 PM Cairo time
i am near to the phone waiting for the call
the phone ring at 8:05 PM and one of software engineers at google start talking to me
the interview was about 45 minutes
he ask me the following questions

1. my work experience as per my cv


2. what is my prefered programming language


3. what the diffrence between the following three java keywords (final,finally and finalize)


4. implement algorithm that find all pairs of integers in an interger array that the sum of each pair equal to specific value.

my answers

1. regards my work experience i am now working at TE-Data.one of the largest internet service provider (ISP) in egypt. i fill the position of Java Software Developer.we are mantain and develop customized software to support the company business regards ADSL services. google interviewer also asked me about the period i spend there at TE-Data and i say i am their from 4 months i joined TE-Data at June 2008 before TE-Data i was doing military service through this period i work as part time J2ME Developer at Telecom-Arabia


2. my prefered programming language is Java as per my study and work experience


3. the three java keywords
   -->final is java keword and have three diffrent meaning in three context. first if i declare avariable as final then its constant its value will not change through the life time of the program.second if method its declared final the the subclasses cannot override it.third if the class declared as final it canot be extended
   --->finally is java keyword that is used with try catch statement its used to closed any open connection or any code that must run if error happen or not.
   -->finalize is java method that is called when the object is reclaimed from the memory its like c++ destructor we put code that free system resources in it but its not preferable to account on this method as we are not sure when this method will be called.


4. algorthim that find the pairs of integers that their sum will equal specific value. i say that the straightforward solution is through two for loops that take each array elment and sum it to every element in the array and i provided this code to support my words

int a[];//this array hold list of integers

int x;//this variable hold the sum

for(int i=0;i<a.lenght;i++)
{
int sum=a[i];
for(int j=0;j<a.lenght;j++)
{
if(i==j)
continue;
if((sum+a[j])==x)
print(i,j);
}
}

then google interviewer this code will repeat the printing of the pairs

and asked how many times it will repeat two,three,...

i sayed it will print every pairs two times

as each two pairs will be compared two times

then i say to modify the inner loop instead of intializing j=0 to i+1

and the algorthim will look like that

int a[];//this array hold list of integers
int x;//this variable hold the sum

for(int i=0;i<a.lenght;i++)

int sum=a[i];
for(int j=i+1;j<a.lenght;j++)

{

if(sum+a[j]==x)

print(i,j);

}

}

google interviewer says ok

and ask about the time complexity of the algorithm i sayed its n square (n2)

he asked about to get it faster (enhancing its performance)

i say can we assume the array is sorted he say assume its sorted then i say we will take every element in the array and subtract this element from the required value then do binary search on this value and i provide the following code to support my words

int a[];//this array hold list of integers

int x;//this variable hold the sum

for(int i=0;i<a.lenght;i++)
{

int secondPair=x-a[i];

int j=binarySearch(secondPair,i+1);

if(index!=-1)

print(i,j);

}

he says ok and good then asked about the time complexity i says its (nlogn)

then he asked again what about if the array is not sorted

the i say we will sort it first using quicksort or mergesort its

then we will do the above algorithm again

then he asked about the time complexity i says

sort will take (nlogn)

pair search will another (nlogn)

then its (2nlogn) and we can ignore the constant factor then the algorithm complexity still (nlogn)

he says good

and asked me if i have any questions

and i says thanks and i am happy from the call