Programming/Design Interview Questions

by Anoop Dixith

Back to Anoop's Homepage

I'm not a big fan of using Leetcode and Leetcode-like question-banks for interviews. I like creating my own questions that fit the purpose, run them by a lot of my smart friends and colleagues, and use them in interviews. There are multiple reasons why I'd do this.

  • This way, I can custom-create my questions for different experience level and background
  • Not all interview questions should test the same thing. Some interview questions test logical ability, some coding proficiency, some test the candidate's ability to convert algorithm to runnable code, and some more explore the candidate's "debugging" and "investigation" skills. I like creating questions that cover these aspects.
  • These are not available anywhere else to have practised earlier. So, fairly original.
  • I like doing it!

    • Problem Category
    Given two arrays, each representing the BFS and DFS traversals of a binary tree, construct the binary tree.

    Input: BFS Array: {3,1,6,7,4} DFS Array: {4,1,3,6,7}
    Construct Binary Tree that satisfies the above two traversals.     		Logic, Data Structures
    Make 'm' using 'n' 'l's. List of operations is provided. Unary (factorial, decimal), binary (sum, difference, multiply, divide etc.) operators. As an extension, also include concatenation operator.

    Example:
    Inpur: Make 20 using 3 4's.
    Operators: add, subtract, multiplication, division
    Output: 4 * 4 + 4     		Logic, Implementation
    Card Punch

    A software firm figures out that one of the employees is swiping another employee's id along with hers, while entering the office, all 5 days of the week.  They want to find out who's doing it. Given are the 5 arrays of the order in which employees swiped their cards while entering office from Monday to Friday. If a person is swiping someone else's card as well, then two numbers should be appearing in adjacent order in all five arrays. If the numbers don't appear adjacent in all 5 arrays, then it might not be a fraud case as people doing car pooling or neighbors often swipe one after the other, however, not all five days of the week, they come together. Find those numbers given 5 arrays of size 10,000 (for 10000 employees) in O(n).     		Logic
    Nibble Swap

    Given a number, swap the nibbles from right to left and return the final number.
    Example:
    Input: 6
    Output: 5
    Input: 21 (10101)
    Output: 26 (11010)
    		Implementation, Edge cases, System knowledge
    Poona Number

    A Poona number is defined as a number that, when written in words in English and the order of its letters in the English alphabet are added, equals the same number!

    For example,
    Sum of orders of the letters of "one" = 15 + 14 + 5 = 34, which is not equal to 1. Thus, 1 is not a Poona number.
    Sum of orders of the letters of "one hundred" = 108, which is a bit more than 100. So, 100 is also not a Poona number.
    There are only two Poona numbers*. Could you find them?

    *When writing in words, the British system is followed where there is an "and" after hundreds, and an "and" after thousands with no hundreds.
    E.g:
    350 is Three hundred and fifty
    1,056 is One thousand and fifty six.
    		Implementation, Efficiency, Numerical
    What does this algorithm do?
    What is its efficiency?
    For what all cases would it fail? (There are no compilation issues)
    How do you fix the issues?

    private void whatDoIDo(int... input) {
      int upperBound = 0;
      for(int i:input) upperBound += i;
      int arr[] = new int[upperBound];
      for(int i: input) arr[upperBound/i] = i;
      for(int i: arr) System.out.print(i > 0 ? i + ",": "");
    }
         		Debugging, Fixing, Code refactoring and clean-up, Naming
    Data Structure/Data Model Design

    Design the data model and APIs (call elevator) for a 100 floor building which has 10 elevators.

    Optimize for:
    1. Least Average Wait Time mode
    2. Energy Efficient mode

    Non Functional Requirements:
    1. Peak time management (mornings and evenings)
    2. Security
    3. Fire and emergencies
    4. Elevator analytics

    Cosmetic Requirements:
    1. Personalized elevator music
    2. Ads and promotions
    		Design, Edge cases, Comprehensiveness, Scalability
    Fermi question - Versioned compiler

    If there is a compiler that stores the previous value of any variable or execution stack by default, what effect will it have on sorting?
    What impact will it have on other operations/algorithms?

    On swapping, for example:
    swap(a,b) { a = b; b = a.prev(); }     		Extrapolation, Creativity, Applicability, Discussion, Comprehensiveness
    h-Depth Index

    We all know that the h-index of an author is the maximum value of h such that the given author has published at least h papers that have each been cited at least h times.
    For example, if a particular author has 3 papers, and they have been cited {5,1,8} times, the h-index is 2 since the author has 2 papers which have been cited at least two times
    The h-Depth index goes one step down and analyzes not only the citations, but also "who" has cited those.
    The h-Depth index is the maximum value of h such that the given author has published at least h papers that have each been cited at least h times by authors who whose h-index is at least h

    Given an array of length l whose elements represent number of citations for an author, and then given l arrays each representing the h-index of authors citing those papers, calculate the h-Depth index of the author.     		Logic, Implementation
    Password Incorrect! Please try again!!

    Given the below rules, write a function to:
    1. Validate a Password
    2. Generate n random passwords.

    Rules
    1. Password should be between 8 and 16 characters both inclusive
    2. Password should contain at least two sepcial characters
    3. Password should contain at least two numeric characters
    4. Password should not contain three or more consecutive alphabets
    5. Password should not contain two or more consecutive numbers
    6. Password should not contain more than two consecutively repeated characters
    7. Password should contain at least one alphabetical character from each of the three rows on a Querty keyboard
    		Edge cases
    Create data model for Rubik's Cube and create a backtracking solution (not necessarily optimal) for solving the same. Data Structure, implementation, optimization
    Towers of Hanoi but with a variable number of auxiliary poles. The number of auxiliary poles is given in the input. (Instead of just one aux pole in the standart Towers of Hanoi problem). Logic, Implementation
    Uprooting!

    Convert an ascending binary search tree whose root node has the minimum value, to a descinding binary search tree whose root node is the maximum value in place, without extra space (other than constant spaces)     		Data structure, logic, implementation
    How do you multiply two million-digit integers? Assume the integers are in a file.

    Write a function to multiply two million-digit numbers, and provide a way to interpret the result of multiplication.     		Data Structure, implementation
    Find the aircraft debris in the ocean

    An image matrix of the top view of an ocean, and of size mxn whose elements are all integers is given.
    Each pixel is represented by an element in the matrix, and the integer values represent the color in an unbounded scale where darker colors/shaded have higher values than lighter colors/shades.
    We want to identify an aircraft debris in the image.
    We know that the debris is in the form of a cross, and scaled to the image, it's in the shape of a 3x3 cross. (1 element in the top middle, 3 elements in the middle row, and 1 element in the bottom middle)
    Though it's known that the aircraft is white, the debris itself could have colored edges, blurred edges, discolored spots on them
    So, we want to identify the cross of above mentioned size whose sum is the minimum in the entire matrix.
    Find such a cross in the matrix.     		Dynamic Programming, logic, implementation
    Minimum number of primes adding up to n

    Given a number `n`, find the minimum number of primes (and primes themselves) adding up to `n`.
    Example 1:
    Input:
    n = 5
    Output: 1 (5 itself)

    Example 2:
    Input:
    n = 4
    Output: 2 (2+2)

    Example 3:
    Input:
    n = 20
    Output: 2 (17+3 or 13+7)

    		Math, Dynamic Progamming, Logic
    Employee ID

    Jane works at E.F. Capital LLC, a Manhattan based algorithmic trading firm. E.F. Capital is a fairly small firm, and it issues Employee ID cards serially from 1 to total number of employees at any point. Jane notices that the product of all the EmployeeID numbers before her is the same as the product of all the EmployeeID numbers after her!
    What is Jane's EmployeeID and how many people work at E.F. Capital?

    Jane also wonders if, at any point in future when the company grows and hires more employees, this mathematical quirk repeats at all. Could you help prove or disprove it does?     		Logic, implementation, efficiency
    Month Day Combination

    Two arrays are given, each having integers between 1 and 31 both inclusive.
    The arrays were supposed to represent the appointment dates booked by customers of an agency
    One array should have represented the "month" (1 to 12) and the other the date (1 to 31)
    Due to mistakes during the data entry process, both arrays have been jumbled up, which means every element in either array could either represent the month or the date
    Obviously, when the number is more than 12, it can be inferred that it represents the date. But not so obvious for other elements
    Additionally, the agency doesn't allow two appointments within a span of ten days. (both days inclusive)
    Given the above constraints, map the arrays into appointments and return a list of tuples, each tuple representing (month, date). If a unique set of appointments cannot be inferred, return "Insufficient Data"

    Input 1:
    arr1 = {3,5}
    arr2 = {1,2}
    Output
    Insufficient data

    Input 2:
    arr1 = {5,29}
    arr2 = {4, 3}
    Output
    [(5,4),(3,29)] // Can't be (4,5) because appointments need to be at least 11 days apart.     		Logic
    Determinent of a Matrix
    Find the max possible value configuration and the min possible value configuration for a 3x3 matrix given its 9 elements.

    Example:
    Input: {1,2,3,4,5,6,7,8,9}
    Output:
    Max value: 412
    Max value configuration: {1,4,8,7,2,6,5,9,3}
    Min value: -412
    Min value configuration: {1,4,8,5,9,3,7,2,6}
    		Logic, Implementation, Efficiency
    Restaurant Owner's Problem

    A restaurant in a remote island has a lot of corrupt waiters who charge their customers less for the food and take a part of the saved money into their personal pockets. The owner wants to combat the waiters' fraudulent practices of billing for lesser money. So, he sets the price of all items in the menu to prime numbers and enforces a maximum of four items per check.
    Items could be repeated (as long as the total is less than or equal to 4). Given the total cost, items should be uniquely identifiable.

    E.g. 40 = 17 + 23. But 15 = 5+5+5 or 11+2+2. Find the smallest prime numbers for a ten item menu that work in this scenario.     		Logic
    Linked List to Binary Tree in-space

    Given a LinkedList and the LinkedList Node class, change the class and convert the linkedlist "in-space" to a binary tree.
    Do the same for a doubly linkedlist.     		Data Structure, Implementation
    (Cricket Related - might not be universally applicable)
    Cricket Scorecard Simulation

    Simulate a cricket scorecard from batting and bowling perspective
    Names of all sort should be sensibly generated strings
    The batting numbers, balls faced, runs scored, fall of wickets etc should match the bowling scorecard.
    		Simulation, Design, Testing, Sample Data
    Number to Words

    Given a number, print the word in standard English words

    Examples:

    Input 1: 123
    Output: One hundred and twenty three

    Input 2: 8,334,667,984,291,896
    Output: Eight quadrillion three hundred and thirty four trillion six hundred and sixty seven billion nine hundred and eithery four million two hundred and ninety one thousand eight hundred and ninety six
         		Logic, edge cases.
    Solution
    Valid email address.
    Extension: Check if valid business email

    Check if a given email address is a valid format email address.

    Some examples of invalid ones:
    1. a@b@c.com
    2. abcde@com
    3. abcde@ghi.co.in.com (abcde@ghi.co.in is valid though)
    4. abcde
    5. abce.ed
    6. /"hg"@ehi.com
    		Edge cases, testing
    Base Conversion

    Validate and then convert a given number from source base to destination base.

    Example:
    Convert 231 from base 4 to base 6
    Convert ABC from base 16 to base 2
    Convert 25 from base 100 to base 10
    		Implementation, Edge Cases
    A company's org chart is represented in the form of a tree.
    Children of a node are reportees of the value of the node. Direct reportees are direct children, indirect reportees are children of children nodes
    Leaves are individual contributors. Root node is the CEO.

    Given the above, implement tree adjustment in cases of:
    1. Promotion: In case of a promotion, the node of the promoted employee starts reporting to parent's parent. All the peers start reporting to the promoted employee.
    2. Termination: In case of termination, all reportees start reporting to terminated employee's manager.
    3. On promotion or termination, no manager (except the CEO) has more than 5 reportees. If they do, promote least number of nodes such that it isn't the case anymore
    		Data structure, implementation, logic
    Binary Tree Sum

    Given a binary tree (not a binary search tree) with nodes whose values are integers, find the subtree with the largest sum.     		Data Structure, logic, implementation
    Year 2000. Two supercomputers running JVM were being used by Bank of Lovindale, the largest mid-western bank for interest calculation on all of its customer loans.
    Surprisingly, even for the same amount of principle and same rate of interest, and similar time period, the two super computers gave different results. Though the difference was minor, when added across all the branches of the bank and across all customer loans, the bank deduced the differene might be sizeable.
    However, the contractor who had written the program audited their software/program multiple times and confirmed there is no bug in the program.
    Eventually, a developer noticed that the programs are being run on different machines with different processors, one on x87 based processor and another on an in-house Proc processor, and identified the issue.
    If you were that developer from 2000, how would you analyze this issue and how would you fix it?

    Hint: The answer is one word.     		Debugging, programming language, investigation
    Sorting algorithms for different scenarios

    What is the best sorting algorithm (in terms of time efficiency) for sorting...
    1. an almost sorted arrays?
    2. an array with a LOT of duplicates?
    3. when you don't have to worry about space complexity AT All?
    4. an array in a highly multi-threaded environment?
    5. an array online?
    6. an array of strings (strings have fixed characters in them)?
    7. a large array but which has only three different elements? (Dutch Flag Problem)
    8. a very large array which doesn't fit in-memory?
    9. a reverse sorted array?
    10. small arrays (say just 7 elements)?     		Discussion, Thinking, Depth, Logic
    Implement an advanced datastructure in Java
    Skiplist or hyperloglog or bloom filter
    Explain the candidate how algorithm works and ask them to implement
    		Onboarding, programming language, data structures, edge cases
    Given a graph of objects as nodes and all the dependencies of each node represented as the node's edges representing the memory of JVM, implement the mark-and-sweep garbage collector.

    Implementation, Logic
    Implement a simple Kafka-esque distributed queuing system. Includes a producer, a broker, and a group of consumers
    The idea of this question is that while Kafka can be notoriously hard to implement for Availability, Redundancy, and Scale, the core of Kafka is pretty straight-forward with minimal yet interesting concepts.

    The producer produces the messages in different topics.
    The broker (for simplicity, just one broker) stores the messages until consumed or a set time period, for different topics.
    The group of consumers consume messages from different topic. Different consumers are at different offset.
    		Implementation, edge cases
    The developers from the infrastructure team want an issue to be debugged by the platform development team.
    The company being old school with no central debugging solutions, the infra team simply wants to send the serialized object of a class which holds the key to the issues to the platform team.
    However, the class being a little sensitive, the infra team wants to serialize only those members of the class which are not customer specific.
    How do they selectively serialize it?

    Hint: The answer is one word.     		Investigation, language specific
    programming
    Back to Anoop's Homepage