Interview Questions

Mixpanel
Ten most frequent triplets
1 a
2 b
1 b
1 c
2 c
2 d
1 d
----------
abc 1
bcd 2


Salesforce
java memory leak possible?
inheritance
hashmap vs tree what's the reason to choose one over another
why use ajax
external sorting of 16G file numbers with 1G mem
1-n relationship how many tables


ipsy
First missing positive integer in array (swap O(N) solution)
Patterns (Singleton (eager, lazy), Observer)


Pure Storage
JIT compiler
left outer join
synchronization and why
java, c++, hadoop, spark, ML, frontend experiences


PRO Unlimited
Spring components, ElasticSearch, Javascript experiences
String (immutable), StringBuilder, StringBuffer (thread safe)
List vs Set (duplicate or not)
HashMap vs Properties (hash, fast lookup)
Comparator/Comparable
ExecuteService, thread pool, Runnable, Callable
SQL group by
coding: change elements after multiples of 10 element [7,8,9,10,15,16,30,15,10,12,8] -> [7,8,9,10,10,10,30,30,10,10,10]
coding: given root dir, get all "*tmp*" filenames in the dir and its subdir
brain teasing: 9 balls, 1 is different weight, a balance to weigh (at most 4 times to find the different ball)


FB
1. version control sys, find first bad version, there is function boolean isBad(int v) (int findBad(int good, int bad)) - binary search, while(start<end-1), return end;
2. parlindrome string (escape punctuations and spaces)


Bill.com
what is RESTful API? how to handle heavy traffic?
reverse char array and return new reversed array (test cases?)
reverse char array in place (test cases?)


Smule
1. MultiMap - thread safe
class MultiMap<K, V> {
    private Map<K, List<V>> map = new ConcurrentHashMap<K, List<V>>();  
    public List<V> get(K key) {
        return new ArrayList(map.get(key)); // put value while iterating through list
    }
    public synchronized void put(K key, V value) { //synchronized
        if(map.contains(key)) {
            List<V> valueList = map.get(key);
            valueList.add(value);
            //map.put(key, valueList);
        } else {
            List<V> valueList = new ArrayList<V>();
            valueList.add(value);
            map.put(key, valueList);
        }
       
    }
    public synchronized void remove(K key) { // synchronized
        map.remove(key);
    }
}

2. design library, book on shelf, due date, check out date

create table Book (
id number (primary key),
bookname varchar(256),
isbn varchar(64)
);

create table Record (
  recordid number (primary key),
  bookid number,
  borrowerId number,
  checkoutDate date,
  dueDate date,
  returnDate date
);

create table Borrower (
id number(primary key),
name varchar(64),
phone varchar(10)
);

// books borrowed by a user which are overdue
select bookname from Record join Book
on Record.bookid=Book.id
where Record.borrowerId=12345
and returnDate=null
and now()>dueDate;

// all borrowing record of a book
select * from Record where bookid=12345 order by checkoutDate;

// return a book
update Record set returnDate=now()
where bookid=12345 and borrowerid=54321 and isReturned=false;

RAID

Redundant Array of Independent Disks

RAID 0 - striping, no data protection, only increase storage/retrieval speed
RAID 1 - mirroring, 1/2 of usable space
RAID 5 - parity, 3+ drives, n-1 disks of usable space
RAID 6 - 2 parities, 4+ drives, n-2 disks of usable space
RAID 10 - RAID 0 + RAID 1, 1/2 of usable space

https://www.youtube.com/watch?v=PP0iQs8qBNU

JMockit

    final static String HTTP_RESP = "Test HTTP response\nHello World!\n";
   
    @Test
    public void test(@Mocked final URLConnection conn, @Mocked final URL url) throws IOException {
       
        new NonStrictExpectations() {
            {
                url.openConnection(); returns(conn);
                conn.getInputStream(); returns(new ByteArrayInputStream(HTTP_RESP.getBytes()));
            }
        };

        Assert.assertEquals(HTTP_RESP, getResponseStr());
    }
   
    public String getResponseStr() throws IOException {
        StringBuilder sb = new StringBuilder();
        URL url = new URL("http://www.google.com");
        URLConnection conn = url.openConnection();
        BufferedReader reader = new BufferedReader(new InputStreamReader(conn.getInputStream()));
        String line = null;
        while((line = reader.readLine()) != null) {
            sb.append(line).append("\n");
        }
        return sb.toString();
    }

http://abhinandanmk.blogspot.com/2012/06/jmockit-tutoriallearn-it-today-with.html

Type Safety

Type safety is closely linked to memory safety, a restriction on the ability to copy arbitrary bit patterns from one memory location to another. For instance, in an implementation of a language that has some type t, such that some sequence of bits (of the appropriate length) does not represent a legitimate member of t, if that language allows data to be copied into a variable of type t, then it is not type-safe because such an operation might assign a non-t value to that variable. Conversely, if the language is type-unsafe to the extent of allowing an arbitrary integer to be used as a pointer, then it is not memory-safe.
Java
The Java language is designed to enforce type safety. Anything in Java happens inside an object and each object is an instance of a class.

To implement the type safety enforcement, each object, before usage, needs to be allocated. Java allows usage of primitive types but only inside properly allocated objects.

Sometimes a part of the type safety is implemented indirectly: e.g. the class BigDecimal represents a floating point number of arbitrary precision, but handles only numbers that can be expressed with a finite representation. The operation BigDecimal.divide() calculates a new object as the division of two numbers expressed as BigDecimal.

In this case if the division has no finite representation, as when one computes e.g. 1/3=0.33333..., the divide() method can rise an exception if no rounding mode is defined for the operation. Hence the library, rather than the language, guarantees that the object respects the contract implicit in the class definition.

C++
Some features of C++ that promote more type-safe code:

    The new operator returns a pointer of type based on operand, whereas malloc returns a void pointer.
    C++ code can use virtual functions and templates to achieve polymorphism without void pointers.
    Preprocessor constants (without type) can be rewritten as const variables (typed).
    Preprocessor macro functions (without type) can be rewritten as inline functions (typed). The flexibility of accepting and returning different types can still be obtained by function overloading.
    Safer casting operators, such as dynamic_cast that performs run-time type checking.

Java 7 new features

Diamond Operator
Map<String, List<Trade>> trades = new TreeMap <> ();


Using strings in switch statements
compared against the case label by using the String.equals() method


Automatic resource management
Resources such as Connections, Files, Input/OutStreams, etc. should be closed manually by the developer by writing bog-standard code.

try (BufferedReader br = new BufferedReader(new FileReader(path)); PrintWriter pw = ...) {
    pw.println(br.readLine());
}

Behind the scenes, the resources that should be auto closed must implement java.lang.AutoCloseable interface.


Numeric literals with underscores
int million  =  1_000_000


Improved exception handling
try {
} catch(ExceptionOne | ExceptionTwo | ExceptionThree e) {
}


New file system API (NIO 2.0)
There were methods such as delete or rename that behaved unexpected in most cases. Working with symbolic links was another issue.
The NIO 2.0 has come forward with many enhancements. It’s also introduced new classes to ease the life of a developer when working with multiple file systems.
Path path = Paths.get("c:\\Temp\\temp");
Files.deleteIfExists(path);
Files.copy(..)
Files.move(..)
Files.createSymbolicLink(..)

File change notifications
The WatchService API lets you receive notification events upon changes to the subject (directory or file).


Fork and Join
Basically the Fork-Join breaks the task at hand into mini-tasks until the mini-task is simple enough that it can be solved without further breakups. It’s like a divide-and-conquer algorithm. One important concept to note in this framework is that ideally no worker thread is idle. They implement a work-stealing algorithm in that idle workers “steal” the work from those workers who are busy.
The core classes supporting the Fork-Join mechanism are ForkJoinPool and ForkJoinTask. The ForkJoinPool is basically a specialized implementation of ExecutorService


Supporting dynamism
This makes VM changes to incorporate non-Java language requirements. A new package, java.lang.invoke, consisting of classes such as MethodHandle, CallSite and others, has been created to extend the support of dynamic languages.

http://radar.oreilly.com/2011/09/java7-features.html

Two phase commit

2PC - A feature of transaction processing systems that enables databases to be returned to the pre-transaction state if some error condition occurs. A single transaction can update many different databases. The two-phase commit strategy is designed to ensure that either all the databases are updated or none of them, so that the databases remain synchronized.

Database changes required by a transaction are initially stored temporarily by each database. The transaction monitor then issues a "pre-commit" command to each database which requires an acknowledgment. If the monitor receives the appropriate response from each database, the monitor issues the "commit" command, which causes all databases to simultaneously make the transaction changes permanent.

Commit request phase

or voting phase

1. The coordinator sends a query to commit message to all cohorts and waits until it has received a reply from all cohorts.
2. The cohorts execute the transaction up to the point where they will be asked to commit. They each write an entry to their undo log and an entry to their redo log.
3. Each cohort replies with an agreement message (cohort votes Yes to commit), if the cohort's actions succeeded, or an abort message (cohort votes No, not to commit), if the cohort experiences a failure that will make it impossible to commit.

Commit phase

or Completion phase

Success

If the coordinator received an agreement message from all cohorts during the commit-request phase:

1. The coordinator sends a commit message to all the cohorts.
2. Each cohort completes the operation, and releases all the locks and resources held during the transaction.
3. Each cohort sends an acknowledgment to the coordinator.
4. The coordinator completes the transaction when all acknowledgments have been received.

Failure

If any cohort votes No during the commit-request phase (or the coordinator's timeout expires):

1. The coordinator sends a rollback message to all the cohorts.
2. Each cohort undoes the transaction using the undo log, and releases the resources and locks held during the transaction.
3. Each cohort sends an acknowledgement to the coordinator.
4. The coordinator undoes the transaction when all acknowledgements have been received.

http://en.wikipedia.org/wiki/Two-phase_commit_protocol

Y2038 Bug

The furthest time that a signed 32-bit integer can represent the Unix time format is 03:14:07 UTC on Tuesday, 19 January 2038 (2147483647 seconds after 1 January 1970).
As of 2012, most embedded systems use 8-bit or 16-bit microprocessors, even as desktop systems are transitioning to 64-bit systems.
MySQL database's inbuilt functions like UNIX_TIMESTAMP() will return 0 after 03:14:07 UTC on 19 January 2038.

Many data structures in use today have 32-bit time representations embedded into their structure. A full list of these data structures is virtually impossible to derive but there are well-known data structures that have the Unix time problem:

    file systems (many filesystems use only 32 bits to represent times in inodes)
    binary file formats (that use 32-bit time fields)
    databases (that have 32-bit time fields)
    database query languages, like SQL that have UNIX_TIMESTAMP() like commands
    COBOL systems of 1970s - 1990s vintage that have not been replaced by 2038-compliant systems
    embedded factory, refinery control and monitoring subsystems
    assorted medical devices
    assorted military devices

Each one of these places where data structures using 32-bit time are in place has its own risks related to failure of the product to perform as designed.

There is no universal solution for the Year 2038 problem. Any change to the definition of the time_t data type would result in code compatibility problems in any application in which date and time representations are dependent on the nature of the signed 32-bit time_t integer. For example, changing time_t to an unsigned 32-bit integer, which would extend the range to the year 2106, would adversely affect programs that store, retrieve, or manipulate dates prior to 1970, as such dates are represented by negative numbers. Increasing the size of the time_t type to 64-bit in an existing system would cause incompatible changes to the layout of structures and the binary interface of functions.