GitHub Viewer
* java api
1. java allows Strings to be split like in python:
String a = "ab,as,as,asf,fr";
String[] tokens = a.split(",");
remeber that tokens array can be accesed just like python list - tokens[0] etc.
also, they are ordered
2. java.util.ArrayList
java.util.Formatter, Calender, Scanner,
3. to read in user input, Scanner object is created and System.in is passed to the constructor.
Scanner in = new Scanner(System.in);
int a = in.nextInt();
System.out.println(a);
4. to read a file :
new File object with filepath to constructor.
BufferReader object with a FileReader object to whom the File object must be given
File file = new File("SongsList.txt");
BufferReader reader = new BufferReader(new FileReader(file));
String line = null;
while ((line = reader.nextLine()) != null) {
System.out.println(line);
5. Hashtable in Java:
HashMap map = new HashMap();
map.put(1, 2);
6. ArrayList in java
ArrayList int_array = new ArrayList();
int_array.add(1);
7. Convert words to a sentence.
Use a StringBuffer for that.
recall, toString is called when anyobject is printed using System.out.println()..., the toString method is present in the Object class. Here, what we infer is that StringBuffer class overloads the toString method and has it accept a list of strings and return them as combined string to the original method.
something like:
class StringBuffer{
//rest of the class
public String toString(String[] words){
String result = "";
for (String word:words){
result+=word;
}
super.toString(result); // the Object classes toString method called
}
}
example of usuage:
class HashMap2
{
public String makeSentence(String[] words) {
StringBuffer sentence = new StringBuffer();
for (String w : words) sentence.append(w);
return sentence.toString();
}
public static void main(String[] args)
{
String[] words = {"one", "two", "three"};
System.out.println(hmap.makeSentence(words));
}
}
8. To find the character at a particular index in a string, use charAt function
eg : String a = "abcd";
System.out.println(a.charAt(1));
-->b
find the length of a string ? int b = a.length();
9. find the ascii code of any char :
int a = "abcd".charAt(2); --> will give the ascii of c
char a = "abcd".charAt(2)l --> will store the value "c".
**This is an example of method overloading? NOO.
This is not special for charAt method. It can be done for any character.
so, int a = "a"; works too. the ascii of a is stored.
This is more of an autoboxing like feature
also, characters can be used in indexing - so, bool[] a = new bool[256];
a['a'] = true; --> works
9. it is boolean, not Boolean, it is true/false, not True/False.
it is null, not Null. Boolean is the object class.
10. when we need to iterate thru the string length for eg, do:
for (int i=0;itarget)
{
root = root.right;
} else {
root = root.left;
}
}
return null; //the value not found.
}
public static searchNode(BSTNode root, int target)
{
if (root.data==target) return root;
if (root.data>target) return searchNode(root.right, target)
}
public static insert(BSTNode root, int insertThis)
{
//we will search for the value and on reaching the null, we will insert it there.
//this code will go in the return null part of searchNode.
BSTNode temp = new BSTNode(target);
if (left) { prev.left = temp;}
else prev.right = temp;
}
for delete, if there is no child, just remove it
if one child, make x's parent point to x's child directly
there are 4 conditions, x is right/left child, x has left/right child
if both children, find x's inorder predecessor, by taking one left and then as many right as possible.
then, place the data of the predecessor (which will be a leaf), in x and delete the predecessor.
Now, DFS
say we have 5 nodes
A --> B --> C
we will have an arrayList -- or better yet, an array of type Vertex.
BASICALLY, we have an array of Vertex. each entry has a Vertex object which has two instance variables. First one is the name of the vertex (A, B, C, D etc), and the other is the pointer to the head of the Linkedlist which houses one Neighbour node for each edge from that vertex. The Neighbour node has vertexNum of the vertex the edge points to and also the next one from there. (the value of the vertex it points to can be found in Neighbour.next.name) the LL has only the Neighbours for that node.
class Vertex{
String name;
Neighbour adjList;
public Vertex(String name, Neighbour negbrs){
this.name = name;
this.adjList = negbrs;
}
}
class Neighbour{
int vertexNum;
Neighbour next; //for storing the weight, we can have an additional int weight variable.
public Neighbour(int vnum, nbr){
this.vertexNum = vnum;
next = nbr;
}
}
Neighbour is a linked list, classical.
class Graph{
Vertex[] vertexes; //this is an array of vertexes.
public void dfs(int v, boolean[] visited){
visited[v] = true;
print vertexes[v].name;
for (Neighbour n = vertexes[v].adjList;n!=null;n=n.next){
if (!visited[v]) dfs(n.vertexNum, visited);
}
}
//writing the driver loop
for (int i=0;i0){
int p = (k-1)/2;
if (array[k]>array[p]){
int temp = array[p];
array[p] = array[k]; array[k] = temp;
} else break;
}
}
56. YOU ADD THINGS TO A SET, YOU PUT THINGS IN A MAP
So, HashSetObejct.add("a"), TreeSetObject.add("sa")
BUT
TreeMapObject.put("as", "as"), HashMapObejct.put("sa", "as");
CRACKING THE CODING INTERVIEW
1. Pratice writing the code on paper before entering it on a PC
2. Prepare a summary of all the projects on your CV, and the challenges you faced and how you overcame them
eg Q: Tell us about your internship experience with Exponentia ?
3. The most important aspects are :
good, clear communication
recall that your cv and knowledge is better than most of the others
asnwering to the point
being extremely courteous and friendly
your plus points? passionate and motivated about computer science, quick learner, excited about trying out new technology, easy going.
4. remember, if selected, they will have you work alongside them everyday, be the one they would love to "go out with a beer for", a person who would be a pleasure to work with
5. OPEN SOURCE and INDEPENDENT projects MATTER A LOOOT. DO 'EM !
6. prepare for these question before you go in:
what is your strength
what is your weakness
what was the happiest, saddest moment on your life
what was the most challenging time of your life
what was the most difficult part of this project
7. DO reasearch on the company to prepare questions when the interviewer gives you a cance to ask them questions.
example question:
what does a typical day look like for a software developer at X? //X is the company you are interviewing for. Duh.
OR better, ask them about their tech stack
How do you use solve problem Y using technology X?
these questions show that you are passionate about the comany and its tech
8. LEARN ABOUT :
singleton design pattern
factory designn pattern
9. When asked a difficult problem, it is okay to take some time to come up with a solution - THINK ALOUD - better than keeping silent.
**sort an list
here, list can be an array or linked list.
10. ASK QUESTIONS seeking clarification if the question they asked is not clear.
11. When they ask you question, there is more often than not, a catch - which they want you to spot. for example note if the data is sorted.
write pseudo code before jumping on writing the code
name your varialbes intelligently, follow good pratices, indentation
when you are done, start testing the code for invalid inputs, negatives, zero, null etc
12 Q: find the minimum in a sorted array - binary search
what if the array is rotated - again, binary search - look for the 'reset' point. the max in the pt beside the reset point.
13 Q: given a string MESSAGE(length m) and a large string POOL(length n), is it possible to construct MESSAGE from POOL ?
naaive: for each character in MESSAGE, check of the character is there in POOL, if there, remove it from there.
if all characters present, possible. O(mn)
better: since we have repeated lookups, we can use a hash table.
**when ever we create a hash table, we need two things: key and value (remember, a hash table is just a dict really).
So, we can have each character in POOL, map to the number of times it appears in POOL. Using the heapofy operation, we can load the data into a hash table in O(n) time. We then in O(m) time, create a character count for each character that appears in the MESSAGE. Then run a loop to check for each character in O(m) time [the check takes a constant time], hence the running time is linear O(max(m, n)), or really, just O(n) [THETA(n) ?]
**how do we store the character, count tuple in java say? OQ
14 Q: print all the permutations of a given string. (abcd = a, b, c, d, ab, ba, bc, cb, ..)
we can write a recursive algorith for this. OQ
def merge(single, long):
return [long[:i+1]+single+long[i+1:] for i in len(long)]
def give_to_merge()
for char in long:
merge(char, )
QUESTIONS like these are called base case and build questions, you have to create their solution bottom up.
15. Q: how to maintain a median of a stream of numbers
two heaps.
one max heap would store the smaller half of the numbers - you have to maintain this invariant
one min heap would sotre the larger half of the numbers
if you have odd number of elements, either of the heap can be bigger
if even number, the roots are the medians
if odd number, the larger heap has the median
when a new number comes along, it can either go in the small number heap or in the large number heap or be exactly in between the two roots (it is then the median), you can put it in either (or smaller) heap.
also, if two consequtive elements go in the smaller heap say, then push one element - the root to the larg number heap
AT any point of time, the difference between the population of the heaps is 1 or 0 (it oscillates between these as the numbers arrive) - this runs in log(n) time.
16. Q: given an odd numer of elements, how to create a perfectly balanced tree such that the median is at the top? this can be done if we follow the binary search tree property - left subtree smaller than the parent, right subtree bigger than the parent, root between both the subtrees.
if the number is even, there are two medians and they are the root and the root of the larger of both the sub trees - this is log time too.
**LL is not great at random access and sorting, great at storing an indefinate number of elements
array - great at random access
binary tree - great at good with ordering
**if you have heard a question before, say that! this will bring big honesty points. also, you it is difficult to pretent as if you are thinking. like say you heard it for one or two questions, then not.
17. Q: given a string determine if it has all unique characters?
optimal should be linear, right?
naaive : run thru the array, for each character, if not there in our array, put it in, else ignore. this is n*n time, because we have to check also.
this has space of O(n) also. a better solution would be to simply check each character against every other. this would take n^2 time and no space.
**the ascii char set is 256 characters long - it has 256 unique characters. SO, create a boolean array of size 256, run a loop thru each character (StringName.charAt(i)), if the index is 1, return false, if not set to 1. outside the loop, return true. time O(n), space O(n).
Otherwise, you can use a heap. store all the characters in a heap one by one after checking if it is not already there. if there, return false, else true.
public boolean uniqueString(String inputStr)
{
boolean[] boolArray = new boolean[256];
for (int i=0;i