sriniatiisc
BAN USER- 0of 0 votes
AnswersQ: Given a collection of records which have fields like first name, last name, describe how would you store them in a hash table. Each object passed is to be stored in the hash table and the key has to be returned for subsequent retrieval.
- sriniatiisc in India
A: Explained about how hash tables work, hash function, what should be the table size (prime number), organization of the hash tables(whether each location in the table stores set of values or single value), from there moved on to collision, collision resolution techniques like open addressing, linear chaining etc.| Report Duplicate | Flag | PURGE
Myntra.com Software Engineer / Developer Hash Table - 1of 1 vote
AnswersQ: How would you print 1000 factorial(1000!). The hint he gave was 70! = 1.19785717 × 10 **100 which does not fit in any data type.
- sriniatiisc in India
A: Given that we just have to compute the factorial and print the value, loop over from 1000 to 1 and keep on accumulating the product. But pretty soon, the intermediate product wont fit in any data type and data truncation happens.
The trick is to represent the intermediate product as linked lists and then keep multiplying the numbers in a loop from 1000 to 1
Lets say the intermediate product you obtained is 125 and you want to multiply with 3. Represent the product as
5->2->1
And multiply the product with 3.
He agreed to this answer. He did not ask me to code this.| Report Duplicate | Flag | PURGE
Myntra.com Software Engineer / Developer Data Structures - 0of 0 votes
AnswersQ:Given an input array of unsorted elements, sort the array using binary search technique.
- sriniatiisc in India
A: Build a bst out of the unsorted array by looping over the array and inserting each element to the tree.
Once you have the bst do inorder traversal.| Report Duplicate | Flag | PURGE
Myntra.com Software Engineer / Developer Arrays
I have come up with a solution which you can be found here. thought-works.blogspot.in/2013/12/object-oriented-design-for-library-to.html
- sriniatiisc December 31, 2013Assumptions:
1) The student id are in the range (0-max role number for students) with out any gaps.
2) To achieve constant insertion time to the map we use studentId as the key. So we assume that we have a hashmap with initial capacity = max role number for students
3) test scores are in the range of [0-100]
Approach:
Lets say there is an object called TestResult which encapusulates testdate, studentId, testscore. These test results are stored in a hashmap with student id as the key
Map<Integer, List<TestResult> perStudentResults = new HashMap<Integer,List<TestResult>
Before we declare the score per student, heapify the results per student as a max heap. Once made as a max heap, get the max element 5 times and perform the average of the score and display it as the score.
Complexity:
If there are n students p results for each students,
* Insertion to the hashmap for n student records -> O(n*p)
* Heapify operation for p elements can be done in O(p). The heapify operation for n student is again n* O(p) = O(n*p)
* For each student
for i = 1 to 5
* retrieve the max element and rearrange the heap = O(logp)
* Compute the average so far
end
end
Complexity here will be O(n*5logp) = O(nlogp)
* finally the complexity is O(n*p)
This is a solution using java Generics. The idea is you can create Furniture made of Metal or Wood. So in future new furniture types can be added and new material types can be added while avoiding class explosion
public abstract class Furniture<T extends Material> {
private String furnitureType;
private T material;
public Furniture() {
};
public Furniture(String type, T material) {
this.furnitureType = type;
this.material = material;
}
public void fireTest() {
System.out.println("Fire Test: This is a " + furnitureType
+ " made of " + material.getClass().getSimpleName());
}
public void stressTest() {
System.out.println("Stress Test: This is a " + furnitureType
+ " made of " + material.getClass().getSimpleName());
}
}
public class Table<T extends Material> extends Furniture<T> {
public Table(T material) {
super("Table", material);
}
}
public class Chair<T extends Material> extends Furniture<T> {
public Chair(T material) {
super("Chair", material);
}
}
public abstract class Material {
public static final String type= "UNKNOWN";
}
public class Metal extends Material{
public static final String type= "Metal";
}
public class Wooden extends Material{
public static final String type= "Wood";
}
//finallly furniture test
import java.util.ArrayList;
import java.util.List;
public class FurnitureTest {
public static void main(String[] args) {
Furniture f1 = new Table<Wooden>(new Wooden());
Furniture f2 = new Chair<Wooden>(new Wooden());
Furniture f3 = new Chair<Metal>(new Metal());
Furniture f4 = new Table<Metal>(new Metal());
List<Furniture> furnitures = new ArrayList<>();
furnitures.add(f1);
furnitures.add(f2);
furnitures.add(f3);
furnitures.add(f4);
for (Furniture furniture : furnitures) {
furniture.fireTest();
furniture.stressTest();
}
}
}
package arrays;
public class FingRepeatingAndMissingElement {
public static void main(String[] args) {
int a[] = { 0, 3, 5, 6, 5, 2, 1 };
for (int i = 0; i < a.length; i++) {
if (a[i] != 0) {
int j = Math.abs(a[i]);
a[j] *= -1;
}
}
int repeating_element = -1;
for (int k = 0; k < a.length; k++) {
if (a[k] > 0) {
repeating_element = a[k];
System.out.println("Repeating element is " + a[k]);
break;
}
}
if (repeating_element != -1) {
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += Math.abs(a[i]);
}
int missing_element = repeating_element - (sum - 21);
System.out.println("Missing element is " + missing_element);
}
}
}
h%t%t%p://thought-works.blogspot.in/2012/11/object-oriented-design-for-online.html
(remove % in the url and paste in the address bar)
A typical library has a set of books which the users can borrow for a certain period of time and return back. Users may choose to renew the return date if they feel they need to more time to read the book. We are trying here to design an online library.
The typical user actions with this online library would be
sign in/register
search books
borrow books
renew the return date for any of the books borrowed
view his profile(check his details, list of books he borrowed )
The online library should support all the above actions. It must keep track of the different books in the library currently available for users to borrow and also the books already borrowed bu users. Put it simply the inventory should be managed.
Going through the above description we can think of these components in the system:
User
Book
BorrowTxn -> record for the event for book b is borrowed by user u
InventoryManager -> manages the books in the library. Adds new books, remove books and respond to book search requests
LibraryManager-> Allows user interaction with the library like logging in, borrowing, renewal and return.
I have out the class diagram at
h%t%t%p://thought-works.blogspot.in/2012/11/object-oriented-design-for-library-to.html
(remove % in the url and paste)
I tried the design of a single elevator and extended that to multiple elevators scenario. Given that i am not able put class diagrams here i have put it here
h%t%t%p://thought-works.blogspot.in/2012/11/object-oriented-design-for-elevator-in.html
(remove % in the url and paste in the address bar )
This is one of the interesting questions and discussion on this would benefit many folks like us who want to learn design.
By asking to design SkyDrive kind of application, the interviewer wants to know how you can design a cloud based storage system.
The typical characterstics/requirements of a cloud storage system:
1) They are essentially file hosting services
2) Allow users to register/sign in
3) Allow registered users to buy more storage
4) Allow users to access/upload/delete the files on the cloud
5) Interact with a Distributed file system to store/delete/retrieve the files on the cloud
I have put up the design here:
h-t-t-p://thought-works.blogspot.in/2012/11/object-oriented-design-for-cloud-based.html as putting the diagrams here is not possible.
I am open for any discussion on that. Please note that without constructive discussion we can not improve our design skills.
If each distinct route starting from the root to leaf node is considered as a path, we need to determine if there is a route from root to leaf which contains nodes x, y, z such that pathindex(y) > pathindex(x) and pathndex(y) < pathindex(z). The below code considers each path and determines if x,y,z exists satisfying the condition on their positions.
First defining the TreeNode class:
******
package trees;
public class TreeNode {
private int data;
private TreeNode left;
private TreeNode right;
private Boolean isVisited = false;
public TreeNode(int d){
this.data = d;
}
public TreeNode appendRight(int d){
this.right = new TreeNode(d);
return this.right;
}
public TreeNode appendLeft(int d){
this.left = new TreeNode(d);
return this.left;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public Boolean IsVisited() {
return isVisited;
}
public void setIsVisited(Boolean isVisited) {
this.isVisited = isVisited;
}
public static void print(TreeNode node){
if(node!= null){
print(node.left);
System.out.print(node.data+ " ");
print(node.right);
}
}
}
******
Next the code to find the paths
package trees;
import java.util.Stack;
/**
* Given a binary tree and 3 nodes x,y,z, write a function which returns true if
* y lies in the path between x and z and false otherwise.
*
* Example:
*
* 1
* / \
* 2 3
* /\ /\
* 4 5 6 7
* /
* 8
*
* Paths to consider are 124,1258,136,137. find if each of the distinct paths has
* the nodes x,y,z satisfying the condition that y should be in between x and z
*
* We use a stack to hold the intermediate paths -> O(n) space
*
*
* @author sriniatiisc
*
*/
public class FindAPathContainingThreeNodes {
public static void main(String[] args) {
TreeNode r = getTree();
String path1 = findPath(r,2,5,8);
if (path1 != null) {
System.out.println(path1);
} else {
System.out.println("No such path exists");
}
}
private static String findPath(TreeNode r, int x, int y, int z) {
if (r == null)
return null;
Stack<TreeNode> nodes = new Stack<>();
nodes.push(r);
String path = "";
TreeNode n1 = r;
while (n1 != null && !n1.IsVisited()) {
if (n1.getLeft() != null && !n1.getLeft().IsVisited()) {
path += new Integer(n1.getData());
nodes.push(n1);
n1 = n1.getLeft();
} else if (n1.getRight() != null && !n1.getRight().IsVisited()) {
path += new Integer(n1.getData());
nodes.push(n1);
n1 = n1.getRight();
} else {
if (!n1.IsVisited()) {
String pathToSearch = path + new Integer(n1.getData());
// find if the path contains x,y,z
int xindex = find(pathToSearch, x);
int yindex = find(pathToSearch, y);
int zindex = find(pathToSearch, z);
if (yindex > xindex && yindex < zindex) {
return pathToSearch;
}
n1.setIsVisited(true);
}
n1 = nodes.pop();
// remove the last character
if (path.length() >= 1) {
path = path.substring(0, path.length() - 1);
} else{
path = "";
}
}
}
return null;
}
private static int find(String path, int x) {
return path.indexOf(new Integer(x) + "");
}
private static TreeNode getTree() {
TreeNode root = new TreeNode(1);
root.appendLeft(2).appendLeft(4);
root.getLeft().appendRight(5).appendLeft(8);
root.appendRight(3).appendLeft(6);
root.getRight().appendRight(7);
return root;
}
}
package trees;
public class TreeNode {
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int d){
this.data = d;
}
public TreeNode appendRight(int d){
this.right = new TreeNode(d);
return this.right;
}
public TreeNode appendLeft(int d){
this.left = new TreeNode(d);
return this.left;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public static void print(TreeNode node){
if(node!= null){
print(node.left);
System.out.print(node.data+ " ");
print(node.right);
}
}
}
package trees;
/**
* Imagine a vertical line sweeping the tree from Left to right and we will print
* nodes at each vertical level in an ascending order of the depth of the node
* from the root.
*/
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class PrintTreeVertically {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.appendLeft(2).appendLeft(4);
root.getLeft().appendRight(5).appendLeft(8);
root.appendRight(3).appendLeft(6);
root.getRight().appendRight(7);
Map<Integer, ArrayList<TreeNode>> nodes = new HashMap<Integer, ArrayList<TreeNode>>();
organizeNodesVertically(root, 0, nodes);
List<Integer> verticalIndices = new ArrayList<Integer>(nodes.keySet());
Collections.sort(verticalIndices);
for (Integer i : verticalIndices) {
ArrayList<TreeNode> list = nodes.get(i);
for (TreeNode treeNode : list) {
System.out.print(treeNode.getData() + " ");
}
}
}
private static void organizeNodesVertically(TreeNode root,
int verticalIndex, Map<Integer, ArrayList<TreeNode>> nodes) {
if (root == null) {
return;
}
if (nodes.get(verticalIndex) == null) {
nodes.put(verticalIndex, new ArrayList<TreeNode>());
}
nodes.get(verticalIndex).add(root);
organizeNodesVertically(root.getLeft(), verticalIndex - 1, nodes);
organizeNodesVertically(root.getRight(), verticalIndex + 1, nodes);
}
}
Longest possible path in the tree = (reverse of longest path from root in left sub tree) + root+ (longest possible path from root in right sub tree)
package trees;
/**
* Program prints the longest possible path starting at the root in a tree
* followed by the longest possible path which can start at any node in the tree
* Longest path in the tree = reverse(longest path from root in the left sub
* tree) + root + (longest path from root in the right sub tree)
*
*
* @author sriniatiisc
*
*/
public class LongestPossiblePathInTree {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.appendLeft(2).appendLeft(4);
root.getLeft().appendRight(5).appendLeft(8);
root.appendRight(3).appendLeft(6);
root.getRight().appendRight(7);
TreeNode.print(root);
String longestPath = longestPath(root);
System.out
.println("Longest path starting at root node: " + longestPath);
String longestLPath = longestPath(root.getLeft());
String longestRPath = longestPath(root.getRight());
System.out.println("Longest path in the tree: " + reverse(longestLPath)
+ root.getData() + longestRPath);
}
private static String longestPath(TreeNode root) {
if (root == null)
return "";
String lPath = longestPath(root.getLeft());
String rPath = longestPath(root.getRight());
if (lPath.length() >= rPath.length()) {
return root.getData() + lPath;
} else {
return root.getData() + rPath;
}
}
public static String reverse(String s) {
char[] str = s.toCharArray();
int i = 0;
int j = str.length - 1;
while (i <= j) {
char t = str[i];
str[i] = str[j];
str[j] = t;
i++;
j--;
}
return new String(str);
}
}
package arrays;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
public class ZeroSumSubArray {
public static void main(String[] args) {
int a[] = { 3, 5, 6, -8, 1, -4, 9, 5, -9 };
// populate the sums
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
a[i] = sum;
}
Map<Integer, ArrayList<Integer>> indices = new HashMap<>();
for (int i = 0; i < a.length; i++) {
indices.put(new Integer(a[i]), new ArrayList<Integer>());
}
for (int i = 0; i < a.length; i++) {
ArrayList<Integer> sumIndices = indices.get(new Integer(a[i]));
if (sumIndices.isEmpty()) {
sumIndices.add(i);
} else {
sumIndices.add(1, i);
}
}
for (Entry<Integer, ArrayList<Integer>> e : indices.entrySet()) {
ArrayList<Integer> list = e.getValue();
if (list.size() > 1) {
System.out.println("sub sequence with zero sum starts at " + list.get(0)+ " till "+ list.get(1));
}
}
}
}
package arrays;
/**
* Returns the kth largest element in the array of elements
* Uses partitioning (order statistics) technique to arrive
* at kth element.
*
* Usage: Kth largest element returned will be the element at index
* k-1;
*
*/
public class KthLargest {
public static void main(String[] args) {
int a[] = { 1, 6, 2, 9, 13, 5, 3, 8 };
int k = 7;
int index = findKth(a,0, a.length -1, k);
System.out.println(k+ "th largest element: "+ a[index]);
}
private static int findKth(int[] a, int low, int high, int k) {
int partitionIndex = partition(a,low,high);
if( k == partitionIndex - low) {
return partitionIndex;
} else if(k < partitionIndex){
return findKth(a, low, partitionIndex-1, k);
} else if(k> partitionIndex) {
return findKth(a, partitionIndex+1, high, k-(partitionIndex+1));
}
return partitionIndex;
}
private static int partition(int[] a, int low, int high) {
if(low<high){
int pIndex = Math.abs((low + high) / 2);
int pivot = a[pIndex];
swap(a, pIndex, high);
int i = low;
int j = high - 1;
while (i <= j) {
while (i < high && a[i] <= pivot) {
i++;
}
while (j >= low && a[j] >= pivot) {
j--;
}
if (i < j) {
swap(a, i, j);
i++;
j--;
}
}
swap(a, i, high);
return i;
} else {
return low;
}
}
private static void swap(int[] a, int i, int pIndex) {
int t = a[i];
a[i] = a[pIndex];
a[pIndex] = t;
}
}
package arrays;
/**
* remove duplicate integers in array
*
*
*/
public class RemoveDuplicatesInArray {
public static void main(String [] args){
int a[] = {1,1,1,1};
int tail = 1;
for (int i = 1;i<a.length;i++){
int j =0;
for(;j<tail;j++){
if (a[j] == a[i]){
break;
}
}
if(j==tail){
a[tail]= a[i];
tail++;
}
}
for (int i=0;i<tail;i++) {
System.out.print(a[i]);
}
}
}
Working Java code which was tested:
package arrays;
/**
*
* lets say a[] = {2,7,8,9}. we should make a contain {2,7,9,0}
*
*/
public class IncrementNumberInArray {
public static void main(String [] args){
int a [] = {9,9,9,9,9};
int b [] = new int[a.length+1];
int i = a.length-1;
int carry = 9;
for(;i>=0;i--) {
int sum=0;
sum += a[i]+carry;
int digit;
if(sum >=10){
digit = sum % 10;
carry = sum /10;
} else {
digit = sum;
carry = 0;
}
b[i+1]= digit;
}
b[0]= carry;
for (int j : b) {
System.out.print(j);
}
}
}
O(n) time and O(1) space solution in Java
package arrays;
public class MoveZeroesToBegin {
public static void main(String[] args) {
int a[] = { 1, 2, 0, 4, 0, 0, 8,9,0,2,3,0,4,5 };
move_zeroes_to_begin(a);
for (int i : a) {
System.out.print(i+" ");
}
}
private static void move_zeroes_to_begin(int[] a) {
int index = -1;
// find the first zero from the end
for (int i = a.length-1; i >= 0; i--) {
if (a[i] == 0) {
index = i;
break;
}
}
if (index != -1) {
int j = index - 1;
while (j >=0) {
if (a[j] != 0) {
a[index] = a[j];
index--;
j--;
} else if (a[j] == 0) {
j--;
}
}
while(index >=0){
a[index--]=0;
}
}
}
}
Java version - O(n) time and O(1) space
package arrays;
public class MoveZeroesToEndInplace {
public static void main(String[] args) {
int a[] = { 1, 2, 0, 4, 0, 0, 8,9,0,2,3,0,4,5 };
move_zeroes_to_end(a);
for (int i : a) {
System.out.print(i+" ");
}
}
private static void move_zeroes_to_end(int[] a) {
int index = -1;
int num_zeroes = 0;
// find the first zero
for (int i = 0; i < a.length; i++) {
if (a[i] == 0) {
index = i;
num_zeroes++;
break;
}
}
if (index != -1) {
int j = index + 1;
while (j < a.length) {
if (a[j] != 0) {
a[index] = a[j];
index++;
j++;
} else if (a[j] == 0) {
j++;
num_zeroes++;
}
}
while(num_zeroes-- > 0){
a[index++]=0;
}
}
}
}
Smart solution. Liked ama's logic
- sriniatiisc October 06, 2012package arrays;
public class BackwardsMergeArray {
public static void main(String [] args){
int a[] = {1,4,6,9,12,0,0,0};
int b[] = {3,7,8};
merge(a,b);
for (int i : a) {
System.out.print(i+", ");
}
}
private static void merge(int[] a, int[] b) {
int j = b.length-1;
int i = a.length-1 -(j+1);
int count = a.length -1;
while(i>=0 && j>=0){
if(a[i] > b[j]){
a[count--] = a[i];
i--;
} else if(a[i]<=b[j]){
a[count--] = b[j];
j--;
}
}
}
}
If all the numbers are negative or all numbers are positive then the pair (min value, next to min value) will be the unique answer. Below is a sorting based approach to arrive the pairs whose sum is closest to zero. I used merge sort here. Actually any nlogn sort can be used.
package arrays;
/**
*
* Imagine arranging the numbers in the array on an integer number line.
* If all the numbers are towards the positive side or the negative side
* of the number line, the pair (min, next min) would be the unique answer.
*
* If we have numbers towards both +ve and -ve sides, then pair (x,y)
* would be a candidate for the answer where x any y are on opposite side
* of the number line with diff(abs(x) -abs(y)) close to zero.
*
* The approach is
* 1) sort the numbers based on the abs value of the data - O(nlogn)
* 2) in the sorted array by abs value pairs like (x,y) discussed above would be
* adjacent to each other
* 3) prepare the sum of adjacent pairs in this array. The pair with min
* sum is the answer
*
*
* I ran this code for
* {2,-3,-5,4,-6,-1,8}
* {2,5,8,-7,2,9};
* {-2,-3,-5,-4,-6,-1,-8}
* {1,2,3,4,5,6}
*
*
*/
public class FindPairsClosestToZero {
// we want to sort the data by abs value and use the
//original data while forming pairs. So create this type
private static class Int_data {
private int data;
private int absData;
public Int_data(int t){
data = t;
absData = Math.abs(t);
}
}
public static Int_data [] sorted_data;
public static void main(String [] args) {
int a[] = {2,5,8,-7,2,9};
Int_data[] data = new Int_data[a.length];
for (int i=0;i<a.length;i++) {
Int_data temp = new Int_data(a[i]);
data[i] = temp;
}
sorted_data = new Int_data[data.length];
merge_sort(data, 0, data.length-1);
int[] closestPairSum = new int[a.length-1];
//form the closest pair sums
for(int i=0;i<closestPairSum.length;i++){
closestPairSum[i] = Math.abs(sorted_data[i].data+sorted_data[i+1].data);
}
for (int i = 0; i < closestPairSum.length; i++) {
System.out.println(closestPairSum[i]+ " formed by ["+ sorted_data[i].data+ ", "+ sorted_data[i+1].data+"]");
}
}
public static void merge_sort(Int_data[] a, int low, int high) {
if (high - low > 1) {
// more than two element
int mid = (int) Math.floor((high + low) / 2);
merge_sort(a, low, mid);
merge_sort(a, mid + 1, high);
// merge the data
int i = low;
int j = mid + 1;
int count = low;
while (i <= mid && j <= high) {
if (a[i].absData <= a[j].absData) {
sorted_data[count++] = a[i];
i++;
} else if (a[i].absData > a[j].absData) {
sorted_data[count++] = a[j];
j++;
}
}
if (j <= high) {
while (j <= high) {
sorted_data[count++] = a[j];
j++;
}
}
if (i <= mid) {
while (i <= mid) {
sorted_data[count++] = a[i];
i++;
}
}
} else {
// we have to deal with less than two elements
if (high == low + 1) {
if (a[low].absData > a[high].absData) {
Int_data tmp = a[low];
a[low] = a[high];
a[high] = tmp;
}
} else if (high == low) {
//System.out.println("One element no sorting needed");
sorted_data[low] = a[low];
}
}
}
}
/**
* Program print the maximum sub sequence sum in the array
* and prints the start and end indices of the sub sequence
*
* If all the elements in the array are negative
* max sub sequence sum is 0
*
*/
public class LargestSumContigiousSubsequence {
public static void main(String[] args) {
int[] a = { -2, 11, -4, 13, -5, 2 };
int maxSum = 0;
int thisSum = 0;
int sIndex = 0;
int eIndex = 0;
for (int i = 0; i < a.length; i++) {
if (thisSum == 0) {
sIndex = i;
eIndex = i;
}
thisSum += a[i];
if (thisSum > maxSum) {
maxSum = thisSum;
eIndex++;
}
if (thisSum < 0) {
thisSum = 0;
}
}
System.out.println("max sum:" + maxSum);
if (maxSum > 0) {
System.out.println("start index :" + sIndex + " eIndex :" + eIndex);
}
}
}
Modifed version of mergesort algorithm could give us the no of inversions in the array. I tested this on
(1), (1,1,1,1), (1,2,3,4,5,6), (3,5,7,2,8)
package arrays;
public class FindIInversionCount {
public static int[] temp_data;
public static int inversion_count = 0;
public static void main(String[] args) {
int[] a = {3,5,7,2,8};
temp_data = new int[a.length];
inversion_count = merge_and_count(a, 0, a.length - 1);
// for (int i : temp_data) {
// System.out.println(i);
//
// }
System.out.println("inversion count: " + inversion_count);
}
private static int merge_and_count(int[] a, int low, int high) {
if (high - low > 1) {
// more than two element
int mid = (int) Math.floor((high + low) / 2);
merge_and_count(a, low, mid);
merge_and_count(a, mid + 1, high);
// merge the data and count the inversions
int i = low;
int j = mid + 1;
int count = low;
while (i <= mid && j <= high) {
if (a[i] <= a[j]) {
temp_data[count++] = a[i];
i++;
} else if (a[i] > a[j]) {
temp_data[count++] = a[j];
j++;
for (int k = i; k <= mid; k++) {
inversion_count++;
}
}
}
if (j <= high) {
while (j <= high) {
temp_data[count++] = a[j];
j++;
}
}
if (i <= mid) {
while (i <= mid) {
temp_data[count++] = a[i];
i++;
inversion_count++;
}
}
} else {
// we have to deal with less than two elements
if (high == low + 1) {
if (a[low] > a[high]) {
int tmp = a[low];
a[low] = a[high];
a[high] = tmp;
inversion_count++;
}
} else if (high == low) {
System.out.println("One element no sorting needed");
temp_data[low] = a[low];
}
}
return inversion_count;
}
}
public class CircularQueue {
public static final int MAX_SIZE = 3;
public static int counter = 0;
private static int [] a = new int[MAX_SIZE];
private static int front = 0;
private static int rear = 0;
public void insert(int d){
if(counter == MAX_SIZE){
System.out.println("queue is full. Cant insert "+ d);
return;
}
a[rear] = d;
rear++;
if(rear>=MAX_SIZE){
rear = rear%MAX_SIZE;
}
counter++;
}
public int remove(){
if(counter ==0){
System.out.println("queue empty");
return -1;
}
int d = a[front];
front++;
if(front >= MAX_SIZE){
front = front % MAX_SIZE;
}
counter--;
return d;
}
public static void main(String [] args){
CircularQueue q = new CircularQueue();
q.insert(1);
q.insert(2);
q.insert(3);
q.insert(4);
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
}
}
public class CircularQueue {
public static final int MAX_SIZE = 3;
public static int counter = 0;
private static int [] a = new int[MAX_SIZE];
private static int front = 0;
private static int rear = 0;
public void insert(int d){
if(counter == MAX_SIZE){
System.out.println("queue is full. Cant insert "+ d);
return;
}
a[rear] = d;
rear++;
if(rear>=MAX_SIZE){
rear = rear%MAX_SIZE;
}
counter++;
}
public int remove(){
if(counter ==0){
System.out.println("queue empty");
return -1;
}
int d = a[front];
front++;
if(front >= MAX_SIZE){
front = front % MAX_SIZE;
}
counter--;
return d;
}
public static void main(String [] args){
CircularQueue q = new CircularQueue();
q.insert(1);
q.insert(2);
q.insert(3);
q.insert(4);
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
System.out.println("data from queue: "+q.remove());
}
}
The same question was asked in microsoft interview again. Here is the java code and some test runs:
public class PrintMatrixSpiral {
public static void main(String[] args) {
int a[][] = { { 1 ,2,3}, { 4,5,6 }, { 7,8,9 }, {10,11,12} };
printSpiral(a, 4, 3);
int b[][] = { { 1 ,2,3,4}, { 4,5,6,7 }, { 8,9,10,11 }, {12,13,14,15} };
printSpiral(b, 4, 4);
int c[][] = { { 1 ,2,3,4}};
printSpiral(c, 1, 4);
int d[][] = { { 1} ,{2},{3},{4}};
printSpiral(d, 4, 1);
int e[][] = { {1}};
printSpiral(e, 1, 1);
}
private static void printSpiral(int[][] a, int m, int n) {
int x = 0;
int y = 0;
int i = 0;
int j = 0;
while (x <= m / 2) {
// step1: print the row
i = 0 + x;
for (j = 0 + y; j <= (n - 1) - y; j++) {
System.out.print(a[i][j] + " ");
}
// step 2: print the right column
j = (n - 1) - y;
for (i = x + 1; i <= (m - 1) - (x + 1); i++) {
System.out.print(a[i][j] + " ");
}
// step3: print bottom row
i = m - 1 - x;
if (i > 0 + x) {
for (j = (n - 1) - y; j >= (0 + y); j--) {
System.out.print(a[i][j] + " ");
}
}
// step 4: print left column
j = (0 + y);
if (j < (n - 1) - y) {
for (i = (m - 1) - (x + 1); i >= (x + 1); i--) {
System.out.print(a[i][j] + " ");
}
}
x++;
y++;
}
System.out.println();
}
}
Java Code:
---------------
public class RunLengthEncoding {
public static void main(String [] args){
char[] a = {'a','a','a','a','b','b','b','b','a','c','b','c'};
int i =1;
char t = a[0];
int count = 1;
while(i<a.length){
if(a[i]==t){
count++;
} else {
System.out.print(t+""+count);
t = a[i];
count =1;
}
i++;
}
System.out.print(t+""+count);
}
}
Test cases:
a
aaaabbbbcc
aaaabbbbacbc
Java code to merge two sorted arrays where one of the arrays can accommodate the other.
public class MergeSortedArrays {
public static void main(String [] s){
//i have chosen 888 as a special number indicating space to be occupied
int[] a = {1,1,1,888,888,888};
int[] b = {1,1,1};
int i,j =0;
for (i=0;i<a.length;i++) {
while(j<b.length){
if(a[i] <= b[j]) {
i++;
} else {
for(int k=a.length-1;k>i;k--){
a[k] = a[k-1];
}
a[i]= b[j];
i++;
j++;
}
}
}
for (int l : a) {
System.out.print(l);
}
}
}
This is the design for library where books are rented. Replace books with dvds and the design should work. thought-works.blogspot.in/2012/11/object-oriented-design-for-library-to.html
- sriniatiisc December 31, 2013