Google Interview Hacks

10 most common problems Dynamic Programming? 1. Longest Common Subsequence 2. Longest Increasing Subsequence 3. Edit Distance 4. Minimum Partition 5. Ways to Cover a Distance 6. Longest Path In Matrix 7. Subset Sum Problem 8. Optimal Strategy for a Game 9. 0-1 Knapsack Problem 10. Boolean Parenthesization Problem Longest Common Subsequence? 1) Optimal Substructure: Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]). If last characters of both sequences match (or X[m-1] == Y[n-1]) then L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2]) If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2]) 2. Longest Increasing Subsequence? There is a recursive way, dynamic programming with brut...

Top 10 algorithms for linked lists? 1. Insertion of a node in Linked List (On the basis of some constraints) 2. Delete a given node in Linked List (under given constraints) 3. Compare two strings represented as linked lists 4. Add Two Numbers Represented By Linked Lists 5. Merge A Linked List Into Another Linked List At Alternate Positions 6. Reverse A List In Groups Of Given Size 7. Union And Intersection Of 2 Linked Lists 8. Detect And Remove Loop In A Linked List 9. Merge Sort For Linked Lists 10. Select A Random Node from A Singly Linked List 1. Insertion of a node in Linked List (On the basis of some constraints) If Linked list is empty then make the node as head and return it. 2) If value of the node to be inserted is smaller than value of head node, then insert the node at start and make it head. 3) In a loop, find the appropriate node after which the input node (let 9) is to be inserted. To find the appropriate node start from head, keep moving until y...

Topological Sorting vs Depth First Traversal (DFS)? In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices.

Explain Boggle (Find all possible words in a board of characters) The idea is to consider every character as a starting character and find all words starting with it. All words starting from a character can be found using Depth First Traversal. We do depth first traversal starting from every cell. We keep track of visited cells to make sure that a cell is considered only once in a word.

Explain Topological Sort? In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don't print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

Explain Minimum Spanning tree *Kruskal* ? 1. Sort all the edges in non-decreasing order of their weight. 2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. 3. Repeat step#2 until there are (V-1) edges in the spanning tree.

Explain does Minimum Spanning tree *Prim* ? 1) Create a set mstSet that keeps track of vertices already included in MST. 2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first. 3) While mstSet doesn't include all vertices ....a) Pick a vertex u which is not there in mstSet and has minimum key value. ....b) Include u to mstSet. ....c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v

How To detect cycle in a Graph *Union Find*? Union-Find Algorithm can be used to check whether an undirected graph contains cycle or not. Note that we have discussed an algorithm to detect cycle. This is another method based on Union-Find. This method assumes that graph doesn't contain any self-loops

Shortest Path from every vertex to every other vertex *Floyd Warshall? We initialize the solution matrix same as the input graph matrix as a first step. Then we update the solution matrix by considering all vertices as an intermediate vertex. The idea is to one by one pick all vertices and update all shortest paths which include the picked vertex as an intermediate vertex in the shortest path. When we pick vertex number k as an intermediate vertex, we already have considered vertices {0, 1, 2, .. k-1} as intermediate vertices. For every pair (i, j) of source and destination vertices respectively, there are two possible cases. 1) k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is. 2) k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][k] + dist[k][j].

Explain Shortest Path from source to all vertices *Dijkstra* algorithm? is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. Mark all nodes unvisited. 1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty. 2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first. 3) While sptSet doesn't include all vertices ....a) Pick a vertex u which is not there in sptSetand has minimum distance value. ....b) Include u to sptSet. ....c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight o...

Explain Depth First Search (DFS)? Pick a starting node and push all its adjacent nodes into a stack. Pop a node from stack to select the next node to visit and push all its adjacent nodes into a stack. Repeat this process until the stack is empty. However, ensure that the nodes that are visited are marked. This will prevent you from visiting the same node more than once. If you do not mark the nodes that are visited and you visit the same node more than once, you may end up in an infinite loop.

