Hot Topics
PayU Solution
Technical Round
Remove all the duplicate elements from string array.
#include <stdio.h>
#include <string.h>
int main() {
char string_array[][10] = {"apple", "banana", "apple", "orange", "banana"};
int n = sizeof(string_array) / sizeof(string_array[0]);
int i, j, k;
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
if (strcmp(string_array[i], string_array[j]) == 0) {
for (k = j; k < n - 1; k++)
strcpy(string_array[k], string_array[k + 1]);
n--;
j--;
}
}
}
for (i = 0; i < n; i++)
printf("%s ", string_array[i]);
return 0;
}
/*
OUTPUT
apple banana orange
*/What is Trie?
Trie is special type of data structure or a type of k-ary search tree used for storing and searching a specific key from a set. It is used to decrease search complexities to optimal limit.
Longest Common Subsequence.
The Longest Common Subsequence (LCS) problem is a classic problem in computer science and is used to find the longest subsequence that is common to two or more strings. A subsequence is a sequence of characters that appear in the same order in the original string, but not necessarily consecutively.
One common approach to solving the LCS problem is using dynamic programming. The basic idea is to build a 2D table where each cell contains the length of the LCS of the substrings of the original strings that correspond to the row and column of the cell. The table is filled in a bottom-up manner, using the following recurrence relation:
LCS(i, j) = max { LCS(i-1, j), LCS(i, j-1), LCS(i-1, j-1) + 1 } if X[i] == Y[j] LCS(i, j) = max { LCS(i-1, j), LCS(i, j-1) } if X[i] != Y[j]
where X and Y are the original strings, i and j are the indices of the characters in the strings, and LCS(i,j) is the length of the LCS of the substrings X[1…i] and Y[1…j].
You can then use the table to backtrack and reconstruct the actual LCS.
Here is an example of C++ code to implement the LCS problem using dynamic programming:
In the above code, the function LCS takes two strings as input and returns the length of their LCS. The variable m and n are the lengths of the two strings.
HashMap implementation.
#include <iostream>
#include <algorithm>
using namespace std;
int LCS(string X, string Y, int m, int n) {
int L[m+1][n+1];
int i, j;
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
return L[m][n];
}
int main() {
string X = "AGGTAB";
string Y = "GXTXAYB";
int m = X.length();
int n = Y.length();
cout << "Length of LCS is " << LCS(X, Y, m, n);
return 0;
}
/*
OUTPUT
Length of LCS is 4
*/A HashMap is a data structure that allows you to map keys to values in a very efficient way. It is implemented using a hash table, which is a collection of buckets. Each bucket contains a linked list of key-value pairs. The key is used to compute an index in the array of buckets, and the value is stored in the corresponding bucket.
Here is an example of a basic HashMap implementation in C++:
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<string, int> myMap;
myMap["apple"] = 5;
myMap["banana"] = 3;
myMap["orange"] = 2;
cout << myMap["apple"] << endl;
cout << myMap["banana"] << endl;
cout << myMap["orange"] << endl;
if (myMap.count("mango") > 0) {
cout << "Mango is in the map!" << endl;
} else {
cout << "Mango is not in the map!" << endl;
}
return 0;
}
/*
OUTPUT
5
3
2
Mango is not in the map!
*/In the above example, unordered_map is a C++ STL container that provides a hash table implementation of the map interface. The keys are strings, and the values are integers. The map is initially empty, but you can add key-value pairs to it using the [] operator. To retrieve the value associated with a key, you can use the same operator. The count() function is used to check if a key exists in the map.
Keep in mind that the C++ unordered_map is not thread-safe by default, and you may need to use other libraries or ways to make it thread-safe.
In case you want to use a hashmap in C, you can use the hashmap.h library which is a simple and efficient hashmap implementation in C. It is a header-only library and can be used by including the hashmap.h file.
Sum of triplet in an array core Java.
In Core Java, you can find the sum of a triplet in an array by using a nested loop to check all possible combinations of three elements in the array. Here’s an example:
public class TripletSum {
public static void main(String[] args) {
int[] arr = {1, 4, 45, 6, 10, 8};
int sum = 22;
boolean found = false;
for (int i = 0; i < arr.length - 2; i++) {
for (int j = i + 1; j < arr.length - 1; j++) {
for (int k = j + 1; k < arr.length; k++) {
if (arr[i] + arr[j] + arr[k] == sum) {
System.out.println("Triplet is " + arr[i] + ", " + arr[j] + ", " + arr[k]);
found = true;
}
}
}
}
if (!found) {
System.out.println("No triplet found");
}
}
}
/*
OUTPUT
Triplet is 4, 10, 8
*/
In this example, the main method takes an array arr and an integer sum as input. It then uses three nested loops to check all possible combinations of three elements in the array. If any combination of three elements equals the given sum, it prints the triplet and sets the found variable to true. If no such triplet is found, it prints “No triplet found”.
Keep in mind that this solution has a time complexity of O(n^3) as it uses three nested loops. To improve the performance, you can sort the array and then use two pointers technique which will bring down the time complexity to O(n^2)
Find the angle between the hours hand and minute hand in clock when it’s 3:15.
To find the angle between the hour hand and the minute hand of a clock when it’s 3:15, we can use the following steps:
At 3:15, the minute hand is at the 12th minute mark, which is at an angle of 90 degrees from the 12 o’clock position.
The hour hand is also at the 3rd hour mark, which is at an angle of 7.5 degrees from the 12 o’clock position (since there are 12 hours on a clock and 360 degrees in a full rotation, each hour mark is at an angle of 360/12 = 30 degrees from the 12 o’clock position).
To find the angle between the two hands, we can subtract the angle of the hour hand from the angle of the minute hand, and take the absolute value of the result.
So in this case, the angle between the hour and minute hand is |90 – 7.5| = 82.5 degrees.
Keep in mind that this is a simplified solution, as the angle between the hour hand and the minute hand on an actual clock may be affected by the “wobble” of the hands, which is caused by the gears inside the clock.
Puzzle of rod cutting.
The rod cutting puzzle is a classic problem in dynamic programming. The problem goes as follows:
You have a rod of length n inches and you need to cut it into smaller pieces. Each piece has a certain value, and you want to maximize the total value of the pieces you cut. However, there’s a cost associated with each cut, and you want to minimize the total cost. The problem is to determine the optimal way to cut the rod.
One common approach to solving this problem is to use a bottom-up dynamic programming algorithm. The basic idea is to build a table where each cell contains the maximum value that can be obtained by cutting a rod of length i with j cuts. The table is filled in a bottom-up manner, using the following recurrence relation:
V[i,j] = max(V[i,j], V[i-k,j-1] + P[k])
where V[i,j] is the maximum value that can be obtained by cutting a rod of length i with j cuts, P[k] is the price of a rod of length k, and k is the length of the piece cut in the current step.
Here is an example of C++ code to implement the rod cutting problem using dynamic programming:
Why doesn’t Java have pointers?
As Java is general purpose Object Oriented Programming language so it doesn’t have pointers.
Query to find second highest employee salary.
SELECT name, MAX(salary) AS salary FROM employee WHERE salary <> (SELECT MAX(salary) FROM employee);
OR
Common Table Expression
WITH T AS ( SELECT * DENSE_RANK() OVER (ORDER BY Salary Desc) AS Rnk FROM Employees) SELECT Name FROM T WHERE Rnk=2
Puzzles and questions revolving around linked list and tree.
Reverse a linked list: Given the head of a singly linked list, reverse the order of the elements in the list.
Merge two sorted linked lists: Given the heads of two sorted linked lists, merge them into a single, sorted linked list.
Check if a linked list has a cycle: Given the head of a linked list, determine if the list contains a cycle (i.e. if any node is visited more than once while traversing the list).
Find the middle element of a linked list: Given the head of a linked list, find the middle element of the list.
Find the nth element from the end of a linked list: Given the head of a linked list and an integer n, find the nth element from the end of the list.
Check if a binary tree is balanced: Given the root of a binary tree, determine if the tree is balanced (i.e. the difference in height between the left and right subtrees is at most 1).
Find the lowest common ancestor of two nodes in a binary tree: Given the root of a binary tree and two nodes in the tree, find the lowest common ancestor of the two nodes.
Check if a binary tree is a binary search tree: Given the root of a binary tree, determine if the tree is a binary search tree (i.e. if the left subtree contains only nodes with smaller keys and the right subtree contains only nodes with larger keys).
Find the maximum depth of a binary tree: Given the root of a binary tree, find the maximum depth of the tree (i.e. the longest path from the root to a leaf).
Traverse a binary tree in pre-order, in-order and post-order: Given the root of a binary tree, implement the three different types of tree traversals.
These are some of the common puzzles and questions revolving around linked list and tree data structures. They are designed to test your understanding of the basic concepts and operations of these data structures, and to help you practice problem-solving skills.
Explain a OOP pattern design and also with a problem design.
One of the most important and widely used design patterns in object-oriented programming (OOP) is the Factory Method pattern.
The Factory Method pattern is a creational design pattern that provides an interface for creating objects in a superclass, but allows subclasses to alter the type of objects that will be created. It is used to create objects without specifying the exact class of object that will be created.
The Factory Method pattern consists of:
An interface for creating objects, which is defined by the Creator class.
Concrete classes that implement the Creator interface and define the factory method that creates objects.
Concrete classes that implement the Product interface and define the objects that will be created.
What data structures you know and have worked with?
As a language model, I have been trained on a vast amount of text data and can answer questions on many data structures. Here is a list of some of the data structures that I am familiar with and have worked with:
Arrays: A collection of elements stored in contiguous memory locations.
Linked Lists: A collection of elements called nodes, where each node has a reference to the next element.
Stacks: A last-in-first-out (LIFO) data structure, where elements are added and removed from the top of the stack.
Queues: A first-in-first-out (FIFO) data structure, where elements are added to the back and removed from the front.
Trees: A hierarchical data structure that consists of nodes, where each node can have one parent and multiple children.
Graphs: A collection of nodes and edges, where nodes represent entities and edges represent relationships between the entities.
Hash Tables: A data structure that uses a hash function to map keys to indices in an array, allowing for efficient insertion, deletion, and lookup operations.
Heaps: A specialized tree-based data structure, where elements are organized in a specific order to support fast extraction of the minimum/maximum element.
Tries: A tree-like data structure that is used for efficient retrieval of keys in a large set of strings.
Bloom Filters: A probabilistic data structure that is used for testing whether an element is a member of a set or not.
I can also provide examples and explain the use cases, time and space complexity, advantages and disadvantages of these data structures.
Reversing a sentence without reversing its words.
Reversing a sentence without reversing its words can be done in several ways, one common approach is to first use the split() method to separate the words in the sentence into an array, then use the reverse() method to reverse the order of the words in the array and finally use the join() method to join the words back into a sentence.
Here is an example in C++ :
#include<bits/stdc++.h>
using namespace std;
string reverseSentence(string sentence)
{
int l = sentence.length();
string ans = "";
for (int i = l - 1; i >= 0; i--) {
if (sentence[i] == ' ') {
int j = i + 1;
while (sentence[j] != ' ' && j < l) {
ans += sentence[j];
j++;
}
ans += " ";
}
}
int j = 0;
while (sentence[j] != ' ' && j < l) {
ans += sentence[j];
j++;
}
return ans;
}
int main()
{
string sentence = "Hello World";
cout<<reverseSentence(sentence);
return 0;
}
/*
OUTPUT
World Hello
*/String manipulation like palindrome, matrices.
Palindrome: A palindrome is a word, phrase, number, or other sequence of characters that reads the same forwards and backwards. For example, “madam” is a palindrome. To check if a string is a palindrome, you can reverse the string and compare it to the original. If they are the same, then the string is a palindrome.
Matrix: A matrix is a two-dimensional array of numbers. Matrices are often used in computer science and mathematics to represent and manipulate data. Common operations on matrices include matrix addition, multiplication, and finding the determinant. To manipulate matrices in Python, you can use the NumPy library which has a lot of matrix manipulation functions.
In summary, String manipulation is the process of manipulating strings using different techniques like reversing, slicing, splitting, joining etc. and Palindrome is one of the examples of String manipulation where we check if a given string is a palindrome or not. And Matrix is a two-dimensional array of numbers that are used to represent and manipulate data and are commonly used in computer science and mathematics.
#include<stdio.h>
int main(){
char str[100];
int len=0,palindrome;
gets(str);
for(len=0;len!='\0';len++);
for(int i=0;i<len/2;i++){
if(str[i]!=str[len-i-1]){
palindrome=1;
break;
}
}
if(palindrome)
printf("Not Palindrome");
else
printf("Palindrome");
}
/*
OUTPUT
545
Palindrome
*/Code for web page using selenium web driver.
Here is an example of how to use Selenium WebDriver in Python to automate a web page:
from selenium import webdriver
# create a new Firefox browser instance
driver = webdriver.Firefox()
# navigate to a website
driver.get("https://www.example.com")
# find an element on the page by its id
element = driver.find_element_by_id("some_id")
# interact with the element
element.click()
# find an element by its class name
elements = driver.find_elements_by_class_name("some_class")
# interact with the elements
for e in elements:
print(e.text)
# close the browser
driver.quit()This code will open a Firefox browser, navigate to the website “https://www.example.com“, find an element on the page with the id “some_id” and click on it, find multiple elements with the class name “some_class” and print their text and close the browser.
You can also use other web browsers like Chrome, Edge, Safari etc by replacing the browser instance with corresponding browser instance like webdriver.Chrome() or webdriver.Edge() etc and also need to provide the driver path before using it.
It’s important to note that you need to have the Selenium WebDriver installed and also the appropriate browser driver (like geckodriver for Firefox) to run this code.
Max chain in an array.
A “max chain” in an array refers to a sequence of elements in the array such that each element in the sequence is greater than or equal to the previous element. The length of this chain is known as the “max chain length.”
Here’s an example of how to find the max chain length in an array using Python:
def max_chain(arr):
max_len = 1
curr_len = 1
for i in range(1, len(arr)):
if arr[i] >= arr[i-1]:
curr_len += 1
else:
max_len = max(max_len, curr_len)
curr_len = 1
return max(max_len, curr_len)
arr = [1, 5, 3, 4, 2, 6, 7, 8, 9]
print(max_chain(arr))
/*
OUTPUT
5
*/This will output 5, which is the length of the max chain in the array [1, 5, 3, 4, 2, 6, 7, 8, 9]. In this case, the max chain is [5, 6, 7, 8, 9].
This code will iterate through the array and compare each element with the previous one. If the current element is greater than or equal to the previous element, it will increment the current chain length by 1. If the current element is less than the previous element, the current chain is ended and max_len is updated with the max of current chain length and max_len.
It’s important to note that this implementation only considers the elements in the array, not their indices. If the problem demands considering the indices too, we can make use of additional variable to store the indices and update that variable along with max_len variable.
Minimize the heights of tower.
To minimize the heights of a tower, there are several strategies that can be used:
Use lightweight materials: Using lightweight materials such as aluminum or composite materials can reduce the weight of the tower, which in turn can reduce the height required to support the structure.
Optimize the design: Using advanced design techniques such as finite element analysis can help to optimize the design of the tower, reducing the amount of material required and minimizing the height.
Use guy wires: Guy wires can be used to provide additional support for the tower, reducing the height required to support the structure.
Use multiple smaller towers: Instead of building one tall tower, multiple smaller towers can be used to achieve the same coverage, reducing the overall height of the towers.
Use existing structures: If possible, the tower can be built on top of existing structures such as buildings or hills, reducing the height required for the tower.
Related to find occurrences in a string, reverse the word of a string.
To find occurrences of a specific word in a string, you can use the str.count() method or the str.find() method. The str.count() method returns the number of occurrences of the specified word, while the str.find() method returns the index of the first occurrence of the specified word.
To reverse the words of a string, you can use the str.split() method to split the string into a list of words, then use the list.reverse() method to reverse the order of the words, and finally use the str.join() method to join the reversed list of words back into a string.
original_string = "This is a test string"
#split the string into a list of words
words = original_string.split()
#reverse the order of the words
words.reverse()
#join the reversed list of words back into a string
reversed_string = " ".join(words)
print(reversed_string)
# Output: "string test a is This"
Alternatively, you can use slicing to reverse the words of a string.
original_string = "This is a test string"
# split the words
words = original_string.split()
# reverse the words
reversed_words = [word[::-1] for word in words]
# join the reversed words
reversed_string = " ".join(reversed_words)
print(reversed_string)
# Output: "sgnirts tset a si sihT"
Related to find occurrences in a string, reverse the word of a string.
Here’s an example of a Python program that replaces adjacent duplicate characters appearing in a string array with a single character:
def remove_duplicates(string_array):
result = []
for string in string_array:
new_string = ""
last_char = ""
for char in string:
if char != last_char:
new_string += char
last_char = char
result.append(new_string)
return result
string_array = ["aabbccddeeffgghhiijj", "kkllmmnnooppqqrrsstt", "uuvvwwxxyyzz"]
print(remove_duplicates(string_array))
# OUTPUT -['abcdefghij', 'klmnopqrst', 'uvwxyz']The time complexity of this program is O(nm), where n is the number of strings in the array and m is the length of the longest string. This is because for every string in the array, we iterate through every character in the string to check for duplicates. Since we are iterating through each character of each string, the overall time complexity is O(nm).
Check if two trees are mirror images of each other.
One way to check if two trees are mirror images of each other is to perform a pre-order traversal of both trees and compare the traversed elements. A pre-order traversal visits the root node first, then the left subtree, and finally the right subtree. If the traversed elements of the two trees are the same, but in reverse order, then the trees are mirror images of each other.
Reverse a stack using recursion.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void pushAtBottom(stack<int> &st,int n){
if(st.empty()){
st.push(n);
return;
}
else{
int top = st.top();
st.pop();
pushAtBottom(st,n);
st.push(top);
}
}
void reverseStack(stack<int> &st) {
if(st.empty())
return;
int num = st.top();
st.pop();
reverseStack(st);
pushAtBottom(st,num);
}
int main() {
stack<int> st;
for(int i=1;i<5;i++){
st.push(i);
}
reverseStack(st);
cout<<"Reverse Stack"<<endl;
while(!st.empty()){
cout<<st.top()<<" ";
st.pop();
}
return 0;
}
/*
OUTPUT
Reverse Stack
1 2 3 4
/*
write a code to check if a given linked list contains a loop.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node* next;
Node(int data){
this->data=data;
this->next=NULL;
}
};
void push(Node* &head,int data){
Node* temp=new Node(data);
temp->next=head;
head=temp;
}
Node* detectLoop(Node* &head){
if(head==NULL || head->next==NULL){
return head;
}
Node* slow=head;
Node* fast=head;
while(slow!=NULL && fast!=NULL){
fast=fast->next;
if(fast!=NULL){
fast=fast->next;
}
slow=slow->next;
if(fast==slow){
return slow;
}
}
return NULL;
}
int main() {
Node* head=NULL;
push(head, 20);
push(head, 4);
push(head, 15);
push(head, 10);
head->next->next->next->next = head;
if (detectLoop(head))
cout << "Loop Found";
else
cout << "No Loop Found";
return 0;
}
/*
OUTPUT
Loop Found
*/Write a recursive function to find the factorial of a given number
#include <stdio.h>
int fact(int);
int main()
{
int n=5;
printf("%d",fact(n));
return 0;
}
int fact(int n){
if(n==1){
return 1;
}
return n*fact(n-1);
}
/*
OUTPUT:
120
*/
Automata Fixing