-3

JUST TO CLARIFY, THIS IS AN AMAZON INTERVIEW QUESTION. SO BE CONSTRUCTIVE!

This is from a website I am reviewing for interviewing. The question is to append 2 arrays in the form of the function.

// a1(size1) and a2(size2) are arrays and you
// have to append them.
int* Append(int* a1,int* a2,int size1,int size2)

The question that I have is. From the code below, why The array a is actually in the function Append and once you leave the function the scope of this array ends?

#include <iostream>
#include <string>
using namespace std;


int* Append(int* a1,int* a2,int size1,int size2)
{
    int a[size1+size2],i;

    for(i=0;i<size1;i++)
    {
         a[i]=a1[i];
    }

    for(i=0;i<size2;i++)
    {
         a[i+size1]=a2[i];
    }

    return a;
}

int main()
{
  int a[] = {1,2,3};
  int b[] = {4,5,6,7};
  int* c;
  c = Append(a,b,3,4);
  for(i=0;i<7;i++)
     cout << c[i] << endl;
  cout << "abc";
}

"I told him that the above code actually fails. He asked me why it fails. I answered him this way.The array a is actually in the function Append and once you leave the function the scope of this array ends. He asked me how to do it then. I had no idea. Later he told me that we have to allocate memory for the array using malloc.Later on he explained me how it works using heap memory."

  1. The question that I have is. From the code above, why The array a is actually in the function Append and once you leave the function the scope of this array ends?

  2. My second question is that is this related to Heap and Stack memory?

  3. How do the Heap and stack memory work in Java? And how is the Heap and Stack in Java different from C++? (I program more in Java, so I would like to learn more about the memory in Java)

Please attach any link/url about the material, I would like to learn more.

NNguyen
  • 113
  • 1
  • 6
  • 4
    You're returning a pointer not an array. The approach that was suggested to you is all so bad and instead you should use a standard container. – Aluan Haddad Mar 12 '18 at 08:23
  • I totally understand your point, but it was an interview question. So the issue here is not why do this? The issue here is why is this method wrong? Even if the function returns a pointer, where does it go? – NNguyen Mar 12 '18 at 08:25
  • 4
    you cannot do it, because once the function ends, the array is destroyed. You will return pointer to object, that stopped existing in the mean time, thus you are risking SegmentationFault. – Krzysztof Skowronek Mar 12 '18 at 08:26
  • 1
    Non-primitive objects in Java are always on the heap, and are kept alive until all references to them are dropped. – Tommy Andersen Mar 12 '18 at 08:27
  • @NNguyen I wasn't trying to poke you. – Aluan Haddad Mar 12 '18 at 08:28
  • the code was written in C++. you were talking about C++ or Java. Sorry but I was confused. Btw, do have a reference? – NNguyen Mar 12 '18 at 08:28
  • 3
    So the question was about how you do it in C++ and he told you the right answer was to use `malloc`? – Killzone Kid Mar 12 '18 at 08:29
  • 1
    Arrays a[] and b[] stored in main application thread stack. I.e. when main function will finish - arrays will be destroyed. Call to Append function will not clear the stack, it will put return address and function arguments into stack and move instruction pointer into function address. Operator return will remove Append local variables and function arguments from thread stack, and return instruction pointer to the main function body. Return from main, will do the same to the main function and back instruction pointer back to CRT startup, this will bring to a[] and b[] to be destroyed. – Victor Gubin Mar 12 '18 at 08:29
  • 2
    https://stackoverflow.com/questions/275214/scope-and-return-values-in-c?rq=1 take a look at this question and it's answers. That's the same problem – Krzysztof Skowronek Mar 12 '18 at 08:29
  • 2
    By the way, the interviewer's answer is somehow questionable, too - if this is C++, one should rather have used `new int[...]` instead of `malloc`... – Aconcagua Mar 12 '18 at 08:30
  • Putting array into heap is one solution, another - is declaring a array as `static` - so that it would be moved from a stack into global memory area shared between all functions. – Agnius Vasiliauskas Mar 12 '18 at 08:32
  • Read a [good C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) – Passer By Mar 12 '18 at 08:33
  • 2
    This is a C question, not C++ (or both the function and the answer to use malloc are bad). A C++ alternative is to use `std::copy` as in https://stackoverflow.com/questions/12791266/c-concatenate-two-int-arrays-into-one-larger-array (and probably prefer `std::vector` to a built-in array if possible). – drRobertz Mar 12 '18 at 08:37
  • 3
    fyi, `int a[size1+size2]` is not legal in standard `C++`. – Galik Mar 12 '18 at 08:41
  • 2
    This really is a terrible interview question. If you get something like this in an interview, it is a sign that your future employers have a terrible `C++` code base. Run! – Galik Mar 12 '18 at 08:44
  • @Galik and Jive Dadson, I removed my comment, it was my misunderstanding of the C++ standard change, that led me to believe it was legal C++ code. Turns out it is simply due to an extension to the GCC compiler originating back from C99 https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html you are correct :) apparently Clang also supports it. – Tommy Andersen Mar 12 '18 at 09:37

2 Answers2

1

1: Yes that is correct. This would also often trigger a warning by the compiler that you are "Returning address of temporary" or something similar.