Explain Breadth First Search (BFS)? First move horizontally and visit all the nodes of the current layer Move to the next layer. To avoid processing a node more than once, we use a boolean visited array.

Top 10 graph problems? 1. Breadth First Search (BFS) 2. Depth First Search (DFS) 3. Shortest Path from source to all vertices *Dijkstra* 4. Shortest Path from every vertex to every other vertex *Floyd Warshall* 5. To detect cycle in a Graph *Union Find* 6. Minimum Spanning tree *Prim* 7. Minimum Spanning tree *Kruskal* 8. Topological Sort 9. Boggle (Find all possible words in a board of characters) 10. Bridges in a Graph

How to check if a given Binary Tree is BST or not? If inorder traversal of a binary tree is sorted, then the binary tree is BST. The idea is to simply do inorder traversal and while traversing keep track of previous key value. If current key value is greater, then continue, else return false. See A program to check if a binary tree is BST or not for more details.

Which Data Structure Should be used for implementing LRU cache? We use two data structures to implement an LRU Cache. Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).The most recently used pages will be near front end and least recently pages will be near rear end. A Hash with page number as key and address of the corresponding queue node as value. See How to implement LRU caching scheme? What data structures should be used?

How to implement a queue using stack? A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways: Method 1 (By making enQueue operation costly) Method 2 (By making deQueue operation costly) See Implement Queue using Stacks

How to implement a stack using queue? A stack can be implemented using two queues. Let stack to be implemented be 's' and queues used to implement be 'q1' and 'q2'. Stack 's' can be implemented in two ways: Method 1 (By making push operation costly) Method 2 (By making pop operation costly) See Implement Stack using Queues

Can doubly linked be implemented using a single pointer variable in every node? Doubly linked list can be implemented using a single pointer. See XOR Linked List - A Memory Efficient Doubly Linked List

Which data structures are used for BFS and DFS of a graph? Queue is used for BFS Stack is used for DFS. DFS can also be implemented using recursion (Note that recursion also uses function call stack).

What is a Linked List and What are its types? A linked list is a linear data structure (like arrays) where each element is a separate object. Each element (that is node) of a list is comprising of two items - the data and a reference to the next node.Types of Linked List : Singly Linked List : In this type of linked list, every node stores address or reference of next node in list and the last node has next address or reference as NULL. For example 1->2->3->4->NULL Doubly Linked List : Here, here are two references associated with each node, One of the reference points to the next node and one to the previous node. Eg. NULL<-1<->2<->3->NULL Circular Linked List : Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. Eg. 1->2->3->1 [The next pointer of last node is pointing to the first] ...

What are Infix, prefix, Postfix notations? Infix notation: X + Y - Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D Postfix notation (also known as "Reverse Polish notation"): X Y + Operators are written after their operands. The infix expression given above is equivalent to A B C + * D/ Prefix notation (also known as "Polish notation"): + X Y Operators are written before their operands. The expressions given above are equivalent to / * A + B C D

What is a Queue, how it is different from stack and how is it implemented? Queue is a linear structure which follows the order is First In First Out (FIFO) to access elements. Mainly the following are basic operations on queue: Enqueue, Dequeue, Front, Rear The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added. Both Queues and Stacks can be implemented using Arrays and Linked Lists.

What is Stack and where it can be used? Stack is a linear data structure which the order LIFO(Last In First Out) or FILO(First In Last Out) for accessing elements. Basic operations of stack are : Push, Pop , Peek Applications of Stack: Infix to Postfix Conversion using Stack Evaluation of Postfix Expression Reverse a String using Stack Implement two stacks in an array Check for balanced parentheses in an expression

How is an Array different from Linked List? The size of the arrays is fixed, Linked Lists are Dynamic in size. Inserting and deleting a new element in an array of elements is expensive, Whereas both insertion and deletion can easily be done in Linked Lists. Random access is not allowed in Linked Listed. Extra memory space for a pointer is required with each element of the Linked list. Arrays have better cache locality that can make a pretty big difference in performance.

