Interview for CA Technologies in Pune on 12 May 2018
Question 1 : Find if the given linked list has a loop?
Solution : Though it is vary common, but still I am putting it here.
One is, you can maintain 2 pointers & start them such that each pointer has different
speed & if they meet then it means that there is a loop. But this will take time
depending on the number of nodes in the list to iterate through.
Second is, if you have time constraints but have enough space to store all the
nodes then store all the nodes in a hashset while iterating through the list, if you get
false while adding then it the node from where loop is starting.
Third is, if your node has any property to define if it is visited or not then it will make it
fast with no requirement of any above ways.
Question 2 : What is singleton? Write a class.
Solution : You can get many answers on this as there are many ways for this but here
purpose is to understand if you know the purposes of those ways.
So you can tell about ways with their reasons given here.
Question 3 : How to find any element in an array?
Solution : In simple, you can iterate through the array with time complexity as O(n).
Second, if possible then you can sort the array & do the binary search & its
complexity will be same as that of sorting algorithm used here.
Question 4 : How to print the elements in an array without using loop, order doesn't matter?
Solution : Solution was given to me, & that is to use recursion.
Question 5 : What is decorator pattern?
Solution : See here.
Question 6 : How will you create your own linked list & provide the method to insert the data.
Solution : Though I was asked to provide the solution by using only one pointer but I feel that
way the insertion operation will become O(n) rather being O(1), and in interview I
was expected to make the logic complex & not simple as using 2 pointers, logic
was getting simple, though I didn't mention at that time that it is also efficient. But
was required to give the logic using one pointer only, so you can mention the
reason that using 2 pointers will make the logic simple, performance efficient & will
also not be taking significant memory space while using 1 pointer only it will surely
reduce the insert operation performance then why to use such?
So below is basic -
/**
* Below using 2 pointers, one to point the start position and
* second to point the current position in list.
* One can skip the use of 2nd pointer(temp), like this can be put in
* the interviews, then you can create that second pointer in the
* insert method. But it will cause performance issue as on every
* insert you have to iterate through the list & insertion will be
* O(n) rather being as O(1)
* @author nitin
*
* @param <T>
*/
public class LinkedList<T> {
Node<T> start;
Node<T> temp;
Node<T> curr;
public void insert(T data) {
if(start == null) {
start = new Node<T>();
temp = start;
curr = start;
} else {
// Below statement can be used if 'temp' is local variable here.
// temp = start;
while(temp.next != null) {
temp = start.next;
}
temp.next = new Node<T>();
temp = temp.next;
}
temp.data = data;
}
public T getData() {
if(curr == null)
return null;
T data = curr.data;
curr = curr.next;
return data;
}
private class Node<E> {
E data;
Node<E> next;
}
}
Question 7 : How to find the nth bit is set or not, using bit operations?
Solutions :
public class KthBitSet {
public static void main(String[] args) {
int num = 25;
int a = num;
int checkBitStartLoc = 5;
int checkBitEndLoc = 4;
int bitsCount = Integer.bitCount(num);
int len = Integer.toBinaryString(num).length();
if(bitsCount == 0)
System.exit(1);
// Bits in num
System.out.println("Binary Value : " + Integer.toBinaryString(num));
// Bits in 1 after left shifting the bits by checkBitEndLoc-1
// Shifting the bits by the count as 1 less because then the position
// of 1 in resulting number will at the required place as shown below.
System.out.println("After shifting 1 to check from last : "
+ Integer.toBinaryString(1 << (checkBitEndLoc-1)));
// If wants to check the bit at the given location is set or not.
// And this location is considered from the last.
System.out.println("If value > 0 then required bit from end is set : "
+ (a & (1 << (checkBitEndLoc-1))));
// If the location of the bit is from the start then
System.out.println("If value > 0 then required bit from start is set : "
+ (a & (1 << (len-checkBitStartLoc))));
// If the location of the bit is from the start and don't want to use
// above way then
num = (1 << len) >> checkBitStartLoc;
System.out.println("If value > 0 then required bit from start is set : "
+ (a & num));
// If the location of the bit is from the start and don't want to use
// above bit operations & not looking to save the memory & performance then
String str = Integer.toBinaryString(a);
if(str.charAt(checkBitStartLoc-1) == '1')
System.out.println("SET.....");
}
}
Can discuss such various ways as per the expectations.
Question 8 : Find the number in an array using recursion.
Solution : One can write a simple code for recursion & put the break condition with return
value. But I really don't understand its any purpose except to test your thought
process.
Solution : Though it is vary common, but still I am putting it here.
One is, you can maintain 2 pointers & start them such that each pointer has different
speed & if they meet then it means that there is a loop. But this will take time
depending on the number of nodes in the list to iterate through.
Second is, if you have time constraints but have enough space to store all the
nodes then store all the nodes in a hashset while iterating through the list, if you get
false while adding then it the node from where loop is starting.
Third is, if your node has any property to define if it is visited or not then it will make it
fast with no requirement of any above ways.
Question 2 : What is singleton? Write a class.
Solution : You can get many answers on this as there are many ways for this but here
purpose is to understand if you know the purposes of those ways.
So you can tell about ways with their reasons given here.
Question 3 : How to find any element in an array?
Solution : In simple, you can iterate through the array with time complexity as O(n).
Second, if possible then you can sort the array & do the binary search & its
complexity will be same as that of sorting algorithm used here.
Question 4 : How to print the elements in an array without using loop, order doesn't matter?
Solution : Solution was given to me, & that is to use recursion.
Question 5 : What is decorator pattern?
Solution : See here.
Question 6 : How will you create your own linked list & provide the method to insert the data.
Solution : Though I was asked to provide the solution by using only one pointer but I feel that
way the insertion operation will become O(n) rather being O(1), and in interview I
was expected to make the logic complex & not simple as using 2 pointers, logic
was getting simple, though I didn't mention at that time that it is also efficient. But
was required to give the logic using one pointer only, so you can mention the
reason that using 2 pointers will make the logic simple, performance efficient & will
also not be taking significant memory space while using 1 pointer only it will surely
reduce the insert operation performance then why to use such?
So below is basic -
/**
* Below using 2 pointers, one to point the start position and
* second to point the current position in list.
* One can skip the use of 2nd pointer(temp), like this can be put in
* the interviews, then you can create that second pointer in the
* insert method. But it will cause performance issue as on every
* insert you have to iterate through the list & insertion will be
* O(n) rather being as O(1)
* @author nitin
*
* @param <T>
*/
public class LinkedList<T> {
Node<T> start;
Node<T> temp;
Node<T> curr;
public void insert(T data) {
if(start == null) {
start = new Node<T>();
temp = start;
curr = start;
} else {
// Below statement can be used if 'temp' is local variable here.
// temp = start;
while(temp.next != null) {
temp = start.next;
}
temp.next = new Node<T>();
temp = temp.next;
}
temp.data = data;
}
public T getData() {
if(curr == null)
return null;
T data = curr.data;
curr = curr.next;
return data;
}
private class Node<E> {
E data;
Node<E> next;
}
}
Question 7 : How to find the nth bit is set or not, using bit operations?
Solutions :
public class KthBitSet {
public static void main(String[] args) {
int num = 25;
int a = num;
int checkBitStartLoc = 5;
int checkBitEndLoc = 4;
int bitsCount = Integer.bitCount(num);
int len = Integer.toBinaryString(num).length();
if(bitsCount == 0)
System.exit(1);
// Bits in num
System.out.println("Binary Value : " + Integer.toBinaryString(num));
// Bits in 1 after left shifting the bits by checkBitEndLoc-1
// Shifting the bits by the count as 1 less because then the position
// of 1 in resulting number will at the required place as shown below.
System.out.println("After shifting 1 to check from last : "
+ Integer.toBinaryString(1 << (checkBitEndLoc-1)));
// If wants to check the bit at the given location is set or not.
// And this location is considered from the last.
System.out.println("If value > 0 then required bit from end is set : "
+ (a & (1 << (checkBitEndLoc-1))));
// If the location of the bit is from the start then
System.out.println("If value > 0 then required bit from start is set : "
+ (a & (1 << (len-checkBitStartLoc))));
// If the location of the bit is from the start and don't want to use
// above way then
num = (1 << len) >> checkBitStartLoc;
System.out.println("If value > 0 then required bit from start is set : "
+ (a & num));
// If the location of the bit is from the start and don't want to use
// above bit operations & not looking to save the memory & performance then
String str = Integer.toBinaryString(a);
if(str.charAt(checkBitStartLoc-1) == '1')
System.out.println("SET.....");
}
}
Can discuss such various ways as per the expectations.
Question 8 : Find the number in an array using recursion.
Solution : One can write a simple code for recursion & put the break condition with return
value. But I really don't understand its any purpose except to test your thought
process.
