ChebbiOS

Interview at Company Y

#Interview#Java#C++#Rust#Complexity#Algorithms

Here are the questions asked during my interview at Company Y. It was a mix of rapid-fire technical questions (QCM style) and a deeper problem-solving discussion.

Part 1: Technical Concepts (QCM & short answers)

1. Static Variables and Class State

Question: What does g() return?

class MyClass {
    static int i;
    static void f() { i = i - 1; }
    static int g() {
        i = 2;
        f();
        return i;
    }
}

Answer: 1. Reason: i is static, so it’s shared. i becomes 2, then f() decrements it to 1.

2. Arrays vs Hash Sets – Complexity

Question: Which statement is true regarding space complexity? Answer: Both hash sets and arrays have O(N) space complexity. Reason: To store N elements, both need linear space relative to N.

3. Bubble Sort Complexity

Question: Time required to sort a list of n elements using Bubble Sort? Answer: O(n²) (Average and Worst Case).

4. Design Patterns

Question: A pattern where a composite object contains a collection of the same interface and delegates operations to children? Answer: Composite Pattern. Key Idea: Treat individual objects and compositions of objects uniformly.

5. Set Data Structure

Question: What is a Set, when to use it, and give a simple example? Answer:

  • Definition: A collection of unique elements (no duplicates).
  • Use Case: When you need to ensure uniqueness or perform fast lookups ($O(1)$) to check existence.
  • Example: Storing unique visitor IP addresses to count distinct users.

6. Data Structure Selection

Question: You have characters and need to store them in the exact order of the message. No uniqueness required. What structure? Answer: List (or Array / Vector). Reason: Sets do not preserve insertion order (typically) and do not allow duplicates. A List/Vector is ordered and allows duplicates.

7. Method Overloading vs Overriding

Question: Difference between Overloading and Overriding? Answer:

  • Overloading: Same method name, different parameters (compile-time polymorphism).
  • Overriding: Same method signature in a subclass (runtime polymorphism).

8. Dynamic Dispatch in C++

Question: Explain dynamic dispatch in C++ in detail. Answer:

  • It’s the mechanism to select which implementation of a polymorphic operation (virtual function) to call at runtime.
  • V-Table (Virtual Table): The compiler creates a static table for each class containing function pointers to virtual methods.
  • V-Ptr (Virtual Pointer): Each object instance has a hidden pointer (vptr) pointing to its class’s V-Table.
  • Runtime: When calling obj->method(), the program follows the vptr to the V-Table, looks up the function address, and calls it.

9. Access Modifiers (Cross-Package Inheritance)

Question: Class B inherits from Class A (different package). Can B access A’s public, protected, private members via an instance of A passed as a parameter? Answer:

  • a.myPublic: YES.
  • a.myProtected: NO. (Protected members are accessible in subclasses via inheritance, but not via object references of the parent class from a different package).
  • a.myPrivate: NO.

10. Static Methods & Instance State

Statement: “Static methods don’t belong to objects — they can’t see instance state.” Verdict: TRUE. Reason: Static methods belong to the class. They do not have a this pointer, so they cannot access non-static fields (this.variable) or methods.

11. Exception Handling (Java vs C++)

Question: Which statements are true?

  • NullPointerException is unchecked? TRUE.
  • Checked exceptions must be handled at compile-time (Java)? TRUE.
  • C++ does exception handling at compile-time? FALSE (C++ exceptions are unchecked).
  • ClassNotFoundException is unchecked? FALSE (It is Checked).
  • Both handled with try-catch-finally? TRUE.

12. Java Thread Creation

Question: How can a thread be created in Java? Answer:

  1. Extend Thread class: class MyThread extends Thread { public void run() { ... } }
  2. Implement Runnable interface: class MyRunnable implements Runnable { public void run() { ... } } (Better practice).
  3. Modern way: Use ExecutorService / CompletableFuture.

13. Multithreading: C++ vs Java

Question: Comparison? Answer:

  • Java: Built-in Thread class, JVM manages stack/memory, synchronized keyword for locks, robust memory model.
  • C++: std::thread (since C++11), manual memory management (danger of accessing freed memory), constructs like std::mutex, std::unique_lock. Lower level, higher control, higher risk.

14. Rust Thread Creation

Question: How is a thread created in Rust? Answer: Using std::thread::spawn.

use std::thread;

thread::spawn(move || {
    // code
});
  • Note: The move keyword is often used to transfer ownership of capturing variables into the new thread.

15. C++ Lambda Syntax

Question: Explain C++ Lambda syntax. Answer: [capture](parameters) -> return_type { body }

  • []: No capture. [=]: Capture all by value. [&]: Capture all by reference.
  • (): Arguments.
  • {}: Function body.

16. C++ RAII & Stack Unwinding

Question: Output of this code?

struct Foo { /* ... throws in raise() ... */ };
int main() { try { Foo f; f.raise(); } catch(...) { /* ... */ } }

Answer: Construct, Raise, Destroy, Catch, Bye! Reason: When raise() throws, Stack Unwinding begins. The destructor ~Foo() is called before control enters the catch block. This is the core of RAII (Resource Acquisition Is Initialization).

17. C++ Temporary Object Lifetime

Question: What happens here?

const char* data = get_data().c_str(); // get_data() returns std::string by value
std::cout << data;

Answer: Undefined Behavior (Dangling Pointer). Reason: get_data() returns a temporary std::string. c_str() gets a pointer to its internal buffer. At the end of the line (semicolon), the temporary string is destroyed, freeing the memory. data now points to garbage. Fix: std::string s = get_data(); std::cout << s.c_str();

Part 2: Problem Solving (Complexity Analysis)

Question: Algorithm Complexity Analysis

Determine the Time Complexity of the following algorithm:

// x is the input size
for (int i = 4; i < x; i++) {
    for (int k = 0; k < ((x * x) / 2); k++) {
        // Constant time data processing
    }
}

Answer: O(x³)

Step-by-Step Analysis

To find the time complexity, we need to count how many times the inner body executes. We can use the Multiplication Rule because the loops are nested.

1. Analyze the Outer Loop (i)

  • Start: i = 4
  • End: i < x
  • Increment: i++ (Step of 1)
  • Iterations: The loop runs from 4 to x - 1.
    • Total iterations $\approx x - 4$.
    • In Big-O notation, we drop lower-order constants, so this is O(x).

2. Analyze the Inner Loop (k)

  • Start: k = 0
  • End: k < (x * x) / 2
  • Iterations: The loop runs from 0 to $\frac{x^2}{2} - 1$.
  • Dependency: This loop runs completely for every single iteration of the outer loop.
    • Total iterations $\approx \frac{x^2}{2}$.
    • In Big-O notation:
      • We ignore coefficients (like $\frac{1}{2}$).
      • We conclude this loop is O(x²).

3. Combine (Multiplication Rule) Since the loops are nested (the inner loop runs fully for each step of the outer loop), we multiply their complexities:

$$ \text{Total Complexity} = O(\text{Outer Loop}) \times O(\text{Inner Loop}) $$

$$ \text{Total Complexity} = O(x) \times O(x^2) $$

$$ \text{Total Complexity} = O(x^3) $$

Conclusion

The algorithm has a Cubic Time Complexity, or O(x³).

Interview Tip: When analyzing nested loops:

  1. Ignore constants (starting at 4 or dividing by 2 doesn’t change the growth rate).
  2. Identify the relationship between the loops (Nested = Multiply, Sequential = Add).
  3. Focus on the dominant term. $x \times x^2 = x^3$.