SDE - 1

This problem is a simple recursive problem. But time complexity of simple recursive calls is exponential. In O(log(n))
this problem can be solved using a simple trick.

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

This method will solve this question in O(log(n)).

Approach :
1) Convert all 0's to -1's .
2) Now , the questions boils down to finding the number of subarrays with sum=0
3) This is a very standard problem which can be solved in O(N) using Hashing .
4) Maintain a Hash Map which keeps a track of all the prefix sums encountered so far
5) Maintain an answer variable and at each step do : ans+=map[prefixSum]
6) Finally return ans

Approach 1 (Using Hashing ) :
1) Traverse the list one by one and keep putting the node addresses in a Hash Table. 
2) At any point, if NULL is reached then return false, and if the next of the current nodes points to any of the previously stored nodes in Hash then return true.

TC : O(N) where N=length of the Linked List
SC : O(N)


Approach 2 (Using Slow and Fast Pointers) : 
1) Traverse linked list using two pointers.
2) Move one pointer(slow_p) by one and another pointer(fast_p) by two.
3) If these pointers meet at the same node then there is a loop. If pointers do not meet then linked list doesn’t have a loop.

TC : O(N) 
SC : O(1)

Answer :
The INNER JOIN selects all rows from both participating tables as long as there is a match between the columns. An SQL INNER JOIN is same as JOIN clause, combining rows from two or more tables.

Syntax :

SELECT * 
FROM table1 INNER JOIN table2 
ON table1.column_name = table2.column_name;

Answer :

Using subquery and MAX() function Use subquery to select all the numbers appearing just one time. Then choose the biggest one using MAX().

Query :

SELECT
MAX(num) AS num
FROM
(SELECT
num
FROM
my_numbers
GROUP BY num
HAVING COUNT(num) = 1) AS t;

Answer : 

Method Overloading :
1) Method overloading is a compile time polymorphism.
2) It is occur within the class.
3) Method overloading may or may not require inheritance.
4) In this, methods must have same name and different signature.
5) In method overloading, return type can or can not be be same, but we must have to change the parameter.

Method Overriding : 
1) Method overriding is a run time polymorphism.
2) It is performed in two classes with inheritance relationship.
3) Method overriding always needs inheritance.
4) In this, methods must have same name and same signature.
5) In this, return type must be same or co-variant.

A pure virtual function (or abstract function) in C++ is a virtual function for which we can have implementation, but we must override that function in the derived class, otherwise the derived class will also become abstract class. A pure virtual function is implemented by classes which are derived from a Abstract class.

Uses :
1) A pure virtual function is useful when we have a function that we want to put in the base class, but only the derived classes know what it should return.
2) A pure virtual function makes it so the base class can not be instantiated, and the derived classes are forced to define these functions before they can be instantiated. 
3) This helps ensure the derived classes do not forget to redefine functions that the base class was expecting them to.

Answer : 
1) In object-oriented programming, a singleton class is a class that can have only one object (an instance of the class) at a time. 
2) After first time, if we try to instantiate the Singleton class, the new variable also points to the first instance created. 
3) So whatever modifications we do to any variable inside the class through any instance, it affects the variable of the single instance created and is visible if we access that variable through any variable of that class type defined.

The key points while defining class as singleton class are :

1) Make constructor private.
2) Write a static method that has return type object of this singleton class. Here, the concept of Lazy initialization is used to write this static method.

Steps :
1 )Declare left and right var which will mark the extreme indices of the array
2) Left will be assigned to 0 and right will be assigned to n-1
3) Find mid = (left+right)/2
4 )Call mergeSort on (left,mid) and (mid+1,rear)
5) Above will continue till left right 
return
mid = (left+right)/2
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
merge(arr, left, mid, right)
end

TC : Best Case - O(N*log(N)) where N=lenght of the array to be sorted
Avg Case - O(N*log(N))
Worst Case - O(N*log(N))

SC : O(N)

Prerequisite to solve this problem : Multithreading

The idea is to create two threads and print even numbers with one thread and odd numbers with another thread.

Below are the steps:

1) Create two threads T1 and T2 , where T1 and T2 are used to print odd and even numbers respectively.
2) Maintain a global counter variable and start both threads.
3) If the counter is even in the Thread T1, then wait for the thread T2 to print that even number. Otherwise, print that
odd number, increment the counter and notify to the Thread T2 .
4)If the counter is odd in the Thread T2, then wait for the thread T1 to print that even number. Otherwise, print that
even number, increment the counter and notify the Thread T1.

Answer : 
1) A pipe is a form of redirection (transfer of standard output to some other destination) that is used in Linux and other Unix-like operating systems to send the output of one command/program/process to another command/program/process for further processing. 

2) The Unix/Linux systems allow stdout of a command to be connected to stdin of another command. We can make it do so by using the pipe character ‘|’.

3) Pipe is also used to combine two or more commands, and in this, the output of one command acts as input to another command, and this command’s output may act as input to the next command and so on.

4) It can also be visualized as a temporary connection between two or more commands/ programs/ processes. The command line programs that do the further processing are referred to as filters.

Examples :
1) Listing all files and directories and give it as input to more command.
$ ls -l | more 

2) Use sort and uniq command to sort a file and print unique values.
$ sort record.txt | uniq

3) Use head and tail to print lines in a particular range in a file.
$ cat sample2.txt | head -7 | tail -5

Answer :
The SOLID principle is an acronym of the five principles which is given below : 

1) Single Responsibility Principle (SRP)
2) Open/Closed Principle
3) Liskov’s Substitution Principle (LSP)
4) Interface Segregation Principle (ISP)
5) Dependency Inversion Principle (DIP)

Uses of SOLID design principles :

1) The SOLID principle helps in reducing tight coupling. 
2) Tight coupling means a group of classes are highly dependent on one another which we should avoid in our code. 
3) Opposite of tight coupling is loose coupling and our code is considered as a good code when it has loosely-coupled classes. 
4) Loosely coupled classes minimize changes in your code, helps in making code more reusable, maintainable, flexible and stable.

Explaining the 5 SOLID principles one by one : 

1) Single Responsibility Principle : This principle states that “a class should have only one reason to change” which means every class should have a single responsibility or single job or single purpose.
Use layers in your application and break God classes into smaller classes or modules. 

2) Open/Closed Principle : This principle states that “software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification” which means you should be able to extend a class behavior, without modifying it. Using this principle separates the existing code from the modified code so it provides better stability, maintainability and minimizes changes as in your code.

3) Liskov’s Substitution Principle : According to this principle “Derived or child classes must be substitutable for their base or parent classes“. This principle ensures that any class that is the child of a parent class should be usable in place of its parent without any unexpected behavior.

One of the classic examples of this principle is a rectangle having four sides. A rectangle’s height can be any value and width can be any value. A square is a rectangle with equal width and height. So we can say that we can extend the properties of the rectangle class into square class. In order to do that you need to swap the child (square) class with parent (rectangle) class to fit the definition of a square having four equal sides but a derived class does not affect the behavior of the parent class so if you will do that it will violate the Liskov Substitution Principle. 

4) Interface Segregation Principle : This principle is the first principle that applies to Interfaces instead of classes in SOLID and it is similar to the single responsibility principle. It states that “do not force any client to implement an interface which is irrelevant to them“. Here your main goal is to focus on avoiding fat interface and give preference to many small client-specific interfaces.

5) Dependency Inversion Principle : Two key points are here to keep in mind about this principle

a) High-level modules/classes should not depend on low-level modules/classes. Both should depend upon abstractions.
b) Abstractions should not depend upon details. Details should depend upon abstractions.

Answer :
a) It is an IT company that caters to the telecommunication domain. The business involved in the telecommunication domain is interesting and can widen your chances of switching into various fields be it in software, hardware or networking profiles. Also, Amdocs carries a good brand name in its domain.

b) Amdocs employees get to enjoy a positive and happy work environment.

c) It is truly an employee friendly organisation.I say this because Amdocs policies are employee oriented above anything else.

Tip 1 : The cross questioning can go intense some time, think before you speak.
Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.
Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round, like what are the projects currently the company is investing, which team you are mentoring. How all is the work environment etc.
Tip 4 : Since everybody in the interview panel is from tech background, here too you can expect some technical questions. No coding in most of the cases but some discussions over the design can surely happen.