2: Yes. All variables you declare in the scope of the function will be placed on the stack and will be automatically destroyed when the scope(the function) ends. To make it persist until you tell it not to(using delete/free) you have to allocate the memory using new or malloc.

3: I've only written very little Java so I can't answer this fully but when programming in Java you don't have to think about stack vs heap memory(although it might be beneficial to know how it works). Java has a "garbage collector" running in the background that cleans up any heap memory that it allocates for you (all variables except primitives as int, float etc are allocated on the heap in Java) when it's not needed anymore. This does of course come at a performance cost though.

Over here you can also see a brief summary of the different ways to handle memory in C++ :) Proper stack and heap usage in C++?

Edit 1: I just noticed now by the way that this program doesn't even compile. In the main function; there is a for loop that does i = 0 without first declaring i as an integer(or whatever type they intended it to be).

Edit 2: Also; as another commenter pointed out; int a[size1+size2] is not legal. For it to be legal; size1 and size2 would have to be const non parameter variables or a would have to be allocated on the heap.

MonzUn
  • 53
  • 1
  • 9
1

C++ support the basic data structures that C does, such as simple arrays, but that does not mean it is encouraged to do so. In C++ you are generally better of not writing basic arrays, but instead using the std::vector class, or similar data structure.

That being said, the question was an interview question, so even though this approach is discouraged, in general, let us look at the function, and the initialization and allocation of the array.

The first thing to notice is that the code does not compile. The main function holds a loop with a loop variable i that is not declared. This is a minor thing, and we can quickly fix it. Compiler output:

prog.cpp: In function ‘int main()’:
prog.cpp:29:7: error: ‘i’ was not declared in this scope
   for(i=0;i<7;i++)
       ^

Once we have fixed the compiler error we can run the code, but the compiler will still provide some warnings, which I strongly suggest you look at:

prog.cpp: In function ‘int* Append(int*, int*, int, int)’:
prog.cpp:8:9: warning: address of local variable ‘a’ returned [-Wreturn- local-addr]
     int a[size1+size2],i;
         ^

The warning has all the information we need at this point. (I do know that at an interview you might not have access to a compiler to see these things, but they are helpful when you get home and wonder why you got the reply like you did).

The warning basically says that the funtion is returning the address of a local variable. The local variable is deallocated once it leaves scope, that is how the stack works. We push to the stack when we declare the variables, and once the scope the variable is declared in is left, we pop the variables from the scope (or rather the allocated memory from the variables).

So the local variable a, is declared in the beginning of the function on the stack, and once the function returns, the address of this local variable is returned, but the memory the variable reserved is released.

So yes, this is related to heap and stack, in that elements on the stack are alive while the scope they are declared in, is alive, while elements on the heap are kept alive until they are explicitly told to no longer be alive (using delete or free).

When you are told that you need to allocate the array on the heap, you can do so using the new[] operator: 

int* a = new a[size1 + size2];

Remember that something that is allocated using new[] must be deallocated using delete[]. I do not agree with using malloc but this might be some requirement for the code, that will at some point release the code with free, at which point you have no choice but using malloc.

Again I would personally not do either, I would use std::vector instead, why worry about this, when it could be as simple as: std::vector<int> a? As an interview question though, it was asked to test your core language understanding, and while it would be good to be able to answer how to allocate the array on the heap, it would show a bit more strength to be able to reflect upon the code, and recommend an alternative, and better, approach. Such as not using new/malloc.

Generally C++ returns values and parses parameters by value (when we are not using the by reference option). Which means that we return a copy of the value we return. This is how we are able to return simple integers, or doubles, or even std::string (we ignore the move constructors, and how they work for simplicity), because we make a copy of them, and return. Actually we also make a copy of the variable a and return that. So you may wonder, why it fails when we make a copy of a. But as we have already established, from the compiler warning, the value we are actually returning, is the address of a.

When we declare an array in C++ (or C), we are allocating an area in memory, that is large enough to hold the requested number of elements. The variable, will then be a pointer to the address of the first element. It is that address we are actually copying, and not the actual area that it points to. So the function will return a pointer to an area, that is no longer allocated. The local variable a, is no longer alive, but the contents of a is copied, and is returned by the function.

Java is higher level language than C++ and does allow you to manipulate memory in the same way. In Java everything that is not a primitive (int, double, ...) is kept on the heap. Java objects are freed when there are no longer any references to them.

Tommy Andersen
  • 7,165
  • 1
  • 31
  • 50
  • Does your compiler support VLA? Doesn't it give a warning on `int a[size1+size2]`? – Tadeusz Kopec for Ukraine Mar 12 '18 at 09:39
  • I used a simple online compiler: https://ideone.com which uses GCC underneath the hood. GCC has an extension that supports the `int a[size1+size2]` https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html so it does not give a warning. I am sure it can be enabled if the site supported providing extra parameters. :) – Tommy Andersen Mar 12 '18 at 09:42
  • @Aconcagua ... only locally for the function `Append` not in the function `main`. Hence the first line in the compiler error message: `prog.cpp: In function ‘int main()’:` :) – Tommy Andersen Mar 12 '18 at 09:46