System Engineer

Approach (Using DP) : 

We reach “currStep” step in taking one step or two steps:

We can take the one-step from (currStep-1)th step or,
We can take the two steps from (currStep-2)th step.

So the total number of ways to reach “currStep” will be the sum of the total number of ways to reach at (currStep-1)th and the total number of ways to reach (currStep-2)th step.
Let dp[currStep] define the total number of ways to reach “currStep” from the 0th. So,

dp[ currStep ] = dp[ currStep-1 ] + dp[ currStep-2 ]

The base case will be, If we have 0 stairs to climb then the number of distinct ways to climb will be one (we are already at Nth stair that’s the way) and if we have only one stair to climb then the number of distinct ways to climb will be one, i.e. one step from the beginning.


TC : O(N), where N = number of stairs.
SC : O(N)

Approach : 

1) Create a hashtable, to store the distinct encoded strings.

2) For each string in the array:
2.1) Find the frequency of even and odd indexed characters and store them in hash table say, freqEven and freqOdd.
2.2) Initially, the encoded string is empty.
2.3) Iterate through the characters from ‘a’ to ‘z’:
2.3.1) Let the current character be ch.
2.3.2) Concatenate the encoded string with “freqEven[ch]-freqOdd[ch]-”.
2.4) If the encoded string is not present in the hashtable, then add it to the hashtable.

3) Return the number of strings present in the hashtable.

TC : O(N*M), where N is the number of strings in the array and M is the length of the longest string.
SC : O(N)

Approach (Using Bit-Masking) : 

1) Declare a 2-D container ans to store all the subsets
2) Run a for loop for num from 1 to 2^N -1
3) Run inner for loop for i from 0 to N-1
4) If the ith bit in num has value equal to 1 then include ith element of the array in the current subset.
5) Push each subset generated into ans
6) Finally, sort and print each container inside ans in a separate line

TC : O( N * 2^N ), where N = size of the input array.
SC : O( N * 2^N )

Approach (Using Kadane's Algo) :

1) Declare a variable ‘maxSum’ and initialize it with ‘minimum integer’

2) Declare a variable ‘localSum’ and initialize it with ‘0’

3) Declare 3 counter variables as ‘start’ , ‘end’ , ‘newStart’ as 0, 0, 0

4) Run a loop from i = 0 to N
4.1) Add a current element to ‘localSum’

4.2) If 'localSum' is greater than 'maxSum'
Update ‘maxSum’ with 'localSum', update start with ‘newStart’ and end with loop counter ‘i’

4.3) If 'localSum' is equal to ‘maxSum’ and the difference between ‘end’ and ‘start’ is less than the
difference between ‘newStart’ and ‘i’
Update start with ‘newStart’ and end with ‘i’

4.4) If 'localSum' is below ‘0’
Update ‘localSum’ as 0 and set ‘newStart' as ‘i’ + 1

5) Return the part of the array starting from ‘start’ and ending at ‘end’


TC : O(N), where N = size of the array
SC : O(N), we need a final array to store the result maximum subarray.

Inner Join : 

1) It returns the combined tuple between two or more tables.
2) Used clause INNER JOIN and JOIN.
3) When any attributes are not common then it will return nothing.
4) If tuples are more. Then INNER JOIN works faster than OUTER JOIN.
5) It is used when we want detailed information about any specific attribute.

SQL Syntax : 

select * 
from table1 INNER JOIN / JOIN table2 
ON table1.column_name = table2.column_name; 



Outer Join :

1) It returns the combined tuple from a specified table even if the join condition fails.
2) Used clause LEFT OUTER JOIN, RIGHT OUTER JOIN, FULL OUTER JOIN, etc.
3) It does not depend upon the common attributes. If the attribute is blank then there is already placed NULL.
4) Generally, The OUTER JOIN is slower than INNER JOIN. But except for some special cases.
5) It is used when we want to complete information.

SQL Syntax : 

select * 
from table1 LEFT OUTER JOIN / RIGHT OUTER JOIN / 
FULL OUTER JOIN / FULL JOIN table2 ON 
table1.column_name = table2.column_name;

Data integrity is one significant aspect while maintaining the database. So, data integrity is enforced in the database system by imposing a series of rules. Those set of integrity is known as the integrity rules.

There are two integrity rules in DBMS:

Entity Integrity : It specifies that "Primary key cannot have a NULL value."

Referential Integrity: It specifies that "Foreign Key can be either a NULL value or should be the Primary Key value of other relation

Approach (Using Array) : 

Definition of Trie Node : 

1) child - storing the address of child nodes (Array of the address of Trie Nodes with size 26 initialized with NULL)
2) isEnd - a bool variable for marking this node as an end of some word.

Then we have defined our Trie Class having members:

1) root - The root node for whole Trie, every word starts from this node.
2) insert(word) - To insert a string "word" in Trie
3) search(word) - To check if string "word" is present in Trie or not.
4) startsWith(word) - To check if there is any string in the Trie that starts with the given prefix string "word".


insert(word) :

1) Initialize the current node with the root node of Trie.
2) Iterate over the word from left to right and if there is NULL in the address of the node for the next character of the word then create a new node and store the address in child member of the previous character’s node.
3) Keep updating the current node to the corresponding node for the next character of the word.
4) Finally, when we reached the end of the word, mark the isEnd member of the current node to true as it will denote the word is present or not.



search(word) :

1) Initialize the current node with the root node of Trie.
2) Iterate over the word from left to right and if there is NULL in the address of the node for the next character of the word then return false as the word is not present in the Trie.
3) Keep updating the current node to the corresponding node for the next character of the word.
4) Finally, when we reached the end of the word, return the isEnd bool variable of the current node as it will denote the word is present or not.



startsWith(word) : 

1) Initialize the current node with the root node of Trie.
2) Iterate over the word from left to right and if there is NULL in the address of the node for the next character of the word then return false as the no word is present in the Trie with this word as a Prefix.
3) Keep updating the current node to the corresponding node for the next character of the word.
4) Finally, when we reached the end of the word, return true as some word must be present in the Trie as we are able to cover the whole prefix word.


TC : O(N*W) (insert - O(W), search - O(W), startsWith - O(W))
where N is the number of queries and W is the average length of words.

SC : O(N*W)

Multitasking : It refers to the process in which a CPU happens to execute multiple tasks at any given time. CPU
switching occurs very often when multitasking between various tasks. This way, the users get to collaborate with
every program together at the same time. Since it involves rapid CPU switching, it requires some time. It is because
switching from one user to another might need some resources. The processes in multi-tasking, unlike multi-
threading, share separate resources and memories.


Multithreading : It is a system that creates many threads out of a single process to increase the overall power and
working capacity of a computer. In the process of multi-threading, we use a CPU for executing many threads out of a
single process at any given time. Also, the process of creation depends entirely on the cost. The process of
multithreading, unlike multitasking, makes use of the very same resources and memory for processing the execution.

Answer :
1) It is generally a situation where the CPU performs less productive work and more swapping or paging work.
2) It spends more time swapping or paging activities rather than its execution.
3) By evaluating the level of CPU utilization, a system can detect thrashing.
4) It occurs when the process does not have enough pages due to which the page-fault rate is increased. 5) It inhibits
much application-level processing that causes computer performance to degrade or collapse.

Constructors :
1) A Constructor is a block of code that initializes a newly created object.
2) A Constructor can be used to initialize an object.
3) A Constructor is invoked implicitly by the system
4) A Constructor is invoked when a object is created using the keyword new.
5) A Constructor doesn’t have a return type.
6) A Constructor’s name must be same as the name of the class.
7) A Constructor cannot be inherited by subclasses.



Method :
1) A Method is a collection of statements which returns a value upon its execution.
2) A Method consists of Java/C++ code to be executed.
3) A Method is invoked by the programmer.
4) A Method is invoked through method calls.
5) A Method must have a return type.
6) A Method’s name can be anything.
7) A Method can be inherited by subclasses.

1) Garbage Collection in Java is a process by which the programs perform memory management automatically.
2) The Garbage Collector(GC) finds the unused objects and deletes them to reclaim the memory. 
3) In Java, dynamic memory allocation of objects is achieved using the new operator that uses some memory and the
memory remains allocated until there are references for the use of the object.
4) When there are no references to an object, it is assumed to be no longer needed, and the memory, occupied by
the object can be reclaimed.
5) There is no explicit need to destroy an object as Java handles the de-allocation automatically.


The technique that accomplishes this is known as Garbage Collection. Programs that do not de-allocate memory can
eventually crash when there is no memory left in the system to allocate. These programs are said to have memory
leaks.

Garbage collection in Java happens automatically during the lifetime of the program, eliminating the need to de-
allocate memory and thereby avoiding memory leaks.

In C language, it is the programmer’s responsibility to de-allocate memory allocated dynamically using free() function.
This is where Java memory management leads.

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.

Answer :

1) Work-Life Balance : As per the employees of Infosys, they have a well-maintained work-life balance. The
employees believe that the company offers them certain opportunities allowing them to maintain their home life while
focusing on the career at the same time.

2) Brand Name : Infosys has become a brand name over time and with the high popularity, it has become one of the
major companies that are making employees jump at the offer from Infosys. The brand has a good reputation in the
market that is one of the top reasons to work at Infosys.

3) Work Environment : The work environment of Infosys is well-known as the colleagues are not only supportive but
ensure that the new employees can work in a learning environment.