SDE - 1

You are given an array “arr'' of integers. Your task is to find the contiguous subarray within the array which has the largest product of its elements. You have to report this maximum product.

An array c is a subarray of array d if c can be obtained from d by deletion of several elements from the beginning and several elements from the end.

For e.g.- The non-empty subarrays of an array [1,2,3] will be- [1],[2],[3],[1,2],[2,3],[1,2,3]. 

For Example:

If arr = {-3,4,5}.
All the possible non-empty contiguous subarrays of “arr” are {-3}, {4}, {5}, {-3,4}, {4,5} and {-3,4,5}.
The product of these subarrays are -3, 4, 5, -12, 20 and -60 respectively.
The maximum product is 20. Hence, the answer is 20.

Follow Up:

Can you solve this in linear time and constant space complexity?

Given a singly linked list of integers. Your task is to return the head of the reversed linked list.

For example:

The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse linked list is 4 -> 3 -> 2 -> 1 -> NULL and the head of the reversed linked list will be 4.

Follow Up :

Can you solve this problem in O(N) time and O(1) space complexity?

While learning DSA, Ninja found two N-ary trees and wants to check whether they are mirror images of each other or not. But, he can’t find a suitable method to check the same. Can you help Ninja to solve this problem?

You are given two N-ary trees, ‘TREEA’ and ‘TREEB’ having ‘N’ vertices labeled from 0 to ‘N’-1, and both the trees are rooted at node 0. Your task is to find whether the trees are mirror images of each other or not. Edges of the tree are in order from left to right.

For Example:

For the given example below, the trees are mirror images of each other.

You are given a ‘Binary Tree’.

Return the level-order traversal of the Binary Tree.

Example:

Input: Consider the following Binary Tree:

Output: 
Following is the level-order traversal of the given Binary Tree: [1, 2, 3, 5, 6, 4]

You are given a string 'S'. Your task is to check whether the string is palindrome or not. For checking palindrome, consider alphabets and numbers only and ignore the symbols and whitespaces.

Note :

String 'S' is NOT case sensitive.

Example :

Let S = “c1 O$d@eeD o1c”.
If we ignore the special characters, whitespaces and convert all uppercase letters to lowercase, we get S = “c1odeedo1c”, which is a palindrome. Hence, the given string is also a palindrome.

A string ‘S’ is said to be special if each of its characters is one of the first ‘P’ letters of the English alphabet and ‘S’ doesn't contain any palindrome contiguous substring of length 2 or more. You will be given a special string ‘S’ of length ‘N’, find the lexicographically next special string of the same length, or else state that such string does not exist. Print the output string if it exists, otherwise, print "NO" (without quotes).

A string “s1” is a substring of another string “s2” if “s2” contains the same characters as in “s1”, in the same order and in a continuous fashion also.

Example: Given a string “cba” and ‘P’ equals 3. So, the next strings which are lexicographically bigger than string ‘S’ are “cbb”, “cbc”, “cca”, “ccb” and “ccc” of size 3. But all of them have a palindrome substring of the size at least 2. So, we will return “NO” as output. If the given string is “cbd” and ‘P’ equals 4 then the next string will be “cda” and it is special. So, we can return an output here.

Note:

It is guaranteed that the input string is special.

Give a brief description of yourself
where did you get to know Accolite digital
where do you see yourself in five years in accolite