What are the various operations that can be performed on different Data Structures? Insertion − Add a new data item in the given collection of data items. Deletion − Delete an existing data item from the given collection of data items. Traversal − Access each data item exactly once so that it can be processed. Searching − Find out the location of the data item if it exists in the given collection of data items. Sorting − Arranging the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.

What are linear and non-linear data Structures? Linear: A data structure is said to be linear if its elements form a sequence or a linear list. Examples: Array. Linked List, Stacks and Queues Non-Linear: A data structure is said to be non-linear if traversal of nodes is nonlinear in nature. Example: Graph and Trees.

What is a Data Structure? A data structure is a way of organizing the data so that the data can be used efficiently

How have you used data to inform the development of your counselling program? I used data first hand for a community project that I created about prescription drug awareness .. I used pre and post surveys to give to the students so I could see the effectiveness of my program. I also had parents evaluate my program at the end for feedback as well. The data I collected helped me see what worked and what I could improve on if I choose to implement the program somewhere else.

Have you ever disagreed with your principal about how to handle an issue involving a student? What did you do? I did not have a situation during my field experience where I disagreed with the principal on a situation with a student. At the end of the day, myself and the principall are a team and I would want to be comfortable running ideas back and forth, receiving feedback from them, and being able to work together to help students resolve issues. If I really did not agree with the principal, I would try to have a conversation where we each talk about our side and see if I could see where he or she was coming from. We could work towards a compromise, but if the principal is adament about something, I would respect their wishes. If for some reason, I really felt the way it was handled was not in the students best interest, I would try to have a conversation about it with my principal in a very cautious way not to make them think I did not respect their decision.

What would you do if a student said they said they planned on killing themselves? I would immediately be alarmed and take it as an extremely serious thing. I would keep them in my office, and talk to them. I would try to find out more, have they just thought about it, or do they have a plan? Do they have access to the thing they want to use at home? I would gather information about the situation and immediately call and tell my principal. We would contact the parents but keep the child with me and comfort them, maybe let them play a game or colour in the meantime. I would explain that I am glad they told me and that I am here for them. I would have the parents come pick the child up and explain to them the process for when a child says they want to kill themselves. Whatever the school policy is, the parents would have to follow that. They might have to have their child evaluated before they can come back to school. I would keep doing follow-ups with the child and help connect the ...

If you had to develop your own comprehensive school counselling program on your first day on the job, how would you start? The first thing I would do would be to give out a needs assessment to faculty and parents. Since it would be a new place for me, I would want to gather data from the people who have been in school far longer than me. Depending on the age of the students, I would also give one to students as well to see what the believe the biggest issues in the school are. Once I got the needs assessment data, I could work on creating beliefs, a vision statement and a mission statement for how I want this program to help students in the future.

How would you help a child with anxiety feel better about school? Help get the parents connected with the teacher before the school year starts, or during the year. Have a meeting between the teacher, counsellor, and parents. Find out what routines take place within the class every day and see if the parents would be willing to do the same things at home to make the child feel more comfortable.

What are some personal goals? Know every student in my case loads name by end of year, that is very important to me, nothing is worse than someone saying Hi Ms.Burnett and I can't say Hi and there name back. Be proactive, instead of reactive. Making myself visible, not always in office. I also want to create something in the school that is new and my own, something that was not previously in place. Make myself feel like an asset to the building.

How do you deal with a difficult parent? Always let them know you hear them; listen; diffuse; set goal;) I would try my best to keep an open mind in any situation involving a difficult parent. I had to make a few calls to parents that were less than happy with what I was telling them, and I got good advice from my supervisor. She told me that there were times where a parent was so angry with her that no matter what she said, it did not matter. She had to tell a parent before that she was going to hang up the phone for a few minutes until things calmed down and that the parent could call back when they felt comfortable. This was usually a good way to diffuse some of the anger. I would always want to let the parents know that I am on their side and see things how they see it. I think establishing some kind of common ground would help and then once they realize I am an advocate for them as well, we can work towards a common goal.

Have I experienced burnout, how do I cope with it? I did experience burnout a bit during my internship when I was trying to balance work, school, and life .. I tried to set some time out for myself and I find that it's important to spend time with my family .. they ground me .. and I feel like exercising is also really important .. you know I was also a swimming coach, and coaches sometimes take on a counseling role .. so with me .. sometimes exercise helps me vent my problems ..

How would you deal with a teacher who does not respect the school counselor? I have come across that during my time during my internship .. and it's usually because the teacher doesn't understand the role of a school counselor. I would first try to understand where the teacher was coming from, and just listen .. try to collaborate with them .. maybe they had an unpleasant with another counselor .. I would try my best to support that teacher in some way .. maybe in the beginning of the year .. I could administer a survey to teachers and find out what they think a counselor's role is .. and then go from there. I feel like teachers spend the most time with the kids, so they are a valuable resource ..

What counselling theories most influence me? Because I feel like I'm still learning and sorting out my own counseling style, I subscribe to a couple of theories: for example .. rebt and cbt .. both of them are behavior based, and deal with a student's thinking pattern .. I also like solution focused because it's time oriented, and helps the student change the way they feel .. But I would have to build rapport and trust with the student before we even begin ..

How do you get a group of rowdy kids attention? In order to get a group of rowdy kids to pay attention to me or to the teacher I would try to get their attention by talking about something that greatly interests them. I would try to relate to something on their level whether it be a game they like, a sport, a movie etc. I would try to incorporate something they love into our conversation or a lesson to them. If there behavior is more intrusive to the school day than that, I would like to start a 6-8 group with the students where we could work towards better behaviors in a small group setting. I could create group lessons and activities geared toward appropriate classroom behavior, following rules, consequences of rowdy behavior, etc.

How do I handle a disruptive child? I would handle a disruptive child by trying to figure out what the root of the disruptive behavior is. Maybe it has to do with a lack of attention at home, maybe it could be ADHD, or it could be because the student just had a bad day, or forgot homework , or had an argument with a student that day. Usually, there is some reason behind it and I would want to meet with the student to get to the bottom of the behavior. If it was just something that happened one time, I would find out what caused the behavior and help support the student in resolving whatever it was that caused the behavior. If it was reoccurring, I would talk to the parents to find out if they are seeing the behavior at home, talk with the teacher to gain more information, and maybe see if we could come up with a motivating behavior plan for the student that could be informed in school, at home, or both. If that didn't work, we could maybe see if the student could get referred ...

What type of students am I most drawn to and which student do I have the most difficulty working with? I am most drawn to the students who tend to come from home where they do not get adequate attention from their parents, whether it be from a home where one parent is not in the picture, or if parents are occupied with work and other things just trying to survive that they cannot always give the child undivided attention. Those students that I have seen in my experience have tended to cling to me and relied on me for comfort during the school day. I formed many bonds with students that I started to love like they were my own children. I have such a desire to give students the support they lack at home and found myself really loving spending time with those children because they were so receptive to me and really enjoyed our time together. I find it difficult to work with students who do not understand the concept of cause and affect, or consequences in general. Students that do ...

What would you do if a student made a drawing that is alarming or concerning? I saw this first hand during my internship many times where teachers would come down to our office to show us an essay that seemed to give off some red flags. There was one that was very inappropriate and we had the student come down to the office and asked questions first to just see what the students intentions were. Sometimes it seems as though the child was very innocent in what they did, and other times it seems alarming. If I believe that the drawing is giving way to some other issue that is important, I will ask the student if they have talked about it with anyone, and that I should probably share it with their parent. I give them the option to call with me in the office, or to have me do it privately.

