Linkedin Interview Question Software Engineer / Developers
Team: Security
Country: United States
Interview Type: Phone Interview
public int fastPower(int n, int exp){
int halfExp = exp/2;
int power = 1;
for(int i=0; i<halfExp;i++, power=power*n);
power = power*power;
if(exp%2 > 0){
power = power*n;
}
return power;
}
using recursion would be better
public in power(int n,int exp)
{
if(exp==1){
return n;
}
int pow = power(n, exp/2);
pow= pow*pow;
if(exp%2 ==0){
pow= pow*n;
}
return pow;
}
mv.sanath it's nice with recursion but you'll use more memory.
// Complexity is O(log(exp))
int pow_num(int n, int exp)
{
if(0 == exp || n == 1) {
return 1;
}
int result = n;
bool k = (0 != (exp % 2));
while(exp > 1) {
result *= result;
exp = exp / 2;
}
return k ? result *= n : result;
}
First off, you'd be shot down if you'd even think of using such GOTO labels in production code. They're HORRIBLE. I can't seem to stress this enough.
Dear Prakash,
Thanks for reminding everyone about the evilness of goto.
However, I would like to let you know that goto can be used effectively than in a bad way. For example, goto with circular jumping is bad, but unidirectional is not bad. goto statements increase maintainability, enhanceability, cleanliness of the code if used properly.
You might not like it but goto is used in production code at kernel and device drivers level. Yes, its usage decreases as one goes up the stack. If you do not believe, go and search in linux kernel soure code @ h t t p://lxr.linux.no/linux+v3.1.2/ (Search box is on top right)
I hope you searched and came back here :).
If you start 'reasoning out' why gotos are bad then you can see that my usage of goto does not fall in that 'bad usage' category. I have been writing systems code for few years and it is very natural for me to use goto even on solving problems like this. You may have got irritated by reading such code (HORRIBLE in caps is an indication that you have irritation feeling). I am sorry to have caused you irritation, but I believe you have to change for better by understanding how useful is goto.
Here is a method written both using and not using gotos.
=============================================
void foo_with_goto()
{
char *p1 = NULL, *p2 = NULL;
int errorCode;
// Some code - 1
...
// Explicitly written code here
p1 = (char *) malloc(10);
if (NULL == p1)
{
errorCode = -1;
goto Exit;
}
if (some_error_condition)
{
errorCode = -2;
goto Exit;
}
// Some code - 2
...
// Explicitly written code here
p2 = (char *) malloc(10);
if (NULL == p2)
{
errorCode = -1;
goto Exit;
}
// Some code - 3
...
if (some_error_condition)
{
errorCode = -2;
goto Exit;
}
// Some code - 4
...
if (some_error_condition)
{
errorCode = -2;
goto Exit;
}
// Some code - 5
...
Exit:
if (NULL != p2) free(p2);
if (NULL != p1) free(p1);
}
=============================================
void foo_without_goto()
{
char *p1 = NULL, *p2 = NULL;
int errorCode;
// Some code - 1
...
// Explicitly written code here
p1 = (char *) malloc(10);
if (NULL == p1)
{
return;
}
if (some_error_condition)
{
free(p1);
return;
}
// Some code - 2
...
// Explicitly written code here
p2 = (char *) malloc(10);
if (NULL == p2)
{
free(p1);
return;
}
// Some code - 3
...
if (some_error_condition)
{
free(p2);
free(p1);
return;
}
// Some code - 4
...
if (some_error_condition)
{
free(p2);
free(p1);
return;
}
// Some code - 5
...
Exit:
free(p2);
free(p1);
}
=============================================
Now think about the next developer (not original developer) who need to add some extra code and also handle error condition in that code. He need to be very careful in case of non-goto version as to what to free based on where he is adding the code. It is also highly error prone in non-goto version as a single miss of free leads to memory leak.
It is even more night mare if the new developer has to allocate another memory and the code is before some other existing allocation. Now suddenly he has to change multiple places to make sure his newly allocated memory has to be freed at multiple points of return.
I would like to thank you if you have taken this positively for a healthy debate than treating this as a fight.
Thanks,
Laxmi
Any competent developer will wrap those char* in a std::string or equivalent so that he doesn't need to free it. Using goto in crap code doesn't make it better
Dear Anonymous,
I do not have any intention to get into fight. Please look at my reply (both original and next one) and realize that my language is 'C' (than C++). Unfortunately, std:string belongs to C++ world.
Again, if you search the linux kernel source code (C language code) you can see many hits 'goto', and is used very effectively. Per your assessment, many of linux kernel developers are incompetent which neither me nor the world agree.
I can only try to educate if people are open to learn than keeping their minds closed and take a chance to get into fight.
I dont have anything to hide here (clear Id 'olnrao' than anonymous). Plus, I dont have time to enter or entertain fight either :). All the best for your 'fight' nature in some other place, it does not work out here :).
Thanks,
Laxmi
Dear Laxmi,
I just went through your post. It is quite exciting to see how an almost forgotten primitive (goto) can be effectively used in certain situations.
This will definitely look crap to anyone not taking into account the maintainability of the code. So, it needs patience to understand what you have mentioned and moreover, a person like you who can put enough effort to make things understandable to others.
Thanks for bringing us back to basics !!
Thanks,
Piyush
import java.util.Scanner;
public class PowerTestLinkedIn {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
if (n == 0) {
if (m == 0) {
System.out.println("error");
return;
} else {
System.out.println("0");
return;
}
}
if (n == 1) {
System.out.println("1");
return;
}
if (n == -1) {
if (m % 2 == 0) {
System.out.println("1");
return;
} else {
System.out.println("-1");
return;
}
}
int result = 1;
int temp = n;
while(m!=0){
if(m%2 != 0){
result *=temp;
}
temp = temp*temp;
m = m/2;
}
System.out.println(result);
}
}
This is a nice solution using bytes and Java:
static double pow(int base, int exp)
{
boolean isNegative = exp < 0;
if (isNegative)
{
exp*= -1;
}
int result = 1;
while (exp != 0)
{
if ((exp & 1) != 0)
result *= base;
exp >>= 1;
base *= base;
}
return isNegative ? (1.0 / result) : result;
}
This is a nice solution using bytes and Java:
static double pow(int base, int exp)
{
boolean isNegative = exp < 0;
if (isNegative)
{
exp*= -1;
}
int result = 1;
while (exp != 0)
{
if ((exp & 1) != 0)
result *= base;
exp >>= 1;
base *= base;
}
return isNegative ? (1.0 / result) : result;
}
double Power(double base, int index)
- Anonymous November 23, 2011{
if(index == 0)
return 1.0;
if(index == 1)
return base;
bool negativeIndex = false;
if(index < 0)
{
negativeIndex = true;
index = -index;
}
double res = 1.0;
while(index > 0)
{
if(index % 2 == 1)
{
res *= base;
--index;
}
else
{
base = base * base;
index /= 2;
}
}
if(negativeIndex)
res = 1.0 /res;
return res;