AnkitSablok19091989
BAN USERMy program works for square matrices -:
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class RotateAnImageBy90Degrees {
// this function is used to rotate the square matrix by 90 degrees
public static void rotateMatrixBy90Degrees(int[][] matrix){
int N = matrix.length;
// first find the transpose of the matrix
for(int i = 0; i < N; ++i){
for(int j = i; j < N; ++j){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// reverse the columns of the matrix till N/2 to rotate the matrix by 90 degrees
for(int i = 0; i < N; ++i){
for(int j = 0; j < N/2; ++j){
int temp = matrix[i][j];
matrix[i][j] = matrix[i][N-j-1];
matrix[i][N-j-1] = temp;
}
}
}
public static void displayMatrix(int[][] matrix){
int N = matrix.length;
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j)
System.out.print(matrix[i][j] + " ");
System.out.println();
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N;
N = 0;
System.out.println("Enter the dimensions of the square matrix you want : ");
N = Integer.parseInt(br.readLine());
int[][] matrix = new int[N][N];
for(int i = 0; i < N; ++i){
String[] s = br.readLine().split("\\s+");
int[] colValues = new int[s.length];
for(int j = 0; j < colValues.length; ++j)
colValues[j] = Integer.parseInt(s[j]);
for(int j = 0; j < colValues.length; ++j)
matrix[i][j] = colValues[j];
}
System.out.println("The original matrix is as follows -: ");
displayMatrix(matrix);
rotateMatrixBy90Degrees(matrix);
System.out.println("The matrix rotated by 90 degrees is as follows -: ");
displayMatrix(matrix);
}
}
My solution to this problem uses an auxiliary hashmap and solves the problem in O(n) time
import java.util.Set;
import java.io.File;
import java.util.HashMap;
import java.util.HashSet;
import java.io.FileReader;
import java.io.IOException;
import java.io.BufferedReader;
public class RomanStringToIntegerConversion {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)));
String[] romanString = br.readLine().split("");
HashMap<String, Integer> romanToIntegerMap = new HashMap<String, Integer>();
romanToIntegerMap.put("I", 1);
romanToIntegerMap.put("V", 5);
romanToIntegerMap.put("X", 10);
romanToIntegerMap.put("L", 50);
romanToIntegerMap.put("C", 100);
romanToIntegerMap.put("D", 500);
romanToIntegerMap.put("M", 1000);
int numLength = romanString.length;
Set<Integer> lessIndices = new HashSet<Integer>();
for(int i = 0; i < numLength; ++i){
if(i+1 < numLength){
if(romanToIntegerMap.get(romanString[i]) < romanToIntegerMap.get(romanString[i+1]))
lessIndices.add(i);
}
}
int num = 0;
for(int i = 0; i < numLength;){
if(!lessIndices.contains(i)){
num = num + romanToIntegerMap.get(romanString[i]);
++i;
}
else{
num = num + romanToIntegerMap.get(romanString[i+1]) - romanToIntegerMap.get(romanString[i]);
i+=2;
}
}
System.out.println("The integer representation of the roman numeral is : " + num);
}
}
This problem is kinda simple and here is my Java code to solve this problem -:
public class BinaryStringAdder {
public static ArrayList<Integer> binaryAdder(ArrayList<Integer> num1, ArrayList<Integer> num2){
Collections.reverse(num1);
Collections.reverse(num2);
int carry = 0;
ArrayList<Integer> sum = new ArrayList<Integer>();
for(int i = 0; i < num2.size(); ++i){
int temp = num1.get(i) + num2.get(i) + carry;
sum.add(temp%2);
carry = temp/2;
}
for(int i = num2.size(); i < num1.size(); ++i){
int temp = num1.get(i) + carry;
sum.add(temp%2);
carry = temp/2;
}
if(carry != 0)
sum.add(carry);
Collections.reverse(sum);
return sum;
}
public static void main(String[] args) throws IOException{
ArrayList<Integer> sum;
if(biNum1.size() >= biNum2.size())
sum = binaryAdder(biNum1, biNum2);
else
sum = binaryAdder(biNum2, biNum1);
for(int i = 0; i < sum.size(); ++i)
System.out.print(sum.get(i));
}
}
Here is my code in Java to solve this problem -:
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.BufferedReader;
public class MoveAllNonZeroElementsToLeftOfAllZeroElements {
public static void main(String[] args) throws IOException{
int start = 0;
int end = integerArray.length - 1;
while(start <= end){
if(integerArray[start] == 0 && integerArray[end] != 0){
int temp = integerArray[start];
integerArray[start] = integerArray[end];
integerArray[end] = temp;
++start; --end;
}else if(integerArray[start] != 0 && integerArray[end] != 0){
++start;
}else if(integerArray[start] == 0 && integerArray[end] == 0){
--end;
} else{
++start;
}
}
for(int i = 0; i < integerArray.length; ++i)
System.out.print(integerArray[i] + " ");
}
}
This seems to be like a simple binary search we use to zero in on the root, updating the upper and lower bounds in each iteration
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Problem4_SquareRootFunction {
public static void main(String[] args) throws NumberFormatException, IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
double num = Double.parseDouble(br.readLine());
double upperBound = num;
double lowerBound = 0.0;
double root = (lowerBound+upperBound)/2;
while(Math.abs(root*root - num) >= 0.001){
if(root*root - num >= 0.001){
upperBound = root;
root = (lowerBound+upperBound)/2;
}else{
lowerBound = root;
root = (lowerBound+upperBound)/2;
}
}
System.out.println("The square root of the number is : " + root);
}
}
I implemented this as a graph problem following a BFS scheme but not entirely BFS, here is my code in Java -
import java.io.File;
import java.util.HashMap;
import java.io.FileReader;
import java.util.ArrayList;
import java.io.IOException;
import java.io.BufferedReader;
/* this class is used to form a graph out of the input boggle matrix characters */
class BoggleGraph{
// the number of vertices in the graph
int nVertices;
// this boolean variable holds the kind of graph one wants, directed or undirected */
boolean isDirected;
// this hashmap holds the adjacency list of the graph data structure
HashMap<Character, ArrayList<Character>> adjacencyList;
// this is the constructor for the class, which constructs a graph object
public BoggleGraph(int nVertices, boolean isDirected){
this.nVertices = nVertices;
this.isDirected = isDirected;
this.adjacencyList = new HashMap<Character, ArrayList<Character>>();
}
// these functions help retrieve the fields of the graph data structure
public int getVertices(){
return this.nVertices;
}
public boolean getIsDirected(){
return this.isDirected;
}
public HashMap<Character, ArrayList<Character>> getAdjacencyList(){
return this.adjacencyList;
}
// this function helps insert an edge in a graph
public void insertEdge(char vertex1, char vertex2, boolean isDirected){
if(isDirected){
if(adjacencyList.containsKey(vertex1)){
if(!adjacencyList.get(vertex1).contains(vertex2))
adjacencyList.get(vertex1).add(vertex2);
}
else{
adjacencyList.put(vertex1, new ArrayList<Character>());
adjacencyList.get(vertex1).add(vertex2);
}
}else{
if(adjacencyList.containsKey(vertex1))
adjacencyList.get(vertex1).add(vertex2);
else{
adjacencyList.put(vertex1, new ArrayList<Character>());
adjacencyList.get(vertex1).add(vertex2);
}
insertEdge(vertex2, vertex1, true);
}
}
// this function is used to display the graph
public void displayGraph(){
for(Character vertex : adjacencyList.keySet()){
System.out.print(vertex + " : ");
for(Character adj : adjacencyList.get(vertex))
System.out.print(adj + " ");
System.out.println();
}
}
}
public class Problem1_BoggleGameQuestion {
// this function checks if a word can be formed out of the input Boggle Matrix
public static boolean checkWord(BoggleGraph bgraph, String word){
HashMap<Character, Boolean> visitedMap = new HashMap<Character, Boolean>();
for(Character c : bgraph.getAdjacencyList().keySet())
visitedMap.put(c, false);
visitedMap.put(word.charAt(0), true);
ArrayList<Character> frontier = bgraph.getAdjacencyList().get(word.charAt(0));
for(int i = 1; i < word.length(); ++i){
if(frontier.contains(word.charAt(i)) && !visitedMap.get(word.charAt(i))){
visitedMap.put(word.charAt(i), true);
frontier = bgraph.getAdjacencyList().get(word.charAt(i));
}else{
return false;
}
}
return true;
}
public static void main(String[] args) throws NumberFormatException, IOException{
BufferedReader br = new BufferedReader(new FileReader(new File("C:/Users/ankitsablok89/Desktop/MS in Computer Science Classes/Competitive Programming/Interview Problems/BoggleGame.txt")));
int dimensions = Integer.parseInt(br.readLine());
char[][] boggleBoard = new char[dimensions][dimensions];
for(int i = 0; i < dimensions; ++i){
for(int j = 0; j < dimensions; ++j){
boggleBoard[i][j] = br.readLine().charAt(0);
}
}
BoggleGraph bgraph = new BoggleGraph(dimensions*dimensions, true);
for(int i = 0; i < dimensions; ++i){
for(int j = 0; j < dimensions; ++j){
if(i-1 >= 0)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i-1][j], bgraph.isDirected);
if(i+1 < dimensions)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i+1][j], bgraph.isDirected);
if(j-1 >= 0)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i][j-1], bgraph.isDirected);
if(j+1 < dimensions)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i][j+1], bgraph.isDirected);
if(i-1 >= 0 && j-1 >= 0)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i-1][j-1], bgraph.isDirected);
if(i+1 < dimensions && j-1 >= 0)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i+1][j-1], bgraph.isDirected);
if(i-1 >= 0 && j+1 < dimensions)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i-1][j+1], bgraph.isDirected);
if(i+1 < dimensions && j+1 < dimensions)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i+1][j+1], bgraph.isDirected);
}
}
System.out.println(checkWord(bgraph, "STAR"));
System.out.println(checkWord(bgraph, "TONE"));
System.out.println(checkWord(bgraph, "NOTE"));
System.out.println(checkWord(bgraph, "SAND"));
}
}
I understand what you are saying, got the problem working on it
- AnkitSablok19091989 August 04, 2014Is there a hidden constraint in the problem that says we can't use sorting, because if we can use sorting then this problem can be solved easily, the following are the steps to do that -:
1) sort the servers by their capacity/memory limits, so for instance in the example shown above we will have our servers in the following order after sorting - 8,8,16,32
2) Perform the same step as above for the tasks that you want to allocate on these servers, so the sequence of jobs now becomes the following - 4,4,6,6,8,8,8,18
3) now for each job scan through the list of server's sorted by their memory limits and if a task can fit in the server decrease the capacity of the server by the size of the job in each step, so the final list becomes the following - 0,2,2,6 and hence you can return true when you have exhausted finding a best fit for all the jobs, else if you failed finding a best fit for a specific task you can return false immediately
What exactly are you looking for, that is the question?
- AnkitSablok19091989 September 10, 2013@noMAD : if you can maintain a max heap of the set of points with the euclidean distance of the point acting as its comparable key, then you can extract the maximum element from the heap in O(logn) time, well its just the first element in the 100 sized max heap, but the logn time taken is to maintain the max heap property, I hope I made the point home
- AnkitSablok19091989 March 12, 2013This question can be easily solved using min-heap of size 100, initially load any 100 elements of the file into the min-heap then starting from element number 101 to the size of residual file, consider 1 element at a time and check if that element is greater than the minimum element if it is indeed greater then use the extract-min operation on the min-heap which can be done in O(logn) time and insert this new element into the min-heap which gives us our current collection of 100 largest elements and repeat the same procedure for other elements in the file. I hope I am correct in my reasoning :).
- AnkitSablok19091989 March 12, 2013Heap isn't exactly a complete binary tree one can view it as a complete binary tree, I hope I got the point home, and even a binary search tree can be a complete binary tree.
- AnkitSablok19091989 March 12, 2013(a)
- AnkitSablok19091989 June 19, 2012using macros such as #ifdef, #else,#elif, #ifndef all these macros support the concept of conditional compilation which means the statements that need to be executed when the condition is true are compiled if the condition is false then the statements are not compiled
- AnkitSablok19091989 May 29, 2012@Gayle Laakman people are posting homework questions here which they are supposed to do themselves, please take a note
- AnkitSablok19091989 March 15, 2012
I used a max heap implementation with custom comparator function, checkout my implementation in Java -:
- AnkitSablok19091989 February 18, 2015