What does a successful and safe school environment look like to me? A successful and safe school environment would look like a few of these things. It would mean students wanting to come to school every day, having faculty greet them by name when they come into the building, giving them a positive start to the day each and every day. No matter what happened that morning, that maybe put their day off to a bad start, it would mean that someone in the school has the ability to turn it around and make the student feel like everything is going to be okay. I believe it would also mean that the faculty is engaged with the students in various activities such as assemblies, trips, guidance lessons, one on one meetings, etc. There would be strict policies in place that the students and faculty were educated on and students would know what to do in case of an emergency. The students would feel supported and would feel like they are not just another name in the school.

What is my main goal as a school counsellor? My main goal is to give students confidence in every area, including academic, personal/social, and career. I've learned through teaching and interning, that there's usually a lack of confidence in one of those areas, or all 3. The greatest gift as a counsellor is hearing a student succeed. Even students that face the biggest obstacles at home, deserve to feel like their future is wide open and that anything is possible. We do want our students to be realistic, but we also want to give them hope.

What is my experience with special education? I have experience teaching special education students in the general ed classroom. I've served on ARDS, and worked with other teachers and parents in coming up with IEP's In my internship, I advocated for a special education student whose teachers were having difficulty with her, and they felt like they couldn't reach her, so we worked together one on one on her organizational skills, and I also worked with the nurse to come up with a plan to help her remember to take her medication.

How a counsellor should and would work with a family who does not respond to communication or show much interest in working with the school faculty? Reach out in various ways, emails, calls, letters home, etc. I would continue to reach out because at least if the parents did not want to be involved, they could never argue that I did not put in all my effort. I would try to create a connection with the parents, make myself relatable to them, talk with my student to find out if there are reasons the parents are not communicating. Maybe there is a language barrier, maybe they do not have access to a computer, finding out these answers could lead me to a more beneficial way of communicating with them.

What is your general attitude toward disciplining students? Students need structure, but also it is important to be patient and flexible with them. Explain consequences to actions. At my practicum and internship, I did not have to discipline students. The principal or vice principal dealt with the disciplining, and I would meet with the students to talk about what happened and how we could move toward. This usually meant we discussed the actions, the thought process, and then set goals or decided on ways we could make a better decision for the future to keep the student from facing this kind of trouble again.

How do you intervene with at-risk students? I start by talking to the students and work with them to set personal goals. I often suggest getting involved with sports teams or after school programs. Finding motivation for them, something they enjoy, a passion, something to give them a sense of belonging. Lunch bunch groups at my internship- helping students make social connections. Help them get into a routine

How would you handle a student reporting abuse by a parent? I would make sure first and foremost that I was very familiar with the school's protocol when it comes to abuse because it can differ at different schools what needs to be done first. I would consult with my supervisor to see what the proper protocol is so I can make sure I am fulfilling all my legal duties while also following school rules. If the child was in my care, I would console them immediately and tell them how brave they are for telling me. I would stay with the child the entire time. In cases of abuse, someone in the school either myself, or the principal would call CPS or if necessary, the police. I would try to keep the student feeling comforted and safe by letting them play with toys, draw, write, anything that they tend to relax to. All of my decisions would be based on whatever is best for the student at that moment and going forward as well. In my experience, when students were telling me something r...

What made you want to become a guidance counsellor? I kind of stumbled onto counselling because as a computer teacher, kids would come to me during lunch and after school, and we would have mini counselling sessions. The kids needed someone to talk to and they trusted me enough to share their feelings about the different situations they were struggling with.

What in Your Job or Life Experience Makes You More Qualified for This Job than Your Peers? I believe that my experiences have led me to be a wonderful counselor. I spent the last year interning at Cole High School, but I also had the opportunity to work at the middle school and elementary school. I was lucky because the schools are in such close proximity with each other. I facilitated several groups .. at the elementary school .. I facilitated a feelings group with kinder and I had a couple of lunch bunches with 1st and 2nd graders. At the middle school, I had an anger management group with 6th, 7th, and 8th graders. At the high school, I facilitated a group of seniors and juniors who needed guidance with FAFSA and preparing for the SAT. I counseled students from all different economic statuses and a wide range of students with academic achievement and social status as well.