// Bagira's Offsite Programming Test / This test is the proprietary and confidential information of "Bagira Systems" and may not be // replicated, copied, disseminated or posted without the express written permission of "Bagira Systems" // (c) 2014 Telekinesys Research Limited. // // You have 2 hours to complete the test. // // Attempt all questions and place your answers directly after each question // Marks are shown for each question. Questions do not carry equal marks. // // Write code or comments where appropriate, preferably code. // // Do not collaborate or use books, the internet or other external sources. // // Where appropriate you can assume some standard routines already exist // e.g. sort, binary search etc. // Enter your name here: // Enter the date here (dd/mm/yyyy): //------------------------------------------------------------------------------ // 1. // // The nth 'Factorial' F(n) for positive integers n is defined by: // // F(0) = 1 // F(n) = 1*2*3*...*(n-1)*n // // So: // F(2) = 1*2 = 2 // F(3) = 1*2*3 = 6 // etc. int factorial(int n); // (1a) Write an iterative (non-recursive) function to compute F(n) // (1b) Write a recursive function to compute F(n) // (1c) Which implementation do you expect to be faster and why? // Give at least 3 reasons. //------------------------------------------------------------------------------ // 2. // // Implement a function reverseAfter() to reverse the elements in a linked list // from the first occurrence of a given value. // e.g. given the input A B C D E F and the value D return the list A B C F E D // You should do this inplace without creating new nodes. // Assume the list is null terminated. struct Node { struct Node* next; int val; }; void reverseAfter( struct Node* head, int val ); //------------------------------------------------------------------------------ // 3. // // Explain the differences between buffer1, buffer2 and buffer3 in the // example code below. Consider: // i. Scope & Lifetime // ii. Performance & use of system resources char buffer1; void func1() { char buffer2; //... } void func2() { char* buffer3 = static_cast<char*> ( malloc(2048) ); //... } //------------------------------------------------------------------------------ // 4. // // Choose any platform you want and describe what happens at machine level in the // execution of the code below when func() is called. // What changes if foo is inlined? int foo( int a, int* b) { return a + *b; } extern int x; void func() { int y = 7; int r; r = foo( x, &y ); printf("%d\n", r); } //------------------------------------------------------------------------------ // 5. // // You are implementing simple 'waypoint' following for an AI hover drone // in a 3D environment. The drone will consider a destination waypoint // acceptable if it is both: // i. Less than 10 units away. // ii. Inside a 60 degree cone centered around the drone's 'forward' vector. // // Implement the function testWayPoint() shown below. If the waypoint is not // acceptable the method should return REJECTED, otherwise it should return the // side that the waypoint is on. This is defined with respect to the drone's // forward vector and the world up vector (you may choose either 'handedness'). //---- // Assume the following functions and structures are defined elsewhere // DO NOT IMPLEMENT // Add v and w, putting the result in sum : sum = v + w void add(const Vector3& v, const Vector3& w, Vector3& sum); // Subtract w from v, putting the result in diff: diff = v - w void subtract(const Vector3& v, const Vector3& w, Vector3& diff); // Compute dot product of Vector3 v and w float dot(const Vector3& v, const Vector3& w); // Compute v X w (cross product): crossOut = v X w void cross(const Vector3& v, const Vector3& w, Vector3& crossOut); // Normalize the Vector3 v to unit length void normalize(Vector3& v); // Compute length of Vector3 float length(const Vector3& v); enum Direction { REJECTED = 0, RIGHT, LEFT }; //---- // This is the function you must implement: Direction testWayPoint(const Vector3& dronePosition, const Vector3& droneForward, const Vector3& targetWaypoint, const Vector3& worldUp ); //------------------------------------------------------------------------------ // 6. // // Identify as many bugs and assumptions as you can in the following code. // NOTE that there is/are (at least): // 1 major algorithmic assumption // 2 portability issues // 1 syntax error // Function to copy 'nBytes' of data from src to dst. void myMemcpy(char* dst, const char* src, int nBytes) { // Try to be fast and copy a word at a time instead of byte by byte int* wordDst = (int*)dst; int* wordSrc = (int*)src; int numWords = nBytes >> 2; for (int i=0; i < numWords; i++) { *wordDst++ = *wordSrc++; } int numRemaining = nBytes - (numWords << 2); dst = (char*)wordDst; src = (char*)wordSrc; for (int i=0 ; i <= numRemaining; i++); { *dst++ = *src++; } } //------------------------------------------------------------------------------ // 7. // // (7a) // An object foo is written to a new file on platform 1 as: write( file, &myFoo, sizeof(struct foo) ); // ...and then read on platform 2 using: read(file, &myFoo, filesize(file) ); // The foo object has the following definition: struct foo { char a; int b; long c; char* d; }; // What kind of issues might arise when loading foo on platform 2? // (7b) // You are writing a unit test to confirm the correctness of a function which // takes 3 float values as arguments. You decide to stress test it by testing // 1000000 'random' inputs. // You find that the function will fail, but very rarely, so you include code // to print out all failure cases, hoping to grab a simple repro case which you // can debug into. // Note: All code here is run in a single-threaded environment. //... // Some code sets a,b,c //... if ( testPasses(a,b,c) ) { printf("Pass\n"); } else // someFunc fails, print the values so we can reproduce { printf("Fail: %f %f %f\n", a, b, c); } // where testPasses has the following signature and executes deterministically // with no side effects: bool testPasses(float f1, float f2, float f3); void testRepro() { float a = // fill in from value printed by above code float b = // fill in from value printed by above code float c = // fill in from value printed by above code bool result = testPasses(a,b,c); }; // Surprisingly, when you type in the 3 values printed out in testRepro() // the test does not fail! // Modify the original code and test bed to reproduce the problem reliably. //------------------------------------------------------------------------------ // 8. // // Suppose that you have an array of shorts which corresponds to the vertex ids // of a set of T triangles. The shorts would be interpreted 3 at a time, so the // array // 0,2,7,1,3,5,6,2,0 // would represent 3 triangles with vertex ids : (0,2,7), (1,3,5) and (6,2,0) // There are 9 edges implicit in the data // Triangle 1 : (0,2), (2,7), (7,0) // Triangle 2 : (1,3), (3,5), (5,1) // Triangle 3 : (6,2), (2,0), (0,6) // Write a method to find all connectivity information between all triangles. // Two triangles are considered connected if they share an edge. // For example, triangle 1 and triangle 3 are connected because triangle 1 has // edge (0,2) and triangle 3 has opposite edge (2,0). // Your method should fill an output array of size 3T with the corresponding // indices of the opposite edge. You may assume that every edge has at most one // match. Edges with no opposite are flagged with -1. // The output for the example above should be // 7, -1, -1, -1, -1, -1, -1, 0, -1 // 8(a) First write the method using a brute force implementation (may be // very slow for large T) // 8(b) Then consider how you might preprocess the data to find // the edge matches more quickly for large T. Use code or // pseudocode to illustrate your approach. // Your method declaration should look like: void findConnectivity(unsigned short* indexTriples, int T, int* connectivityOut); //--------------------------------------------------------------------------------- /