Find products of all locations of an array except its own location

In this algorithm we are asked to find the product of all elements in the array expect the location where the counter is pointing currently.

For example:

1. If array looks like this 1, 2, 3, 4, 5 where 1 is at location 0, 2 is at location 1 and so on.
2. The the product array will look like: 120, 60, 40, 30, 25.
3. 120 is the product of 2 * 3, * 4 * 5
4. 60 is the product of 1 * 3 * 4 * 5 and so on.

Approach:

1. We will first find the product of all elements by going through the entire array. Then at each location we will divide the value found at that location.
2. For example: 120 is product of 1 * 2 * 3 * 4 * 5
3. For location 0 we will do 120/1 so at location 0 we have 120.
4. For location 1 we will do 120/2 so at location 1 we will have 60
5. For location 2 we will do 120/3 so at location 1 we will have 40

Algorithm:

1. Initialize a variable product = 1; 
2. Initialize a variable i at 0 
3. Multiply product with a[i] and increment i by 1. 
4. Repeat step 3 till end of array a is reached. 
5. Initialize a variable i at 0 
6. Do product/a[i] and increment i by 1. Store the result in a array location. 
7.  Repeat step 6 till end of array a is reached.

Implementation:

 void arr(int a[MAX])
{
 int product = 1;

 for(int i=0;i < MAX;i++)
   product = product * a[i];

 for(int i=0;i < MAX;i++)
   a[i] = product/a[i];
}

int main()
{
 int a[4] = {1,2,3,4};

 for(int i=0;i < 4;i++)
   std::cout <<  a[i] <<  "\t";
 arr(a);

 std::cout <<  std::endl;

 for(int i=0;i < 4;i++)
   std::cout <<  a[i] <<  "\t";

 getch();
 return 0;
}

Complexity:
O(n) for the time complexity since we iterate through the entire array twice.
O(1) for space complexity.

You might also like:
Find White Spaces in Character Array
Find a character in the String
Number is prime or not
Finding Absolute Value
Notes on Sorting and Searching Algorithms
Common String Functions
Reverse a String
Find a cycle in the Linked List
Find a binomial co-efficient
Remove duplicates from the array

Telephonic phone technical interview questions

Telephonic phone technical interview questions - Part 2
Counting sort algorithm
B-Tree

How will you reverse a string

Reversing a string is a simple operation and it is often asked in telephonic interviews or first round of interviews. If input string is 'Hello World' then reversed string will look like 'dlroW olleH'. If the string is stored in an array then the operation is very simple because we just need to swap the characters at two pointers.

Algorithm:

1. Initialize two pointers one at location 0 and other at length of the string. Let's name them i and j. 
2. If location of i is less than or equal to location of j then swap the characters at location i and j. 
3. Increment i counter. 
4. Decrement j counter. 
5. Repeat steps 2, 3, 4 till the condition in step 2 is met.

Implementation

reverseString()
{
 String names[] = {"a","b","c","d","e","f"};
 int i=0,j=5;
 String temp;

 while(i<=j)
 {
    temp = names[i];
    names[i] = names[j];
    names[j] = temp;
    i++;
    j--;
 }
}

Complexity: 
The time complexity of this algorithm is O(n) since we have to go through all the locations of the array or string. The space complexity is O(1) since we didn't need additional space for this.

You might also like:
Find White Spaces in Character Array
Find a character in the String
Number is prime or not
Finding Absolute Value
Notes on Sorting and Searching Algorithms
Common String Functions
Product of all array location expect its own
Find a cycle in the Linked List
Find a binomial co-efficient
Remove duplicates from the array

Telephonic phone technical interview questions

Telephonic phone technical interview questions - Part 2
Counting sort algorithm
B-Tree

Serialization and Deserialization in Java

Imagine that you have to send a java object to someone via a network or you want to store it in the db or in memory. If you are looking to perform any of these operations then Serialization will help you.
Serialization will transform the object to bytes so that it can be stored in the DB or memory or sent via a network. Deserialization on the other hand, will transform the bytes to the object.

In java Serialization and Deserialization can be achieved by implementing 'Serializable' interface. It is a Marker interface in which the implementing class don't have to implement any functions of the interface.

In the following example 'Student' object contains name and id. Since the object is implementing 'Serializable' interface we can define 2 methods that will serialize and deserialize.

 //Define a class that needs to be serialized and de-serialized
public class Student implements Serializable {
    String sName;
    int sId;
}

Following serializeStudent method will write the object to the file stream that is named as 'Student.ser'. Similarly, deserializeStudent method will read the file stream and convert it to the Student object. 

Implementation:

   
//Serialize it 
public class serializeStudent {
   Student s = new Student();
   s.sName = “jack”;
   s.sId = 1;

   try {
       FileOutputStream fs = new FileOutputStream(“Student.ser”);
       ObjectOutputStream os = new ObjectOutputStream(fs);
       os.writeObject(s);
       os.close();
      }
}

 //DeSerialize it
public void deserializeStudent {
   FileInputStream fin = new FileInputStream(“FileName”);
   ObjectInputStream ion = new ObjectInputStream(fin);
   Student sObject = (student)oin.readObject();
}

You might also like:


Java Concepts

Java String concepts

Immutable classes in Java

Remove duplicates from the array

Telephonic phone technical interview questions

Telephonic phone technical interview questions - Part 2

Jersey Package Dependencies

Observable and Observer Interface

Servlet Filter

Servlet Client Request

Spring dependencies for Maven

Java String Operations

Telephonic interview Technical Questions

Question 1: Find top n queries.

This problem is best solved with hash map. However, there are iterative approaches too. Take a look at the 2 solutions below.

There are 3 approaches:

1. Let’s say there is a file and queries are stored in it with their date.
2. Get the queries till a specific date and sort them in descending order.
3. Top n entries will be your top n.

2nd Approach

1. Calculate hash code of each query.
2. In a hash map, put the hash code as the key value and its count as hash value.
3. Once all queries are covered, the one with top n largest hash values will be top n queries.

Space complexity: O(n)

Time complexity: O(n.logn)

Disadvantage: If there are millions of queries, you will have to calculate its hash code and store it before hand. Hashmap’s size might increase in value too.

---

Question 2: How will you find a random element between a range min to max

