Google Interview Round 2 Question

February 9, 2018 at 4:11 pm | Posted in C++, Hacking, Programming | 1 Comment

I was just searching for C and C++ related topics and came across Google interview question.:

/**
*
* Google OnSite Round 2
*
* Input is an integer array A
* Return an array B such that B[i] = product of all elements of A except A[i]
*
*/

Original Question was on CareerCup. I wrote an algorithm on paper in 7 min and took me another 10 min to type it in computer. Do it without using division.

#include 

enum { SIZE = 3 };

void printArr(int ai[]);

int main(void)
{
  int arrA[] = {1,2,3,4};
  int arrB[SIZE+1];
  int m = 1;

  printArr(arrA);
  for(int i = 0; i = 0; --j)
	{
	  if(i != j)
	    {
	      m = m * (arrA[j]);
	    }
	}
      arrB[i] = m;
      m = 1;
    }

  printArr(arrB);

  return 0;
}

void printArr(int ai[])
{
  for(int i = 0; i <= SIZE; ++i)
    printf("%d ", ai[i]);

  printf("\n\n");
}

and it compiles fine and produces what is needed. I was quite shocked by my own performance. I was always scared of Google/Microsft/Amazon/Facebook interview questions. I thought their problems could be solved by only smart programmers (by smart I mean "born smart"). But Now after 5 years in C and programming, I think I an do it. I do not have any CS degree and I do not even qualify for getting into the interview with Google. It was quite exhilarating to know that I can solve their interview problems 🙂

[arnuld@arch64 programs]$ gcc -std=c99 -pedantic -Wall -Wextra g1.c
[arnuld@arch64 programs]$ ./a.out
1 2 3 4

24 12 8 6

[arnuld@arch64 programs]$

I posted this on comp.lang.c and then Keith Thompson, one of the top of the line C Hackers around the world and one handsome fella :), replied “Not bad at all“. Now that means a lot from a C Hacker. He edited the code, put his experience in it and made it much more beautiful, much more elegant. I loved it. He even explained it in detail. Thats is one thing I love about Hacker Community. You show you can work hard on solving a problem and they will spend their time in teaching you, to guide you, to help you, all for because they share passion for coding like you and I. Here is the full post from comp.lang.c in Keith’s own words. This guy is really a C scientist.

Not bad at all. Let me suggest some minor improvements.

enum { SIZE = 3 };

SIZE is actually one less than the number of elements in each array, which is misleading. I’d define SIZE as 4 and use “< SIZE" rather than "<= SIZE" in the loops. (Though as you'll see some other changes I'm going to suggest eliminate the need for SIZE anyway.)

I also used "length" rather than "size" to avoid confusion with "sizeof" (which counts bytes rather than elements).

int arrA[] = {1,2,3,4};
int arrB[SIZE+1];

You've defined the number of elements in one place, and the values of the elements in another. Never count something yourself when you can let the computer do it; they're really good at that. Not only is it easier, but you can make an update in just one place and the compiler will figure out the new size.

You define m outside the outer loop, and then reset it to 1 at the bottom. Instead, define it above the top of the inner loop. Since you get a new m on each iteration of the outer loop, you only need to initialize it once.

I also added an argument to printArr to indicate the length of the
array.

Here's my modified version:

int main(void)
{
  int arrA[] = {1,2,3,4};
  enum { length = sizeof arrA / sizeof arrA[0] };

  int arrB[length];

  printArr(arrA, length);
  for(int i = 0; i < length; ++i)
    {
      int m = 1;
      for(int j = 0; j < length; ++j)
        {
          if(i != j)
            {
              m *= arrA[j];
            }
        }
      arrB[i] = m;
    }

    printArr(arrB, length);

    return 0;
}

void printArr(int ai[], int length)
{
  for(int i = 0; i < length; ++i)
    printf("%d ", ai[i]);

  printf("\n\n");
}

Then you get this:

[arnuld@arch64 programs]$ gcc -ansi -pedantic -Wall -Wextra t.c
[arnuld@arch64 programs]$ ./a.out
10
[arnuld@arch64 programs]$

Again, there’s nothing wrong with your version, I just wanted to present a few ideas.

I note that the problem statement says “Return an integer array B such that …”. You can’t literally return an array from a function in C. There are several ways to do something similar, varying in how the memory for the result is allocated and deallocated. You’ve created the new array inside the main() function, which is fine for a small example like this, but perhaps not if this were meant to be included in a larger program.

Like I always say, C is a very small language. You can put entire C language in your head if you do few years of serious coding in C. For the standard libraries, you have have H&S5. After 5 years, I still feel the same. Always learn from the best. If you want to learn good C language, get a USENET Newsreader like Pan, read about NNTP protocol and start using Pan. Do not use Google Groups to post on comp.lang.c because all those C hackers have put Google Groups on a kill file because of too much spam from there. You can use Google groups to search for comp.lang.c archives.

Copyright © 2018 Arnuld Uttre, Hyderabd, Telangana – 500017 (INDIA)
Licensed Under Attribution 4.0 International (CC BY 4.0)

Advertisements

1 Comment »

RSS feed for comments on this post. TrackBack URI

  1. […] solve problems in C after 5 years of experience which I never could never did earlier. Like this Google Interview Question. I am very much confident in C now. Imagine 10+10 more years in C, what it will make me, a Samson […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

Create a free website or blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: