# Software design engineer Interview Questions

# 366

Software Design Engineer interview questions shared by candidates### Given a string find the first non-repeated character.

12 Answers↳

@Rajiv : Your solution is completely wrong. It will fail for input of "aaa" Reason: on first check, you insert "a". On next check you remove it. On next check you again insert it and return that as your answer, even though it was repeated thrice. Less

↳

program to find first non repeating character in a string c# - three ways

↳

My python implementation: def firstNonRepeatingCharacter(inputString): hashmap = {} for x in inputString: if (x in hashmap): hashmap[x] = hashmap[x] + 1 else: hashmap[x] = 1 for x in inputString: if (hashmap[x] > 1): continue else: return x return "No nonrepeating character found" Less

### find if 2 strings are anagrams

5 Answers↳

Hash what, lol ? :))) You simply need to alphabetically sort characters in strings and then compare the result. Less

↳

think about the time complexity. Whats the time complexity of the sorting? NlogN And when using hash mapping, it can be only N. Mapping the string to an alphabet array, the index is the char and the value stores the frequency of the char. Hope it helps. Less

↳

Just reverse one string and then compare the result with other string.

### How would you design a Zoo class using OO design?

4 Answers↳

This seems more like a Zoo management structure than "Zoo". I'd create this by making Zoo its own class and then having other abstract classes such as Animal, Worker, Building so they cannot be instantiated directly. I'd then have subclasses for each of these, for instance, Animal may have the subclass Reptile or Mammal. Less

↳

I would include a class for customer to demonstrate customer focus. Also an interface for Partner Zoo's to borrow exhibits. Also one for suppliers such that you may keep your customers happy and animals fed. Less

↳

In addition to the above, I'll implement polymorphism in the Zoo class. i.e. declaring variables for each of the abstract classe that point to actual instantiation of the sub-classes Less

### Binary tree with parent pointers, given two nodes find common ancestor.

3 Answers↳

Hint: use a hash table

↳

For each node traversed from the root, if both values are less than the current Node, then move to the left if both values are greater than the currentNode, then move to the right, if the value of current Node is between value 1 and value 2, then you have found the nearest common ancestor. Less

↳

Rajiv, you can't do that is tree is by parent pointers. you need to bubble up from the given nodes and put parents to a hash. Less

### Given an array of 100 integers where every integer from 1-101 occurs once, except for one. Find the missing integer.

3 Answers↳

Let a = XOR of all elements in array and b = XOR of all numbers from 1 to 100. The final result is a XOR b Less

↳

XOR all numbers in the array + till closest power of 2 - 1(in this case 127). Output will be the missing number. i.e. 1 ^ 2 ^ 3 ....... ^ 101 ^ 102...... ^ 127 = missing number Less

↳

sum of number from 1 to n is n(n+1)/2 So Sum from 1 to 101 = (101*102)/2 = 5151 So missing number is 5151 - (sum of all elements in the given array) Less

### Find the max subsequent sum for a random array of numbers

2 Answers↳

int maxSum(int arr[], int size) { int maxSum= 0; int currMaxSum = 0; for (int i = 0; i < size ; i++) { currMaxSum += arr[i]; if (currMaxSum < 0) { currMaxSum = 0; } if (maxSum < currMaxSum ) { maxSum = currMaxSum ; } } returb naxSum; } } Less

↳

private static int findMaxSubSeqSum(ArrayList allRecords) { int maxSum = 0; int prevSum = 0; int currentSum = 0; for (int i = 0; i maxSum) { maxSum = currentSum; } if (currentSum < prevSum) { currentSum = 0; } } return maxSum; } Less

### Write a function to find the node where two linked lists meet.

3 Answers↳

// solution in C++ #include #include using namespace std; // simple Node class class Node { public: Node(int v) : val(v), next(NULL) {} int val; Node* next; }; // function to find intersection Node Node* findNodeWhere2ListsMeet(Node* head1, Node* head2) { // interate through first list and populate map map nodeMap; while (head1 != NULL) { nodeMap[head1] = head1->val; head1 = head1->next; } // interate through second list and try to find in map while (head2 != NULL) { if (nodeMap.find(head2) != nodeMap.end()) { return head2; } head2 = head2->next; } return NULL; } // test code (happy path only) int main() { // linked list 1 values = 1,2,3,4,5,6 Node* head1 = new Node(1); Node* n12 = new Node(2); Node* n13 = new Node(3); Node* n14 = new Node(4); Node* n15 = new Node(5); Node* n16 = new Node(6); head1->next = n12; n12->next = n13; n13->next = n14; n14->next = n15; n15->next = n16; // linked list 2 values = 11,12,13,5,6 Node* head2 = new Node(11); Node* n22 = new Node(12); Node* n23 = new Node(13); head2->next = n22; n22->next = n23; n23->next = n15; Node* intersection = findNodeWhere2ListsMeet(head1, head2); while (head1 != NULL) { cout val next; } cout val next; } cout << endl; Less

↳

Previous answer got truncated. Here's the last of the test code starting at the function call. Node* intersection = findNodeWhere2ListsMeet(head1, head2); while (head1 != NULL) { cout val next; } cout val next; } cout val << endl; cout << "\n\n\nPress Enter to quit. "; cin.ignore(); return 0; } Less

↳

public static void main(String[] args) { List L1 = Arrays.asList(1,2,5,7,9,10,12,18,3); List L2 = Arrays.asList(2,3,4,8,9,9,10,11,12,18); LinkedList list1 = new LinkedList(); list1.addAll(L1); LinkedList list2 = new LinkedList(); list2.addAll(L2); System.out.println("L1 : " + list1); System.out.println("L2 : " + list2); ArrayList result = new ArrayList(); System.out.println("two linked lists meet: " + findCommon(list1, list2,result)); } public static ArrayList findCommon(LinkedList list1,LinkedList list2,ArrayList result) { if (list1.isEmpty()) return result; int pop = list1.pop(); if (list2.contains(pop)) result.add(pop); return findCommon(list1, list2, result); } Less

### Design an email sender that can send 100,000,000 emails. You have 5 machines how could you do it efficiently.

3 Answers↳

You could probably have your input application send messages to a clustered queue. There are 5 servers running on the 5 machines, each server with its own MDB. The MDB would then pick it up from the JMS queue and send it to the recipient. The queue depth of the intermediate queue should be sufficient enough to allow sufficient buffer so that you dont have to worry about your input program putting messages at a much faster rate than the MDBs can process. Less

↳

Need to discuss where the performance bottlenecks are and how to mitigate them.

↳

use worker threads aka. Executors they have internal job queues that worker threads pick on. Provides high parallelism Less