1. Call a standard random function of Math library. x = Math.Random();
2. Calculate the range: range = max - min;
3. Add 1 to range since max value will be excluded. range = range + 1;
4. Calculate sum by multiplying a random number to the range. sum = x * range (
5. Add min to sum to shift it to the start of min value. Random Element = sum + min.

---

Question 3: If you are given 2 binary trees how will you output them in ascending order.

1. Traverse them in order and store the values in 2 arrays.
2. Apply merge sort on them. It will output the array values in ascending order.

---

Question 4: Find if a point lies inside a triangle

To solve this, we will be using property of triangle were area of 3 triangles is equal to one

If the area of all 3 is equal to a bigger triangle then the point lies inside it.

Area((x1,y1) (x2,y2) (x,y)) + Area((x1,y1) (x3,y3) (x,y)) + Area((x1,y1) (x2,y3) (x,y) = Area((x1,y1) (x2,y2) (x3,y3)).

Find Area of triangle:

A1 = (x1 * (y2-y3) + x2 * (y1-y3) + x3 * (y1-y2))/2.0;

---

Question 5: How to find out if a number is multiple of 3 without using divide operator

1. Find number of odd bits that are set.
2. Find number of even bits that are set.
3. Find difference.  If the difference is a multiple of 3 then the number is 3’s multiple

---

Question 6: Function to check if singly LL is palindrome

1. Get the middle of the linked list.
2. Reverse the second half of the LL.
3. Iterate the first half and second half. Compare elements one by one. If element comparison matches then proceed to next element. Or else break.
4. If you reach end of both LL then it is a palindrome.

---

Question 7: Good Design Principles

1. It should be highly cohesive and loosely coupled
2. DRY (Don't Repeat Yourself) - Put Common values to public final constant
3. Don't put common code at one place for unrelated things.
4. Make variables private then update or change access modifier to protected or public
5. Follow open closed design principle: Open for extension, closed for modification
6. Follow IOC: Inversion Of Control. Dependency injection through some config instead of adding it in the code.
7. Favor composition over inheritance

---

Question 8: 4 OO Principles:

1. Abstraction
2. Polymorphism
3. Encapsulation
4. Inheritance

---

Question 9: BFS vs DFS

BFS should be avoided for the larger trees since it uses large amount of memory to tack all children of current node. DFS has lower memory requirements.

---

Question 10: Sorting Algos

1. If you have small number of elements then use insertion sorn.
2. If elements are > 100 then use Heap, merge, quicksort,
3. If elements are > 5000 then use external memory sorting algorithm.
4. nlogn algorithms are not stable since order is not maintained.
5. If you have uniform or random distribution then use bucket sort.
6. If you know the range of elements to be sorted then use counting sort.
7. For very large number of elements use multi-way merge sort or load the data into B-Tree and do inorder traversal.

---

Question 11: Searching Algos

1. Linear Search
2. Binary Search
3. Use self-organizing lists. Recently accessed elements moves to the front.

---

Question 12: What are dynamic arrays?

1. When array grows in size & reaches it capacity then its capacity is increased.
2. If size threshold is reached then its size is increased till its capacity is reached.

---

Question 13: B-Trees

1. Each node contains multiple elements/values
2. Internal node contains values.
3. Insertion, deletion, lookup are O(logn)
4. Use in case of range queries.

---

Question 14: Difference between HashSet, HashMap, HashTable:

1. HashSet has no mapping of the key value pairs. The elements are just added to it. They are not added in any order.
2. HashMap has the mapping of the key value pair. It is unsynchronized and hence, gives a better performance. It allows null for key value pairs. You can add null key value pairs, you will not get the NullPointerException.
3. HashTable is the mapping of the key value pair. Synchronized so only thread can operate on it. It doesn’t all null for the key value pair. It will return NullPointerException if we have such values.

---

Question 15: How to get 10 largest elements from the array?

1. We can use insertion sort 10 times and the top 10 elements will come up. It will be 10 * n complexity.
2. Or we could construct the min heap and then extract the top 10 elements out of it.
3. Or sort the file and then tail -10. This means the sorted file will contain the 10 largest elements at the bottom part.

---

Question 16: If we have an array of numbers and all of them are appearing even no. of times bult only one appear odd number of times. How will you find it?

Solution: xor all the numbers. The odd counted number will be the output.

2n+1 numbers are given and 2n are unique. Only one is not. So xor all the numbers and then result will be one number that was excluded.

Algorithmic approach: Sort->O(nlogn) and keep a count = 2n. For every new element load the counter and when you are scanning that particular element decrement the counter by 1. For element with count = 2n+1 the counter will be decremented to -1. Hence, we found the element.

You might also like:
Find White Spaces in Character Array
Find a character in the String
Number is prime or not
Finding Absolute Value
Notes on Sorting and Searching Algorithms
Common String Functions
Reverse a String
Product of all array location expect its own
Find a cycle in the Linked List
Find a binomial co-efficient
Remove duplicates from the array

Telephonic phone technical interview questions

Telephonic phone technical interview questions - Part 2
Counting sort algorithm
B-Tree

Common Design Questions

Here is the list of common design questions that are asked in technical interviews. 

1. Design a parking garage
2. Design a deck of cards
3. Design an aeroplane reservation system.
4. How would you design a chat system
5. Design Game of Life
6. Design Chess Game
7. Design a system for a parking lot
8. Design a poker game
9. Design a Farm with Object Oriented Concepts
10. Design a restaurant reservation system.
11. Design a JukeBox
12. Design a file system
13. Design a recommendation system
14. Design the Boggle Game. (Given a 4x4 character matrix, output all possible words by moving through the matrix)

Common differences asked in coding interviews

SAX Parser v/s DOM Parser

SAX Parser	DOM Parser
It is event based. Fires an event when it encounters opening tag, or element attribute.	Document Object Model. Creates in-memory tree representation of XML files and then parses them.
Good for large files because it reads large files in small parts.	Good for small files since entire XML is loaded in the memory.
Need to implement more methods for parsing.	It has good implementation of different parsing.

---

Stack V/s Heap

Stack	Heap
Allocation of memory is static in stack.	Allocation of memory is dynamic. If more memory is needed more space is allocated and vice-versa.
Each thread gets its own stack.	An application gets a heap of memory.
Scope of stack is till the thread execution. Once thread exits, stack is reclaimed.	Heap is reclaimed once the application exits.
It is faster since allocation and deallocation of memory is faster.	The allocation and deallocation of memory is slow in case of heap.
Once a function returns, stack is discarded.	Destructed manually or is Garbage collected.
Primitives are stored on stack, pass by values are also stored on stack.	Objects are stored on heap.

---

Trie v/s BST

Trie	Binary search tree
Lookup is O(m)	Lookup is O(logn)
Storage space is less because node share the content.	Nodes doesn’t share the content.
Number of internal nodes equals key length.	It doesn’t depend on key length, instead it depends upon what order the keys appear.

---

Primary Key v/s Unique Key

Primary Key	Unique key
Primary keys are indexed by clusters.	Their index is not clustered.
Primary constraint is applicable.	Unique constraint on a column of the table.
Only one per table.	A table can have more than 1 unique keys.
Could be combination of unique keys.	Cannot be a combination of different keys.

You might also like:

Find White Spaces in Character Array
Find a character in the String
Number is prime or not
Finding Absolute Value
Notes on Sorting and Searching Algorithms
Common String Functions
Reverse a String
Product of all array location expect its own
Find a cycle in the Linked List
Find a binomial co-efficient
Remove duplicates from the array

Telephonic phone technical interview questions - Part 2

Counting sort algorithm
B-Tree

Common String functions in C

It is very common to for the interviewer to ask a string question. Following blogpost will help you implement some of the string functions. It is not an extensive list but will give you a basic idea of what kind of questions can be asked.

1) Finding length of the string

It is a common phone interview question. The interviewer is checking your understand of strings and how you will parse them. You can start with the algorithm and then can continue with its implementation.

Algorithm:

1. Initialize length counter to 0.
2. Initialize a pointer to the start of the string.
3. If character at pointer location is not null('\0') then increment the length and pointer location.
4. Repeat step 3 till you find a character whose value is null.
5. The counter length at the end of the string will specify the string's length.

Implementation:

int len = 0;
char *ptr;
ptr = s;
while(*ptr!='\0')
{
       len++;
       ptr++;
}

---

2) Copying strings with the help of arrays

This is another common interview question which is often asked in phone interview or initial rounds of technical interviews. It is asking to copy one string to another and both strings are represented as arrays.

Algorithm:

1. Initialize a length counter to 0 and pointer to the the first location in the source array.
2. If character at pointer location is not null then copy the character at target[len], where len is the pointer location of target array.
3. Increment the source pointer and target pointer.
4. Repeat steps 2 and 3 till the pointer in the source location is null

Implementation:

void func(char source[],char target[])
{
int len = 0;
char *ptr;
ptr = source;
while(*ptr!='\0')
{
       //*target = *source;
       target[len++] = *ptr;
       ptr++;
}
target[len++] = '\0';
std::cout << target << std::endl;
}

Complexity:

O(M + N) where M is the length of source string, and N is the length of target string.

---

3) Concatenating the strings

It will append one string to the end of another. If string1 = 'hello ' and string2 = 'world' then concatenating string2 to string1 will result in 'hello world'

Algorithm:

1) Point one pointer to start of string1 and another to the start of string2

2) Move pointer one till you encounter end of string1.

3) Then append characters from string2 to string1 one by one. Meanwhile move pointers along by one location at a time.

4) At the end append a null character.

void func(char *source,char *target)
{
int len = 0;
char *ptr_s,*ptr_t;
ptr_s = source;
while(*ptr_s!='\0')
{
       source++;
       ptr_s++;
}
ptr_t = target;
while(*ptr_t!='\0')
{
       *source = *ptr_t;
       source++;
       ptr_t++;
}
*source = '\0';
}

---

4) Comparing the strings

It will compare the strings and displays if strings match or not.

Algorithm:

1) Initialize pointers at the start of string1 and string2. Initialize a flag to zero.

2) If characters at location i match in both the strings then move the pointers to next location.

3) Keep on repeating the step 2 till you either reach the end of string or till you don't find a match.

4) If you don't find a match then break loop and change the flag value to 1.

5) If flag is zero then output 'Strings match' or else 'Strings don't match'.

Implementation:

void func(char *source,char *target)
{
int len = 0,flag=0;

char *ptr_s,*ptr_t; ptr_s = source; ptr_t = target; while(*ptr_s!='\0' && *ptr_t!='\0') { if(*ptr_s != *ptr_t) { flag = 1; break; } ptr_s++; ptr_t++; } if(flag==0) std::cout << "String matches" << std::endl; else std::cout << "String does not matches" << std::endl; }

---

5)  String matching brute force

It will search for a pattern in string in a brute force manner. 

Algorithm: 
1) Find of string and pattern. 
2) Intialize a counter1 and counter. 
3) If character a location counter is found then increment both counters or else increment only counter 1. 
4) If counter2 matches the length of pattern then the match is found or else not. 
5) Repeat steps 3,4 till end of input string. Implementation:

Implementation:
char string[] = {'B','o','x','o','x','m','\0'};// "Box";
char pattern[] = {'o','x','\0'};//"ha";
 
int len1 = strlen(string);
int len2 = strlen(pattern);
int flag = 0;
int count = 0;
 
std::cout << len1 << std::endl;
std::cout << len2 << std::endl;
 
int curr = 0;
int curr1 = 0;
while(curr != len1)
{
       if(string[curr] != pattern[curr1])
               curr++;
       else if(string[curr] == pattern[curr1])
       {
               curr++;
               curr1++;
       }
       if(curr1 == len2)
       {
               flag = 1;
               curr1 = 0;
               count++;
       }
}
 
if(flag == 0)
       std::cout << "String not matching\n";
else
       std::cout << "String matching\n" << count;

You might also like:

Find White Spaces in Character Array

Find a character in the String

Number is prime or not

Finding Absolute Value

Notes on Sorting and Searching Algorithms

Reverse a String

Product of all array location expect its own

Find a cycle in the Linked List

Find a binomial co-efficient

Remove duplicates from the array

Telephonic phone technical interview questions

Telephonic phone technical interview questions - Part 2

Counting sort algorithm

B-Tree