Software development engineer i Interview Questions | Glassdoor.co.in

Software development engineer i Interview Questions

187

software development engineer i interview questions shared by candidates

Top Interview Questions

Sort: RelevancePopular Date

Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, etc.

4 Answers

Use two stacks: one to store actual stack elements and other as an auxiliary stack to store minimum values. The idea is to do push() and pop() operations in such a way that the top of auxiliary stack is always the minimum.

how it can be in O(1) all these operations

You have to maintain 2 stack. One is where first latest element is being added second is where the top element is the minimum one. While adding the element itself you can sort the stack to find perticular position with the help of a temporary stack(third stack) Below is the code for how can you add element public void push(int n) { mainStack.push(n); if(sortedStack.isEmpty()) { sortedStack.push(n); } else { int topnumber = -1; if(n= sortedStack.peek() && !sortedStack.isEmpty()) { topnumber = sortedStack.pop(); temp.push(topnumber); } sortedStack.push(n); while(!temp.isEmpty()) { topnumber = temp.pop(); sortedStack.push(topnumber); } } } } How to get minimum with O(1) public int getMin() { int n = -1; if(!sortedStack.isEmpty()) { n = sortedStack.pop(); } return n; } This will always return with complexity as O(1)

You've a singly linked list where every node in the list has a field "random" which points to other node in the same list. Write a function to clone this list (create a new copy of the same). Don't use extra space (just the pointer variables are fine).

3 Answers

Find the longest palindrome in a string

3 Answers

One or more comments have been removed.
Please see our Community Guidelines or Terms of Service for more information.

Questions related to stacks, queues (Eg:Implement a queue using stacks) Trees were heavily asked as well (Print a tree spirally, check if one BT is a mirror of another BT)

2 Answers

Coin weight puzzle. find out which coin bag is heavy.

1 Answer

1) Difference in Angular JS 1 and Angular JS 2 2) Impact of Angular JS 2 for Ionic framework. 3) Which version of Angular JS are you using? 4) Which version of Bootstrap are you using? 5) What is the difference between Phongap and Cordova? 6) Given: var a = [1,2, 3]; Ho do you implement : a.sum() returns summation of the values in that array.

1 Answer

You're converting a string (s1) into another (s2) by changing the characters in s1. You can do add/delete/replace the characters of s1 to get s2. The cost of any of those operation for a character is 1. Find the minimum cost to convert s1 into s2. Write program and test cases for the same. For example: Convert "Hi" into "Hey". This would require minimum two cost. 1. Replace 'i' with 'e' in s1 2. Add 'y' to s1. Now we've s2.

1 Answer

trees, inc\zigzag\dec array , optimaizations keen

1 Answer

1. Longest palindromic sub-string 2. check if two linked lists merge a some point and report the merging node 3. 2 similar questions that could be solved using binary search 4. convert a BST to DLL 5. A DP question : minimum number of jumps to reach the end 6. A design based questions: Make a software to schedule appointments. Not much was expected here, just discussed some ideas of possible algos and how I would implement 7. Discussion on OOPS & OS concepts

1 Answer

Find the number present in first array but not in second array?

1 Answer