Please enable JavaScript.

Coggle requires JavaScript to display documents.

CtCI (Concepts & Algorithms (Sorting & Searching (Questions (1.…

- - - - 1.
        
        You are given two 32-bit numbers, N and M, and two bit positions, i and j.
        
        Write a method to set all bits between i and j in N equal to M
        
        e.g. M becomes a substring of N located at i and a starting at j
        
        Ex.
        
        Input: N = 10000000000, M = 10101, i = 2, j = 6
        
        Output: N = 10001010100
      - 2.
        
        Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binary representation.
        
        If the number can not be represented accurately in binary, print "ERROR"
      - 3.
        
        Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
      - 4.
        
        Explain what the following code does:
        
        ((n & (n - 1)) == 0)
      - 5.
        
        Write a function to determine the number of bits required to convert integer A to integer B.
        
        Input: 31, 14
        
        Output: 2
      - 6.
        
        Write a program to swap odd and even bits in an integer with as few instructions as possible.
        
        e.g. bit 0 and bit 1 are swapped
        
        e.g. bit 2 and bit 3 are swapped
      - 7.
        
        An array A[1...n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A[i]", which takes constant time.
        
        Write code to find the missing integer.
        
        Can you do it in O(n) time?
  - - - 1.
        
        Add arithmetic operators (+, -, *, /) to make the following expression true: 3 1 3 6 = 8
        
        Parentheses are allowed
      - 2.
        
        There is an 8x8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares.
        
        Can you use the 31 dominos to cover the entire board?
        
        Prove your answer (by providing an example, or showing it's impossible).
      - 3.
        
        You have a five quart jug and a three quart jug, and an unlimited supply of water (but no measuring cup). How would you come up with exactly four quarts of water?
        
        Note: The jugs are oddly shaped, such that filling up exactly 'half' a jug would be impossible.
      - 4.
        
        A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people's heads (i.e. at least one person has a hat).
        
        The hat is magical: it can be seen by other people, but not by the wearer of the hat himself.
        
        To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight.
        
        If there are N people and C hats, how long does it take the men to remove the hats?
        
        The men cannot tell each other (in any way) that they have a hat.
      - 5.
        
        There is a building of 100 floors.
        If an egg drops from the Nth floor or above, it will break.
        If it's dropped from any floor below, it will not break.
        
        You're given 2 eggs. Find N, while minimizing the number of drops for the worst case.
      - 6.
        
        There are 100 closed lockers in a hallway. A man begins by opening all 100 lockers.
        
        Next, he closes every second locker.
        
        Then he goes to every third locker and closes it if it is open or opens it if it is closed (e.g. toggles every third locker).
        
        After his 100th pass in the hallway, in which he toggles only locker number 100, how many lockers are open?
  - - - 1.
        
        Design the data structures for a generic deck of cards.
        
        Explain how you would sub-class it to implement particular card games.
      - 2.
        
        Image you have a call center with 3 levels of employees; fresher, technical lead (TL), product manager (PM).
        
        There can be multiple employees, but only one TL or PM.
        
        An incoming call must be allocated to a fresher who is free.
        
        If a fresher can't handle the call, he/she must escalate the call to technical lead.
        
        If the TL is not free or not able to handle it, then the call should escalate to PM.
        
        Design the classes and data structures for this problem.
        
        Implement a method getCallHandler()
      - 3.
        
        Design a musical jukebox using object oriented principles.
      - 4.
        
        Design a chess game using object oriented principles.
      - 5.
        
        Design the data structures for an online book reader system.
      - 6.
        
        Implement a jigsaw puzzle.
        
        Design the data structures and explain an algorithm to solve the puzzle.
      - 7.
        
        Explain how you would design a chat server.
        
        In particular, provide details about the various backend components, classes, and methods.
        
        What would be the hardest problems to solve?
      - 8.
        
        Othello is played as follows:
        
        Each Othello piece is white on one side and black on the other.
        
        When a piece is surrounded by its opponents on both the left and right sides, or both the top and bottom, it is said to be captured and its color is flipped.
        
        On your turn, you must capture at least one of your opponent's pieces.
        
        The game ends when either user has no more valid moves, and the win is assigned to the person with the most pieces.
        
        Implement the object oriented design for Othello.
      - 9.
        
        Explain the data structures and algorithms that you would use to design an in-memory file system.
        
        Illustrate with an example in code where possible.
      - 10.
        
        Describe the data structures and algorithms that you would use to implement a garbage collector in C++.
  - - - 1.
        
        Write a method to generate the nth Fibonacci number.
      - 2.
        
        Imagine a robot sitting on the upper left hand corner of an NxN grid.
        
        The robot can only move in two directions: right and down
        
        How many possible paths are there for the robot?
        
        Follow Up: Image certain squares are "off limits", such that the robot can not step on them
        
        Design an algorithm to get all possible paths for the robot.
      - 3.
        
        Write a method that returns all subsets of a set.
      - 4.
        
        Write a method that computes all permutations of a string.
      - 5.
        
        Implement an algorithm to print all valid (e.g. properly opened and closed) combinations of n-pairs of parentheses.
        
        Ex.
        
        input: 3 (e.g. 3 pairs of parentheses)
        
        output: ()()(), ()(()),((()))
      - 6.
        
        Implement the "paint fill" function that one might see on many image editing programs.
        
        That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.
      - 7.
        
        Given an infinite number of quarters, dimes, nickels, and pennies, write code to calculate the number of ways of representing n cents.
      - 8.
        
        Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.
  - - - 1.
        
        You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.
      - 2.
        
        Write a method to sort an array of strings so that all the anagrams are next to each other.
      - 3.
        
        Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array.
        
        You may assume that the array was originally sorted in increasing order.
        
        Ex.
        
        Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
        
        Output: 8 (the index of 5 in the array)
      - 4.
        
        If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?
      - 5.
        
        Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
        
        Ex.
        
        Find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
        
        Ex.
        
        Find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1
      - 6.
        
        Given a matrix in which each row and each column is sorted, write a method to find an element in it.
      - 7.
        
        A circus is designing a tower routine consisting of people standing atop one another's shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her.
        
        Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
        
        Ex.
        
        Input (ht, wt): (5, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
        
        Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)
  - - - 1.
        
        You have a basketball hoop and someone says that you can play 1 of 2 games.
        
        Game #1: You get one shot to make the hoop
        
        Game #2: You get three shots and you have to make 2 of 3 shots.
        
        If p is the probability of making a particular shot, for which values of p should you pick one game or the other?
      - 2.
        
        There are three ants on different vertices of a triangle.
        What is the probability of collision (between two or all of them) if they start walking on the sides of the triangle?
        
        Similarly find the probability of collision with 'n' ants on an 'n' vertex polygon.
      - 3.
        
        Given two lines on a Cartesian plane, determine whether the two lines would intersect.
      - 4.
        
        Write a method to implement (* ,- ,/) operations.
        
        You should use only the + operator.
      - 5.
        
        Given two squares on a two dimensional plane, find a line that would cut these two squares in half.
      - 6.
        
        Given a two dimensional graph with points on it, find a line which passes the most number of points.
      - 7.
        
        Design an algorithm to find the kth number such that only prime factors are 3, 5, and 7.
  - - - 1.
        
        Find the mistake(s) in the following code:
        
        unsigned int i;
        for (i = 100; i <= 0; --i)
        printf("%d\n", i);
      - 2.
        
        You are given the source to an application which crashes when it runs.
        
        After running it ten times in a debugger, you find it never crashes in the same place.
        
        The application is single threaded, and only uses the C standard library.
        
        What programming errors could be causing this crash?
        How would you test each one?
      - 3.
        
        We have the following method used in a chess game:
        
        boolean canMoveTo(int x, int y) (x and y are the coordinates of the chess board and it returns whether or not the piece can move to that position.
        
        Explain how you would test this method.
      - 4.
        
        How would you load test a webpage without using any test tools?
      - 5.
        
        How would you test a pen?
      - 6.
        
        How would you test an ATM in a distributed banking system?
  - - - 1.
        
        If you were integrating a feed of end of day stock price information (open, high, low, and closing price) for 5,000 companies, how would you do it?
        
        You are responsible for the development, rollout and ongoing monitoring and maintenance of the feed.
        
        Describe different methods you considered and why you would recommend your approach.
        
        The feed is delivered once per trading day in a comma-separated format via an FTP site.
        
        The feed will be used by 1,000 daily users in a web application.
      - 2.
        
        How would you design the data structures for a very large social network (FB, LinkedIn, etc)?
        
        Describe how you would design an algorithm to show the connection, or path, between two people.
        
        e.g. Me -> Bob -> Susan -> Jason -> You
      - 3.
        
        Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file.
        
        Assume you have 1 GB of memory.
        
        Follow Up
        
        What if you only have 10 MB of memory?
      - 4.
        
        You have an array with all the numbers from 1 to N, where N is at most 32,000.
        
        The array may have duplicate entries and you do not know what N is.
        
        With only 4KB of memory available, how would you print all duplicate elements in the array?
      - 5.
        
        If you were designing a web crawler, how would you avoid getting into infinite loops?
      - 6.
        
        You have a billion urls, where each is a huge page.
        
        How do you detect the duplicate documents?
      - 7.
        
        You have to design a database that can store terabytes of data.
        
        It should support efficient range queries.
        
        How do you do it?
- - - - 1.
        
        Write a method to print the last K lines of an input file using C++.
      - 2.
        
        Compare and contrast a hash table vs. an STL map.
        
        How is a hash table implemented?
        
        If the number of inputs is small, what data structure options can be used instead of a hash table?
      - 3.
        
        How do virtual functions work in C++?
      - 4.
        
        What is the difference between deep copy and shallow copy?
        
        Explain how you would use each.
      - 5.
        
        What is the significance of the keyword "volatile" in C?
      - 6.
        
        What is name hiding in C++?
      - 7.
        
        Why does a destructor in base class need to be declared virtual?
      - 8.
        
        Write a method that takes a pointer to a Node structure as a parameter and returns a complete copy of the passed-in data structure.
        
        The Node structure contains two pointers to other Node structures.
      - 9.
        
        Write a smart pointer (smart_ptr) class.
  - - - 1.
        
        In terms of inheritance, what is the effect of keeping a constructor private?
      - 2.
        
        In Java, does the finally block get executed if we insert a return statement inside the try block of a try-catch-finally?
      - 3.
        
        What is the difference between final, finally, and finalize?
      - 4.
        
        Explain the difference between templates in C++ and generics in Java.
      - 5.
        
        Explain what object reflection is in Java and why it is useful.
      - 6.
        
        Suppose you are using a map in your program, how would you count the number of times the program calls the put() and get() functions?
  - - - 1.
        
        Write a method to find the number of employees in each department.
      - 2.
        
        What are the different types of joins?
        
        Please explain how they differ and why certain types are better in certain situations.
      - 3.
        
        What is denormalization?
        
        Explain the pros and cons.
      - 4.
        
        Draw an entity-relationship diagram for a database with companies, people, and professionals (people who work for companies).
      - 5.
        
        Imagine a simple database storing information for students' grades.
        
        Design what this database might look like, and provide a SQL query to return a list of the honor roll students (top 10%), sorted by their grade point average.
  - - - 1.
        
        Explain the following terms:
        
        Virtual Memory
        
        Page Fault
        
        Thrashing
      - 2.
        
        What is a Branch Target buffer?
        
        Explain ho it can be used in reducing bubble cycles in case of branch misprediction.
      - 3.
        
        Describe direct memory access (DMA).
        
        Can a user level buffer / pointer be used by kernel or drivers?
      - 4.
        
        Write a step by step execution of things that happen after a user presses a key on the keyboard.
        
        Use as much detail as possible.
      - 5.
        
        Write a program to find whether a machine is big endian or little endian.
      - 6.
        
        Discuss how you would make sure that a process doesn't access an unauthorized part of the stack.
      - 7.
        
        What are the best practices to prevent reverse engineering of DLLs?
      - 8.
        
        A device boots with an empty FIFO queue.
        
        In the first 400 ns period after startup, and in each subsequent 400 ns period,a maximum of 80 words will be written to the queue.
        
        Each write takes 4 ns.
        
        A worker thread requires 3 ns to read a word, and 2 ns to process it before reading the next word.
        
        What is the shortest depth of the FIFO such that no data is lost?
      - 9.
        
        Write an aligned malloc & free function that takes number of bytes and aligned byte (whic is always power of 2)
        
        Ex.
        
        align_malloc (1000, 128) will return a memory address that is a multiple of 128 and that points to memory of size 1000 bytes.
        
        aligned_free() will free memory allocated by align_malloc
      - 10.
        
        Write a function called my2DAlloc which allocates a two dimensional array.
        
        Minimize the number of calls to malloc and make sure that the memory is accessible by the notation arr[i][j].
  - - - 1.
        
        Explain what happens, step by step, after you type a URL into a browser.
        
        Use as much detail as possible.
      - 2.
        
        Explain any common routing protocol in detail.
        
        Ex.
        
        BFP
        
        OSPF
        
        RIP
      - 3.
        
        Compare and contrast the IPv4 and IPv6 protocols.
      - 4.
        
        What is a network / subnet mask?
        
        Explain how host A sends a message / packet to host B when:
        
        (a) both are on the same network
        
        (b) both are on different networks.
        
        Explain which layer makes the routing decisions and how.
      - 5.
        
        What are the differences between TCP and UDP?
        
        Explain how TCP handles reliable delivery (explain ACK mechanism), flow control (explain TCP sender's / receiver's window) and congestion control.
  - - - 1.
        
        What's the difference between a thread and a process?
      - 2.
        
        How can you measure the time spent in a context switch?
      - 3.
        
        Implement a singleton design pattern as a template such that, for any given class Foo, you can call Singleton::instance() and get a pointer to an instance of a singleton of type Foo.
        
        Assume the existence of a class Lock which has acquire() and release() methods.
        
        How could you make your implementation thread safe and exception safe?
      - 4.
        
        Design a class which provides a lock only if there are no possible deadlocks.
      - 5.
        
        Suppose we have the code: (Reference GoogleDrive Doc)
      - 6.
        
        You are given a class with synchronized method A, and a normal method C.
        
        If you have two threads in one instance of a program, can they call A at the same time?
        
        Can they call A and C at the same time?
- - - - 1.
        
        Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
      - 2.
        
        Write code to reverse a C-Style String. (C-String means that “abcd” is represented as !ve characters, including the null character.)
      - 3.
        
        Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer.
        
        Follow Up: Write the test cases for this method.
        
        Note: One or two additional variables are okay. An extra copy of the array is not.
      - 4.
        
        Write a method to decide if two strings are anagrams or not.
      - 5.
        
        Write a method to replace all spaces in a string with ‘%20’.
      - 6.
        
        Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
      - 7.
        
        Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
      - 8.
        
        Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).
  - - - 1.
        
        Write code to remove duplicates from an unsorted linked list.
        
        Follow Up: How would you solve this problem if a temporary buffer is not allowed?
      - 2.
        
        Implement an algorithm to find the nth to last element of a singly linked list.
      - 3.
        
        Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
        
        Ex.
        
        Input: the node ‘c’ from the linked list a->b->c->d->e
        
        Result: nothing is returned, but the new linked list looks like a->b->d->e
      - 4.
        
        You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
        
        Ex.
        
        Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
        
        Result: 8 -> 0 -> 8
      - 5.
        
        Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
        
        Circular LL
        
        A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
        
        Ex.
        
        Input: A -> B -> C -> D -> E -> C (Same C as earlier in LL)
        
        Result: C
  - - - Describe how you could use a single array to implement three stacks.
      - How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.
      - 3.
        
        Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold.
        
        Follow Up: Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.
        
        SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity.
        
        Implement a data structure SetOfStacks that mimics this.
        
        SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack.
        
        pop() should return the same values as it would if there were just a single stack).
      - 4.
        
        In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one).
        
        You have the following constraints
        
        Only one disk can be moved at a time.
        
        A disk is slid off the top of one rod onto the next rod.
        
        A disk can only be placed on top of a larger disk.
        
        Write a program to move the disks from the first rod to the last using Stacks.
      - 5.
        
        Implement a MyQueue class which implements a queue using two stacks.
      - 6.
        
        Write a program to sort a stack in ascending order.
        
        You should not make any assumptions about how the stack is implemented.
        
        The following are the only functions that should be used to write this program: push | pop | peek | isEmpty
  - - - 1.
        
        Implement a function to check if a tree is balanced.
        
        A balanced tree here is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.
      - 2.
        
        Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
      - 3.
        
        Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.
      - 4.
        
        Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth.
        
        I.E. if you have a tree with depth D, you'll have D linked lists.
      - 5.
        
        Write an algorithm to find the 'next' node of a given node in a binary search tree where each node has a link to its parent.
      - 6.
        
        Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree.
        
        Avoid storing additional nodes in a data structure.
        
        Note: This is not necessarily a binary search tree.
      - 7.
        
        You have two very large binary trees
        
        T1, with millions of nodes
        
        T2, with hundreds of nodes
        
        Create an algorithm to decide if T2 is a subtree of T1
      - 8.
        
        You are given a binary tree in which each node contains a value.
        Design an algorithm to print all paths which sum up to that value.
        
        Note: it can be any path in the tree - it doesn't have to start at the root.
- - - - Write strong bullet points
        
        Format:
        Accomplished X by implementing Y which led to Z
      - Project experience
        
        Look into open source
        
        Work on team projects
        
        Personal Projects
        
        Have a Projects section
        
        List 2-4 most relevant projects
        
        Separate Course projects and Independent projects
      - Software
        
        List only developer specific or technical software
      - Languages
        
        List most languages you’ve used
        
        Format
        Java (expert), C++ (proficient), JavaScript (prior experience), C (prior experience)
        
        Add your experience level #
      - Filter relevant experience to the job
    - - How to Prepare
        
        Preparation Grid
        
        Create a table with columns represented by your projects and rows represented by conversation points
        
        The conversation points are as listed:
        
        Most Challenging
        
        What You Learned
        
        Most Interesting
        
        Hardest Bug
        
        Enjoyed Most
        
        Conflicts with Teammates
        
        Fill in table with the most relevant projects
        
        Find keywords that stick out and practice
        
        Suggestions
        
        Give a real weakness if they ask for one.
        Tell them how you plan to overcome said weakness.
        
        When ask about most challenging, don't fall back on "Learned new technologies"
        
        Don't just answer the questions.
        Communicate what they mean to you.
        
        Create a Behavioral Preparation Grid
        Similar to a Preparation Grid but with rows like:
        
        Challenging Interaction
        
        Failure
        
        Success
        
        Influencing People
      - Questions for Interviewer
        
        Genuine
        
        "How much of your day do you spend coding?"
        
        "How many meetings do you have every week?"
        
        "What is the ratio of testers to developers to product managers? Interaction between them? Project planning?"
        
        Insightful
        
        "I noticed you use technology X. How do you handle problem Y?"
        
        "Why did the product choose to use the X protocol over the Y protocol?
        
        Passion
        
        "I'm very interested in X. Did you come in with a background in this, or what opportunities are there to learn about it?"
        
        "I'm not familiar with technology X, but it sounds like a very interesting solution. Could you tell me a bit more about how it works?"
    - - How to Prepare
        
        Solve the problems on your own.
        
        Analyze your thought processes throughout the problem.
        
        Think about space and time efficiency.
        
        Ask if these things can be improved with different solutions.
        
        Write algorithm code on paper.
        
        Simulate a white board situation as best as possible.
        
        Type paper code as-is into a computer
        
        Keep track of mistakes to watch out for.
        
        Do a mock interview
        
        CareerCup
      - What to Know
        
        Must Know
        
        Data Structures
        
        Linked Lists
        
        Binary Trees
        
        Tries
        
        Stacks
        
        Queues
        
        Vectors / ArrayLists
        
        Hash Tables
        
        Algorithms
        
        Breadth First Search
        
        Depth First Search
        
        Binary Search
        
        Merge Sort
        
        Quick Sort
        
        Tree Insert / Find / etc
        
        Concepts
        
        Bit Manipulation
        
        Singleton Design Pattern
        
        Factory Design Pattern
        
        Memory(Stack vs Heap)
        
        Recursion
        
        Big-O-Time
        
        Additional
        
        Prepare for questions related to job field
        
        Research company interview techniques / questions through websites like Glassdoor / CareerCup
        
        Expand the need to know knowledge to make it relevant to the position
  - - - Be Specific, Not Arrogant
      - Limit Details
        
        Stay light on technical details and focus on key points
        
        Ask if they would like more detail if you can
      - Structure Answers
        
        S.A.R.
        
        Situation
        
        Outline the situation
        
        Action
        
        Explain the actions you took
        
        Response
        
        Describe the results of your actions
    - - General
        
        Even if you don't know, start talking, start solving.
        
        You're not done until the interviewer say so
        
        Look for bugs
        
        Try some testing
      - 5 Step Process
        
        Resolve Ambiguity
        
        Ask questions to clarify the problem
        
        What are the data types?
        
        How much data is there?
        
        What assumptions do you need to solve the problem?
        
        Who is the user?
        
        Some interviewers look for good questions
        
        Design an Algorithm
        
        What are the space and time complexities?
        
        What happens if there is a lot of data?
        
        Does your design cause other issues?
        
        If there are other issues, did you make the right trade-off?
        
        If they gave specific data, have you leveraged that information?
        
        Pseudo-Code
        
        Communicate your writing pseudo-code
        
        Code
        
        Be slow and methodical
        
        Use Data Structures Generously
        
        Shows you care about good OO design
        
        Don't crowd the code
        
        Be conscious of the the board
        
        Test
        
        Extreme Cases
        
        0
        
        null
        
        maximums
        
        User error: What happens if the user passes in null or a negative value?
        
        General Cases
        
        Consider testing complex or highly numerical algorithms while writing code.
        Should always get what you expect so there is no backtracking.
        
        If you failed, think and explain why you failed.
      - 5 Algorithm Approaches
        
        Examplify
        
        Write out specific examples of the problem.
        See if there is a general rule.
        
        Apply general rule to the problem at hand.
        
        Pattern Matching
        
        Consider what problems the algorithm is similar to.
        Figure out if you can modify the solution to develop an algorithm to the problem at hand.
        
        Simplify & Generalize
        
        Change a constraint (data type, size, etc.) to simplify the problem.
        
        If you can solve the simplified version, create an algorithm for it.
        
        Apply the general algorithm to the more complex problem with the gaps filled in.
        
        Base Case & Build
        
        Solve the algorithm first for a base case.
        
        Once solved base case, solve element 1 and 2.
        
        Then 1, 2, and 3
        
        Find the pattern and start implementing.
        
        These problems typically resolve to recursion problems
        
        Data Structure Brainstorm
        
        Simply run the problem through a list of data structures until the most appropriate selection appears
    - - Practice on a Computer
        
        Only use a computer to verify your solutions
      - Not Rehearsing Behavioral Questions
        
        Relatively easy to practice and makes up usually half of the test.
      - Not doing a Mock Interview
      - Trying to Memorize Solutions
        
        Companies need problem solvers, not problem memorizers
      - Talking too Much
        
        Remember the S.A.R. structure
      - Talking too Little
        
        Communicate your thought process, but don't ramble.
      - Rushing
        
        Rushing will make you seem nervous and can lead to detrimental mistakes.
        
        Be slow and methodical.
      - Not Debugging
        
        Debug throughout to avoid mistakes down the road.
        
        Debug at the end to ensure accuracy.
      - Sloppy Coding
        
        Write for maintainability.
        
        Keep good OOP design patterns
        
        Keep data structures in line.
        
        No duplicate code
      - Giving Up
        
        Interviews typically get harder as they go. You will struggle no matter what.
        
        The interviewer wants to see your problem solving skills, even if the problem doesn't necessarily get solved in the end.
- - - - 1.
        
        Write a function to swap a number in place without temporary variables.
      - 2.
        
        Design an algorithm to figure out if someone has won in a game of tic-tac-toe.
      - 3.
        
        Write an algorithm which computes the number of trailing zeros in N factorial.
      - 4.
        
        Write a method which finds the maximum of two numbers.
        
        You should not use if-else or any other comparison operator.
        
        Ex.
        
        Input: 5, 10
        
        Output: 10
      - 5.
        
        The Game of Master Mind is played as follows:
        
        The computer has four slots containing balls that are red (R), yellow (Y), green (G) or blue (B). For example, the computer might have RGGB.
        
        You, the user, are trying to guess the solution. You might, for example, guess YRGB.
        
        When you guess the correct color for the correct slot, you get a "hit". If you guess a color that exists but is in the wrong slot, you get a "pseudo-hit" .For example, the guess YRGB has 2 hits and 1 pseudo hit.
        
        For each guess, you are tld the number of hits and pseudo-hits.
        
        Write a method that, given a guess and a solution, returns the number of hits and pseudo hits.
      - 6.
        
        Given an integer between 0 and 999,999, print an English phrase that describes the integer (eg, "One Thousand, Two Hundred and Thirty Four")
      - 7.
        
        You are given an array of integers (both positive and negative).
        
        Find the continuous sequence with the largest sum. Return the sum.
        
        Ex.
        
        Input: {2, -8, 3, -2, 4, -10}
        
        Output: 5 (i.e., {3, -2, 4})
      - 8.
        
        Design a method to find the frequency of occurrences of any given word in a book.
      - 9.
        
        Since XML is very verbose, you are given a way of encoding it where each tag gets mapped to a predefined integer value.
        
        The language/grammar is as follows:
        
        Element -> Element Attr* END Element END [aka, encode the element tag, then its attributes, then tack on an END character, then encode its children, then another end tag]
        Attr -> Tag Value [assume all values are strings]
        END -> 01
        Tag -> some predefined mapping to int
        Value -> string value END
        
        Write code to print the encoded version of an xml element (passed in as string).
        
        Follow Up
        
        Is there anything else you could do to (in many cases) compress this even further?
      - 10.
        
        Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5 (i.e. implement rand7() using rand5())
      - 11.
        
        Design an algorithm to find all pairs of integers within an array which sum to a specified value.
  - - - 1.
        
        Write a function that adds two numbers.
        
        You should not use + or any arithmetic operators.
      - 2.
        
        Write a method to shuffle a deck of cards.
        
        Assume that you are given a random number generator which is perfect.
        
        It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely.
      - 3.
        
        Write a method to randomly generate a set of m integers from an array of size n.
        
        Each element must have equal probability of being chosen.
      - 4.
        
        Write a method to count the number of 2s between 0 and n.
      - 5.
        
        You have a large text file containing words.
        
        Given two words, find the shortest distance (in terms of number of words) between them in the file.
        
        Can you make the searching operation in O(1) time?
        
        What about the space complexity for you solution?
      - 6.
        
        Describe an algorithm to find the largest 1 million numbers in 1 billion numbers.
        
        Assume that the computer memory can hold all one billion numbers.
      - 7.
        
        Write a program to find the longest word made of other words in a list of words.
        
        Ex.
        
        Input: test, tester, testertest, testing, testingtester
        
        Output: testingtester
      - 8.
        
        Given a string s and an array of smaller strings T, design a method to search s for each small string in T.
      - 9.
        
        Numbers are randomly generated and passed to a method.
        
        Write a program to find and maintain the median value as new values are generated.
      - 10.
        
        Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time.
        
        The new word you get in each step must be in the dictionary.
        
        Ex.
        
        Input: DAMP, LIKE
        
        Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE
      - 11.
        
        Imagine you have a square matrix, where each cell is filled with either black or white.
        
        Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
      - 12.
        
        Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.
      - 13.
        
        Given a dictionary of millions of words, give an algorithm to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom).